tpl_treapRk.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_TREAPRK_H
# define TPL_TREAPRK_H
 
# include <gsl/gsl_rng.h>
# include <ahFunction.H>
# include <tpl_binTreeOps.H>
# include <ran_array.h>
# include <treapNode.H>
# include <ah-errors.H>
 
using namespace Aleph;
 
namespace Aleph {
 
class TreapRkNode_Data
{
  unsigned long priority;
 
  unsigned long count;
 
public:
 
  TreapRkNode_Data() noexcept : priority(Max_Priority), count(1)
  {
    /* empty */
  }
 
  TreapRkNode_Data(SentinelCtor) noexcept : priority(Max_Priority), count(0)
  {
    /* empty */
  }
 
  unsigned long & getPriority() noexcept { return priority; }
 
  unsigned long & getCount() noexcept { return count; }
 
  void reset() noexcept { count = 1; }
};
 
  DECLARE_BINNODE_SENTINEL(Treap_Rk_Node, 80, TreapRkNode_Data);
 
    template <template <class> class NodeType, class Key, class Compare>
class Gen_Treap_Rk
{
public:
 
  using Node = NodeType<Key>; 
 
private:
 
  Node      head;
  Node *    head_ptr;
  Node *&   tree_root;
  gsl_rng * r;
  Compare   cmp;
 
  void init(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));
  }
 
public:
 
  void set_seed(const unsigned long seed) noexcept { gsl_rng_set(r, seed); }
 
  Compare & key_comp() noexcept { return cmp; }
 
  Compare & get_compare() noexcept { return key_comp(); }
 
  Gen_Treap_Rk(const unsigned long seed, Compare __cmp = Compare())
    : head_ptr(&head), tree_root(RLINK(head_ptr)), r(nullptr), cmp(__cmp)
  {
    init(seed);
  }
 
  Gen_Treap_Rk(Compare __cmp = Compare()) : Gen_Treap_Rk(time(nullptr), __cmp)
  {
    // empty
  }
 
  ~Gen_Treap_Rk()
  {
    if (r != nullptr)
      gsl_rng_free(r);
  }
 
  void swap(Gen_Treap_Rk & tree) noexcept
  {
    std::swap(tree_root, tree.tree_root);
    std::swap(cmp, tree.cmp);
    std::swap(r, tree.r);
  }
 
  Node *& getRoot() noexcept { return tree_root; }
 
  Node * getRoot() const noexcept { return tree_root; }
 
  Node * search(const Key & key) const noexcept
  {
    Node* ret_val = searchInBinTree(tree_root, key, cmp);
    return ret_val == Node::NullPtr ? nullptr : ret_val;
  }
 
private:
 
  bool insert(Node *& root, Node * p) noexcept
  {
    if (root == Node::NullPtr)
      {
        root = p;
        return true;
      }
 
    const Key & pk = KEY(p);
    const Key & rk = KEY(root);
    if (cmp(pk, rk))
      {
        if (insert(LLINK(root), p))
          {
            ++COUNT(root);
            if (PRIO(LLINK(root)) < PRIO(root) )
              root = rotate_to_right_xt(root);
 
            return true;
          }
      }
    else if (cmp(rk, pk))
      {
        if (insert(RLINK(root), p))
          {
            ++COUNT(root);
            if (PRIO(RLINK(root)) < PRIO(root) )
              root = rotate_to_left_xt(root);
 
            return true;
          }
      }
 
    return false;
  }
 
  // Search or insert p. Return p if KEY(p) is not in the tree;
  // otherwise, it returns a pointer to a node containing KEY(p)
  Node * search_or_insert(Node *& root, Node * p) noexcept
  {
    if (root == Node::NullPtr)
      return root = p;
 
    const Key & pk = KEY(p);
    const Key & rk = KEY(root);
    if (cmp(pk, rk))
      {
        Node * ret = search_or_insert(LLINK(root), p);
        if (ret == p) // insertion done?
          { // yes ==> increase counter and perhaps rotate
            ++COUNT(root);
            if (PRIO(LLINK(root)) < PRIO(root))
              root = rotate_to_right_xt(root);
 
            assert(PRIO(root) <= PRIO(LLINK(root)) and
                   PRIO(root) <= PRIO(LLINK(root)));
          }
 
        return ret;
      }
    if (cmp(rk, pk))
      {
        Node * ret = search_or_insert(RLINK(root), p);
        if (ret == p) // insertion done?
          { // yes ==> increase counter and perhaps rotate
            ++COUNT(root);
            if (PRIO(RLINK(root)) < PRIO(root))
              root = rotate_to_left_xt(root);
 
            assert(PRIO(root) <= PRIO(LLINK(root)) and
                   PRIO(root) <= PRIO(LLINK(root)));
          }
 
        return ret;
      }
 
    assert(PRIO(root) <= PRIO(LLINK(root)) and PRIO(root) <= PRIO(LLINK(root)));
 
    return root;
  }
 
  // Return p; root could be modified
  Node * insert_dup(Node *& root, Node * p) noexcept
  {
    if (root == Node::NullPtr)
      return root = p;
 
    const Key & pk = KEY(p);
    const Key & rk = KEY(root);
    if (cmp(pk, rk))
      {
        insert_dup(LLINK(root), p);
        ++COUNT(root);
        if (PRIO(LLINK(root)) < PRIO(root))
          root = rotate_to_right_xt(root);
      }
    else
      {
        insert_dup(RLINK(root), p);
        ++COUNT(root);
        if (PRIO(RLINK(root)) < PRIO(root))
          root = rotate_to_left_xt(root);
      }
 
    return p;
  }
 
