tpl_dynSetTree.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  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_DYNSETTREE_H
# define TPL_DYNSETTREE_H
 
# include <cassert>
# include <typeinfo>
# include <type_traits>
# include <utility>
# include <algorithm>
# include <memory>
# include <stdexcept>
# include <ah-errors.H>
# include <ah-args-ctor.H>
# include <ahIterator.H>
# include <ah-zip.H>
# include <ah-arena.H>
# include <tpl_binNodeUtils.H>
# include <tpl_binNodeXt.H>
# include <tpl_binTree.H>
# include <tpl_treap.H>
# include <tpl_treapRk.H>
# include <tpl_avl.H>
# include <tpl_avlRk.H>
# include <tpl_rand_tree.H>
# include <tpl_rb_tree.H>
# include <tpl_rbRk.H>
# include <tpl_tdRbTree.H>
# include <tpl_tdRbTreeRk.H>
# include <tpl_hRbTree.H>
# include <tpl_hRbTreeRk.H>
# include <tpl_splay_tree.H>
# include <tpl_splay_treeRk.H>
# include <ah-concepts.H>
 
using namespace Aleph;
 
namespace Aleph
{
  template <typename Node>
  class AbstractTreeNodeAllocator
  {
  public:
    AbstractTreeNodeAllocator() = default;
 
    virtual Node * alloc_lval(const typename Node::key_type & key) = 0;
 
    virtual Node * alloc_rval(typename Node::key_type && key) = 0;
 
    virtual void unalloc(Node *) = 0;
 
    virtual ~AbstractTreeNodeAllocator() = default;
  };
 
  template <typename Node>
  class DftTreeNodeAllocator : public AbstractTreeNodeAllocator<Node>
  {
  public:
    Node * alloc_lval(const typename Node::key_type & key) override
    {
      return new Node(key);
    }
 
    Node * alloc_rval(typename Node::key_type && key) override
    {
      return new Node(std::forward<typename Node::key_type>(key));
    }
 
    void unalloc(Node *p) override
    {
      delete p;
    }
 
    ~DftTreeNodeAllocator() override = default;
  };
 
  template <typename Node>
  struct ArenaTreeAllocator : public AbstractTreeNodeAllocator<Node>
  {
    AhArenaAllocator arena;
 
    ArenaTreeAllocator(const size_t & sz = 1024 * 1024)
      : arena(sz)
    {
      // empty
    }
 
    ArenaTreeAllocator(const char *base_addr, const size_t & sz)
      : arena(base_addr, sz)
    {
      // empty
    }
 
    Node * alloc_lval(const typename Node::key_type & key) override
    {
      Node *ptr = allocate<Node>(arena, key);
      ah_bad_alloc_if(ptr == nullptr);
      return ptr;
    }
 
    Node * alloc_rval(typename Node::key_type && key) override
    {
      Node *ptr =
          allocate<Node>(arena, std::forward<typename Node::key_type>(key));
      ah_bad_alloc_if(ptr == nullptr);
      return ptr;
    }
 
    void unalloc(Node *p) override
    {
      dealloc<Node>(arena, p);
    }
 
    [[nodiscard]] size_t allocated_size() const noexcept
    {
      return arena.allocated_size();
    }
 
    [[nodiscard]] size_t available_size() const noexcept
    {
      return arena.available_size();
    }
 
    ~ArenaTreeAllocator() = default;
  };
 
  template <typename Container, typename T>
  struct CmpContainer
  {
    bool operator ()(const Container & c1, const Container & c2) const
    {
      return std::lexicographical_compare(c1.begin(), c1.end(), c2.begin(), c2.end(),
                                          [](const T & item1, const T & item2)
                                            {
                                              return item1 < item2;
                                            });
    }
  };
 
