tpl_interval_tree.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_INTERVAL_TREE_H
# define TPL_INTERVAL_TREE_H
 
# include <gsl/gsl_rng.h>
 
# include <cassert>
# include <ctime>
# include <type_traits>
 
# include <ahFunction.H>
# include <tpl_binNodeUtils.H>
# include <treapNode.H>
# include <tpl_binTreeOps.H>
# include <ah-errors.H>
# include <ah-concepts.H>
# include <ah-dry.H>
# include <ahDry.H>
# include <htlist.H>
# include <utility>
# include <memory>
 
namespace Aleph
{
  template <typename T>
  struct Interval
  {
    T low; 
    T high; 
 
    Interval()
      noexcept(std::is_nothrow_default_constructible_v<T>)
      : low(), high() {}
 
    Interval(const T & lo, const T & hi)
      noexcept(std::is_nothrow_copy_constructible_v<T>)
      : low(lo), high(hi) {}
 
    Interval(T && lo, T && hi)
      noexcept(std::is_nothrow_move_constructible_v<T>)
      : low(std::move(lo)), high(std::move(hi)) {}
 
    static Interval point(const T & p)
      noexcept(std::is_nothrow_copy_constructible_v<T>)
    {
      return {p, p};
    }
 
    template <class Compare = Aleph::less<T>>
    [[nodiscard]] bool overlaps(const Interval & other,
                                const Compare & cmp = Compare()) const
      noexcept(std::is_nothrow_invocable_v<const Compare &, const T &, const T &>)
    {
      // [a,b] overlaps [c,d] iff a <= d and c <= b
      return not cmp(other.high, low) and not cmp(high, other.low);
    }
 
    template <class Compare = Aleph::less<T>>
    [[nodiscard]] bool contains(const T & p,
                                const Compare & cmp = Compare()) const
      noexcept(std::is_nothrow_invocable_v<const Compare &, const T &, const T &>)
    {
      return not cmp(p, low) and not cmp(high, p);
    }
 
    template <class Compare = Aleph::less<T>>
    [[nodiscard]] bool is_valid(const Compare & cmp = Compare()) const
      noexcept(std::is_nothrow_invocable_v<const Compare &, const T &, const T &>)
    {
      return not cmp(high, low);
    }
 
    bool operator ==(const Interval & other) const
      noexcept(noexcept(std::declval<const T &>() == std::declval<const T &>()))
    {
      return low == other.low and high == other.high;
    }
 
    bool operator !=(const Interval & other) const
      noexcept(noexcept(*this == other))
    {
      return not (*this == other);
    }
  };
 
  template <typename T, class Compare = Aleph::less<T>>
  struct Interval_Less
  {
    Compare cmp;
 
    Interval_Less(const Compare & c = Compare())
      noexcept(std::is_nothrow_copy_constructible_v<Compare>)
      : cmp(c) {}
 
    bool operator ()(const Interval<T> & a, const Interval<T> & b) const
      noexcept(std::is_nothrow_invocable_v<const Compare &, const T &, const T &>)
    {
      if (cmp(a.low, b.low))
        return true;
      if (cmp(b.low, a.low))
        return false;
      return cmp(a.high, b.high);
    }
  };
 
  template <typename Key>
  struct interval_endpoint;
 
  template <typename T>
  struct interval_endpoint<Interval<T>>
  {
    using type = T;
  };
 
  template <typename Key>
  using interval_endpoint_t = typename interval_endpoint<Key>::type;
 
  template <typename T>
  class Interval_Tree_Node_Data
  {
    unsigned long priority;
    T max_endpoint;
 
  public:
    Interval_Tree_Node_Data()
      noexcept(std::is_nothrow_default_constructible_v<T>)
      : priority(Max_Priority), max_endpoint() {}
 
    Interval_Tree_Node_Data(SentinelCtor)
      noexcept(std::is_nothrow_default_constructible_v<T>)
      : priority(Max_Priority), max_endpoint() {}
 
    unsigned long &getPriority() noexcept { return priority; }
 
    T &getMaxEndpoint() noexcept { return max_endpoint; }
    const T &getMaxEndpoint() const noexcept { return max_endpoint; }
 
    static void reset() noexcept
    { /* empty */
    }
  };
 
