tpl_persistent_treap.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef TPL_PERSISTENT_TREAP_H
#define TPL_PERSISTENT_TREAP_H
 
#include <algorithm>
#include <concepts>
#include <cstdint>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
 
#include <ah-errors.H>
#include <ahFunction.H>
#include <tpl_array.H>
 
namespace Aleph
{
 
namespace detail
{
  [[nodiscard]] inline std::uint64_t persistent_treap_priority(const std::uint64_t n) noexcept
  {
    std::uint64_t x = n + 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
  }
 
  template <typename Node, typename Key, class Compare>
  struct PersistentTreapNodeOps
  {
    using NodePtr = std::shared_ptr<const Node>;
 
    [[nodiscard]] static size_t node_size(const NodePtr &p) noexcept
    {
      return p == nullptr ? 0 : p->count;
    }
 
    [[nodiscard]] static const Key *min_key(const NodePtr &node) noexcept
    {
      const Node *curr = node.get();
      while (curr->left != nullptr)
        curr = curr->left.get();
      return curr->key.get();
    }
 
    [[nodiscard]] static const Key *max_key(const NodePtr &node) noexcept
    {
      const Node *curr = node.get();
      while (curr->right != nullptr)
        curr = curr->right.get();
      return curr->key.get();
    }
 
    [[nodiscard]] static bool can_join(const NodePtr &left,
                                       const NodePtr &right,
                                       const Compare &cmp)
    {
      return left == nullptr or right == nullptr or cmp(*max_key(left), *min_key(right));
    }
 
    template <class Rebuild>
    [[nodiscard]] static NodePtr rotate_right(const NodePtr &node, const Rebuild &rebuild)
    {
      const NodePtr child = node->left;
      NodePtr new_right = rebuild(node, child->right, node->right);
      return rebuild(child, child->left, std::move(new_right));
    }
 
    template <class Rebuild>
    [[nodiscard]] static NodePtr rotate_left(const NodePtr &node, const Rebuild &rebuild)
    {
      const NodePtr child = node->right;
      NodePtr new_left = rebuild(node, node->left, child->left);
      return rebuild(child, std::move(new_left), child->right);
    }
 
    template <class Rebuild>
    [[nodiscard]] static NodePtr join_nodes(const NodePtr &left,
                                            const NodePtr &right,
                                            const Rebuild &rebuild)
    {
      if (left == nullptr)
        return right;
      if (right == nullptr)
        return left;
 
      if (left->priority <= right->priority)
        {
          NodePtr new_right = join_nodes(left->right, right, rebuild);
          return rebuild(left, left->left, std::move(new_right));
        }
 
      NodePtr new_left = join_nodes(left, right->left, rebuild);
      return rebuild(right, std::move(new_left), right->right);
    }
 
    template <class Rebuild>
    [[nodiscard]] static NodePtr erase_rec(const NodePtr &node,
                                           const Key &key,
                                           const Compare &cmp,
                                           bool &erased,
                                           const Rebuild &rebuild)
    {
      if (node == nullptr)
        {
          erased = false;
          return nullptr;
        }
 
      if (cmp(key, *node->key))
        {
          NodePtr new_left = erase_rec(node->left, key, cmp, erased, rebuild);
          if (not erased)
            return node;
          return rebuild(node, std::move(new_left), node->right);
        }
 
      if (cmp(*node->key, key))
        {
          NodePtr new_right = erase_rec(node->right, key, cmp, erased, rebuild);
          if (not erased)
            return node;
          return rebuild(node, node->left, std::move(new_right));
        }
 
      erased = true;
      return join_nodes(node->left, node->right, rebuild);
    }
 
    template <class Rebuild>
    [[nodiscard]] static std::pair<NodePtr, NodePtr> split_rec(const NodePtr &node,
                                                               const Key &pivot,
                                                               const Compare &cmp,
                                                               const Rebuild &rebuild)
    {
      if (node == nullptr)
        return {nullptr, nullptr};
 
      if (cmp(*node->key, pivot))
        {
          auto [right_left, right_right] = split_rec(node->right, pivot, cmp, rebuild);
          NodePtr left = rebuild(node, node->left, std::move(right_left));
          return {std::move(left), std::move(right_right)};
        }
 
      auto [left_left, left_right] = split_rec(node->left, pivot, cmp, rebuild);
      NodePtr right = rebuild(node, std::move(left_right), node->right);
      return {std::move(left_left), std::move(right)};
    }
 
