tpl_treapRk.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/

# ifndef TPL_TREAPRK_H
# define TPL_TREAPRK_H

# include <gsl/gsl_rng.h>
# include <ahFunction.H>
# include <tpl_binNodeUtils.H>
# include <tpl_binNodeXt.H>
# include <ran_array.h>
# include <treapNode.H>

using namespace Aleph;

namespace Aleph {

class TreapRkNode_Data
{
  long priority; 

  long count;

public:

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

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

  long & getPriority () { return priority; }

  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;
  Compare   cmp;
  gsl_rng * r;

public:

  Gen_Treap_Rk () : head_ptr(&head), tree_root(RLINK(head_ptr)), r(NULL)
  {
    PRIO (head_ptr) = Min_Priority;

      r = gsl_rng_alloc (gsl_rng_mt19937);

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

      gsl_rng_set(r, time(NULL) % gsl_rng_max(r));
  }

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

  void swap (Gen_Treap_Rk & tree)
  {
    Aleph::swap (LLINK (head_ptr), LLINK (tree.head_ptr) );
    Aleph::swap (RLINK (head_ptr), RLINK (tree.head_ptr) );
    Aleph::swap (head_ptr, tree.head_ptr);
    Aleph::swap (tree_root, tree.tree_root);
  }

  Node *& getRoot () { return tree_root; }

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

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

private:

  Node * insert (Node * root, Node * p) 
  {
    if (root == Node::NullPtr)
      return p;

    Node * insertion_result;

    if (cmp (KEY (p), KEY (root) ) )
      {
        insertion_result = insert (LLINK (root), p);

        if (insertion_result == Node::NullPtr)
          return Node::NullPtr;

     ++COUNT (root);
        LLINK (root) = insertion_result;

        if (PRIO (insertion_result) < PRIO (root) )
          return rotate_to_right_xt (root);

     return root;
      }
    else if (cmp (KEY (root), KEY (p) ) )
      {
        insertion_result = insert (RLINK (root), p);

        if (insertion_result == Node::NullPtr)
          return Node::NullPtr;

     ++COUNT (root);
        RLINK (root) = insertion_result;

        if (PRIO (insertion_result) < PRIO (root) )
          return rotate_to_left_xt (root);

     return root;
      }

    return Node::NullPtr;
  }

public:

  Node * insert (Node * p)
  {
    I (p not_eq Node::NullPtr);

    PRIO(p) = gsl_rng_get(r);

    Node * result = insert (tree_root, p);

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

    tree_root = result;

    return p;  
  }

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

  size_t position (const Key & key)
  {
    Node * p;

    const long ret_val = Aleph::inorder_position(tree_root, key, p);

    IG(KEY(p) == key, ret_val >= 0);

    return ret_val;
  }

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

  private:

    bool pos_updated () const
    {
      return curr_pos not_eq -2;
    }

    bool curr_updated () const
    {
      return curr not_eq NULL;
    }

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

    void update_pos () const
    {
      I (curr not_eq NULL);

      curr_pos = 
     Aleph::inorder_position (tree_ptr->getRoot (), KEY (curr), curr);
    }

    void update_curr () const
    {
      I (curr_pos not_eq -2);

      if (curr_pos == -1 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(-2)
    {
      /* empty */ 
    }

    Iterator (Gen_Treap_Rk & __tree) 
      : tree_ptr(&__tree), curr(NULL), curr_pos(0)
    {
      // Empty
    }

    Iterator (Gen_Treap_Rk & __tree, Node * __curr)
      : tree_ptr(&__tree), curr(__curr), curr_pos(-2)
    {
      // 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 = 0;
    }

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

    void reset_to_key (const Key & key)
    {
      curr_pos = Aleph::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; 
    }

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

    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 (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>
    { /* empty */ };

    template <class Key, class Compare = Aleph::less<Key> >
class Treap_Rk_Vtl : public Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare>
    { /* empty */ };

} // end namespace Aleph

# endif // TPL_TREAPRK_H

---