  template <typename Key>
  class Interval_Tree_Node
      : public Interval_Tree_Node_Data<interval_endpoint_t<Key>>
  {
  public:
    using Endpoint = interval_endpoint_t<Key>;
    using Data = Interval_Tree_Node_Data<Endpoint>;
 
    static constexpr size_t MaxHeight = 80;
    static Interval_Tree_Node *const NullPtr;
 
    using key_type = Key;
    using Key_Type = Key;
 
  private:
    Key key = Key();
    Interval_Tree_Node *lLink;
    Interval_Tree_Node *rLink;
 
    // sentinel node
    static Interval_Tree_Node sentinel_node;
 
  public:
    Key &get_key() noexcept { return key; }
    const Key &get_key() const noexcept { return key; }
 
    Interval_Tree_Node *&getL() noexcept { return lLink; }
    Interval_Tree_Node *&getR() noexcept { return rLink; }
    const Interval_Tree_Node * getL() const noexcept { return lLink; }
    const Interval_Tree_Node * getR() const noexcept { return rLink; }
 
    Interval_Tree_Node(const Key & k)
      : key(k), lLink(NullPtr), rLink(NullPtr)
    {
      this->getMaxEndpoint() = k.high;
    }
 
    Interval_Tree_Node(Key && k)
      noexcept(std::is_nothrow_move_constructible_v<Key>)
      : key(std::move(k)), lLink(NullPtr), rLink(NullPtr)
    {
      this->getMaxEndpoint() = key.high;
    }
 
    Interval_Tree_Node(const Interval_Tree_Node & node)
      : Data(node),
        key(node.key), lLink(NullPtr), rLink(NullPtr)
    {
      /* empty */
    }
 
    Interval_Tree_Node(Interval_Tree_Node && node)
      noexcept(std::is_nothrow_move_constructible_v<Key> and
               std::is_nothrow_move_constructible_v<Data>)
      : Data(std::move(static_cast<Data &>(node))),
        key(std::move(node.key)), lLink(NullPtr), rLink(NullPtr)
    {
      /* empty */
    }
 
    Interval_Tree_Node()
      : lLink(NullPtr), rLink(NullPtr)
    {
      /* empty */
    }
 
    void reset() noexcept
    {
      Data::reset();
      this->getMaxEndpoint() = key.high;
      rLink = lLink = NullPtr;
    }
 
  private:
    // sentinel constructor
    Interval_Tree_Node(SentinelCtor)
      : Data(sentinelCtor), lLink(nullptr), rLink(nullptr)
    {
      /* empty - links set to nullptr will be fixed when NullPtr is initialized */
    }
  };
 
  template <typename Key>
  Interval_Tree_Node<Key> Interval_Tree_Node<Key>::sentinel_node(sentinelCtor);
 
  template <typename Key>
  Interval_Tree_Node<Key> *const
      Interval_Tree_Node<Key>::NullPtr = &Interval_Tree_Node<Key>::sentinel_node;
 