    static void collect_keys(const NodePtr &node, Array<Key> &out)
      requires std::copy_constructible<Key>
    {
      if (node == nullptr)
        return;
      collect_keys(node->left, out);
      out.append(Key(*node->key));
      collect_keys(node->right, out);
    }
 
    [[nodiscard]] static bool verify_rec(const NodePtr &node,
                                         const Key *lo,
                                         const Key *hi,
                                         const Compare &cmp,
                                         size_t &count)
    {
      if (node == nullptr)
        return true;
      if (node->key == nullptr)
        return false;
      if constexpr (requires (const Node &n) { n.value; })
        if (node->value == nullptr)
          return false;
      if (lo != nullptr and not cmp(*lo, *node->key))
        return false;
      if (hi != nullptr and not cmp(*node->key, *hi))
        return false;
      if (node->left != nullptr and node->left->priority < node->priority)
        return false;
      if (node->right != nullptr and node->right->priority < node->priority)
        return false;
 
      size_t left_count = 0;
      size_t right_count = 0;
      if (not verify_rec(node->left, lo, node->key.get(), cmp, left_count))
        return false;
      if (not verify_rec(node->right, node->key.get(), hi, cmp, right_count))
        return false;
      if (node->count != left_count + right_count + 1)
        return false;
      count = node->count;
      return true;
    }
 
    [[nodiscard]] static bool is_valid_under(const NodePtr &node, const Compare &cmp)
    {
      size_t count = 0;
      return verify_rec(node, nullptr, nullptr, cmp, count) and count == node_size(node);
    }
  };
}
 
template <typename Key, class Compare = Aleph::less<Key>>
class PersistentTreapSet
{
  struct Node
  {
    std::shared_ptr<const Key> key;
    std::uint64_t priority = 0;
    size_t count = 1;
    std::shared_ptr<const Node> left;
    std::shared_ptr<const Node> right;
  };
 
  using NodePtr = std::shared_ptr<const Node>;
  using NodeOps = detail::PersistentTreapNodeOps<Node, Key, Compare>;
 
  NodePtr root_;
  Compare cmp_;
  std::uint64_t next_priority_ = 0;
 
  [[nodiscard]] static NodePtr make_node(std::shared_ptr<const Key> key,
                                         const std::uint64_t priority,
                                         NodePtr left,
                                         NodePtr right)
  {
    const size_t left_size = NodeOps::node_size(left);
    const size_t right_size = NodeOps::node_size(right);
    ah_overflow_error_if(left_size > std::numeric_limits<size_t>::max() - right_size)
      << "PersistentTreapSet: node size would overflow";
    const size_t children_size = left_size + right_size;
    ah_overflow_error_if(children_size == std::numeric_limits<size_t>::max())
      << "PersistentTreapSet: node size would overflow";
 
    auto node = std::make_shared<Node>();
    node->key = std::move(key);
    node->priority = priority;
    node->left = std::move(left);
    node->right = std::move(right);
    node->count = children_size + 1;
    return node;
  }
 
  [[nodiscard]] static NodePtr rebuild_node(const NodePtr &node, NodePtr left, NodePtr right)
  {
    return make_node(node->key, node->priority, std::move(left), std::move(right));
  }
 
  [[nodiscard]] static NodePtr insert_rec(const NodePtr &node,
                                          std::shared_ptr<const Key> key,
                                          const std::uint64_t priority,
                                          const Compare &cmp,
                                          bool &inserted)
  {
    if (node == nullptr)
      {
        inserted = true;
        return make_node(std::move(key), priority, nullptr, nullptr);
      }
 
    if (cmp(*key, *node->key))
      {
        NodePtr new_left = insert_rec(node->left, std::move(key), priority, cmp, inserted);
        if (not inserted)
          return node;
        NodePtr rebuilt = make_node(node->key, node->priority, std::move(new_left), node->right);
        return rebuilt->left->priority < rebuilt->priority
          ? NodeOps::rotate_right(rebuilt, rebuild_node) : rebuilt;
      }
 
    if (cmp(*node->key, *key))
      {
        NodePtr new_right = insert_rec(node->right, std::move(key), priority, cmp, inserted);
        if (not inserted)
          return node;
        NodePtr rebuilt = make_node(node->key, node->priority, node->left, std::move(new_right));
        return rebuilt->right->priority < rebuilt->priority
          ? NodeOps::rotate_left(rebuilt, rebuild_node) : rebuilt;
      }
 
    inserted = false;
    return node;
  }
 
