tpl_rb_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_RB_TREE_H
# define TPL_RB_TREE_H

# include <ahFunction.H>
# include <tpl_arrayStack.H>
# include <tpl_binNodeUtils.H>
# include <rbNode.H>

using namespace Aleph;

namespace Aleph {

    template <template <typename> class NodeType, typename Key, class Compare>
class Gen_Rb_Tree 
{

public:

  typedef NodeType<Key> Node;


private:

  Node                               head_node;  // Node cabecera centinela
  Node *                             head; // puntero a cabecera centinela
  Node *&                            root; // raíz
  FixedStack<Node*, Node::MaxHeight> rb_stack; 
  Node * search_and_stack_rb(const Key & key)             
  {
    Node * p = root;
    rb_stack.push(head);
      
    do 
      {
        rb_stack.push(p); 
   
        if (Compare () (key, KEY(p)))
          p = LLINK(p);
        else if (Compare () (KEY(p), key))
          p = RLINK(p);
        else
          return p;
      }
    while (p != Node::NullPtr);

    return rb_stack.top();
  }
  void fix_red_condition(Node * p)
  {

    I(COLOR(p) == RED);

    while (p != root) 
      {
        Node * pp = rb_stack.pop(); // padre de p
        
        if (COLOR(pp) == BLACK) // ¿padre de p es negro?
          break; // sí ==> no hay nodos rojos consecutivos ==> terminar

        if (root == pp) // ¿p es hijo directo de la raíz?
          {    // sí ==> colorear raíz de negro y terminar
            COLOR(root) = BLACK; 
            break; 
          }

        Node * ppp = rb_stack.pop(); // abuelo de p
        Node * spp = LLINK(ppp) == pp ? RLINK(ppp) : LLINK(ppp); // tío de p

        if (COLOR(spp) == RED) // ¿tío de p es rojo?
          {     // intercambiar colores entre los niveles
            COLOR(ppp) = RED;
            COLOR(pp)  = BLACK;
            COLOR(spp) = BLACK;
            p = ppp;
            continue; // avanzar al próximo ancestro y verificar violaciones
          }

        Node *pppp = rb_stack.pop(); // bisabuelo de p

        if (LLINK(pp) == p and LLINK(ppp) == pp)
          {
            rotate_to_right(ppp, pppp);
            COLOR(pp) = BLACK;
          }
        else if (RLINK(pp) == p and RLINK(ppp) == pp)
          {
            rotate_to_left(ppp, pppp);
            COLOR(pp) = BLACK;
          }
        else 
          {
            if (RLINK(pp) == p)
              {
                rotate_to_left(pp, ppp);
                rotate_to_right(ppp, pppp);
              }
            else
              {
                rotate_to_right(pp, ppp);
                rotate_to_left(ppp, pppp);
              }
            COLOR(p) = BLACK;
          }
        COLOR(ppp) = RED;

        break; // árbol es rojo-negro ==> terminar
      }
     rb_stack.empty();
  }
  void find_succ_and_swap(Node * p, Node *& pp)
  {
    Node *& ref_rb_stack = rb_stack.top(); 

    /* Find successor while updating rb_stack */
    Node * fSucc = p;        // successor's parent
    Node * succ  = RLINK(p); // Searching starts from p's right child 

    rb_stack.push(succ);
    while (LLINK(succ) != Node::NullPtr)  // go down to leftmost
      {
        fSucc = succ;
        succ  = LLINK(succ);
        rb_stack.push(succ);
      }

      ref_rb_stack   = succ; /* swap old top with current top */
      rb_stack.top() = p; 

      if (LLINK(pp) == p) /* Setting of parent of p to new child(succ) */ 
        LLINK(pp) = succ;
      else
        RLINK(pp) = succ;
      
      LLINK(succ) = LLINK(p); /* Swaps left branches */
      LLINK(p)    = Node::NullPtr; 

      if (RLINK(p) == succ) /* For right branches there are two cases */
        { /* successor is just right child of p */   
          RLINK(p)    = RLINK(succ); 
          RLINK(succ) = p;
          pp          = succ;
        }
      else
        { /* Successor is leftmost node descending from right child of p */ 
          Node *succr  = RLINK(succ); 
          RLINK(succ)  = RLINK(p);
          LLINK(fSucc) = p;
          RLINK(p)     = succr;
          pp           = fSucc;
        }

      Aleph::swap(COLOR(succ), COLOR(p));
    }