  template <typename Key>
  class Interval_Tree_NodeVtl
      : public Interval_Tree_Node_Data<interval_endpoint_t<Key>>
  {
  public:
    using Endpoint = interval_endpoint_t<Key>;
    using Data = Interval_Tree_Node_Data<Endpoint>;
 
    static constexpr size_t MaxHeight = 80;
    static Interval_Tree_NodeVtl *const NullPtr;
 
    using key_type = Key;
    using Key_Type = Key;
 
  private:
    Key key = Key();
    Interval_Tree_NodeVtl *lLink;
    Interval_Tree_NodeVtl *rLink;
 
    static Interval_Tree_NodeVtl sentinel_node;
 
  public:
    Key &get_key() noexcept { return key; }
    const Key &get_key() const noexcept { return key; }
 
    Interval_Tree_NodeVtl *&getL() noexcept { return lLink; }
    Interval_Tree_NodeVtl *&getR() noexcept { return rLink; }
    const Interval_Tree_NodeVtl * getL() const noexcept { return lLink; }
    const Interval_Tree_NodeVtl * getR() const noexcept { return rLink; }
 
    Interval_Tree_NodeVtl(const Key & k)
      : key(k), lLink(NullPtr), rLink(NullPtr)
    {
      this->getMaxEndpoint() = k.high;
    }
 
    Interval_Tree_NodeVtl(Key && k)
      noexcept(std::is_nothrow_move_constructible_v<Key>)
      : key(std::move(k)), lLink(NullPtr), rLink(NullPtr)
    {
      this->getMaxEndpoint() = key.high;
    }
 
    Interval_Tree_NodeVtl(const Interval_Tree_NodeVtl & node)
      : Data(node),
        key(node.key), lLink(NullPtr), rLink(NullPtr)
    {
      /* empty */
    }
 
    Interval_Tree_NodeVtl(Interval_Tree_NodeVtl && node)
      noexcept(std::is_nothrow_move_constructible_v<Key> and
               std::is_nothrow_move_constructible_v<Data>)
      : Data(std::move(static_cast<Data &>(node))),
        key(std::move(node.key)), lLink(NullPtr), rLink(NullPtr)
    {
      /* empty */
    }
 
    Interval_Tree_NodeVtl()
      : lLink(NullPtr), rLink(NullPtr)
    {
      /* empty */
    }
 
    virtual ~Interval_Tree_NodeVtl() = default;
 
    void reset() noexcept
    {
      Data::reset();
      this->getMaxEndpoint() = key.high;
      rLink = lLink = NullPtr;
    }
 
  private:
    Interval_Tree_NodeVtl(SentinelCtor)
      : Data(sentinelCtor), lLink(nullptr), rLink(nullptr)
    {
      /* empty */
    }
  };
 
  template <typename Key>
  Interval_Tree_NodeVtl<Key> Interval_Tree_NodeVtl<Key>::sentinel_node(sentinelCtor);
 
  template <typename Key>
  Interval_Tree_NodeVtl<Key> *const
      Interval_Tree_NodeVtl<Key>::NullPtr = &Interval_Tree_NodeVtl<Key>::sentinel_node;
 
  template <class Node>
  inline auto &MAX_EP(Node *p) noexcept { return p->getMaxEndpoint(); }
 
  template <class Node>
  inline const auto &MAX_EP(const Node *p) noexcept
  {
    return p->getMaxEndpoint();
  }
 
  template <template <typename> class NodeType,
            typename T,
            class Compare = Aleph::less<T>>
    requires StrictWeakOrder<Compare, T>
  class Gen_Interval_Tree
  {
  public:
    using Key = Interval<T>;
    using IntervalCmp = Interval_Less<T, Compare>;
    using Node = NodeType<Key>;
 
  private:
    Node head;
    Node *head_ptr;
    Node *& tree_root;
    gsl_rng *r;
    Compare cmp;
    size_t num_nodes;
 
    void init(const unsigned int seed)
    {
      PRIO(head_ptr) = Min_Priority;
      r = gsl_rng_alloc(gsl_rng_mt19937);
      ah_bad_alloc_if(r == nullptr);
      gsl_rng_set(r, seed % gsl_rng_max(r));
    }
 
    static void update_max(Node *p, const Compare & cmp)
    {
      auto & mx = MAX_EP(p);
      mx = KEY(p).high;
      if (LLINK(p) != Node::NullPtr)
        if (cmp(mx, MAX_EP(LLINK(p))))
          mx = MAX_EP(LLINK(p));
      if (RLINK(p) != Node::NullPtr)
        if (cmp(mx, MAX_EP(RLINK(p))))
          mx = MAX_EP(RLINK(p));
    }
 
    static Node * rotate_to_right_it(Node *p, const Compare & cmp)
    {
      assert(p != Node::NullPtr);
      Node *q = LLINK(p);
      LLINK(p) = RLINK(q);
      RLINK(q) = p;
      update_max(p, cmp); // old parent first (now child)
      update_max(q, cmp); // new parent (depends on updated p)
      return q;
    }
 
    static Node * rotate_to_left_it(Node *p, const Compare & cmp)
    {
      assert(p != Node::NullPtr);
      Node *q = RLINK(p);
      RLINK(p) = LLINK(q);
      LLINK(q) = p;
      update_max(p, cmp);
      update_max(q, cmp);
      return q;
    }
 