public:
 
  Node * insert(Node * p) noexcept
  {
    assert(p != Node::NullPtr);
 
    PRIO(p) = gsl_rng_get(r);
 
    return insert(tree_root, p) ? p : nullptr;
  }
 
  Node * insert_dup(Node * p) noexcept
  {
    assert(p != Node::NullPtr);
 
    PRIO(p) = gsl_rng_get(r);
 
    return insert_dup(tree_root, p);
  }
 
  Node * search_or_insert(Node * p) noexcept
  {
    assert(p != Node::NullPtr);
 
    PRIO(p) = gsl_rng_get(r);
 
    return search_or_insert(tree_root, p);
  }
 
  bool verify() const { return is_treap(tree_root); }
 
private:
 
  static Node * join_exclusive(Node * t1, Node * t2) noexcept
  {
    if (t1 == Node::NullPtr)
      return t2;
 
    if (t2 == Node::NullPtr)
      return t1;
 
    if (PRIO(t1) < PRIO(t2))
      {
        COUNT(t1) += COUNT(t2);
        RLINK(t1) = join_exclusive(RLINK(t1), t2);
        return t1;
      }
    COUNT(t2) += COUNT(t1);
    LLINK(t2) = join_exclusive(t1, LLINK(t2) );
    return t2;
  }
 
  Node * remove(Node *& root, const Key & key) noexcept
  {
    if (root == Node::NullPtr)
      return Node::NullPtr;
 
    Node * ret_val;
    const Key & rk = KEY(root);
    if (cmp(key, rk))
      ret_val = remove(LLINK(root), key);
    else if (cmp(rk, key))
      ret_val = remove(RLINK(root), key);
    else
      {
        ret_val = root;
        root = join_exclusive(LLINK(root), RLINK(root) );
 
        return ret_val;
      }
 
    if (ret_val == Node::NullPtr)
      return Node::NullPtr;
 
    --COUNT(root);
 
    return ret_val;
  }
 
public:
 
  Node * remove(const Key & key) noexcept
  {
    Node * ret_val = remove(tree_root, key);
    if (ret_val == Node::NullPtr)
      return nullptr;
 
    ret_val->reset();
 
    return ret_val;
  }
 
  Node * remove(const size_t beg, const size_t end)
  {
    ah_range_error_if(beg > end or end > COUNT(tree_root)) << "remove of TreapRk out of range";
 
    Node * before_beg, * after_end, * aux;
 
    Node * ret_val = tree_root;
 
    split_pos_rec(ret_val, end + 1, aux, after_end);
    split_pos_rec(aux, beg, before_beg, ret_val);
 
    tree_root = join_exclusive(before_beg, after_end);
 
    return ret_val;
  }
 
private:
 
  static Node * remove_pos(Node *& root, const size_t pos) noexcept
  {
    if (pos == COUNT(LLINK(root)))
      {
        Node * ret_val = root;
        root = join_exclusive(LLINK(ret_val), RLINK(ret_val));
        return ret_val;
      }
 
    --COUNT(root);
    if (pos < COUNT(LLINK(root)))
      return remove_pos(LLINK(root), pos);
    return remove_pos(RLINK(root), pos - COUNT(LLINK(root)) - 1);
  }
 