  void fix_black_condition(Node * p)
  {
    if (COLOR(p) == RED) // ¿p es rojo?
      {     // sí ==> lo pintamos de negro y terminamos
        COLOR(p) = BLACK; // esto compensa el déficit 
        return;
      }

    Node * pp = rb_stack.popn(2); // padre de p
        
    while (p != root)
      {

        I(LLINK(pp) == p or RLINK(pp) == p);
        I(LLINK(rb_stack.top()) == pp or RLINK(rb_stack.top()) == pp);

        Node * sp = LLINK(pp) == p ? RLINK(pp) : LLINK(pp); // hermano de p
        
        if (COLOR(sp) == RED) // ¿hermano de p es rojo?
          {
            Node *& ppp = rb_stack.top(); // abuelo de p

            if (LLINK(pp) == p)
              {
                sp  = LLINK(sp);
                ppp = rotate_to_left(pp, ppp);
              }
            else
              {
                sp  = RLINK(sp);
                ppp = rotate_to_right(pp, ppp);
              }

            COLOR(ppp) = BLACK;
            COLOR(pp)  = RED;
          }

        Node * np, * snp;
        if (LLINK(pp) == p) // ¿p es hijo izquierdo?
          {     // sí ==> que sp es hijo derechos
            np  = RLINK(sp);
            snp = LLINK(sp);
          }
        else
          {
            np  = LLINK(sp);
            snp = RLINK(sp);
          }

        if (COLOR(np) == RED) // ¿np es rojo?
          {
            Node * ppp = rb_stack.top();

            if (RLINK(sp) == np)
              rotate_to_left(pp, ppp);
             else
              rotate_to_right(pp, ppp);

            COLOR(sp) = COLOR(pp);
            COLOR(pp) = BLACK;
            COLOR(np) = BLACK;
            return;
          }

        if (COLOR(snp) == RED) // ¿snp es rojo?
          {
            Node * ppp = rb_stack.top();

            if (LLINK(sp) == snp)
              {
                rotate_to_right(sp, pp);
                rotate_to_left(pp, ppp);
              }
             else
               {
                 rotate_to_left(sp, pp);
                 rotate_to_right(pp, ppp);
               }

            COLOR(snp) = COLOR(pp);
            COLOR(pp)  = BLACK;;
            return;
          }

        if (color(pp) == RED) // ¿pp es rojo?
          {
            COLOR(pp) = BLACK;
            COLOR(sp) = RED;;
            return;
          }

            // no hay nodo rojo en las adyacencias de p ==> desplazar el
            // déficit hacia pp y repetir la iteración
        COLOR(sp) = RED;
        p         = pp;
        pp        = rb_stack.pop(); 
      }
  }


public:


  Gen_Rb_Tree() : head(&head_node), root(head_node.getR()) { /* empty */ }

  virtual ~Gen_Rb_Tree() { /* empty */ }

  Node * search(const Key & key)
  {
    Node * retVal = Aleph::searchInBinTree<Node, Compare>(root, key);

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

  Node *& getRoot() { return root; }
  Node * insert(Node * p)
  {

    I(COLOR(p) == RED);

    if (root == Node::NullPtr) // inserción en árbol vacío
      return root = p;

    Node * q = search_and_stack_rb(KEY(p));

    if (Compare () (KEY(p), KEY(q))) 
      LLINK(q) = p;
    else if (Compare () (KEY(q), KEY(p))) 
      RLINK(q) = p;
    else
      {
        rb_stack.empty();

        return NULL;  // clave duplicada
      }

    fix_red_condition(p);

    return p;
  }
  Node* remove(const Key & key)
  {
    if (root == Node::NullPtr)
      return NULL;
        
    Node * q = search_and_stack_rb(key);

    if (no_equals<Key, Compare> (KEY(q), key))
      {
        rb_stack.empty();
        return NULL;
      }

    Node * pq = rb_stack.top(1); // padre de 1
    Node * p; // hijo de q luego de que éste ha sido eliminado

   repeat:   // Eliminación tradicional en árbol binario de búsqueda
    
    if (LLINK(q) == Node::NullPtr) 
      {
        if (LLINK(pq) == q)
          p = LLINK(pq) = RLINK(q);
        else
          p = RLINK(pq) = RLINK(q);

        goto end;
      }

    if (RLINK(q) == Node::NullPtr) 
      {
        if (LLINK(pq) == q)
          p = LLINK(pq) = LLINK(q);
        else
          p = RLINK(pq) = LLINK(q);

        goto end;
      }
            
    find_succ_and_swap(q, pq);

    goto repeat;

   end:
    if (COLOR(q) == BLACK) // ¿se eliminó un nodo negro?
      fix_black_condition(p);

    q->reset();
    rb_stack.empty();
        
    return q;
  }
};

    template <typename Key, class Compare = Aleph::less<Key> >
struct Rb_Tree : public Gen_Rb_Tree<RbNode, Key, Compare>
{ /* Empty */ };

    template <typename Key, class Compare = Aleph::less<Key> >
struct Rb_Tree_Vtl : public Gen_Rb_Tree<RbNodeVtl, Key, Compare>
{ /* Empty */ };

} // end namespace Aleph

# endif // TPL_RB_TREE_H

---