tpl_binNodeUtils.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_BINNODEUTILS_H
# define TPL_BINNODEUTILS_H 

# include <ahFunction.H>
# include <ahPair.H>
# include <tpl_arrayStack.H> 
# include <tpl_arrayQueue.H>
# include <tpl_dynArray.H>
# include <tpl_dynDlist.H>
# include <tpl_binNode.H>

using namespace Aleph;
namespace Aleph {

    template <class Node> inline static
void __inorder_rec(Node *node, const int& level, int & position, 
                   void (*visitFct)(Node*, int, int))
{
  if (node == Node::NullPtr) 
    return;

  __inorder_rec(static_cast<Node*>(LLINK(node)), 
                level + 1, position, visitFct);
  (*visitFct)(node, level, position);
  ++position;
  __inorder_rec(static_cast<Node*>(RLINK(node)),
                level + 1, position, visitFct); 
}
    template <class Node> inline
int inOrderRec(Node * root, void (*visitFct)(Node*, int, int))
{
  int position = 0;
  
  __inorder_rec(root, 0, position, visitFct); 

  return position;
}
    template <class Node> inline static
void __preorder_rec (Node *p, const int & level, int & position,
                     void (*visitFct)(Node*, int, int))
{
  if (p == Node::NullPtr) 
    return;

  (*visitFct)(p, level, position);
  ++position;

  __preorder_rec(static_cast<Node*>(LLINK(p)), 
                 level + 1, position, visitFct);
  __preorder_rec(static_cast<Node*>(RLINK(p)), 
                 level + 1, position, visitFct);
} 

    template <class Node> inline 
int preOrderRec(Node * root, void (*visitFct)(Node*, int, int))
{
  int position = 0;
  
  __preorder_rec(root, 0, position, visitFct); 

  return position;
}

    template <class Node> inline static
void __postorder_rec(Node *node, const int & level, int & position, 
                     void (*visitFct)(Node*, int, int))
{
  if (node == Node::NullPtr) 
    return;

  __postorder_rec(static_cast<Node*>(LLINK(node)), 
                  level + 1, position, visitFct);
  __postorder_rec(static_cast<Node*>(RLINK(node)), 
                  level + 1, position, visitFct); 

  (*visitFct)(node, level, position);
  ++position;
}