    Node * insert(Node *root, Node *p)
    {
      if (root == Node::NullPtr)
        return p;
 
      const Key & pk = KEY(p);
      const Key & rk = KEY(root);
      const IntervalCmp interval_cmp(cmp);
      Node *result = nullptr;
      if (interval_cmp(pk, rk))
        {
          result = insert(LLINK(root), p);
          if (result == Node::NullPtr)
            return Node::NullPtr;
          LLINK(root) = result;
          update_max(root, cmp);
          if (PRIO(LLINK(root)) < PRIO(root))
            return rotate_to_right_it(root, cmp);
          return root;
        }
      if (interval_cmp(rk, pk))
        {
          result = insert(RLINK(root), p);
          if (result == Node::NullPtr)
            return Node::NullPtr;
          RLINK(root) = result;
          update_max(root, cmp);
          if (PRIO(RLINK(root)) < PRIO(root))
            return rotate_to_left_it(root, cmp);
          return root;
        }
 
      return Node::NullPtr; // duplicate
    }
 
    Node * insert_dup(Node *root, Node *p)
    {
      if (root == Node::NullPtr)
        return p;
 
      const Key & pk = KEY(p);
      const Key & rk = KEY(root);
      const IntervalCmp interval_cmp(cmp);
      if (interval_cmp(pk, rk))
        {
          LLINK(root) = insert_dup(LLINK(root), p);
          update_max(root, cmp);
          if (PRIO(LLINK(root)) < PRIO(root))
            return rotate_to_right_it(root, cmp);
          return root;
        }
      RLINK(root) = insert_dup(RLINK(root), p);
      update_max(root, cmp);
      if (PRIO(RLINK(root)) < PRIO(root))
        return rotate_to_left_it(root, cmp);
      return root;
    }
 
    static Node * join_exclusive(Node *t1, Node *t2,
                                 const Compare & cmp)
    {
      if (t1 == Node::NullPtr)
        return t2;
      if (t2 == Node::NullPtr)
        return t1;
 
      if (PRIO(t1) < PRIO(t2))
        {
          RLINK(t1) = join_exclusive(RLINK(t1), t2, cmp);
          update_max(t1, cmp);
          return t1;
        }
      LLINK(t2) = join_exclusive(t1, LLINK(t2), cmp);
      update_max(t2, cmp);
      return t2;
    }
 
    Node * remove(Node *& root, const Key & key)
    {
      if (root == Node::NullPtr)
        return Node::NullPtr;
 
      const Key & rk = KEY(root);
      const IntervalCmp interval_cmp(cmp);
      Node *ret_val;
      if (interval_cmp(key, rk))
        ret_val = remove(LLINK(root), key);
      else if (interval_cmp(rk, key))
        ret_val = remove(RLINK(root), key);
      else
        {
          ret_val = root;
          root = join_exclusive(LLINK(root), RLINK(root), cmp);
          return ret_val;
        }
 
      if (ret_val == Node::NullPtr)
        return Node::NullPtr;
 
      update_max(root, cmp);
      return ret_val;
    }
 
    template <class Op>
    static void all_overlaps(Node *root, const Key & query,
                             Op & op, const Compare & cmp)
    {
      if (root == Node::NullPtr)
        return;
 
      // Prune: if max_endpoint < query.low, no overlap in this subtree
      if (cmp(MAX_EP(root), query.low))
        return;
 
      // Recurse left
      all_overlaps(LLINK(root), query, op, cmp);
 
      // Check current node
      if (KEY(root).overlaps(query, cmp))
        op(KEY(root));
 
      // Prune right: if root.low > query.high, no overlap in right subtree
      if (cmp(query.high, KEY(root).low))
        return;
 
      // Recurse right
      all_overlaps(RLINK(root), query, op, cmp);
    }
 
    static bool check_max(Node *root, const Compare & cmp)
    {
      if (root == Node::NullPtr)
        return true;
 
      T expected = KEY(root).high;
      if (LLINK(root) != Node::NullPtr)
        if (cmp(expected, MAX_EP(LLINK(root))))
          expected = MAX_EP(LLINK(root));
      if (RLINK(root) != Node::NullPtr)
        if (cmp(expected, MAX_EP(RLINK(root))))
          expected = MAX_EP(RLINK(root));
 
      if (cmp(MAX_EP(root), expected) or cmp(expected, MAX_EP(root)))
        return false; // MAX_EP(root) != expected
 
      return check_max(LLINK(root), cmp) and check_max(RLINK(root), cmp);
    }
 
