tpl_binNodeUtils.H

# ifndef TPL_BINNODEUTILS_H
# define TPL_BINNODEUTILS_H 

# include <ahFunction.H>
# include <tpl_arrayStack.H> 
# include <tpl_arrayQueue.H>
# include <tpl_dynListQueue.H>
# include <bitArray.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((Node*) LLINK(node), level + 1, position, visitFct);
 
 (*visitFct)(node, level, position);
  ++position;

  __inorder_rec((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((Node*) LLINK(p), level + 1, position, visitFct);
  __preorder_rec((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((Node*) LLINK(node), level + 1, position, visitFct);
  __postorder_rec((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, class Op> 
class For_Each_In_Order
{
  static void for_each_inorder(Node * root, Op & op) 
  {
    if (root == Node::NullPtr)
      return;

    for_each_inorder((Node*) LLINK(root), op);
    op(root);
    for_each_inorder((Node*) RLINK(root), op);
  }

public:

  void operator () (Node * root, Op & op) 
  {
    for_each_inorder(root, op);
  }

  void operator () (Node * root, Op && op = Op()) 
  {
    for_each_inorder(root, op);
  }
};

  template <class Node, class Operation> inline
bool traverse(Node * root, Operation & operation)
{
  if (root == Node::NullPtr)
    return true;

  return traverse<Node, Operation>((Node*) LLINK(root), operation) and
    operation(root) and 
    traverse<Node, Operation>((Node*) RLINK(root), operation);
}

  template <class Node, class Operation> inline
bool traverse(Node * root, Operation && operation = Operation())
{
  return traverse<Node, Operation>(root, operation);
}

    template <class Node, class Op> 
class Goto_In_Order
{
  bool to_leave;

  void inorder(Node * root, Op & op) 
  {
    if (root == Node::NullPtr or to_leave)
      return;

    for_each_inorder((Node*) LLINK(root), op);
    to_leave = op(root);
    for_each_inorder((Node*) RLINK(root), op);
  }

public:

  Goto_In_Order() : to_leave(false) { /* empty */ }

  void leave() { to_leave = true; }

  void operator () (Node * root, Op & op) 
  {
    inorder(root, op);
  }

  void operator () (Node * root, Op && op = Op()) const 
  {
    inorder(root, op);
  }

};
    template <class Node, class Op> 
class For_Each_Preorder
{
  static void preorder(Node * root, Op & op) 
  {
    if (root == Node::NullPtr)
      return;

    op(root);
    preorder((Node*) LLINK(root), op);
    preorder((Node*) RLINK(root), op);
  }

public:

  void operator () (Node * root, Op & op) 
  {
    preorder(root, op);
  }

  void operator () (Node * root, Op && op = Op()) 
  {
    preorder(root, op);
  }
};

/* 
    template <class Node> 
class For_Each_Preorder
{
  static void preorder(Node * root, void (*op)(Node*))
  {
    if (root == Node::NullPtr)
      return;

    op(root);
    preorder((Node*) LLINK(root), op);
    preorder((Node*) RLINK(root), op);
  }

public:

  void operator () (Node * root, void (*op)(Node*))
  {
    preorder(root, op);
  }
};
*/

    template <class Node, class Op> 
class For_Each_Postorder
{
  static void postorder(Node * root, Op & op) 
  {
    if (root == Node::NullPtr)
      return;

    postorder((Node*) LLINK(root), op);
    postorder((Node*) RLINK(root), op);
    op(root);
  }

public:
  void operator () (Node * root, Op & op) 
  {
    postorder(root, op);
  }

  void operator () (Node * root, Op && op = Op())
  {
    postorder(root, op);
  }
};

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

  ArrayStack<Node *> stack(Node::MaxHeight);
  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 *> stack(Node::MaxHeight);
  Node *p = node;
  size_t count = 0;

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

      if (LLINK(p) != Node::NullPtr)
        {
          stack.push(p); // 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 *> stack(Node::MaxHeight);
  Node *p = node;
  size_t count = 0;

  while (true)
    {
      if (LLINK(p) != Node::NullPtr)
        {
          stack.push(p); // 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 std::pair<Node*, char> Postorder_Pair;
  ArrayStack<Postorder_Pair> stack(Node::MaxHeight);

  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>
static void prefix(Node * root, DynList<Node*> & acc)
{
  if (root == Node::NullPtr)
    return;

  acc.append(root);
  prefix((Node*) LLINK(root), acc);
  prefix((Node*) RLINK(root), acc);
}

template <class Node>
static void infix(Node * root, DynList<Node*> & acc)
{
  if (root == Node::NullPtr)
    return;

  infix((Node*) LLINK(root), acc);
  acc.append(root);
  infix((Node*) RLINK(root), acc);
}

template <class Node>
static void suffix(Node * root, DynList<Node*> & acc)
{
  if (root == Node::NullPtr)
    return;

  sufffix((Node*) LLINK(root), acc);
  siffix((Node*) RLINK(root), acc);
  acc.append(root);
}

template <class Node>
DynList<Node*> prefix(Node * root)
{
  DynList<Node*> ret_val;
  prefix(root, ret_val);
  return ret_val;
}

template <class Node>
DynList<Node*> infix(Node * root)
{
  DynList<Node*> ret_val;
  infix(root, ret_val);
  return ret_val;
}

template <class Node>
DynList<Node*> suffix(Node * root)
{
  DynList<Node*> ret_val;
  suffix(root, ret_val);
  return ret_val;
}


    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 + std::max(left_height, right_height);
}

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

  destroyRec((Node*&) LLINK(root));
  destroyRec((Node*&) RLINK(root));
  delete root;

  root = (Node*) Node::NullPtr;
}

    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>((Node*) LLINK(src_root));
      RLINK(tgt_root) = copyRec<Node>((Node*) RLINK(src_root));

    }
  catch (...)
    {
      I(RLINK(tgt_root) == Node::NullPtr);

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

      delete tgt_root;

      throw;
    }

  return tgt_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), size_t queue_size)
{

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

  const size_t two_power = 
     (size_t) (std::log((float)queue_size)/std::log(2.0) + 1);
  ArrayQueue<std::pair<Node*, bool> > queue(two_power); 
  queue.put(std::pair<Node*, bool>(root, bool()));

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

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

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

      if (RLINK(p) != Node::NullPtr)
        queue.put(std::pair <Node*, bool> (RLINK(p), false));
    }
}


  template <class Node, class Operation> inline
bool level_traverse(Node * root, Operation & operation)
{
  if (root == Node::NullPtr)
    return true;

  DynListQueue<Node*> queue; 
  queue.put(root);

  while (not queue.is_empty())
    {
      Node * p = queue.get();

      if (not operation(p))
        return false;

      if (LLINK(p) != Node::NullPtr)
        queue.put((Node*) LLINK(p));

      if (RLINK(p) != Node::NullPtr)
        queue.put((Node*) RLINK(p));
    }
  return true;
}

  template <class Node, class Operation> inline
bool level_traverse(Node * root, Operation && operation = Operation())
{
  return level_traverse<Node, Operation>(root, operation);
}

    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) 
    return root; // recorrido de longitud 1
  
  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 (current_level == 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> inline 
void tree_to_bits(Node * root, BitArray & array)
{
  if (root == Node::NullPtr)
    {
      array.push(1);
      return;
    }

  array.push(0);
  tree_to_bits((Node*) LLINK(root), array);
  tree_to_bits((Node*) RLINK(root), array);
}

template <class Node> inline 
BitArray tree_to_bits(Node * root)
{
  BitArray ret_val;
  tree_to_bits(root, ret_val);
  return ret_val;
}

     template <class Node> static inline 
Node * __bits_to_tree(BitArray & array, int & i)
{
  int bit = array.read_bit(i++);
  if (bit == 1) // ¿Es un nodo externo?
    return Node::NullPtr; // sí

  Node * p = new Node;  // crear nodo interno actual
  LLINK(p) = (Node*) __bits_to_tree<Node>(array, i); // subárbol izq.
  RLINK(p) = (Node*) __bits_to_tree<Node>(array, i); // subárbol der.

  return p;
}

template <class Node> inline Node * bits_to_tree(BitArray & array, int idx = 0)
{
  return __bits_to_tree <Node> (array, idx);
}

  template <class Node, class Get_Key> inline 
void save_tree_keys_in_prefix(Node * root, ofstream & output)
{
  if (root == Node::NullPtr)
    return;

  output << Get_Key () (root) << " ";

  save_tree_keys_in_prefix<Node,Get_Key>((Node*)LLINK(root), output);
  save_tree_keys_in_prefix<Node,Get_Key>((Node*)RLINK(root), output);
}

  template <class Node, class Load_Key> inline 
void load_tree_keys_in_prefix(Node * root, ifstream & input)
{
  if (root == Node::NullPtr)
    return;

  Load_Key () (root, input);

  load_tree_keys_in_prefix<Node,Load_Key>((Node*)LLINK(root), input);
  load_tree_keys_in_prefix<Node,Load_Key>((Node*)RLINK(root), input);
}

  template <class Node, class Get_Key> inline 
void save_tree(Node * root, ofstream & output)
{
  BitArray prefix;
  tree_to_bits(root, prefix); 
  prefix.save(output);
  save_tree_keys_in_prefix <Node, Get_Key> (root, output);
}

  template <class Node, class Load_Key> inline 
Node * load_tree(ifstream & input)
{
  BitArray prefix;
  prefix.load(input);
  Node * root = bits_to_tree <Node> (prefix);
  load_tree_keys_in_prefix <Node, Load_Key> (root, input); 
  return root;
}

   
   template <class Node, class Get_Key> inline 
void put_tree_keys_in_array(Node * root, ofstream & out)
{
  if (root == Node::NullPtr)
    return;

  const string str = Get_Key () (root);

  if (str == "\t")
    out << "\"\t\"";
  else if (str == "\n")
    out << "\"\\n\""; 
  else
    out << "\"" << str << "\"";
  out << ", ";

  put_tree_keys_in_array <Node, Get_Key> ((Node *) LLINK(root), out);
  put_tree_keys_in_array <Node, Get_Key> ((Node *) RLINK(root), out);
}


    template <class Node, class Load_Key> inline 
void load_tree_keys_from_array(Node * root, const char * keys[], int & idx)
{
  if (root == Node::NullPtr)
    return;

  if (Load_Key()(root, keys[idx]))
    ++idx;

  load_tree_keys_from_array <Node, Load_Key> ((Node *) LLINK(root), keys, idx);
  load_tree_keys_from_array <Node, Load_Key> ((Node *) RLINK(root), keys, idx);
}

   template <class Node, class Get_Key> inline 
void save_tree_in_array_of_chars(Node *         root, 
                                 const string & array_name, 
                                 ofstream &     output)
{
  BitArray prefix;
  tree_to_bits(root, prefix); 
  prefix.save_in_array_of_chars(array_name + "_cdp", output);
  output << "const char * " << array_name << "_k[] = { " << endl;
  put_tree_keys_in_array <Node, Get_Key> (root, output);
  output << "NULL };" << endl;
}


    template <class Node, class Load_Key> inline 
Node * load_tree_from_array(const unsigned char bits[], 
                            const size_t &      num_bits, 
                            const char *        keys[])
{
  BitArray prefix;
  prefix.load_from_array_of_chars(bits, num_bits);
  Node * root = bits_to_tree <Node> (prefix);
  int i = 0;
  load_tree_keys_from_array <Node, Load_Key> (root, keys, i);
  return root;
}


    template <class Node, 
              class Compare = Aleph::less<typename Node::key_type> > inline
bool check_binary_search_tree(Node * p)
{
  typedef typename Node::key_type Key_Type;

  if (p == Node::NullPtr) 
    return true;

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

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

    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 = Aleph::less<typename Node::key_type>> 
  inline 
Node * searchInBinTree(Node * root, 
                       const typename Node::key_type & key,
                       Compare & cmp)
{
  while (root != Node::NullPtr)
    if (cmp(key, KEY(root)))      // ¿en rama izquierda?
      root = (Node*) LLINK(root);  // baje a la izquierda
    else if(cmp (KEY(root), key)) // ¿en rama derecha?
      root = (Node*) RLINK(root);  // baje a la derecha
    else
      break;                       // se encontró!

  return root;
}

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

    template <class Node> inline 
Node * find_min(Node * root)
{
  while (LLINK(root) != Node::NullPtr)
    root = static_cast<Node*>(LLINK(root));

  return root;
}

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

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

  pp = p;
  p  = (Node*) RLINK(p);
  while (LLINK(p) != Node::NullPtr)
    {
      pp = p;
      p  = (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 = Aleph::less<typename Node::key_type> > inline
Node * search_parent(Node * root, const typename Node::key_type & key, 
                     Node *& parent, Compare && cmp = Compare())
{
  I((LLINK(parent) == root) or (RLINK(parent) == root));
  I(root != Node::NullPtr);

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

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

        parent = root;
        root = static_cast<Node*>(RLINK(root));
      }
    else
      return root;
}

    template <class Node, 
              class Compare = Aleph::less<typename Node::key_type> > 
    inline Node * 
search_rank_parent(Node * root, 
                   const typename Node::key_type & key,
                   Compare && cmp = Compare())
{
  I(root != Node::NullPtr);

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

        root = static_cast<Node*>(RLINK(root));
      }
    else
      return root;
}

  template <class Node, 
            class Compare = Aleph::less<typename Node::key_type> > inline
Node * insert_in_binary_search_tree(Node *& root, Node * p)
{
  if (root == Node::NullPtr) 
    return root = p;

  if (Compare () (KEY(p), KEY(root)))        // ¿p < root?
    return insert_in_binary_search_tree<Node,Compare>((Node*&) LLINK(root), p);
  else if (Compare () (KEY(root), KEY(p)))   // ¿p > root?
    return insert_in_binary_search_tree<Node,Compare>((Node*&) RLINK(root), p);

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

# define INSERT_DUP insert_dup_in_binary_search_tree<Node,Compare>

  template <class Node, 
            class Compare = Aleph::less<typename Node::key_type> > inline
Node * insert_dup_in_binary_search_tree(Node *& root, Node * p)
{
  if (root == Node::NullPtr) 
    return root = p;

  if (Compare () (KEY(p), KEY(root)))        // ¿p < root?
    return INSERT_DUP ((Node*&) LLINK(root), p);
  
  return INSERT_DUP((Node*&) RLINK(root), p);
}
# undef INSERT_DUP

  template <class Node, 
            class Compare = Aleph::less<typename Node::key_type> > inline
Node * search_or_insert_in_binary_search_tree(Node *& r, Node * p)
{
  if (r == Node::NullPtr) 
    return r = p;

  if (Compare () (KEY(p), KEY(r)))        // ¿p < root?
    return 
      search_or_insert_in_binary_search_tree<Node,Compare>((Node*&)LLINK(r), p);
  else if (Compare () (KEY(r), KEY(p)))   // ¿p > root?
    return 
      search_or_insert_in_binary_search_tree<Node,Compare>((Node*&)RLINK(r), p);

  return r; 
}

# define SPLIT split_key_rec<Node, Compare>

  template <class Node, 
            class Compare = Aleph::less<typename Node::key_type> > 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((Node*&) LLINK(root), key, ts, (Node*&) LLINK(root)))
      {
        tg = root;
        return true;
      }
    else
      return false;

  if (Compare() (KEY(root), key)) // ¿key > KEY(root)?
    if (SPLIT((Node*&) RLINK(root), key, (Node*&) RLINK(root), tg))
      {
        ts = root;
        return true;
      }
    else
      return false;

  return false; // clave existe en árbol ==> se deja intacto
}

# undef SPLIT

# define SPLIT split_key_dup_rec<Node, Compare>

  template <class Node, 
            class Compare = Aleph::less<typename Node::key_type> > inline
void split_key_dup_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;
    }

  if (Compare() (key, KEY(root))) // ¿key < KEY(root)?
    SPLIT((Node*&) LLINK(root), key, ts, (Node*&) LLINK(root));
  else if (Compare () (KEY(root), key)) // ¿key > KEY(root)?
    SPLIT((Node*&) RLINK(root), key, (Node*&) RLINK(root), tg);
  else // key == KEY(root)
    SPLIT((Node*&) LLINK(root), key, ts, (Node*&) LLINK(root));
}

# undef SPLIT

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 = Aleph::less<typename Node::key_type> > 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)))       // ¿key < KEY(root)?
    return REMOVE((Node*&) LLINK(root), key);
  else if (Compare () (KEY(root), key))  // ¿key > KEY(root)?
    return REMOVE((Node*&) RLINK(root), key);

  Node * ret_val = root; // respaldar root que se va a borrar
  root = join_exclusive((Node*&) LLINK(root), (Node*&) RLINK(root));

  ret_val->reset();

  return ret_val;
}

