tpl_rand_tree.H

# ifndef TPL_RAND_TREE_H
# define TPL_RAND_TREE_H

# include <limits.h>
# include <gsl/gsl_rng.h>
# include <ahUtils.H>
# include <ahFunction.H>
# include <tpl_randNode.H>
# include <tpl_binTreeOps.H>

using namespace Aleph;

namespace Aleph { 

  template <template <typename> class NodeType, typename Key, class Compare>
class Gen_Rand_Tree
{
public:

  typedef NodeType<Key> Node;

private:

  Node *    tree_root; 
  gsl_rng * r;
  Compare & cmp;

  Node * random_insert(Node * root, Node * p)
  {
    const long & n = COUNT(root); 
    const size_t rn = gsl_rng_uniform_int(r, n + 1);
    if (rn == n) // ¿Gana p el sorteo de ser raíz?
      return BinTreeXt_Operation<Node, Compare>(cmp).insert_root(root, p);

    Node * result;
    if (cmp(KEY(p), KEY(root))) // KEY(p) < KEY(root) ?
      {     // sí ==> insertar en árbol izquierdo
        result = random_insert(LLINK(root), p); 
        if (result != Node::NullPtr) // ¿hubo inserción?
          {    // si ==> actualizar rama y contadores
            LLINK(root) = result;
            ++COUNT(root); 

            return root;
          }
      }
    else if (cmp(KEY(root), KEY(p))) // KEY(p) > KEY(root) ?
      {     // insertar en árbol derecho
        result = random_insert(RLINK(root), p); 
        if (result != Node::NullPtr) // ¿hubo inserción?
          {    // si ==> actualizar rama y contadores
            RLINK(root) = result;
            ++COUNT(root); 

            return root;
          }
      }

    return Node::NullPtr; // clave duplicada ==> no hay inserción
  }

  Node * random_insert_dup(Node * root, Node * p)
  {
    const long & n = COUNT(root); 
    const size_t rn = gsl_rng_uniform_int(r, n + 1);
    if (rn == n) // ¿Gana p el sorteo de ser raíz?
      return BinTreeXt_Operation<Node, Compare>(cmp).insert_dup_root(root, p); 

    if (cmp(KEY(p), KEY(root))) // KEY(p) < KEY(root) ?
      LLINK(root) = random_insert_dup(LLINK(root), p); 
    else
      RLINK(root) = random_insert_dup(RLINK(root), p); 
      
    ++COUNT(root); 

    return root;
  }

  Gen_Rand_Tree& operator = (const Gen_Rand_Tree&);

  void init(unsigned int seed)
  {
    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(); }


  gsl_rng * gsl_rng_object() { return r;}

  Gen_Rand_Tree(unsigned int seed, Compare && __cmp) 
    : tree_root(Node::NullPtr), r(NULL), cmp(__cmp)
  {
    init(seed);
  }

  Gen_Rand_Tree(unsigned int seed, Compare & __cmp) 
    : tree_root(Node::NullPtr), r(NULL), cmp(__cmp)
  {
    init(seed);
  }

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


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

  Node * insert(Node * p)
  {

    I(p != Node::NullPtr);
    I((LLINK(p) == Node::NullPtr) and (RLINK(p) == Node::NullPtr));
    I(COUNT(p) == 1);

    Node * result = random_insert(tree_root, p);
    if (result == Node::NullPtr) 
      return NULL;

    return tree_root = result;
  }

  Node * insert_dup(Node * p)
  {
    I(p != Node::NullPtr);
    I((LLINK(p) == Node::NullPtr) and (RLINK(p) == Node::NullPtr));
    I(COUNT(p) == 1);

    return tree_root = random_insert_dup(tree_root, p);
  }