public:
 
  Node * remove_pos(const size_t pos)
  {
    ah_out_of_range_error_if(pos >= COUNT(tree_root)) << "infix position out of range";
 
    return remove_pos(tree_root, pos);
  }
 
  Node * select(const size_t i) const
  {
    return Aleph::select(tree_root, i);
  }
 
  size_t size() const noexcept { return COUNT(tree_root); }
 
  bool is_empty() const noexcept { return tree_root == Node::NullPtr; }
 
  std::pair<int, Node*> position(const Key & key) const noexcept
  {
    std::pair<int, Node*> ret_val;
 
    ret_val.first = BinTreeXt_Operation<Node, Compare>(cmp).
      inorder_position(tree_root, key, ret_val.second);
 
    return ret_val;
  }
 
  std::pair<int, Node*> find_position(const Key & key) const noexcept
  {
    std::pair<int, Node*> r(-2, nullptr);
 
    r.first = BinTreeXt_Operation <Node, Compare>(cmp) .
      find_position(tree_root, key, r.second);
 
    return r;
  }
 
  bool split_key(const Key & key, Gen_Treap_Rk & t1, Gen_Treap_Rk & t2) noexcept
  {
    return split_key_rec_xt(tree_root, key, t1.getRoot(), t2.getRoot());
  }
 
  void
  split_key_dup(const Key & key, Gen_Treap_Rk & t1, Gen_Treap_Rk & t2) noexcept
  {
    split_key_dup_rec_xt(tree_root, key, t1.getRoot(), t2.getRoot());
  }
 
  void split_pos(size_t pos, Gen_Treap_Rk & t1, Gen_Treap_Rk & t2)
  {
    split_pos_rec(tree_root, pos, t1.getRoot(), t2.getRoot());
  }
 
private:
 
  void join_dup(Node *& t1, Node * t2) noexcept
  {
    if (t2 == Node::NullPtr)
      return;
 
    Node * l = LLINK(t2), * r = RLINK(t2);
    t2->reset();
    insert_dup(t1, t2);  // insert_dup modifies t1 by reference
    join_dup(t1, l);
    join_dup(t1, r);
  }
 
  void join(Node *& t1, Node * t2, Node *& dup) noexcept
  {
    if (t2 == Node::NullPtr)
      return;
 
    Node * l = LLINK(t2), * r = RLINK(t2);
    t2->reset();
  ins:
    const bool inserted = insert(t1, t2);
    if (not inserted)
      {
        Node * removed = remove(t1, KEY(t2));
        removed->reset();
        insert_dup(dup, removed);
        goto ins;
      }
    join(t1, l, dup);
    join(t1, r, dup);
  }
 