# undef REMOVE

  template <class Node, 
            class Compare = Aleph::less<typename Node::key_type> > inline
Node * insert_root(Node *& root, Node * p)
{
  Node * l = Node::NullPtr, * r = Node::NullPtr;

  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, 
            class Compare = Aleph::less<typename Node::key_type> > inline
Node * insert_dup_root(Node *& root, Node * p)
{
  split_key_dup_rec<Node, Compare>(root, KEY(p), LLINK(p), RLINK(p));
  return root = p;
}

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

  Node * l = (Node*) LLINK(t2); // respaldos de ramas de t2
  Node * r = (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 = Aleph::less<typename Node::key_type> > inline
Node * join(Node * t1, Node * t2, Node *& dup)
{
  if (t1 == Node::NullPtr) 
    return t2;

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

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

  t1->reset();

      // mientras la clave raíz de t1 esté contenida en t2
  while (t1 != Node::NullPtr and 
         insert_root<Node, Compare>(t2, t1) == Node::NullPtr) 
    {     // sí ==> sáquelo de t1 e insértelo en dup
      Node * p = remove_from_search_binary_tree(t1, KEY(t1));

      l = (Node*) LLINK(t1);
      r = (Node*) RLINK(t1);

      I(p != Node::NullPtr);

      insert_in_binary_search_tree<Node, Compare>(dup, p);
    }

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

  return t2;
}

    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( ((Node*) LLINK(pp)) == p or ((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 = Aleph::less<typename Node::key_type> > 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> 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;

  std::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;
  std::swap(pp, pq);
}

    template <class Node, class Key, 
              class Compare = Aleph::less<typename Node::key_type> > 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, 
              class Compare = Aleph::less<typename Node::key_type> > inline
Node * search_or_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 = 
        search_or_insert_root_rec<Node, Key, Compare>((Node*) LLINK(root), p);
      if (left_branch == p) // ¿hubo inserción?
        {
          LLINK(root) = left_branch;
          root        = rotate_to_right(root);
          return p;
        }

        return left_branch; // no la hubo
    }
  else if (Compare () (KEY(root), KEY(p)))
    { // insert in right subtree 
      Node * right_branch = 
        search_or_insert_root_rec<Node, Key, Compare>((Node*) RLINK(root), p);
      if (right_branch == p) // ¿hubo inserción?
        {
          RLINK(root) = right_branch;
          root        = rotate_to_left(root);
          return p;
        }

      return right_branch; // no la hubo
    }

  return root;
}


} // end Aleph

# endif // TPL_BINNODEUTILS_H