    template <class Node> inline
int postOrderRec(Node * root, void (*visitFct)(Node*, int, int))
{
  int position = 0;
  
  __postorder_rec(root, 0, position, visitFct); 

  return position;
}
    template <class Node> inline
size_t simple_preOrderStack(Node * node, void (*visitFct)(Node *, int, int))
{
  if (node == Node::NullPtr) 
    return 0;

  ArrayStack<Node *, Node::MaxHeight> stack;

  stack.push(node); 

  Node * p;

  size_t count = 0;

  while (not stack.is_empty())
    {
      p = stack.pop();

      (*visitFct) (p, stack.size(), count++); 

      if (RLINK(p) != Node::NullPtr)
        stack.push(RLINK(p));

      if (LLINK(p) != Node::NullPtr)
        stack.push(LLINK(p));
    }

  return count;
} 
    template <class Node> inline
size_t preOrderStack(Node * node, void (*visitFct)(Node *, int, int))
{
  if (node == Node::NullPtr) 
    return 0;

  ArrayStack<Node *, Node::MaxHeight> stack;
  Node *p = node;

  size_t count = 0;

  while (true)
    {
      (*visitFct)(p, stack.size(), count++);

      if (LLINK(p) != Node::NullPtr)
        {
          stack.push(p); // push porque p y RLINK(p) faltan por visitarse
          p = LLINK(p);  // avanzar a la izquierda

          continue; // ir a visitar raíz rama izquierda
        }
      
      while (true) 
        {
          if (RLINK(p) != Node::NullPtr)
            {
              p = RLINK(p); // avanzar a la derecha
              break;        // ir a visitar raíz rama derecha
            }

          if (stack.is_empty()) 
            return count; // fin

          p = stack.pop(); // sacar para ir a rama derecha
        }
    }
}
    template <class Node> inline
size_t inOrderStack(Node * node, void (*visitFct)(Node *, int, int))
{
  if (node == Node::NullPtr) 
    return 0;

  ArrayStack<Node *, Node::MaxHeight> stack;
  Node *p = node;

  size_t count = 0;

  while (true)
    {
      if (LLINK(p) != Node::NullPtr)
        {
          stack.push(p); // push porque p y RLINK(p) faltan por visitarse
          p = LLINK(p);  // avanzar a la izquierda

          continue; // continuar bajando por la rama izquierda
        }
      while (true)
        {
          (*visitFct)(p, stack.size(), count++);

          if (RLINK(p) != Node::NullPtr)
            {
              p = RLINK(p); // avanzar a la derecha
              break;        // ir a visitar raíz rama derecha
            }

          if (stack.is_empty()) 
            return count;

          p = stack.pop(); // sacar para ir a rama derecha
        }
    }
}
    template <class Node> inline
size_t postOrderStack(Node * root, void (*visitFct)(Node *, int, int))
{    
  if (root == Node::NullPtr) 
    return 0;

  typedef Aleph::pair<Node*, char> Postorder_Pair;
  ArrayStack<Postorder_Pair, Node::MaxHeight> stack;

  Postorder_Pair __pair;

  Node *& p   = __pair.first  = root;
  char & side = __pair.second = 'i';

  stack.push(__pair);

  size_t count = 0;

  while (not stack.is_empty())
    {
      __pair = stack.pop();

      switch (side)
        {
        case 'i': 
          if (LLINK(p) != Node::NullPtr)
            stack.push(Postorder_Pair(LLINK(p), 'i'));

          stack.push(Postorder_Pair(p, 'l'));

          break;
        case 'l':
          if (RLINK(p) != Node::NullPtr)
            stack.push(Postorder_Pair(RLINK(p), 'i'));

          stack.push(Postorder_Pair(p, 'r'));
          
          break;
        case 'r':
          (*visitFct) (p, stack.size(), count++); 

          break;
        }
    }

  return count;
}
    template <class Node> inline
size_t compute_cardinality_rec(Node * node)
{
  if (node == Node::NullPtr) 
    return 0;

  return (compute_cardinality_rec(LLINK(node)) + 1 + 
          compute_cardinality_rec(RLINK(node)));
}
    template <class Node> inline
size_t computeHeightRec(Node * node)
{
  if (node == Node::NullPtr) 
    return 0;

  const size_t left_height  = computeHeightRec(LLINK(node));
  const size_t right_height = computeHeightRec(RLINK(node));

  return 1 + Aleph::max(left_height, right_height);
}
    template <class Node> inline 
Node * copyRec(Node * src_root) throw(std::exception, std::bad_alloc) 
{
  if (src_root == Node::NullPtr) 
    return (Node*) Node::NullPtr;

  Node * tgt_root = new Node(*src_root); 

  try 
    {
      LLINK(tgt_root) = copyRec<Node>(static_cast<Node*>(LLINK(src_root)));
      RLINK(tgt_root) = copyRec<Node>(static_cast<Node*>(RLINK(src_root)));
    }
  catch (...)
    {

      I(RLINK(tgt_root) == Node::NullPtr);

      if (LLINK(tgt_root) != Node::NullPtr) 
        destroyRec(LLINK(tgt_root)); // TODO: diff de Node*&

      delete tgt_root;

      throw;
    }

  return tgt_root;
}      
    template <class Node> inline
void destroyRec(Node * root)
{
  if (root == Node::NullPtr) 
    return;

  destroyRec(static_cast <Node*> (LLINK(root)));
  destroyRec(static_cast <Node*> (RLINK(root)));

  delete root;
}
    template <class Node> inline
bool areSimilar(Node * t1, Node * t2)
{
  if (t1 == Node::NullPtr and t2 == Node::NullPtr)
    return true;

  if (t1 == Node::NullPtr or t2 == Node::NullPtr)
    return false;
  
  return (areSimilar(LLINK(t1), LLINK(t2)) and
          areSimilar(RLINK(t1), RLINK(t2)));
}
    template <class Node, class Equal> inline
bool areEquivalents(Node * t1, Node * t2)
{
  if (t1 == Node::NullPtr and t2 == Node::NullPtr)
    return true;

  if (t1 == Node::NullPtr or t2 == Node::NullPtr)
    return false;
  
  if (not Equal () (KEY(t1), KEY(t2)))
    return false;

  return (areEquivalents<Node, Equal>(LLINK(t1), LLINK(t2)) and 
          areEquivalents<Node, Equal>(RLINK(t1), RLINK(t2)));
}
    template <class Node> inline
bool areEquivalents(Node * t1, Node * t2)
{
  return 
    areEquivalents<Node, Aleph::equal_to<typename Node::key_type> >(t1, t2);
}
    template <class Node> inline
void levelOrder(Node *         root, 
                void           (*visitFct)(Node*, int, bool), 
                const size_t & queue_size)
{
  if (root == Node::NullPtr)
    return;

  const size_t two_power = 
    static_cast<size_t>(std::log((float)queue_size)/std::log(2.0) + 1);

  ArrayQueue<Aleph::pair<Node*, bool> > queue(two_power); 

  queue.put(root);

  for (int pos = 0; not queue.is_empty(); pos++)
    {
      Aleph::pair<Node*, bool> pr = queue.get();

      Node *& p = pr.first;

      (*visitFct) (p, pos, pr.second);

      if (LLINK(p) != Node::NullPtr)
        queue.put(Aleph::pair <Node*, bool> (LLINK(p), true));

      if (RLINK(p) != Node::NullPtr)
        queue.put(Aleph::pair <Node*, bool> (RLINK(p), false));
    }
}
    template <template <class> class Node, typename Key> inline
Node<Key> * build_tree(DynArray<Key> & preorder, 
                       const int & l_p, const int & r_p,
                       DynArray<Key> & inorder, 
                       const int & l_i, const int & r_i)
{
  if (l_p > r_p) // ¿está vacío el recorrido?

    { // sí, retornar árbol vacío
    I(l_i > r_i);

    return Node <Key> ::NullPtr;

    }

  I(r_p - l_p == r_i - l_i); 


  Node<Key> * root = new Node <Key> (preorder[l_p]); // crear la raíz

  if (r_p == l_p) // ¿recorrido de longitud 1?
    return root; // sí ==> no hay infijo a buscar

  
  I(l_i <= r_i);

  int i = 0;
  for (int j = l_i; j <= r_i; ++j)
    if (inorder[j] == preorder[l_p])
      {
        i = j - l_i;
        break;
      }

  I(i <= r_i);


  LLINK(root) = build_tree <Node, Key> (preorder, l_p + 1, l_p + i, 
                                        inorder, l_i, l_i + (i - 1));

  RLINK(root) = build_tree <Node, Key> (preorder, l_p + i + 1, r_p,
                                        inorder, l_i + i + 1, r_i);
    
  return root;
}
    template <class Node> inline static
void __compute_nodes_in_level(Node *            root, 
                              const int &       level,
                              const int &       current_level, 
                              DynDlist<Node*> & level_list)
{
  if (root == Node::NullPtr)
    return;

  if (level == current_level)
    {
      level_list.append(root);

      return; // no vale la pena descender más
    }

  __compute_nodes_in_level(LLINK(root), level, current_level + 1, level_list);

  __compute_nodes_in_level(RLINK(root), level, current_level + 1, level_list);
}
    template <class Node> inline
void compute_nodes_in_level(Node *          root, 
                            const int &     level, 
                            DynDlist<Node*>& list)
{
  __compute_nodes_in_level(root, level, 0, list);
}
    template <class Node> inline
void inOrderThreaded(Node * root, void (*visitFct)(Node*))
{
  if (root == Node::NullPtr) 
    return;

  Node *p = root, *r = Node::NullPtr, *q;

  while (p != Node::NullPtr)
    {
      q = LLINK(p); 

      if (q == Node::NullPtr) 
        { // No hay rama izq ==> visitar p

          (*visitFct)(p);  

          r = p;          
          p = RLINK(p);   

          continue;       
        }

          // avanzar hacia el nodo más a la derecha de la rama izquierda
      while (q != r and RLINK(q) != Node::NullPtr)
        q = RLINK(q);

      if (q != r) // tiene p un predecesor? 
        { // si ==> dejar un hilo para luego subir a visitar p
          RLINK(q) = p; // Aquí se coloca el hilo
          p = LLINK(p); // Seguir bajando por la izquierda

          continue;     
        }

      (*visitFct)(p);

      RLINK (q) = Node::NullPtr; // Borrar hilo
      r = p;            
      p = RLINK(p); // avanzar a la rama derecha
    }
}
    template <class Node> inline
void preOrderThreaded(Node * node, void (*visitFct)(Node*))
{
  if (node == Node::NullPtr) 
    return;

  Node *p = node, *r = Node::NullPtr, *q;

  while (p != Node::NullPtr)
  {
    q = LLINK(p); 

    if (q == Node::NullPtr) 
      { 
        (*visitFct)(p);  

        r = p;
        p = RLINK(p);

        continue;    
      }

        // avanzar hacia el nodo más a la derecha de la rama izquierda
    while (q != r and RLINK(q) != Node::NullPtr)
      q = RLINK(q);

    if (q != r) 
      { 
        RLINK(q) = p;

        (*visitFct)(p);

        p = LLINK(p);

        continue;    
      }

    RLINK(q) = Node::NullPtr; /* delete thread */
    r = p;                  
    p = RLINK(p);       /* advance to right branch */
  }
} 
    template <class Node> inline  static
size_t __internal_path_length(Node * p, const size_t & level)
{
  if (p == Node::NullPtr) 
    return 0;

  return level + __internal_path_length(LLINK(p), level + 1) +
         __internal_path_length(RLINK(p), level + 1);
}
    template <class Node> inline 
size_t internal_path_length(Node * p) 
{
  return __internal_path_length(p, 0);
}
    template <class Node, class Compare> inline
bool check_binary_search_tree(Node * node)
{
  if (node == Node::NullPtr) 
    return true;

  if (LLINK(node) != Node::NullPtr)
    {
      if (Compare () (KEY(LLINK(node)), KEY(node)))
        return check_binary_search_tree<Node, Compare>(LLINK(node));
      else
        return false;
    }

  if (RLINK(node) != Node::NullPtr)
    {
      if (Compare () (KEY(node), KEY(RLINK(node))))
        return check_binary_search_tree<Node, Compare>(RLINK(node));
      else
        return false;
    }

  return true;
}