public:
 
  void join(Gen_Treap_Rk & t, Gen_Treap_Rk & dup) noexcept
  {
    join(tree_root, t.tree_root, dup.tree_root);
    t.tree_root = Node::NullPtr;
  }
 
  void join_dup(Gen_Treap_Rk & t) noexcept
  {
    join_dup(tree_root, t.tree_root);
    t.tree_root = Node::NullPtr;
  }
 
  void join_exclusive(Gen_Treap_Rk & t) noexcept
  {
    tree_root = join_exclusive(tree_root, t.tree_root);
    t.tree_root = Node::NullPtr;
  }
 
  class Iterator
  {
  protected:
 
    mutable Gen_Treap_Rk * tree_ptr;
    mutable Node *         curr;
    mutable int            curr_pos;
 
    static constexpr int Pos_Not_Current     = -1;
    static constexpr int Pos_Empty_Container = -2;
    static constexpr int Pos_Not_Updated     = -3;
 
  private:
 
    bool is_container_empty() const noexcept
    {
      return COUNT(tree_ptr->getRoot()) == 0;
    }
 
    bool pos_updated() const noexcept
    {
      return curr_pos != Pos_Not_Updated;
    }
 
    bool curr_updated() const noexcept
    {
      return curr != nullptr;
    }
 
    bool is_updated() const noexcept
    {
      return pos_updated() and curr_updated();
    }
 
    void update_pos() const noexcept
    {
      assert(curr != nullptr);
 
      curr_pos = BinTreeXt_Operation<Node, Compare>(tree_ptr->cmp).
        inorder_position(tree_ptr->getRoot(), KEY(curr), curr);
    }
 
    void update_curr() const noexcept
    {
      assert(curr_pos != Pos_Not_Updated);
 
      if (curr_pos == Pos_Empty_Container or curr_pos == Pos_Not_Current or
          curr_pos == COUNT(tree_ptr->getRoot()))
        return;
 
      curr = Aleph::select(tree_ptr->getRoot(), curr_pos);
    }
 
  public:
 
    Iterator() noexcept
    : tree_ptr(nullptr), curr(nullptr), curr_pos(Pos_Not_Current)
    {
      /* empty */
    }
 
    Iterator(const Gen_Treap_Rk & __tree) noexcept
      : tree_ptr(&const_cast<Gen_Treap_Rk&>(__tree)), curr(nullptr)
    {
      curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
    }
 
    Iterator(const Gen_Treap_Rk & __tree, Node * __curr) noexcept
      : tree_ptr(&const_cast<Gen_Treap_Rk&>(__tree)),
        curr(__curr), curr_pos(Pos_Not_Updated)
    {
      // empty
    }
 
    Iterator(const Gen_Treap_Rk & __tree, const size_t pos) noexcept
      : tree_ptr(&const_cast<Gen_Treap_Rk&>(__tree)),
        curr(nullptr), curr_pos(pos)
    {
      // empty
    }
 
    Iterator(const Iterator & itor) noexcept
      : tree_ptr(itor.tree_ptr), curr(itor.curr), curr_pos(itor.curr_pos)
    {
      // Empty
    }
 
    Iterator & operator = (const Iterator & itor) noexcept
    {
      if (this == &itor)
        return *this;
 
      tree_ptr = itor.tree_ptr;
      curr = itor.curr;
      curr_pos = itor.curr_pos;
 
      return *this;
    }
 
    void reset_first() noexcept
    {
      curr = nullptr;
      curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
    }
 
    void reset_last() noexcept
    {
      curr = nullptr;
      curr_pos = (is_container_empty() ? Pos_Empty_Container :
                  COUNT(tree_ptr->getRoot()) - 1);
    }
 
    void end() noexcept
    {
      put_itor_at_the_end(*this);
    }
 
    void reset_to_key(const Key & key) noexcept
    {
      std::pair<int, Node*> p = tree_ptr->find_position(key);
      curr_pos = p.first;
    }
 
    void reset_to_node(Node * node) noexcept
    {
      curr = node;
      curr_pos = -2;
    }
 
    void reset_to_pos(const size_t pos) noexcept
    {
      curr = nullptr;
      curr_pos = pos;
    }
 
    Node * get_curr_ne() const noexcept
    {
      if (not curr_updated())
        update_curr();
 
      return curr;
    }
 
    Node * get_curr() const noexcept
    {
      return get_curr_ne();
    }
 
    size_t get_current_position() const
    {
      if (not pos_updated())
        update_pos();
 
      ah_range_error_if(curr_pos < -1) << "TreapRk iterator has not current";
 
      ah_range_error_if(curr_pos > COUNT(tree_ptr->getRoot())) << "TreapRk iterator has not current";
 
      return curr_pos;
    }
 
    size_t get_pos() const { return get_current_position(); }
 
    bool has_curr() const noexcept
    {
      if (not pos_updated())
        update_pos();
 
      return curr_pos >= 0 and curr_pos < COUNT(tree_ptr->getRoot());
    }
 
    void prev()
    {
      ah_underflow_error_if(not has_curr()) << "TreapRk iterator has not current";
 
      --curr_pos;
      curr = nullptr;
    }
 
    void next_ne() noexcept
    {
      ++curr_pos;
      curr = nullptr;
    }
 
    void next()
    {
      ah_underflow_error_if(not has_curr()) << "TreapRk iterator has not current";
      next_ne();
    }
 
    Node * del()
    {
      ah_underflow_error_if(not has_curr()) << "TreapRk iterator has not current";
 
      if (not curr_updated())
        update_curr();
 
      Node * ret_val = tree_ptr->remove(KEY(curr) );
 
      curr = nullptr;
 
      return ret_val;
    }
 
    bool operator == (const Iterator & itor) const noexcept
    {
      if (is_container_empty() and itor.is_container_empty())
        return true;
 
      if (pos_updated() and itor.pos_updated())
        return curr_pos == itor.curr_pos;
 
      if (curr_updated() and itor.curr_updated())
        return curr == itor.curr;
 
      if (not pos_updated())
        {
          update_pos();
          return curr_pos == itor.curr_pos;
        }
 
      itor.update_pos();
 
      return curr_pos == itor.curr_pos;
    }
 
    bool operator != (const Iterator & itor) const
    {
      return not (*this == itor);
    }
 
    bool verify(Gen_Treap_Rk * r) const noexcept
    {
      return tree_ptr->getRoot() == r->getRoot();
    }
 
    bool verify(const Iterator & it) const noexcept
    {
      return tree_ptr->getRoot() == it.tree_ptr->getRoot();
    }
  }; // end class Iterator
};
 
    template <typename Key, class Compare = Aleph::less<Key>>
struct Treap_Rk : public Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>
{
  using Base = Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>;
  using Base::Base;
};
 
    template <typename Key, class Compare = Aleph::less<Key>>
struct Treap_Rk_Vtl : public Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>
{
  using Base = Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>;
  using Base::Base;
};
 
 
} // end namespace Aleph
 
# endif // TPL_TREAPRK_H