tpl_rand_tree.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_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_binNodeUtils.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;
  Gen_Rand_Tree(const Gen_Rand_Tree&);

  Gen_Rand_Tree& operator = (const Gen_Rand_Tree&);

public:

  gsl_rng * gsl_rng_object() { return r;}
  Gen_Rand_Tree() : tree_root(Node::NullPtr), r(NULL)
  {
    r = gsl_rng_alloc (gsl_rng_mt19937);

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

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

  virtual ~Gen_Rand_Tree() 
  {
    if (r != NULL)
      gsl_rng_free(r);
  }
  Node * random_insert(Node * root, Node * node)
  {
    if (root == Node::NullPtr)
      return node;

    const long & n = COUNT(root); 

    const size_t rn = gsl_rng_uniform_int(r, n + 1);;

    if (rn == n) // ¿Gana node el sorteo de ser raíz?
      return insert_root_xt<Node, Compare> (root, node); // sí, node será raíz

    Node * result;
    if (Compare() (KEY(node), KEY(root))) // ¿insertar en árbol izquierdo?
      {
        result = random_insert(LLINK(root), node); // inserta en rama izquierda

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

        if (result != Node::NullPtr) // ¿hubo inserción?
          {    // si ==> actualizar rama y contadores
            RLINK(root) = result;
            ++COUNT(root); 
          }
      }
    else
      return Node::NullPtr; // clave duplicada ==> no hay inserción

    return root;
  }
  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;

    tree_root = result;

    return 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 (Compare() (key, KEY(root)))
      {
        ret_val = random_remove(LLINK(root), key);

        if (ret_val != Node::NullPtr)
          COUNT(root)--;

        return ret_val;
      }
    else if (Compare() (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);

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

  Node *& getRoot() { return tree_root; }

};

    template <typename Key, class Compare = Aleph::less<Key> >
class Rand_Tree : public Gen_Rand_Tree<RandNode, Key, Compare>
    { /* empty */ };

    template <typename Key, class Compare = Aleph::less<Key> >
class Rand_Tree_Vtl : public Gen_Rand_Tree<RandNodeVtl, Key, Compare>
    { /* empty */ };

} // end namespace Aleph

# endif // TPL_RAND_TREE_H 

---