  PersistentTreapSet(NodePtr root, Compare cmp, const std::uint64_t next_priority)
    : root_(std::move(root)), cmp_(std::move(cmp)), next_priority_(next_priority)
  {
    // Empty.
  }
 
public:
  explicit PersistentTreapSet(Compare cmp = Compare())
    : cmp_(std::move(cmp))
  {
    // Empty.
  }
 
  [[nodiscard]] bool is_empty() const noexcept { return root_ == nullptr; }
 
  [[nodiscard]] size_t size() const noexcept { return NodeOps::node_size(root_); }
 
  [[nodiscard]] const Key *find(const Key &key) const
  {
    const Node *curr = root_.get();
    while (curr != nullptr)
      if (cmp_(key, *curr->key))
        curr = curr->left.get();
      else if (cmp_(*curr->key, key))
        curr = curr->right.get();
      else
        return curr->key.get();
    return nullptr;
  }
 
  [[nodiscard]] bool contains(const Key &key) const
  {
    return find(key) != nullptr;
  }
 
  [[nodiscard]] PersistentTreapSet insert(const Key &key) const
  {
    auto stored_key = std::make_shared<const Key>(key);
    bool inserted = false;
    NodePtr root = insert_rec(root_, std::move(stored_key),
                              detail::persistent_treap_priority(next_priority_),
                              cmp_, inserted);
    return inserted ? PersistentTreapSet(std::move(root), cmp_, next_priority_ + 1) : *this;
  }
 
  [[nodiscard]] PersistentTreapSet insert(Key &&key) const
  {
    auto stored_key = std::make_shared<const Key>(std::move(key));
    bool inserted = false;
    NodePtr root = insert_rec(root_, std::move(stored_key),
                              detail::persistent_treap_priority(next_priority_),
                              cmp_, inserted);
    return inserted ? PersistentTreapSet(std::move(root), cmp_, next_priority_ + 1) : *this;
  }
 
  [[nodiscard]] PersistentTreapSet erase(const Key &key) const
  {
    bool erased = false;
    NodePtr root = NodeOps::erase_rec(root_, key, cmp_, erased, rebuild_node);
    return erased ? PersistentTreapSet(std::move(root), cmp_, next_priority_) : *this;
  }
 
  [[nodiscard]] std::pair<PersistentTreapSet, PersistentTreapSet>
  split(const Key &pivot) const
  {
    auto [left, right] = NodeOps::split_rec(root_, pivot, cmp_, rebuild_node);
    return {PersistentTreapSet(std::move(left), cmp_, next_priority_),
            PersistentTreapSet(std::move(right), cmp_, next_priority_)};
  }
 
  [[nodiscard]] static PersistentTreapSet join(const PersistentTreapSet &left,
                                               const PersistentTreapSet &right)
  {
    ah_domain_error_unless(NodeOps::is_valid_under(right.root_, left.cmp_))
      << "PersistentTreapSet::join(): right tree must be ordered by left comparator";
    ah_domain_error_unless(NodeOps::can_join(left.root_, right.root_, left.cmp_))
      << "PersistentTreapSet::join(): left keys must be strictly less than right keys";
    return PersistentTreapSet(NodeOps::join_nodes(left.root_, right.root_, rebuild_node), left.cmp_,
                              std::max(left.next_priority_, right.next_priority_));
  }
 
  [[nodiscard]] PersistentTreapSet join(const PersistentTreapSet &right) const
  {
    return join(*this, right);
  }
 
  [[nodiscard]] Array<Key> keys() const
    requires std::copy_constructible<Key>
  {
    Array<Key> out;
    out.reserve(size());
    NodeOps::collect_keys(root_, out);
    return out;
  }
 
  [[nodiscard]] bool verify() const
  {
    size_t count = 0;
    return NodeOps::verify_rec(root_, nullptr, nullptr, cmp_, count) and count == size();
  }
};
 
template <typename Key, typename T, class Compare = Aleph::less<Key>>
class PersistentTreapMap
{
  struct Node
  {
    std::shared_ptr<const Key> key;
    std::shared_ptr<const T> value;
    std::uint64_t priority = 0;
    size_t count = 1;
    std::shared_ptr<const Node> left;
    std::shared_ptr<const Node> right;
  };
 
  using NodePtr = std::shared_ptr<const Node>;
  using NodeOps = detail::PersistentTreapNodeOps<Node, Key, Compare>;
 
  NodePtr root_;
  Compare cmp_;
  std::uint64_t next_priority_ = 0;
 