    template <class Node> inline
bool check_binary_search_tree(Node * node)
{
  return 
    check_binary_search_tree<Node, Aleph::less<typename Node::key_type> >(node);
}
    template <class Node> inline
  Node * 
preorder_to_binary_search_tree(DynArray<typename Node::key_type> & preorder, 
                               const int & l, const int & r)
{
  if (l > r)
    return Node::NullPtr;

  Node * root = new Node(preorder[l]);

  if (l == r)
    return root;

  int first_greater = l + 1;

  while ( (first_greater <= r) and (preorder[first_greater] < preorder[l]))
    ++first_greater; 
  LLINK(root) = 
    preorder_to_binary_search_tree<Node>(preorder, l + 1, first_greater - 1);
  RLINK(root) = 
    preorder_to_binary_search_tree<Node>(preorder, first_greater, r);

  return root;
}
    template <class Node, class Compare> inline 
Node * searchInBinTree(Node * root, const typename Node::key_type & key)
{
  Node * p = root;

  while (p != Node::NullPtr)
    if (Compare () (key, KEY(p)))       // ¿Está en rama izquierda?
      p = static_cast<Node*>(LLINK(p)); // baje a rama izquierda
    else if (Compare() (KEY(p), key))   // ¿Está en rama derecha?
      p = static_cast<Node*>(RLINK(p)); // baje a rama derecha
    else
      break; // se encontró!

  return p;
}
    template <class Node> inline
Node * searchInBinTree(Node *root, const typename Node::key_type & key)
{
  return 
    searchInBinTree<Node, Aleph::less<typename Node::key_type> >(root, key);
}
    template <class Node>
Node * find_min(Node * root)
{
  Node * ret_val = root;
  while (LLINK(ret_val) != Node::NullPtr)
    ret_val = static_cast<Node*>(LLINK(ret_val));

  return ret_val;
}