    static size_t count_nodes(Node *root) noexcept
    {
      if (root == Node::NullPtr)
        return 0;
      return 1 + count_nodes(LLINK(root)) + count_nodes(RLINK(root));
    }
 
  public:
    void set_seed(const unsigned long seed) noexcept { gsl_rng_set(r, seed); }
 
    IntervalCmp key_comp() const noexcept { return IntervalCmp(cmp); }
 
    const Compare & endpoint_comp() const noexcept { return cmp; }
 
    const Compare & get_compare() const noexcept { return endpoint_comp(); }
 
    void swap(Gen_Interval_Tree & tree)
      noexcept(noexcept(std::swap(tree_root, tree.tree_root)) and
               noexcept(std::swap(cmp, tree.cmp)) and
               noexcept(std::swap(r, tree.r)) and
               noexcept(std::swap(num_nodes, tree.num_nodes)))
    {
      std::swap(tree_root, tree.tree_root);
      std::swap(cmp, tree.cmp);
      std::swap(r, tree.r);
      std::swap(num_nodes, tree.num_nodes);
    }
 
    Gen_Interval_Tree(const unsigned long seed,
                      const Compare & _cmp = Compare())
      : head_ptr(&head), tree_root(RLINK(head_ptr)), r(nullptr),
        cmp(_cmp), num_nodes(0)
    {
      init(seed);
    }
 
    Gen_Interval_Tree(const Compare & _cmp = Compare())
      : Gen_Interval_Tree(static_cast<unsigned long>(time(nullptr)), _cmp)
    {
      /* empty */
    }
 
    Gen_Interval_Tree(const Gen_Interval_Tree &) = delete;
    Gen_Interval_Tree &operator =(const Gen_Interval_Tree &) = delete;
    Gen_Interval_Tree(Gen_Interval_Tree &&) = delete;
    Gen_Interval_Tree &operator =(Gen_Interval_Tree &&) = delete;
 
    ~Gen_Interval_Tree()
    {
      if (r != nullptr)
        gsl_rng_free(r);
    }
 
    [[nodiscard]] gsl_rng * gsl_rng_object() const noexcept { return r; }
 
    Node *&getRoot() noexcept { return tree_root; }
 
    const Node * getRoot() const { return tree_root; }
 
    [[nodiscard]] size_t size() const noexcept { return num_nodes; }
 
    [[nodiscard]] bool is_empty() const noexcept { return num_nodes == 0; }
 
    void reset_num_nodes() noexcept { num_nodes = 0; }
 
    const Node * search(const Key & key) const
    {
      Node *ret_val = searchInBinTree(tree_root, key, key_comp());
      return ret_val == Node::NullPtr ? nullptr : ret_val;
    }
 
    Node * insert(Node *p)
    {
      assert(p != Node::NullPtr);
      PRIO(p) = gsl_rng_get(r);
      p->getMaxEndpoint() = KEY(p).high;
      Node *result = insert(tree_root, p);
      if (result == Node::NullPtr)
        return nullptr;
      tree_root = result;
      ++num_nodes;
      return p;
    }
 
    Node * insert_dup(Node *p)
    {
      assert(p != Node::NullPtr);
      PRIO(p) = gsl_rng_get(r);
      p->getMaxEndpoint() = KEY(p).high;
      tree_root = insert_dup(tree_root, p);
      ++num_nodes;
      return p;
    }
 
    Node * remove(const Key & key)
    {
      Node *ret_val = remove(tree_root, key);
      if (ret_val == Node::NullPtr)
        return nullptr;
      ret_val->reset();
      --num_nodes;
      return ret_val;
    }
 
    const Node * overlap_search(const Key & query) const
    {
      Node *x = tree_root;
      while (x != Node::NullPtr)
        {
          if (KEY(x).overlaps(query, cmp))
            return x;
 
          if (LLINK(x) != Node::NullPtr and
              not cmp(MAX_EP(LLINK(x)), query.low))
            x = LLINK(x);
          else
            x = RLINK(x);
        }
      return nullptr;
    }
 
    template <class Op>
    void all_overlaps(const Key & query, Op && op) const
    {
      all_overlaps(tree_root, query, op, cmp);
    }
 
    [[nodiscard]] DynList<Key> find_all_overlaps(const Key & query) const
    {
      DynList<Key> result;
      all_overlaps(query, [&result](const Key & iv) { result.append(iv); });
      return result;
    }
 