  [[nodiscard]] static NodePtr make_node(std::shared_ptr<const Key> key,
                                         std::shared_ptr<const T> value,
                                         const std::uint64_t priority,
                                         NodePtr left,
                                         NodePtr right)
  {
    const size_t left_size = NodeOps::node_size(left);
    const size_t right_size = NodeOps::node_size(right);
    ah_overflow_error_if(left_size > std::numeric_limits<size_t>::max() - right_size)
      << "PersistentTreapMap: node size would overflow";
    const size_t children_size = left_size + right_size;
    ah_overflow_error_if(children_size == std::numeric_limits<size_t>::max())
      << "PersistentTreapMap: node size would overflow";
 
    auto node = std::make_shared<Node>();
    node->key = std::move(key);
    node->value = std::move(value);
    node->priority = priority;
    node->left = std::move(left);
    node->right = std::move(right);
    node->count = children_size + 1;
    return node;
  }
 
  [[nodiscard]] static NodePtr rebuild_node(const NodePtr &node, NodePtr left, NodePtr right)
  {
    return make_node(node->key, node->value, node->priority,
                     std::move(left), std::move(right));
  }
 
  [[nodiscard]] static NodePtr insert_rec(const NodePtr &node,
                                          std::shared_ptr<const Key> key,
                                          std::shared_ptr<const T> value,
                                          const std::uint64_t priority,
                                          const Compare &cmp,
                                          bool &inserted)
  {
    if (node == nullptr)
      {
        inserted = true;
        return make_node(std::move(key), std::move(value), priority, nullptr, nullptr);
      }
 
    if (cmp(*key, *node->key))
      {
        NodePtr new_left = insert_rec(node->left, std::move(key), std::move(value),
                                      priority, cmp, inserted);
        if (not inserted)
          return node;
        NodePtr rebuilt = make_node(node->key, node->value, node->priority,
                                    std::move(new_left), node->right);
        return rebuilt->left->priority < rebuilt->priority
          ? NodeOps::rotate_right(rebuilt, rebuild_node) : rebuilt;
      }
 
    if (cmp(*node->key, *key))
      {
        NodePtr new_right = insert_rec(node->right, std::move(key), std::move(value),
                                       priority, cmp, inserted);
        if (not inserted)
          return node;
        NodePtr rebuilt = make_node(node->key, node->value, node->priority,
                                    node->left, std::move(new_right));
        return rebuilt->right->priority < rebuilt->priority
          ? NodeOps::rotate_left(rebuilt, rebuild_node) : rebuilt;
      }
 
    inserted = false;
    return node;
  }
 
  [[nodiscard]] static NodePtr insert_or_assign_rec(const NodePtr &node,
                                                    std::shared_ptr<const Key> key,
                                                    std::shared_ptr<const T> value,
                                                    const std::uint64_t priority,
                                                    const Compare &cmp,
                                                    bool &inserted)
  {
    if (node == nullptr)
      {
        inserted = true;
        return make_node(std::move(key), std::move(value), priority, nullptr, nullptr);
      }
 
    if (cmp(*key, *node->key))
      {
        NodePtr new_left = insert_or_assign_rec(node->left, std::move(key),
                                                std::move(value), priority, cmp,
                                                inserted);
        NodePtr rebuilt = make_node(node->key, node->value, node->priority,
                                    std::move(new_left), node->right);
        return inserted and rebuilt->left->priority < rebuilt->priority
          ? NodeOps::rotate_right(rebuilt, rebuild_node) : rebuilt;
      }
 
    if (cmp(*node->key, *key))
      {
        NodePtr new_right = insert_or_assign_rec(node->right, std::move(key),
                                                 std::move(value), priority, cmp,
                                                 inserted);
        NodePtr rebuilt = make_node(node->key, node->value, node->priority,
                                    node->left, std::move(new_right));
        return inserted and rebuilt->right->priority < rebuilt->priority
          ? NodeOps::rotate_left(rebuilt, rebuild_node) : rebuilt;
      }
 
    inserted = false;
    return make_node(node->key, std::move(value), node->priority, node->left, node->right);
  }
 
  static void collect_items(const NodePtr &node, Array<std::pair<Key, T>> &out)
    requires (std::copy_constructible<Key> and std::copy_constructible<T>)
  {
    if (node == nullptr)
      return;
    collect_items(node->left, out);
    out.append(std::pair<Key, T>{*node->key, *node->value});
    collect_items(node->right, out);
  }
 
  PersistentTreapMap(NodePtr root, Compare cmp, const std::uint64_t next_priority)
    : root_(std::move(root)), cmp_(std::move(cmp)), next_priority_(next_priority)
  {
    // Empty.
  }
 
public:
  explicit PersistentTreapMap(Compare cmp = Compare())
    : cmp_(std::move(cmp))
  {
    // Empty.
  }
 