  template <typename Key,
            template <typename, class> class Tree = Avl_Tree,
            class Compare = Aleph::less<Key>>
    requires StrictWeakOrder<Compare, Key> &&
             BSTPolicy<Tree<Key, Compare>, Key>
  class DynSetTree
      : public LocateFunctions<DynSetTree<Key, Tree, Compare>, Key>,
        public FunctionalMethods<DynSetTree<Key, Tree, Compare>, Key>,
        public GenericKeys<DynSetTree<Key, Tree, Compare>, Key>,
        public EqualToMethod<DynSetTree<Key, Tree, Compare>>,
        public StlAlephIterator<DynSetTree<Key, Tree, Compare>>
  {
  public:
    using Node = typename Tree<Key, Compare>::Node;
 
    using Tree_Type = Tree<Key, Compare>;
 
  private:
    template <typename T>
    struct Has_Range_Methods
    {
      // The const forms cover RB, AVL, etc.; the non-const ones cover the
      // splay tree, whose lookups restructure the tree.
      static constexpr bool has_select =
          requires(const T & t) { t.select(std::declval<size_t>()); } or
          requires(T & t) { t.select(std::declval<size_t>()); };
      static constexpr bool has_remove_pos =
          requires(T & t) { t.remove_pos(std::declval<size_t>()); };
      static constexpr bool has_split_pos =
          requires(T & t, T & l, T & r) { t.split_pos(std::declval<size_t>(), l, r); };
      static constexpr bool has_position =
          requires(const T & t, const Key & k) { t.position(k); } or
          requires(T & t, const Key & k) { t.position(k); };
      static constexpr bool has_find_position =
          requires(const T & t, const Key & k) { t.find_position(k); } or
          requires(T & t, const Key & k) { t.find_position(k); };
    };
 
    // call_select for const trees (RB, AVL, etc.)
    template <typename T>
    static auto call_select(const T & t, const size_t i, int)
      -> decltype(t.select(i))
    {
      return t.select(i);
    }
 
    // call_select for non-const trees (Splay - mutates on access)
    template <typename T>
    static auto call_select_nc(T & t, const size_t i, int)
      -> decltype(t.select(i))
    {
      return t.select(i);
    }
 
    template <typename T>
    static Node * call_select(const T &, const size_t, ...)
    {
      ah_domain_error() << "select is not supported by underlying tree";
      return nullptr;
    }
 
    template <typename T>
    static Node * call_select_nc(T &, const size_t, ...)
    {
      ah_domain_error() << "select is not supported by underlying tree";
      return nullptr;
    }
 
    template <typename T>
    static auto call_remove_pos(T & t, const size_t i, int)
      -> decltype(t.remove_pos(i))
    {
      return t.remove_pos(i);
    }
 
    template <typename T>
    static Node * call_remove_pos(T &, const size_t, ...)
    {
      ah_domain_error() << "remove_pos is not supported by underlying tree";
      return nullptr;
    }
 
    template <typename T>
    static auto call_split_pos(T & t, const size_t pos, T & l, T & r, int)
      -> decltype(t.split_pos(pos, l, r), void())
    {
      t.split_pos(pos, l, r);
    }
 
    template <typename T>
    static void call_split_pos(T &, const size_t, T &, T &, ...)
    {
      ah_domain_error() << "split_pos is not supported by underlying tree";
    }
 
    template <typename T>
    static auto call_position(const T & t, const Key & key, int)
      -> decltype(t.position(key))
    {
      return t.position(key);
    }
 
    template <typename T>
    static std::pair<long, Node *> call_position(const T &, const Key &, ...)
    {
      ah_domain_error() << "position is not supported by underlying tree";
      return std::pair<long, Node *>(0, nullptr);
    }
 
    template <typename T>
    static auto call_find_position(const T & t, const Key & key, int)
      -> decltype(t.find_position(key))
    {
      return t.find_position(key);
    }
 
    template <typename T>
    static std::pair<long, Node *> call_find_position(const T &, const Key &, ...)
    {
      ah_domain_error() << "find_position is not supported by underlying tree";
      return std::pair<long, Node *>(0, nullptr);
    }
 
    static constexpr size_t dim = 13;
 
    mutable Tree<Key, Compare> tree;
    size_t num_nodes;
    std::unique_ptr<ArenaTreeAllocator<Node>> arena_allocator;
 
    Node * alloc_node(const Key & key)
    {
      if (arena_allocator)
        return arena_allocator->alloc_lval(key);
      return new Node(key);
    }
 
    Node * alloc_node(Key && key)
    {
      if (arena_allocator)
        return arena_allocator->alloc_rval(std::forward<Key>(key));
      return new Node(std::forward<Key>(key));
    }
 
    void free_node(Node *p)
    {
      if (arena_allocator)
        arena_allocator->unalloc(p);
      else
        delete p;
    }
 
  public:
    typedef DynSetTree Set_Type;
 
    typedef Key Item_Type;
 
    typedef Key Key_Type;
 
    void swap(DynSetTree & dset)
      noexcept(noexcept(tree.swap(dset.tree)) and
               noexcept(std::swap(num_nodes, dset.num_nodes)) and
               noexcept(std::swap(arena_allocator, dset.arena_allocator)))
    {
      tree.swap(dset.tree);
      std::swap(num_nodes, dset.num_nodes);
      std::swap(arena_allocator, dset.arena_allocator);
    }
 
    DynSetTree(const Compare & cmp = Compare())
      : tree(cmp), num_nodes(0)
    {
      // empty
    }
 
    DynSetTree(const char *base_addr, const size_t & sz,
               const Compare & cmp = Compare())
      : tree(cmp), num_nodes(0),
        arena_allocator(std::make_unique<ArenaTreeAllocator<Node>>(base_addr, sz))
    {
      // empty
    }
 
    explicit DynSetTree(const size_t & arena_sz,
                        const Compare & cmp = Compare())
      : tree(cmp), num_nodes(0),
        arena_allocator(std::make_unique<ArenaTreeAllocator<Node>>(arena_sz))
    {
      // empty
    }
 
    DynSetTree(const DynSetTree & srcTree)
      : tree(srcTree.tree.get_compare()), num_nodes(srcTree.num_nodes)
    {
      Node *srcRoot = srcTree.tree.getRoot();
      try
        {
          tree.getRoot() = copyRec(srcRoot);
        }
      catch (...)
        {
          num_nodes = 0;
          throw;
        }
    }
 
    Special_Ctors(DynSetTree, Key);
 
    DynSetTree(DynSetTree && srcTree)
      noexcept : num_nodes(0)
    {
      swap(srcTree);
    }
 
    void empty()
    {
      if (arena_allocator)
        {
          // For arena allocation, just call destructors on keys
          // (arena handles memory deallocation)
          callKeyDestructorsRec(tree.getRoot());
 
          // Reset tree
          tree.getRoot() = Node::NullPtr;
          num_nodes = 0;
          return;
        }
 
      destroyRec(tree.getRoot());
      tree.getRoot() = Node::NullPtr;
      num_nodes = 0;
    }
 
    void clear() { empty(); }
 
    DynSetTree &operator =(const DynList<Key> & list)
    {
      return *this = DynSetTree(list);
    }
 
    DynSetTree &operator =(const DynSetTree & srcTree)
    {
      if (this == &srcTree)
        return *this;
 
      Node *src_root = srcTree.tree.getRoot();
 
      empty();
 
      tree.getRoot() = copyRec(src_root);
      num_nodes = srcTree.num_nodes;
 
      return *this;
    }
 
    DynSetTree &operator =(DynSetTree && srcTree)
      noexcept
    {
      if (this == &srcTree)
        return *this;
 
      empty();
      swap(srcTree);
      return *this;
    }
 
    virtual ~DynSetTree()
    {
      empty();
    }
 
  private:
    Key * __insert(Node *p)
    {
      Node *q = nullptr;
      try
        {
          q = tree.search_or_insert(p);
        }
      catch (...)
        {
          free_node(p);
          throw;
        }
 
      if (q != p)
        return nullptr;
 
      ++num_nodes;
 
      return &p->get_key();
    }
 
  public:
    Key * insert(const Key & key)
    {
      Node *p = alloc_node(key);
      Key *key_p = __insert(p);
      if (key_p == nullptr) // was there insertion?
        { // No (KEY(p) is already in the tree) ==> free p and return nullptr
          free_node(p);
          return nullptr;
        }
 
      return key_p;
    }
 
    Key * insert(Key && key)
    {
      Node *p = alloc_node(std::forward<Key>(key));
      Key *key_p = __insert(p);
      if (key_p == nullptr) // was there insertion?
        {
          free_node(p);
          return nullptr;
        }
 
      return key_p;
    }
 
    Key * append(const Key & key)
    {
      return insert(key);
    }
 
    Key * append(Key && key)
    {
      return insert(std::forward<Key>(key));
    }
 
  private:
    Key * __search_or_insert(Node *p)
    {
      Node *q = nullptr;
      try
        {
          q = tree.search_or_insert(p);
        }
      catch (...)
        {
          free_node(p);
          throw;
        }
      if (q != p) // was there an insertion?
        free_node(p); // No (KEY(p) is already in the tree) ==> free
        // allocated node
      else
        ++num_nodes;
 
      return &q->get_key();
    }
 
    std::pair<Node *, bool> __contains_or_insert(Node *p)
    {
      Node *q = nullptr;
      try
        {
          q = tree.search_or_insert(p);
        }
      catch (...)
        {
          free_node(p);
          throw;
        }
      if (q != p)
        { // KEY(p) is already inside the tree
          free_node(p);
          return std::pair<Node *, bool>(q, true);
        }
      ++num_nodes;
      return std::pair<Node *, bool>(p, false);
    }
 
  public:
    Key * search_or_insert(const Key & key)
    {
      return __search_or_insert(alloc_node(key));
    }
 
    Key * search_or_insert(Key && key)
    {
      return
          __search_or_insert(alloc_node(std::forward<Key>(key)));
    }
 
    /* Look for the key <code>key</code> in the binary search tree and
       eventually inserts it if it is not found.
 
       <code>contains_or_insert(key)</code> searches the tree for the key
       <code>key</code>. If the key is already found, then it is returned
       true. Otherwise, the key is inserted and false is returned.
 
       @param[in] key to find or insert
       @return a std::pair whose first field is a pointer to the found or
       inserted key, and the second field is a boolean whose value is
       `false` if the key was inserted; `true` otherwise, that is if the
       key is already present in the tree.
    */
    std::pair<Key *, bool> contains_or_insert(const Key & key)
    {
      auto p = __contains_or_insert(alloc_node(key));
      return std::pair<Key *, bool>(&p.first->get_key(), p.second);
    }
 
    std::pair<Key *, bool> contains_or_insert(Key && key)
    {
      auto p = __contains_or_insert(alloc_node(std::forward<Key>(key)));
      return std::pair<Key *, bool>(&p.first->get_key(), p.second);
    }
 
  private:
    Key * __insert_dup(Node *q)
    {
      try
        {
          Node *p = tree.insert_dup(q);
          ++num_nodes;
          return &p->get_key();
        }
      catch (...)
        {
          free_node(q);
          throw;
        }
    }
 
  public:
    Key * insert_dup(const Key & key)
    {
      return __insert_dup(alloc_node(key));
    }
 
    Key * insert_dup(Key && key)
    {
      return __insert_dup(alloc_node(std::forward<Key>(key)));
    }
 
    Key * put(const Key & key)
    {
      return insert(key);
    }
 
    Key * put(Key && key)
    {
      return insert(std::forward<Key>(key));
    }
 
    size_t remove(const Key & key)
    {
      Node *p = static_cast<Node *>(tree.remove(key));
 
      if (p == nullptr)
        return num_nodes;
 
      free_node(p);
 
      return --num_nodes;
    }
 
    Key del(const Key & key)
    {
      Node *p = static_cast<Node *>(tree.remove(key));
 
      ah_domain_error_if(p == nullptr)
        << "DynSetTree::del key is not found in the tree";
 
      auto ret_val = p->get_key();
 
      free_node(p);
 
      --num_nodes;
 
      return ret_val;
    }
 
    Key remove_pos(const size_t i)
    {
      ah_domain_error_if_constexpr(not Has_Range_Methods<Tree_Type>::has_remove_pos)
        << "remove_pos is not supported by underlying tree";
 
      ah_out_of_range_error_if(i >= num_nodes)
        << "remove_pos index out of range";
 
      Node *p = static_cast<Node *>(call_remove_pos(tree, i, 0));
      ah_logic_error_if(p == nullptr)
        << "remove_pos returned nullptr";
      const Key ret_val = KEY(p);
 
      free_node(p);
 
      --num_nodes;
 
      return ret_val;
    }
 
    bool exist(const Key & key) const
    {
      return search(key) != nullptr;
    }
 
    bool has(const Key & key) const
    {
      return exist(key);
    }
 
    bool contains(const Key & key) const
    {
      return exist(key);
    }
 
    Key &find(const Key & key) const
    {
      Node *node = static_cast<Node *>(tree.search(key));
 
      ah_domain_error_if(node == nullptr)
        << "key not found";
 
      return node->get_key();
    }
 
    std::pair<long, Key *> find_position(const Key & key) const
    {
      ah_domain_error_if_constexpr(not Has_Range_Methods<Tree_Type>::has_find_position)
        << "find_position is not supported by underlying tree";
 
      if (num_nodes == 0)
        return std::pair<long, Key *>(0, nullptr);
 
      auto p = call_find_position(tree, key, 0);
      if (p.second == nullptr)
        return std::pair<long, Key *>(static_cast<long>(p.first), nullptr);
 
      return std::pair<long, Key *>(static_cast<long>(p.first),
                                    &p.second->get_key());
    }
 
    Key * search(const Key & key) const
    {
      Node *node = static_cast<Node *>(tree.search(key));
 
      if (node == nullptr)
        return nullptr;
 
      return &(node->get_key());
    }
 
    const Key &min() const
    {
      ah_domain_error_if(num_nodes == 0)
        << "set is empty";
 
      return find_min(tree.getRoot())->get_key();
    }
 
    const Key &get_first() const { return min(); }
 
    const Key &max() const
    {
      ah_domain_error_if(num_nodes == 0)
        << "set is empty";
 
      return find_max(tree.getRoot())->get_key();
    }
 
    const Key &get_last() const { return max(); }
 
    const Key &get() const { return max(); }
 
    const size_t &size() const { return num_nodes; }
 
    bool is_empty() const { return num_nodes == 0; }
 
    [[nodiscard]] bool uses_arena() const noexcept
    {
      return arena_allocator != nullptr;
    }
 
    [[nodiscard]] size_t arena_allocated_size() const noexcept
    {
      if (arena_allocator)
        return arena_allocator->allocated_size();
      return 0;
    }
 
    [[nodiscard]] size_t arena_available_size() const noexcept
    {
      if (arena_allocator)
        return arena_allocator->available_size();
      return 0;
    }
 
    size_t internal_path_length() const
    {
      return Aleph::internal_path_length(tree.getRoot());
    }
 
    Node * get_root_node() const { return tree.getRoot(); }
 
    const Key &get_root() const
    {
      ah_domain_error_if(num_nodes == 0)
        << "Tree is empty";
      return KEY(tree.getRoot());
    }
 
    const Key &get_item() const { return get_root(); }
 
    size_t height() const { return computeHeightRec(tree.getRoot()); }
 
    template <class Op>
    void for_each_in_preorder(void (*visitFct)(Node *, int, int))
    {
      Node *root = static_cast<Node *>(tree.getRoot());
      preOrderRec(root, visitFct);
    }
 
    long position(const Key & key) const
    {
      ah_domain_error_if_constexpr(not Has_Range_Methods<Tree_Type>::has_position)
        << "position is not supported by underlying tree";
 
      auto p = call_position(tree, key, 0);
      return static_cast<long>(p.first);
    }
 
    Key &select(size_t i)
    {
      ah_domain_error_if_constexpr(not Has_Range_Methods<Tree_Type>::has_select)
        << "select is not supported by underlying tree";
 
      ah_out_of_range_error_if(i >= num_nodes)
        << "select index out of range";
 
      // Try non-const first (for Splay trees), then const
      Node *p = call_select_nc(tree, i, 0);
      ah_logic_error_if(p == nullptr)
        << "select returned nullptr";
      return p->get_key();
    }
 
    const Key &select(size_t i) const
    {
      ah_domain_error_if_constexpr(not Has_Range_Methods<Tree_Type>::has_select)
        << "select is not supported by underlying tree";
 
      ah_out_of_range_error_if(i >= num_nodes)
        << "select index out of range";
 
      // For const version, only const select works (not for Splay trees)
      Node *p = call_select(tree, i, 0);
      ah_logic_error_if(p == nullptr)
        << "select returned nullptr";
      return p->get_key();
    }
 
    Key &operator ()(size_t i)
    {
      return select(i);
    }
 
    const Key &operator [](const Key & key) const
    {
      return find(key);
    }
 
    const Key &operator [](const Key & key)
    {
      return *search_or_insert(key);
    }
 
    Key &access(size_t i)
    {
      return select(i);
    }
 
    bool verify() const
    {
      return tree.verify() and check_bst(tree.getRoot());
    }
 
  private:
    template <class Key_Op>
    struct Node_Op
    {
      Key_Op & key_op;
 
      Node_Op(Key_Op & __key_op) : key_op(__key_op)
      { /* empty */
      }
 
      Node_Op(Key_Op && __key_op) : key_op(__key_op)
      {
        /* empty */
      }
 
      void operator ()(Node *root)
      {
        assert(root != nullptr);
        key_op(KEY(root));
      }
    };
 
  public:
    template <class Key_Op>
    void for_each_preorder(Key_Op & key_op) const
    {
      Node *root = static_cast<Node *>(tree.getRoot());
 
      Node_Op<Key_Op> node_op(const_cast<Key_Op &>(key_op));
 
      For_Each_Preorder<Node>()(root, node_op);
    }
 
    template <class Key_Op>
    void for_each_preorder(Key_Op && key_op = Key_Op()) const
    {
      for_each_preorder<Key_Op>(key_op);
    }
 
    template <class Key_Op>
    void for_each_inorder(Key_Op & key_op) const
    {
      Node *root = static_cast<Node *>(tree.getRoot());
 
      Node_Op<Key_Op> node_op(const_cast<Key_Op &>(key_op));
 
      For_Each_In_Order<Node>()(root, node_op);
    }
 
    template <class Key_Op>
    void for_each_inorder(Key_Op && key_op = Key_Op()) const
    {
      for_each_inorder<Key_Op>(key_op);
    }
 
    template <class Key_Op>
    void for_each_postorder(Key_Op & key_op) const
    {
      Node *root = static_cast<Node *>(tree.getRoot());
 
      Node_Op<Key_Op> node_op(const_cast<Key_Op &>(key_op));
 
      For_Each_Postorder<Node>()(root, node_op);
    }
 
    template <class Key_Op>
    void for_each_postorder(Key_Op && key_op = Key_Op()) const
    {
      for_each_postorder<Key_Op>(key_op);
    }
 
    DynSetTree &join(DynSetTree & t, DynSetTree & dup)
    {
      tree.join(t.tree, dup.tree);
      t.tree.getRoot() = Node::NullPtr;
      t.num_nodes = 0;
      num_nodes = compute_cardinality_rec(tree.getRoot());
      dup.num_nodes = compute_cardinality_rec(dup.tree.getRoot());
      return *this;
    }
 
    DynSetTree &join(DynSetTree & t, DynSetTree && dup = DynSetTree())
    {
      return join(t, dup);
    }
 
    DynSetTree &join_dup(DynSetTree & t)
    {
      tree.join_dup(t.tree);
      t.num_nodes = 0;
      t.tree.getRoot() = Node::NullPtr;
      num_nodes = compute_cardinality_rec(tree.getRoot());
      return *this;
    }
 
    bool split_key(const Key & key, DynSetTree & l, DynSetTree & r)
    {
      if (not tree.split_key(key, l.tree, r.tree))
        return false;
 
      tree.getRoot() = Node::NullPtr;
      num_nodes = 0;
      l.num_nodes = compute_cardinality_rec(l.tree.getRoot());
      r.num_nodes = compute_cardinality_rec(r.tree.getRoot());
 
      return true;
    }
 
    void split_pos(const size_t pos, DynSetTree & l, DynSetTree & r)
    {
      ah_domain_error_if_constexpr(not Has_Range_Methods<Tree_Type>::has_split_pos)
        << "split_pos is not supported by underlying tree";
 
      ah_out_of_range_error_if(pos >= num_nodes)
        << "split_pos position out of range";
 
      // Underlying split_pos splits at [0, pos) and [pos, N)
      // But we want [0, pos] and (pos, N), so we split at pos+1
      call_split_pos(tree, pos + 1, l.tree, r.tree, 0);
      tree.getRoot() = Node::NullPtr;
      num_nodes = 0;
      l.num_nodes = compute_cardinality_rec(l.tree.getRoot());
      r.num_nodes = compute_cardinality_rec(r.tree.getRoot());
    }
 
    void split_key_dup(const Key & key, DynSetTree & l, DynSetTree & r)
    {
      tree.split_key_dup(key, l.tree, r.tree);
      tree.getRoot() = Node::NullPtr;
      num_nodes = 0;
      l.num_nodes = compute_cardinality_rec(l.tree.getRoot());
      r.num_nodes = compute_cardinality_rec(r.tree.getRoot());
    }
 
    struct Iterator : public Tree_Type::Iterator
    {
      using Base = typename Tree_Type::Iterator;
 
      using Set_Type = DynSetTree;
 
      Iterator() noexcept = default;
 
      Iterator(const DynSetTree & tree) : Base(tree.tree)
      { /* empty */
      }
 
      const Key &get_curr_ne() const noexcept
      {
        return Base::get_curr_ne()->get_key();
      }
 
      Key &get_curr_ne() noexcept { return Base::get_curr_ne()->get_key(); }
 
      const Key &get_curr() const { return Base::get_curr()->get_key(); }
 
      Key &get_curr() { return Base::get_curr()->get_key(); }
    };
 
    template <class Operation>
    bool traverse(Operation & op)
    {
      return Aleph::traverse(tree.getRoot(), [&op](Node *p)
                               {
                                 return op(p->get_key());
                               });
    }
 
    template <class Operation>
    bool traverse(Operation && op = Operation())
    {
      return traverse<Operation>(op);
    }
 
    template <class Operation>
    bool traverse(Operation & op) const
    {
      return Aleph::traverse(tree.getRoot(), [&op](Node *p)
                               {
                                 return op(p->get_key());
                               });
    }
 
    template <class Operation>
    bool traverse(Operation && op = Operation()) const
    {
      return traverse<Operation>(op);
    }
  };
 
 
# define SETTREE_ITOR(Name, Key, Cmp)                           \
  class Iterator : public DynSetTree<Key, Name, Cmp>::Iterator  \
  {                                                             \
  public:                                                       \
    Iterator() : DynSetTree<Key, Name, Cmp>::Iterator()         \
      { /* empty */ }                                           \
                                                                \
    Iterator(DynSetTree<Key, Name, Cmp> & tree)                 \
      : DynSetTree<Key, Name, Cmp>::Iterator(tree)              \
      { /* empty */ }                                           \
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetBinTree : public DynSetTree<Key, BinTree, Compare>
  {
  public:
    using Base = DynSetTree<Key, BinTree, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetAvlTree : public DynSetTree<Key, Avl_Tree, Compare>
  {
  public:
    using Base = DynSetTree<Key, Avl_Tree, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetSplayTree : public DynSetTree<Key, Splay_Tree, Compare>
  {
  public:
    using Base = DynSetTree<Key, Splay_Tree, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetSplayRkTree : public DynSetTree<Key, Splay_Tree_Rk, Compare>
  {
  public:
    using Base = DynSetTree<Key, Splay_Tree_Rk, Compare>;
    using Base::Base;
    SETTREE_ITOR(Splay_Tree_Rk, Key, Compare);
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetRandTree : public DynSetTree<Key, Rand_Tree, Compare>
  {
  public:
    using Base = DynSetTree<Key, Rand_Tree, Compare>;
    using Base::Base;
 
    class Iterator : public DynSetTree<Key, Rand_Tree, Compare>::Iterator
    {
    public:
      Iterator() : DynSetTree<Key, Rand_Tree, Compare>::Iterator()
      { /* empty */
      }
 
      Iterator(DynSetTree<Key, Rand_Tree, Compare> & tree)
        : DynSetTree<Key, Rand_Tree, Compare>::Iterator(tree)
      { /* empty */
      }
    };
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetTreap : public DynSetTree<Key, Treap, Compare>
  {
  public:
    using Base = DynSetTree<Key, Treap, Compare>;
    using Base::Base;
  };
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetTreapRk : public DynSetTree<Key, Treap_Rk, Compare>
  {
  public:
    using Base = DynSetTree<Key, Treap_Rk, Compare>;
    using Base::Base;
    SETTREE_ITOR(Treap_Rk, Key, Compare);
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetAvlRkTree : public DynSetTree<Key, Avl_Tree_Rk, Compare>
  {
  public:
    using Base = DynSetTree<Key, Avl_Tree_Rk, Compare>;
    using Base::Base;
    SETTREE_ITOR(Avl_Tree_Rk, Key, Compare);
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetRbTree : public DynSetTree<Key, Rb_Tree, Compare>
  {
  public:
    using Base = DynSetTree<Key, Rb_Tree, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetTdRbTree : public DynSetTree<Key, TdRbTree, Compare>
  {
  public:
    using Base = DynSetTree<Key, TdRbTree, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetRbRkTree : public DynSetTree<Key, Rb_Tree_Rk, Compare>
  {
  public:
    using Base = DynSetTree<Key, Rb_Tree_Rk, Compare>;
    using Base::Base;
    SETTREE_ITOR(Rb_Tree_Rk, Key, Compare);
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetTdRbRkTree : public DynSetTree<Key, TdRbTreeRk, Compare>
  {
  public:
    using Base = DynSetTree<Key, TdRbTreeRk, Compare>;
    using Base::Base;
    SETTREE_ITOR(TdRbTreeRk, Key, Compare);
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetHtdRbTree : public DynSetTree<Key, HtdRbTree, Compare>
  {
  public:
    using Base = DynSetTree<Key, HtdRbTree, Compare>;
    using Base::Base;
    SETTREE_ITOR(HtdRbTree, Key, Compare);
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
  class DynSetHtdRbRkTree : public DynSetTree<Key, HtdRbTreeRk, Compare>
  {
  public:
    using Base = DynSetTree<Key, HtdRbTreeRk, Compare>;
    using Base::Base;
    SETTREE_ITOR(HtdRbTreeRk, Key, Compare);
  };
 
 
  template <typename T, class Op, class C>
  DynSetTree<T> set_unify(const C & c, Op op)
  {
    DynSetTree<T> ret;
    for (auto it = c.get_it(); it.has_curr(); it.next_ne())
      ret.insert(op(it.get_curr()));
    return ret;
  }
} // end namespace Aleph
 
# endif /* TPL_DYNSETTREE_H */