tpl_treapRk.H

# 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>

using namespace Aleph;

namespace Aleph {

class TreapRkNode_Data
{
  unsigned long priority; 

  unsigned long count;

public:

  TreapRkNode_Data() : priority(Max_Priority), count(1) 
  { 
    /* empty */ 
  }

  TreapRkNode_Data(SentinelCtor) 
    : priority(Max_Priority), count(0) 
  { 
    /* empty */ 
  }

  unsigned long & getPriority() { return priority; }

  unsigned long & getCount() { return count; }

  void reset() 
  {
    priority = Max_Priority; 
    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:

  typedef NodeType<Key> Node;

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);

    if (r == NULL)
      throw std::bad_alloc();

    gsl_rng_set(r, seed % gsl_rng_max(r));
  }

public:

  Compare & key_comp() { return cmp; }

  Compare & get_compare() { return key_comp(); }

  Gen_Treap_Rk(unsigned int seed, Compare & __cmp) 
    : head_ptr(&head), tree_root(RLINK(head_ptr)), r(NULL), cmp(__cmp)
  {
    init(seed);
  }

  Gen_Treap_Rk(unsigned int seed, Compare && __cmp) 
    : head_ptr(&head), tree_root(RLINK(head_ptr)), r(NULL), cmp(__cmp)
  {
    init(seed);
  }

  ~Gen_Treap_Rk()
  {
    if (r != NULL)
      gsl_rng_free(r);
  }

  Gen_Treap_Rk(const Gen_Treap_Rk &) 
  {
    // empty
  }

  void swap(Gen_Treap_Rk & tree)
  {
    std::swap(tree_root, tree.tree_root);
    std::swap(cmp, tree.cmp);
    std::swap(r, tree.r);
  }

  Node *& getRoot() { return tree_root; }

  Node * search(const Key & key)
  {
    Node* ret_val = searchInBinTree<Node, Compare>(tree_root, key, cmp);

    return ret_val == Node::NullPtr ? NULL : ret_val;
  }

private:

  // retorna true si la clave fue insertada (si no se encuentra en el árbol)
  bool insert(Node *& root, Node * p) 
  {
    if (root == Node::NullPtr)
      {
        root = p;
        return true;
      }

    if (cmp(KEY(p), KEY(root)))
      {
        if (insert(LLINK(root), p))
          {
            ++COUNT(root);
            if (PRIO(LLINK(root)) < PRIO(root) )
              root = rotate_to_right_xt(root);

            return true;
          }
      }
    else if (cmp(KEY(root), KEY(p)))
      {
        if (insert(RLINK(root), p))
          {
            ++COUNT(root);
            if (PRIO(RLINK(root)) < PRIO(root) )
              root = rotate_to_left_xt(root);

            return true;
          }
      }

    return false;
  }

public:

  // busca o inserta p. Retorna p si KEY(p) no se encuentra dentro del
  // árbol; de lo contrario, se retorna la dirección del nodo contentivo
  // de KEY(p)
  Node * search_or_insert(Node *& root, Node * p) 
  {
    if (root == Node::NullPtr)
      return root = p;

    if (cmp(KEY(p), KEY(root)))
      {
        Node * ret = search_or_insert(LLINK(root), p);
        if (ret == p) // ¿hubo inserción?
          {     // sí la hubo ==> incrementar contadores y eventualmente
                // reequilibrar
            ++COUNT(root);
            if (PRIO(LLINK(root)) < PRIO(root))
              root = rotate_to_right_xt(root);
            
            I(PRIO(root) <= PRIO(LLINK(root)) and
              PRIO(root) <= PRIO(LLINK(root)));
          }

        return ret;
      }
    else if (cmp(KEY(root), KEY(p)))
      {
        Node * ret = search_or_insert(RLINK(root), p);
        if (ret == p) // ¿hubo inserción?
          {     // sí la hubo ==> incrementar contadores y eventualmente
                // reequilibrar
            ++COUNT(root);
            if (PRIO(RLINK(root)) < PRIO(root))
              root = rotate_to_left_xt(root);

            I(PRIO(root) <= PRIO(LLINK(root)) and
              PRIO(root) <= PRIO(LLINK(root)));
          }

        return ret;
      }

    I(PRIO(root) <= PRIO(LLINK(root)) and PRIO(root) <= PRIO(LLINK(root)));

    return root; // root contiene KEY(p)
  }