  [[nodiscard]] bool is_empty() const noexcept { return root_ == nullptr; }
 
  [[nodiscard]] size_t size() const noexcept { return NodeOps::node_size(root_); }
 
  [[nodiscard]] const T *find(const Key &key) const
  {
    const Node *curr = root_.get();
    while (curr != nullptr)
      if (cmp_(key, *curr->key))
        curr = curr->left.get();
      else if (cmp_(*curr->key, key))
        curr = curr->right.get();
      else
        return curr->value.get();
    return nullptr;
  }
 
  [[nodiscard]] bool contains(const Key &key) const
  {
    return find(key) != nullptr;
  }
 
  template <typename KArg, typename VArg>
    requires std::constructible_from<Key, KArg &&> and std::constructible_from<T, VArg &&>
  [[nodiscard]] PersistentTreapMap insert(KArg &&key, VArg &&value) const
  {
    auto stored_key = std::make_shared<const Key>(std::forward<KArg>(key));
    auto stored_value = std::make_shared<const T>(std::forward<VArg>(value));
    bool inserted = false;
    NodePtr root = insert_rec(root_, std::move(stored_key), std::move(stored_value),
                              detail::persistent_treap_priority(next_priority_),
                              cmp_, inserted);
    return inserted ? PersistentTreapMap(std::move(root), cmp_, next_priority_ + 1) : *this;
  }
 
  template <typename KArg, typename VArg>
    requires std::constructible_from<Key, KArg &&> and std::constructible_from<T, VArg &&>
  [[nodiscard]] PersistentTreapMap insert_or_assign(KArg &&key, VArg &&value) const
  {
    auto stored_key = std::make_shared<const Key>(std::forward<KArg>(key));
    auto stored_value = std::make_shared<const T>(std::forward<VArg>(value));
    bool inserted = false;
    NodePtr root = insert_or_assign_rec(root_, std::move(stored_key),
                                        std::move(stored_value),
                                        detail::persistent_treap_priority(next_priority_),
                                        cmp_, inserted);
    return PersistentTreapMap(std::move(root), cmp_, inserted ? next_priority_ + 1
                                                              : next_priority_);
  }
 
  [[nodiscard]] PersistentTreapMap erase(const Key &key) const
  {
    bool erased = false;
    NodePtr root = NodeOps::erase_rec(root_, key, cmp_, erased, rebuild_node);
    return erased ? PersistentTreapMap(std::move(root), cmp_, next_priority_) : *this;
  }
 
  [[nodiscard]] std::pair<PersistentTreapMap, PersistentTreapMap>
  split(const Key &pivot) const
  {
    auto [left, right] = NodeOps::split_rec(root_, pivot, cmp_, rebuild_node);
    return {PersistentTreapMap(std::move(left), cmp_, next_priority_),
            PersistentTreapMap(std::move(right), cmp_, next_priority_)};
  }
 
  [[nodiscard]] static PersistentTreapMap join(const PersistentTreapMap &left,
                                               const PersistentTreapMap &right)
  {
    ah_domain_error_unless(NodeOps::is_valid_under(right.root_, left.cmp_))
      << "PersistentTreapMap::join(): right tree must be ordered by left comparator";
    ah_domain_error_unless(NodeOps::can_join(left.root_, right.root_, left.cmp_))
      << "PersistentTreapMap::join(): left keys must be strictly less than right keys";
    return PersistentTreapMap(NodeOps::join_nodes(left.root_, right.root_, rebuild_node), left.cmp_,
                              std::max(left.next_priority_, right.next_priority_));
  }
 
  [[nodiscard]] PersistentTreapMap join(const PersistentTreapMap &right) const
  {
    return join(*this, right);
  }
 
  [[nodiscard]] Array<Key> keys() const
    requires std::copy_constructible<Key>
  {
    Array<Key> out;
    out.reserve(size());
    NodeOps::collect_keys(root_, out);
    return out;
  }
 
  [[nodiscard]] Array<std::pair<Key, T>> items() const
    requires (std::copy_constructible<Key> and std::copy_constructible<T>)
  {
    Array<std::pair<Key, T>> out;
    out.reserve(size());
    collect_items(root_, out);
    return out;
  }
 
  [[nodiscard]] bool verify() const
  {
    size_t count = 0;
    return NodeOps::verify_rec(root_, nullptr, nullptr, cmp_, count) and count == size();
  }
};
 
} // namespace Aleph
 
#endif // TPL_PERSISTENT_TREAP_H