tpl_treap.H

# ifndef TPL_TREAP_H
# define TPL_TREAP_H

# include <gsl/gsl_rng.h> 
# include <ahFunction.H>
# include <treapNode.H>
# include <tpl_binTreeOps.H>

using namespace Aleph;

namespace Aleph
{

  template <template <typename> class NodeType, typename Key, class Compare>
class Gen_Treap
{
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:

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

  Compare & key_comp() { return cmp; }

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

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

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

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

  gsl_rng * gsl_rng_object() { return 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:

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

    Node * insertion_result = NULL;
    if (cmp(KEY(p), KEY(root))) 
      {
        insertion_result = insert(LLINK(root), p);
        if (insertion_result == Node::NullPtr) 
          return Node::NullPtr;

        LLINK(root) = insertion_result;
        if (PRIO(insertion_result) < PRIO(root))
          return rotate_to_right(root);
        else
          return root;
      }
    else if (cmp(KEY(root), KEY(p)))
      {
        insertion_result = insert(RLINK(root), p);
        if (insertion_result == Node::NullPtr) 
          return Node::NullPtr;

        RLINK(root) = insertion_result;
        if (PRIO(insertion_result) < PRIO(root))
          return rotate_to_left(root);
        else
          return root;
      }

    return Node::NullPtr;
  }

     // 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 ==> eventualmente reequilibrar
          if (PRIO(LLINK(root)) < PRIO(root))
            root = rotate_to_right (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 ==> eventualmente reequilibrar
          if (PRIO(RLINK(root)) < PRIO(root))
            root = rotate_to_left (root);
            
        return ret;
      }

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

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

    if (cmp(KEY(p), KEY(root))) 
      {
        Node * result = LLINK(root) = insert_dup(LLINK(root), p);
        if (PRIO(result) < PRIO(root))
          return rotate_to_right(root);
        else
          return root;
      }

    Node * result = RLINK(root) = insert_dup(RLINK(root), p);

    if (PRIO(result) < PRIO(root))
      return rotate_to_left(root);
    else
      return root;
  }

  public:

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

    PRIO(p)       = gsl_rng_get(r); // selección aleatoria de prioridad
    Node * result = insert(tree_root, p);
    if (result == Node::NullPtr) 
      return NULL;

    tree_root = result;

    return p;  
  }

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

    PRIO(p) = gsl_rng_get(r); // selección aleatoria de prioridad
    
    return search_or_insert(tree_root, p);  
  }

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

    PRIO(p)   = gsl_rng_get(r); // selección aleatoria de prioridad
    tree_root = insert_dup(tree_root, p);

    return p;  
  }

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

  Node * remove(const Key & key)
  {
    Node ** pp = &RLINK(head_ptr);
    Node * p   = tree_root;

        // descender buscando la clave
    while (p != Node::NullPtr)
      if (cmp(key, KEY(p)))
        {
          pp = &LLINK(p);
          p  = LLINK(p);
        }
      else if (cmp(KEY(p), key))
        {
          pp = &RLINK(p);
          p  = RLINK(p);
        }
      else
        break; // encontrada!

    if (p == Node::NullPtr) 
      return NULL; // clave no fue encontrada

        // rotar p hasta que devenga hoja
    while (not (LLINK(p) == Node::NullPtr and RLINK(p) == Node::NullPtr))
      if (PRIO(LLINK(p)) < PRIO(RLINK(p)))
        {
          *pp = rotate_to_right(p);
          pp  = &RLINK(*pp);
        }
      else
        {
          *pp = rotate_to_left(p);
          pp  = &LLINK(*pp);
        }

    *pp = Node::NullPtr;

    p->reset();

    return p;
  } 
};

    template <typename Key, class Compare = Aleph::less<Key>>
class Treap : public Gen_Treap<TreapNode, Key, Compare> 
{
public:

  Treap(unsigned int seed, Compare && cmp = Compare()) 
    : Gen_Treap<TreapNode, Key, Compare>(seed, std::move(cmp))
  {
    // empty
  }

  Treap(Compare && cmp = Compare()) 
    : Gen_Treap<TreapNode, Key, Compare>(time(NULL), std::move(cmp))
  {
    // empty
  }

  Treap(unsigned int seed, Compare & cmp) 
    : Gen_Treap<TreapNode, Key, Compare>(seed, cmp)
  {
    // empty
  }

  Treap(Compare & cmp) 
    : Gen_Treap<TreapNode, Key, Compare>(time(NULL), cmp)
  {
    // empty
  }
};

    template <typename Key, class Compare = Aleph::less<Key>>
class Treap_Vtl : public Gen_Treap<TreapNodeVtl, Key, Compare>
{
public:

  Treap_Vtl(unsigned int seed, Compare && cmp = Compare()) 
    : Gen_Treap<TreapNodeVtl, Key, Compare>(seed, std::move(cmp))
  {
    // empty
  }

  Treap_Vtl(Compare && cmp = Compare()) 
    : Gen_Treap<TreapNodeVtl, Key, Compare>(time(NULL), std::move(cmp))
  {
    // empty
  }

  Treap_Vtl(unsigned int seed, Compare & cmp) 
    : Gen_Treap<TreapNodeVtl, Key, Compare>(seed, cmp)
  {
    // empty
  }

  Treap_Vtl(Compare & cmp) 
    : Gen_Treap<TreapNodeVtl, Key, Compare>(time(NULL), cmp)
  {
    // empty
  }
};


} // end namespace Aleph
# endif // TPL_TREAP_H