    template <class Op>
    void stab(const T & p, Op && op) const
    {
      Key point_iv = Key::point(p);
      all_overlaps(point_iv, std::forward<Op>(op));
    }
 
    [[nodiscard]] DynList<Key> find_stab(const T & p) const
    {
      return find_all_overlaps(Key::point(p));
    }
 
    [[nodiscard]] bool verify() const
    {
      if (not check_bst(tree_root, key_comp()))
        return false;
      if (not is_treap(tree_root))
        return false;
      if (not check_max(tree_root, cmp))
        return false;
      if (count_nodes(tree_root) != num_nodes)
        return false;
      return true;
    }
 
    struct Iterator : public BinNodeInfixIterator<Node>
    {
      Iterator() noexcept = default;
 
      Iterator(const Gen_Interval_Tree & t)
        : BinNodeInfixIterator<Node>(t.tree_root) {}
    };
  };
 
  template <typename T, class Compare = Aleph::less<T>>
    requires StrictWeakOrder<Compare, T>
  struct Interval_Tree
      : public Gen_Interval_Tree<Interval_Tree_Node, T, Compare>
  {
    using Base = Gen_Interval_Tree<Interval_Tree_Node, T, Compare>;
    using Base::Base;
  };
 
  template <typename T, class Compare = Aleph::less<T>>
    requires StrictWeakOrder<Compare, T>
  struct Interval_Tree_Vtl
      : public Gen_Interval_Tree<Interval_Tree_NodeVtl, T, Compare>
  {
    using Base = Gen_Interval_Tree<Interval_Tree_NodeVtl, T, Compare>;
    using Base::Base;
  };
 