  Node * random_join_exclusive(Node * tl, Node * tr)
  {
    if (tl == Node::NullPtr) 
      return tr;

    if (tr == Node::NullPtr) 
      return tl;

    const size_t & m = COUNT(tl);
    const size_t & n = COUNT(tr);
    const size_t rn = 1 + gsl_rng_uniform_int(r, m + n);  
    if (rn <= m) 
      {    // rama izquierda gana sorteo
        COUNT(tl) += COUNT(tr);
        RLINK(tl) = random_join_exclusive(RLINK(tl), tr);

        return tl;
      }
    else 
      {
        COUNT(tr) += COUNT(tl);
        LLINK(tr) = random_join_exclusive(tl, LLINK(tr));

        return tr;
      }
  }

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

    Node * ret_val;
    if (cmp(key, KEY(root)))
      {
        ret_val = random_remove(LLINK(root), key);
        if (ret_val != Node::NullPtr)
          COUNT(root)--;

        return ret_val;
      }
    else if (cmp(KEY(root), key))
      {
        ret_val = random_remove(RLINK(root), key);
        if (ret_val != Node::NullPtr)
          COUNT(root)--;

        return ret_val;
      }

        // clave encontrada
    ret_val = root;
    root = random_join_exclusive(LLINK(root), RLINK(root));
    ret_val->reset();

    return ret_val;
  }
  Node * remove(const Key & key)
  {
    Node * ret_val = random_remove(tree_root, key);

    return ret_val != Node::NullPtr ? ret_val : NULL;
  }
  Node * search(const Key & key)
  {
    Node * retVal = searchInBinTree<Node, Compare>(tree_root, key, cmp);

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

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

    Node * result = search(KEY(p));
    if (result != NULL)
      return result;

    tree_root = random_insert(tree_root, p);

    return p;
  }

  bool verify() const
  {
    return check_rank_tree(tree_root);
  }

  Node *& getRoot() { return tree_root; }

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

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

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

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

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

  void join(Gen_Rand_Tree & t, Gen_Rand_Tree & 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_Rand_Tree & t)
  {
    tree_root = random_join_exclusive(tree_root, t.tree_root);    
  }
};

    template <typename Key, class Compare = Aleph::less<Key>>
class Rand_Tree : public Gen_Rand_Tree<RandNode, Key, Compare> 
{
public:

  Rand_Tree(unsigned int seed, Compare && cmp = Compare()) 
    : Gen_Rand_Tree<RandNode, Key, Compare>(seed, std::move(cmp))
  {
    // empty
  }

  Rand_Tree(Compare && cmp = Compare()) 
    : Gen_Rand_Tree<RandNode, Key, Compare>(time(NULL), std::move(cmp))
  {
    // empty
  }

  Rand_Tree(Compare & cmp) 
    : Gen_Rand_Tree<RandNode, Key, Compare>(time(NULL), cmp)
  {
    // empty
  }

  Rand_Tree(unsigned int seed, Compare & cmp) 
    : Gen_Rand_Tree<RandNode, Key, Compare>(seed, cmp)
  {
    // empty
  }
};

    template <typename Key, class Compare = Aleph::less<Key>>
class Rand_Tree_Vtl : public Gen_Rand_Tree<RandNodeVtl,Key,Compare>
{
public:

  Rand_Tree_Vtl(unsigned int seed, Compare && cmp = Compare()) 
    : Gen_Rand_Tree<RandNodeVtl, Key, Compare>(seed, std::move(cmp))
  {
    // empty
  }

  Rand_Tree_Vtl(Compare && cmp = Compare()) 
    : Gen_Rand_Tree<RandNodeVtl, Key, Compare>(time(NULL), std::move(cmp))
  {
    // empty
  }

  Rand_Tree_Vtl(unsigned int seed, Compare & cmp) 
    : Gen_Rand_Tree<RandNodeVtl, Key, Compare>(seed, cmp)
  {
    // empty
  }

  Rand_Tree_Vtl(Compare & cmp) 
    : Gen_Rand_Tree<RandNodeVtl, Key, Compare>(time(NULL), std::move(cmp))
  {
    // empty
  }
};


} // end namespace Aleph

# endif // TPL_RAND_TREE_H