  // retorna p
  Node * insert_dup(Node *& root, Node * p) 
  {
    if (root == Node::NullPtr)
      return root = p;

    if (cmp(KEY(p), KEY(root)))
      {
        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;
  }

  Node * insert(Node * p)
  {
    I (p != Node::NullPtr);

    PRIO(p) = gsl_rng_get(r);

    return insert(tree_root, p) ? p : NULL;
  }


  Node * insert_dup(Node * p)
  {
    I(p != Node::NullPtr);

    PRIO(p) = gsl_rng_get(r);

    return insert_dup(tree_root, p);
  }

  Node * search_or_insert(Node * p)
  {
    I(p != Node::NullPtr);

    PRIO(p) = gsl_rng_get(r);

    return search_or_insert(tree_root, p);
  }

  bool verify() { return is_treap(tree_root); }

private:

  static Node * join_treaps(Node * t1, Node * t2)
  {
    if (t1 == Node::NullPtr)
      return t2;

    if (t2 == Node::NullPtr)
      return t1;

    if (PRIO(t1) < PRIO(t2) )
      {
        COUNT(t1) += COUNT(t2);
        RLINK(t1) = join_treaps(RLINK(t1), t2);
        
        return t1;
      }
    else
      {
        COUNT(t2) += COUNT(t1);
        LLINK(t2) = join_treaps(t1, LLINK(t2) );
        
        return t2;
      }
  }

  Node * remove(Node *& root, const Key & key)
  {
    if (root == Node::NullPtr)
      return Node::NullPtr;

    Node * ret_val;

    if (cmp(key, KEY(root) ))
      ret_val = remove(LLINK(root), key);
    else if (cmp(KEY(root), key))
      ret_val = remove(RLINK(root), key);
    else
      {
        ret_val = root;
        root = join_treaps(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)
  {
    Node * ret_val = remove(tree_root, key);

    if (ret_val == Node::NullPtr)
      return NULL;

    ret_val->reset();

    return ret_val;
  } 

  Node * remove(const size_t & beg, const size_t & end)
  {
    if (beg > end or end > COUNT(tree_root))
      throw std::range_error("remove of TreapRk out of range");

    Node * before_beg, * after_end;

    Node * ret_val = tree_root;

    split_pos_rec(ret_val, end + 1, ret_val, after_end);

    split_pos_rec(ret_val, beg, before_beg, ret_val);

    tree_root = join_treaps(before_beg, after_end);

    return ret_val;
  }
  
  Node * select(const size_t & i)
  {
    return Aleph::select(tree_root, i); 
  }

  size_t size() const 
  {
    return COUNT(tree_root);
  }

  bool is_empty() const 
  {
    return tree_root == Node::NullPtr; 
  }

  std::pair<int, Node*> position(const Key & key)
  {
    std::pair<int, Node*> ret_val;

    ret_val.first = BinTreeXt_Operation<Node, Compare>(cmp).
      inorder_position(tree_root, key, ret_val.second);

    IG(KEY(ret_val.second) == key, ret_val.first >= 0);

    return ret_val;
  }

  std::pair<int, Node*> find_position(const Key & key)
  {
    std::pair<int, Node*> r(-2, NULL);

    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)
  {
    return split_key_rec_xt(tree_root, key, t1, t2);
  }

  bool split_key_dup(const Key & key, Gen_Treap_Rk & t1, Gen_Treap_Rk & t2)
  {
    split_key_dup_rec_xt(tree_root, key, t1, t2);
  }

  void split_pos(size_t pos, Gen_Treap_Rk & t1, Gen_Treap_Rk & t2)
  {
    split_pos_rec(tree_root, pos, t1, t2);
  }

  void join(Gen_Treap_Rk & t, Gen_Treap_Rk & dup)
  {
    Node * l = (Node*) LLINK(t.tree_root);
    Node * r = (Node*) RLINK(t.tree_root);
    
    t.tree_root->reset();
    Node * ret = insert(t.tree_root);
    if (ret == NULL)
      dup.insert(t.tree_root);

    join(l, dup);
    join(r, dup);
  }

  void join_dup(Gen_Treap_Rk & t)
  {
    tree_root = join_treaps(tree_root, t.tree_root);    
  }

  class Iterator
  {
  protected:
    
    mutable Gen_Treap_Rk * tree_ptr; 
    mutable Node *         curr;
    mutable int            curr_pos;

    static const int Pos_Not_Current     = -1;
    static const int Pos_Empty_Container = -2;
    static const int Pos_Not_Updated     = -3;

  private:

    bool is_container_empty() const
    {
      return COUNT(tree_ptr->getRoot()) == 0;
    }

    bool pos_updated() const
    {
      return curr_pos != Pos_Not_Updated;
    }

    bool curr_updated() const
    {
      return curr != NULL;
    }

    bool is_updated() 
    {
      return pos_updated() and curr_updated();
    }

    void update_pos() const
    {
      I(curr != NULL);

      curr_pos = BinTreeXt_Operation<Node, Compare>(tree_ptr->cmp).
        inorder_position(tree_ptr->getRoot(), KEY(curr), curr);
    }

    void update_curr() const
    {
      I(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() : tree_ptr(NULL), curr(NULL), curr_pos(Pos_Not_Current)
    {
      /* empty */ 
    }

    Iterator(Gen_Treap_Rk & __tree) 
      : tree_ptr(&__tree), curr(NULL)
    {
      curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
    }

    Iterator(Gen_Treap_Rk & __tree, Node * __curr)
      : tree_ptr(&__tree), curr(__curr), curr_pos(Pos_Not_Updated)
    {
      // empty
    }

    Iterator(Gen_Treap_Rk & __tree, const size_t & pos)
      : tree_ptr(&__tree), curr(NULL), curr_pos(pos)
    {
      // empty
    }

    Iterator(const Iterator & itor)
      : tree_ptr(itor.tree_ptr), curr(itor.curr), curr_pos(itor.curr_pos)
    {
      // Empty
    }

    Iterator & operator = (const Iterator & itor)
    {
      if (this == &itor)
        return *this;

      tree_ptr = itor.tree_ptr;
      curr = itor.curr;
      curr_pos = itor.curr_pos;

      return *this;
    }

    void reset_first()
    {
      curr = NULL;
      curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
    }

    void reset_last()
    {
      curr = NULL;
      curr_pos = (is_container_empty() ? Pos_Empty_Container : 
                  COUNT(tree_ptr->getRoot()) - 1);
    }

    void reset_to_key(const Key & key)
    {
      curr_pos = BinTreeXt_Operation<Node, Compare>(tree_ptr->cmp).
        inorder_position(tree_ptr->getRoot(), key, curr);
    }

    void reset_to_node(Node * node)
    {
      curr = node;
      curr_pos = -2;
    }

    void reset_to_pos(size_t pos)
    {
      curr = NULL;
      curr_pos = pos;
    }

    Node * get_current() const
    {
      if (not curr_updated())
        update_curr();

      return curr; 
    }

    Node * get_curr() const
    {
      return get_current();
    }

    size_t get_current_position() const
      throw(std::exception, std::underflow_error, std::overflow_error)
    {
      if (not pos_updated())
        update_pos();

      if (curr_pos < -1 )
        throw std::range_error("TreapRk iterator has not current");
        
      if (curr_pos > COUNT(tree_ptr->getRoot() ) )
        throw std::range_error("TreapRk iterator has not current");

      return curr_pos;
    }

    bool has_current() const
    {
      if (not pos_updated())
        update_pos();

      return curr_pos >= 0 and curr_pos < COUNT(tree_ptr->getRoot());
    }

    bool has_curr() const
    {
      return has_current();
    }

    void prev() throw(std::exception, std::underflow_error)
    {
      if (not has_current() )
        throw std::underflow_error("TreapRk iterator has not current");

      --curr_pos;
      curr = NULL;
    }

    void next() throw(std::exception, std::overflow_error)
    {
      if (not has_current() )
        throw std::underflow_error("TreapRk iterator has not current");

      ++curr_pos;
      curr = NULL;
    }

    Node * del()
    {
      if (not has_current() )
        throw std::underflow_error("TreapRk iterator has not current");

      if (not curr_updated())
        update_curr();

      Node * ret_val = tree_ptr->remove(KEY(curr) );
      
      curr = NULL;

      return ret_val;
    }

    bool operator == (const Iterator & itor) const
    {
      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
    {
      return tree_ptr->getRoot() == r->getRoot();
    }

    bool verify(const Iterator & it) const
    {
      return tree_ptr->getRoot() == it.tree_ptr->getRoot();
    }
  }; // end class Iterator
};

    template <class Key, class Compare = Aleph::less<Key> >
class Treap_Rk : public Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>
{
public:

  Treap_Rk(unsigned int seed, Compare && cmp = Compare()) 
    : Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>(seed, std::move(cmp))
   {
     // empty
   }

  Treap_Rk(Compare && cmp = Compare()) 
    : Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>(time(NULL), std::move(cmp))
   {
     // empty
   }

  Treap_Rk(unsigned int seed, Compare & cmp) 
     : Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>(seed, cmp)
   {
     // empty
   }

  Treap_Rk(Compare & cmp) 
     : Gen_Treap_Rk<Treap_Rk_Node, Key, Compare>(time(NULL), cmp)
   {
     // empty
   }
};

    template <class Key, class Compare = Aleph::less<Key> >
class Treap_Rk_Vtl : public Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>
{
public:

  Treap_Rk_Vtl(unsigned int seed, Compare && cmp = Compare()) 
    : Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>(seed, std::move(cmp))
   {
     // empty
   }

  Treap_Rk_Vtl(Compare && cmp = Compare()) 
    : Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>(time(NULL), std::move(cmp))
   {
     // empty
   }

   Treap_Rk_Vtl(unsigned int seed, Compare & cmp) 
     : Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>(seed, cmp)
   {
     // empty
   }

  Treap_Rk_Vtl(Compare & cmp) 
    : Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>(time(NULL), cmp)
  {
    // empty
  }
};

} // end namespace Aleph

# endif // TPL_TREAPRK_H