  template <typename T, class Compare = Aleph::less<T>>
    requires StrictWeakOrder<Compare, T>
  class DynIntervalTree
      : public EqualToMethod<DynIntervalTree<T, Compare>>,
        public FunctionalMethods<DynIntervalTree<T, Compare>, Interval<T>>,
        public GenericKeys<DynIntervalTree<T, Compare>, Interval<T>>,
        public StlAlephIterator<DynIntervalTree<T, Compare>>
  {
  public:
    using Key = Interval<T>;
    using Item_Type = Key;
    using Key_Type = Key;
    using Node = typename Interval_Tree<T, Compare>::Node;
    using Tree = Interval_Tree<T, Compare>;
 
  private:
    Tree tree;
 
    void copy_from(const DynIntervalTree & src)
    {
      src.for_each([this](const Key & iv) { append(iv); });
    }
 
    void destroy_tree()
    {
      destroyRec(tree.getRoot());
      tree.reset_num_nodes();
    }
 
  public:
    DynIntervalTree(const Compare & cmp = Compare()) : tree(cmp) {}
 
    DynIntervalTree(const unsigned long seed,
                    const Compare & cmp = Compare())
      : tree(seed, cmp) {}
 
    DynIntervalTree(const DynIntervalTree & src)
      : tree(src.tree.endpoint_comp())
    {
      DynIntervalTree tmp(src.tree.endpoint_comp());
      tmp.copy_from(src);
      this->swap(tmp);
    }
 
    DynIntervalTree(DynIntervalTree && src)
      : tree(src.tree.endpoint_comp())
    {
      tree.swap(src.tree);
    }
 
    DynIntervalTree &operator =(const DynIntervalTree & src)
    {
      if (this == &src)
        return *this;
      DynIntervalTree tmp(src);
      swap(tmp);
      return *this;
    }
 
    DynIntervalTree &operator =(DynIntervalTree && src)
      noexcept(noexcept(std::declval<Tree &>().swap(std::declval<Tree &>())))
    {
      if (this == &src)
        return *this;
      destroy_tree();
      tree.swap(src.tree);
      return *this;
    }
 
    ~DynIntervalTree() { destroy_tree(); }
 
    void swap(DynIntervalTree & other)
      noexcept(noexcept(std::declval<Tree &>().swap(std::declval<Tree &>())))
    {
      tree.swap(other.tree);
    }
 
    Special_Ctors(DynIntervalTree, Key);
 
    Key &insert(const Key & iv)
    {
      ah_domain_error_if(not iv.is_valid(tree.endpoint_comp()))
        << "Invalid interval: low > high";
      std::unique_ptr<Node> p(new Node(iv));
      Node *result = tree.insert(p.get());
      if (result == nullptr)
        ah_domain_error() << "Duplicate interval";
      
      p.release();
      return KEY(result);
    }
 
    Key &insert(Key && iv)
    {
      ah_domain_error_if(not iv.is_valid(tree.endpoint_comp()))
        << "Invalid interval: low > high";
      std::unique_ptr<Node> p(new Node(std::move(iv)));
      Node *result = tree.insert(p.get());
      if (result == nullptr)
        ah_domain_error() << "Duplicate interval";
      
      p.release();
      return KEY(result);
    }
 
    Key &insert(const T & lo, const T & hi)
    {
      return insert(Key(lo, hi));
    }
 
    Key &insert_dup(const Key & iv)
    {
      ah_domain_error_if(not iv.is_valid(tree.endpoint_comp()))
        << "Invalid interval: low > high";
      std::unique_ptr<Node> p(new Node(iv));
      tree.insert_dup(p.get());
      return KEY(p.release());
    }
 
    Key &append(const Key & iv) { return insert_dup(iv); }
 
    bool remove(const Key & iv)
    {
      Node *p = tree.remove(iv);
      if (p == nullptr)
        return false;
      delete p;
      return true;
    }
 
    bool remove(const T & lo, const T & hi)
    {
      return remove(Key(lo, hi));
    }
 
    const Key * search(const Key & iv) const noexcept
    {
      auto *p = tree.search(iv);
      return p != nullptr ? &KEY(p) : nullptr;
    }
 
    const Key * overlap_search(const Key & query) const
    {
      auto *p = tree.overlap_search(query);
      return p != nullptr ? &KEY(p) : nullptr;
    }
 
    const Key * overlap_search(const T & lo, const T & hi) const
    {
      return overlap_search(Key(lo, hi));
    }
 
    template <class Op>
    void all_overlaps(const Key & query, Op && op) const
    {
      tree.all_overlaps(query, std::forward<Op>(op));
    }
 
    [[nodiscard]] DynList<Key> find_all_overlaps(const Key & query) const
    {
      return tree.find_all_overlaps(query);
    }
 
    [[nodiscard]] DynList<Key> find_all_overlaps(const T & lo,
                                                 const T & hi) const
    {
      return find_all_overlaps(Key(lo, hi));
    }
 
    template <class Op>
    void stab(const T & p, Op && op) const
    {
      tree.stab(p, std::forward<Op>(op));
    }
 
    [[nodiscard]] DynList<Key> find_stab(const T & p) const
    {
      return tree.find_stab(p);
    }
 
    [[nodiscard]] size_t size() const noexcept { return tree.size(); }
 
    [[nodiscard]] bool is_empty() const noexcept { return tree.is_empty(); }
 
    [[nodiscard]] bool empty() const noexcept { return is_empty(); }
 
    [[nodiscard]] bool verify() const { return tree.verify(); }
 
    template <class Operation>
    bool traverse(Operation & op)
    {
      return Aleph::traverse(tree.getRoot(), [&op](const 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](const Node *p)
                               {
                                 return op(p->get_key());
                               });
    }
 
    template <class Operation>
    bool traverse(Operation && op = Operation()) const
    {
      return traverse<Operation>(op);
    }
 
    class Iterator
    {
      typename Tree::Iterator it;
 
    public:
      Iterator() noexcept = default;
 
      Iterator(const DynIntervalTree & t) : it(t.tree) {}
 
      [[nodiscard]] bool has_curr() const noexcept { return it.has_curr(); }
 
      const Key &get_curr() const
      {
        return KEY(static_cast<const Node*>(it.get_curr()));
      }
 
      const Key &get_curr_ne() const noexcept
      {
        return KEY(static_cast<const Node*>(it.get_curr_ne()));
      }
 
      void next() { it.next(); }
 
      void next_ne() noexcept { it.next_ne(); }
 
      void prev() { it.prev(); }
 
      void reset_first() noexcept { it.reset_first(); }
 
      void end() noexcept { it.end(); }
 
      [[nodiscard]] size_t get_pos() const { return it.get_pos(); }
    };
  };
} // end namespace Aleph
 
# endif // TPL_INTERVAL_TREE_H