    template <class Node>
Node * find_max(Node * root)
{
  Node * ret_val = root;
  while (RLINK(ret_val) != Node::NullPtr)
    ret_val = static_cast<Node*>(RLINK(ret_val));

  return ret_val;
}
    template <class Node> inline
Node * find_successor(Node*  p, Node *& pp)
{ 

  I(p != Node::NullPtr);
  I(RLINK(p) != Node::NullPtr);

  pp = p;
  p  = static_cast<Node*>(RLINK(p));

  while (LLINK(p) != Node::NullPtr)
    {
      pp = p;
      p  = static_cast<Node*>(LLINK(p));
    }

  return p;
}
    template <class Node> inline
Node* find_predecessor(Node * p, Node *& pp)
{
  I(p != Node::NullPtr);
  I(LLINK(pp) != Node::NullPtr);

  pp = p;
  p  = static_cast<Node*>(LLINK(p));

  while (RLINK(p) != Node::NullPtr)
    {
      pp = p;
      p  = static_cast<Node*>(RLINK(p));
    }

  return p;
}
    template <class Node, class Compare> inline
Node * search_parent(Node *                          root, 
                     const typename Node::key_type & key, 
                     Node *&                         parent)
{

  I((LLINK(parent) == root) or (RLINK(parent) == root));
  I(root != Node::NullPtr);

  Compare cmp;
  Node * p = root;

  while (true)
    if (cmp(key, KEY(p)))
      { 
        if (LLINK(p) == Node::NullPtr)
          return p;

        parent = p;
        p = static_cast<Node*>(LLINK(p));
      }
    else if (cmp(KEY(p), key))
      {
        if (RLINK(p) == Node::NullPtr)
          return p;

        parent = p;
        p = static_cast<Node*>(RLINK(p));
      }
    else
      return p;
}
    template <class Node> inline
Node * search_parent(Node * root, const typename Node::key_type & key, 
                     Node *& parent)
{
  return search_parent<Node, Aleph::less<typename Node::key_type> >
    (root, key, parent);
}
    template <class Node, class Compare> inline
Node * search_rank_parent(Node * root, const typename Node::key_type & key)
{

  I(root != Node::NullPtr);

  Compare cmp;
  Node *p = root;

  while (true)
    if (cmp(key, KEY(p)))
      { 
        if (LLINK(p) == Node::NullPtr)
          return p;
        
        p = static_cast<Node*>(LLINK(p));
      }
    else if (cmp(KEY(p), key))
      {
        if (RLINK(p) == Node::NullPtr)
          return p;

        p = static_cast<Node*>(RLINK(p));
      }
    else
      return p;
}
    template <class Node> inline
Node * search_rank_parent(Node * root, const typename Node::key_type & key)
{
  return 
    search_rank_parent<Node, Aleph::less<typename Node::key_type> >(root, key);
}
    template <class Node, class Compare> inline
Node * insert_in_binary_search_tree(Node *& root, Node * p)
{
  if (root == Node::NullPtr) // ¿Inserción en árbol vacío?
    return root = p;

  if (Compare () (KEY(p), KEY(root)))      // ¿p < root?
        // insertar en subárbol izquierdo
    return insert_in_binary_search_tree <Node, Compare> 
      (static_cast<Node*&>(LLINK(root)), p);
  else if (Compare () (KEY(root), KEY(p))) // ¿p > root?
        // insertar en subárbol derecho
    return insert_in_binary_search_tree <Node, Compare> 
      (static_cast<Node*&>(RLINK(root)), p);

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

    template <class Node> inline
Node * insert_in_binary_search_tree(Node *& root, Node * p)
{
  return
    insert_in_binary_search_tree<Node, Aleph::less<typename Node::key_type> >
      (root, p);
}
# define SPLIT split_key_rec<Node, Compare>

    template <class Node, class Compare> inline
bool split_key_rec(Node * root, 
                   const typename Node::key_type & key, 
                   Node *& ts, Node *& tg)
{
  if (root == Node::NullPtr)
    {    // key no se encuentra en árbol ==> split tendrá éxito
      ts = tg = Node::NullPtr;
      return true;
    }
  if ( Compare() (key, KEY(root)) ) // ¿key < KEY(root)?
    {
      if (SPLIT(static_cast<Node*&>(LLINK(root)), key, 
                ts, static_cast<Node*&>(LLINK(root))))
        {
          tg = root;
          return true;
        }
      else
        return false;
    }
  if ( Compare() (KEY(root), key) ) // ¿key > KEY(root)?
    {
      if (SPLIT(static_cast<Node*&>(RLINK(root)), key, 
                static_cast<Node*&>(RLINK(root)), tg))
        {
          ts = root;
          return true;
        }
      else
        return false;
    }
  return false; // clave existe en árbol ==> se deja intacto
}

# undef SPLIT

    template <class Node> inline
bool split_key_rec(Node * root, const typename Node::key_type & key, 
                   Node *& l, Node *& r)
{
  return split_key_rec<Node, Aleph::less<typename Node::key_type> >(root, 
                                                                    key, l, r);
}
    template <class Node> inline
Node * join_exclusive(Node *& ts, Node *& tg)
{
  if (ts == Node::NullPtr)
    return tg;

  if (tg == Node::NullPtr)
    return ts;

  LLINK(tg) = join_exclusive(RLINK(ts), LLINK(tg));

  RLINK(ts) = tg;

  Node * ret_val = ts;

  ts = tg = Node::NullPtr; // deben quedar vacíos después del join

  return ret_val;
}  
# define REMOVE remove_from_search_binary_tree<Node, Compare>

    template <class Node, class Compare> inline
Node * remove_from_search_binary_tree(Node *& root, 
                                      const typename Node::key_type & key)
{
  if (root == Node::NullPtr)
    return Node::NullPtr;

  if (Compare () (key, KEY(root)))
    return REMOVE(static_cast<Node*&>(LLINK(root)), key);
  else if (Compare () (KEY(root), key))
    return REMOVE(static_cast<Node*&>(RLINK(root)), key);
  
  Node * ret_val = root; // respaldar root que se va a borrar

  root = join_exclusive(static_cast<Node*&>(LLINK(root)),
                        static_cast<Node*&>(RLINK(root)));

  ret_val->reset();

  return ret_val;
}
# undef REMOVE
# define REMOVE remove_from_search_binary_tree<Node,\
          Aleph::less<typename Node::key_type> >

    template <class Node> inline
Node * remove_from_search_binary_tree(Node *& root, 
                                      const typename Node::key_type & key)
{
  return REMOVE(root, key);
}

# undef REMOVE

  template <class Node, class Compare> inline
Node * insert_root(Node *& root, Node * p)
{
  Node * l = Node::NullPtr, 
       * r = Node::NullPtr; // para guardar resultados del split

  if (not split_key_rec<Node, Compare>(root, KEY(p), l, r))
    return Node::NullPtr; 

  LLINK(p) = l;
  RLINK(p) = r;

  root = p;

  return root; 
}
    template <class Node> inline
Node * insert_root(Node *& root, Node * p)
{
  return insert_root<Node, Aleph::less<typename Node::key_type> >(root, p);
}
    template <class Node, class Compare> inline
Node * join_preorder(Node * t1, Node * t2, Node *& dup)
{
  if (t2 == Node::NullPtr)
    return t1;

  Node * l = static_cast<Node*>(LLINK(t2)); // respaldos de ramas de t2
  Node * r = static_cast<Node*>(RLINK(t2));

  if (insert_in_binary_search_tree <Node, Compare> (t1, t2) == Node::NullPtr)
        // inserción fallida ==> elemento duplicado ==> insertar en dup
    insert_in_binary_search_tree<Node, Compare>(dup, t2);

  join_preorder(t1, l, dup);
  join_preorder(t1, r, dup);

  return t1;
}
    template <class Node, class Compare> inline
Node * join(Node * t1, Node * t2, Node *& dup)
{
  if (t1 == Node::NullPtr)
    return t2;

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

  Node * l = static_cast<Node*>(LLINK(t1)); // respaldos de ramas de t1
  Node * r = static_cast<Node*>(RLINK(t1));

  t1->reset();

  if (insert_root<Node, Compare>(t2, t1) == Node::NullPtr)
    insert_in_binary_search_tree<Node, Compare>(dup, t1); 

  LLINK(t2) = join<Node, Compare>(l, static_cast<Node*>(LLINK(t2)), dup);
  RLINK(t2) = join<Node, Compare>(r, static_cast<Node*>(RLINK(t2)), dup);

  return t2;
}

    template <class Node> inline
Node * join(Node * t1, Node * t2, Node *& dup)
{
  return join<Node, Aleph::less<typename Node::key_type> >(t1, t2, dup);
}

    template <class Node> inline
Node * rotate_to_right(Node * p)
{

  I(p != Node::NullPtr);

  Node * q  = static_cast<Node*>(LLINK(p));
  LLINK(p) = RLINK(q);
  RLINK(q) = p;

  return q;           
} 
    template <class Node> inline
Node * rotate_to_right(Node * p, Node * pp)
{

  I(p != Node::NullPtr);
  I(pp != Node::NullPtr);
  I((static_cast<Node*>(LLINK(pp)) == p) or 
         (static_cast<Node*>(RLINK(pp)) == p));

  Node *q = static_cast<Node*>(LLINK(p));
        
  LLINK(p) = RLINK(q);
  RLINK(q) = p;

  if (static_cast<Node*>(LLINK(pp)) == p) // actualización del padre
    LLINK(pp) = q;
  else
    RLINK(pp) = q;
     
  return q;           
} 
    template <class Node> inline
Node* rotate_to_left(Node * p)
{
  I(p != Node::NullPtr);

  Node *q  = static_cast<Node*>(RLINK(p));
  RLINK(p) = LLINK(q);
  LLINK(q) = p;

  return q;                  
} 

    template <class Node> inline
Node* rotate_to_left(Node * p, Node * pp)
{
  I(p != Node::NullPtr);
  I(pp != Node::NullPtr);
  I(static_cast<Node*>(LLINK(pp)) == p or 
         static_cast<Node*>(RLINK(pp)) == p);

  Node *q = static_cast<Node*>(RLINK(p));

  RLINK(p) = LLINK(q);
  LLINK(q) = p;

      // actualización del padre
  if (LLINK(pp) == p)
    LLINK(pp) = q;
  else
    RLINK(pp) = q;        
      
  return q;                  
} 
    template <class Node, class Key, class Compare> inline
void split_key(Node * root, const Key & key, Node *& l, Node *& r)
{
  if (root == Node::NullPtr) 
    {
      l = r = (Node*) Node::NullPtr;
      return;
    }

  Node * current;
  Node ** current_parent = NULL;
  Node ** pending_child  = NULL;
  char current_is_right;
  Compare cmp;

  if (cmp (key, KEY(root)))
    {
      r = root;
      pending_child    = &l;
      current_is_right = true;
    }
  else
    {
      l = root;
      pending_child    = &r;
      current_is_right = false;
    }
  current = root;

  while (current != Node::NullPtr) 
    {
      if (cmp (key, KEY(current)))
        { /* current must be in right side */
          if (not current_is_right)
            { 
              current_is_right = not current_is_right;
              *pending_child   = *current_parent; /* change of side */
              pending_child    = current_parent;
            }
          current_parent = static_cast<Node**>(&LLINK(current));
        }
      else
        { /* current must be in left side */
          if (current_is_right)
            { 
              current_is_right = not current_is_right;
              *pending_child   = *current_parent; /* change of side */
              pending_child    = current_parent;
            }
          current_parent = static_cast<Node**>(&RLINK(current));
        }
      current = *current_parent;
    }
  *pending_child = static_cast<Node*>(Node::NullPtr);
}

  template <class Node, class Key> inline
void split_key(Node *root, const Key& key, Node *& l, Node *& r)
{
  split_key<Node, Key, Aleph::less<Key> >(root, key, l, r);
}

    template <class Node> inline
void swap_node_with_successor(Node *  p,  // Node for swapping
                              Node *& pp, // parent of p
                              Node *  q,  // Successor inorder of p 
                              Node *& pq) // parent of q
 
{
  I(p != Node::NullPtr and q != Node::NullPtr and 
    pp != Node::NullPtr and pq != Node::NullPtr);
  I(LLINK(pp) == p or RLINK(pp) == p); 
  I(LLINK(pq) == q or RLINK(pq) == q); 
  I(LLINK(q) == Node::NullPtr);        
     
  /* Set of pp to its new son q */ 
  if (LLINK(pp) == p)
    LLINK(pp) = q;
  else
    RLINK(pp) = q;
     
  LLINK(q) = LLINK(p);
  LLINK(p) = Node::NullPtr; 

  /* Checks if successor is right child of p. In this case, p will
     become q's son. This situation happens when p's son does not have
     a left branch */   
  if (RLINK(p) == q) 
    {
      RLINK(p) = RLINK(q);
      RLINK(q) = p;
      pq        = pp;
      pp        = q;
      return;
    }

  /* In this case, successor is the leftmost node descending from
     right son of p */ 
  Node *qr   = RLINK(q); 
  RLINK(q)  = RLINK(p);
  LLINK(pq) = p;
  RLINK(p)  = qr;

  Aleph::swap(pp, pq);
}

    template <class Node> inline
void swap_node_with_predecessor(Node *  p,  // Node for swapping
                                Node *& pp, // p's parent
                                Node *  q,  // Predecessor inorder of p 
                                Node *& pq) // q's parent
{
  I((p != Node::NullPtr) and (q != Node::NullPtr) and 
    (pp != Node::NullPtr) and (pq != Node::NullPtr));
  I((RLINK(pp) == p) or (LLINK(pp) == p)); /* assert pp is parent of p */
  I((RLINK(pq) == q) or (LLINK(pq) == q)); /* assert pq is parent of q */
  I(RLINK(q) == Node::NullPtr);
     
  /* Set of pp to its new son q */ 
  if (RLINK(pp) == p)
    RLINK(pp) = q;
  else
    LLINK(pp) = q;
     
  RLINK(q) = RLINK(p);
  RLINK(p) = Node::NullPtr; 

  /* Checks if predecessor is left child of p. In this case, p will
     become q's son. This situation happens when p's son does not have
     a right branch */   
  if (LLINK(p) == q) 
    {
      LLINK(p) = LLINK(q);
      LLINK(q) = p;
      pq       = pp;
      pp       = q;
      return;
    }

  /* In this case, predecessor is the rightmost node descending from
     right son of p */ 
  Node *ql  = LLINK(q); 
  LLINK(q)  = LLINK(p);
  RLINK(pq) = p;
  LLINK(p)  = ql;

  Aleph::swap(pp, pq);
}

    template <class Node, class Key, class Compare> inline
Node * insert_root_rec(Node * root, Node * p)
{
  if (root == Node::NullPtr)
    return p; /* insertion in empty tree */

  if (Compare () (KEY(p), KEY(root)))
    { /* insert in left subtree */
      Node *left_branch = 
        insert_root_rec<Node, Key, Compare>(static_cast<Node*>(LLINK(root)),
                                             p);
      if (left_branch == Node::NullPtr)
        return (Node*) Node::NullPtr;

      LLINK(root) = left_branch;
      root        = rotate_to_right(root);
    }
  else if (Compare () (KEY(root), KEY(p) ))
    { /* insert in right subtree */
      Node *right_branch = 
        insert_root_rec<Node, Key, Compare>(static_cast<Node*>(RLINK(root)), 
                                            p);
      if (right_branch == Node::NullPtr)
        return (Node*) Node::NullPtr;

      RLINK(root) = right_branch;
      root        = rotate_to_left(root);
    }
  else
    return (Node*) Node::NullPtr; /* duplicated key */

  return root;
}

    template <class Node, class Key> inline
Node * insert_root_rec(Node * root, Node * p)
{
  return insert_root_rec<Node, Key, Aleph::less<Key> >(root, p);
}


} // end Aleph

# endif // TPL_BINNODEUTILS_H 

---