tpl_avl.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_AVL_H
# define TPL_AVL_H

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

using namespace Aleph;

namespace Aleph {

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

public:

  typedef NodeType<Key> Node;

private:

  FixedStack<Node *, Node::MaxHeight> avl_stack;
  Node    head_node; 
  Node *  head_ptr;  
  Node *& root;      
  Compare cmp;       
  bool avl_stack_empty() { return avl_stack.top() == head_ptr; }

  void clean_avl_stack() { avl_stack.popn (avl_stack.size() - 1); }
  Node * search_and_stack_avl(const Key &  key)
  {

    I(avl_stack_empty());

    Node * p = root;

    do // desciende en búsqueda de key y empila el camino de búsqueda
      {
        avl_stack.push(p);

        if (cmp(key, KEY(p))) // ¿key < KEY(p)?
          p = LLINK(p);
        else if (cmp(KEY(p), key)) // ¿key > KEY(p)?
          p = RLINK(p);
        else
          return p; // clave duplicada
      }
    while (p != Node::NullPtr);

    return avl_stack.top();
  }
  static Node * rotateLeft(Node * p)
  {
    I(DIFF(p) == 2);
    I(RLINK(p) != Node::NullPtr);

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

    if (DIFF(q) == 0)      // ajuste de los factores de equilibrio
      { // este caso ocurre durante la eliminación
        DIFF(q) = -1;
        DIFF(p) = 1;
      }
    else
      DIFF(q) = DIFF(p) = 0;

    return q;
  }

  static Node * rotateRight(Node * p)
  {
    I(DIFF(p) == -2);
    I(LLINK(p) != Node::NullPtr);

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

    if (DIFF(q) == 0)       // ajuste de los factores de equilibrio
      { // este caso ocurre durante la eliminación
        DIFF(q) = 1;
        DIFF(p) = -1;
      }
    else
      DIFF(q) = DIFF(p) = 0;

    return q;
  }
  static Node * doubleRotateLeft(Node * p)
  {
    I(DIFF(p) == 2 or DIFF(p) == -2);
    I(RLINK(p) != Node::NullPtr and LLINK(RLINK(p)) != Node::NullPtr);

    Node * q = RLINK(p);
    Node * r = LLINK(q);
    RLINK(p) = LLINK(r);
    LLINK(q) = RLINK(r);
    LLINK(r) = p;
    RLINK(r) = q;

    unsigned char b; // altura lógica de hijo izq de r
    unsigned char c; // altura lógica de hijo der de r

        // Determinación de alturas lógicas de p, q y r 
    if (DIFF(r) == 1) // ==> c > b ==> c-b == 1
      {
        c = 1;
        b = 0;
      }
    else if (DIFF(r) == -1) // ==> c < b ==> c-b = -1
      {
        c = 0;
        b = 1;
      }
    else
      c = b = 1;
            
        // ajuste de factores de equilibrio
    DIFF(r) = 0; 
    DIFF(p) = b - 1; // altura lógica de hijo izq de p es 1
    DIFF(q) = 1 - c; // altura lógica de hijo der de q es 1

    return r;
  }

  static Node * doubleRotateRight(Node * p)
  {
    I(DIFF(p) == 2 or DIFF(p) == -2);
    I(LLINK(p) != Node::NullPtr and 
       RLINK(LLINK(p)) != Node::NullPtr);

    Node * q  = LLINK(p);
    Node * r  = RLINK(q);
    LLINK(p) = RLINK(r);
    RLINK(q) = LLINK(r);
    RLINK(r) = p;
    LLINK(r) = q;

    unsigned char b; // altura lógica de hijo izq de r
    unsigned char c; // altura lógica de hijo der de r

        // determinación de alturas lógicas de hijos de p, q y r
    if (DIFF(r) == 1) // ==> c > b ==> c-b == 1
      {
        c = 1;
        b = 0;
      }
    else if (DIFF(r) == -1) // ==> c < b ==> c-b == -1
      {
        c = 0;
        b = 1;
      }
    else
      c = b = 1;

        // ajuste de factores de equilibrio
    DIFF(r) = 0;
    DIFF(p) = 1 - c; // altura lógica de hijo der de p es 1
    DIFF(q) = b - 1; // altura lógica de hijo izq de p es 1

    return r;
  }
  enum Rotation_Type 
  { ROTATE_LEFT, ROTATE_RIGHT, DOUBLE_ROTATE_LEFT, DOUBLE_ROTATE_RIGHT };
  static Rotation_Type rotation_type(Node * p) 
  {

    I(DIFF(p) == 2 or DIFF(p) == -2);

    Node * pc; // p's child

    if (DIFF(p) == 2) // hacia la izquierda
      {
        pc = RLINK(p);
        if (DIFF(pc) == 1 or DIFF(pc) == 0) 
          return ROTATE_LEFT;

        return DOUBLE_ROTATE_LEFT;
      }

    pc = LLINK(p);
    if (DIFF(pc) == -1 or DIFF(pc) == 0) 
      return ROTATE_RIGHT;

    return DOUBLE_ROTATE_RIGHT;
  }
  static Node * restore_avl(Node * p, Node * pp)
  {

    I(LLINK(pp) == p or RLINK(pp) == p);
    I(DIFF(p) == -2 or DIFF(p) == 2);

    Node ** link = LLINK(pp) == p ? &LLINK(pp) : &RLINK(pp);
        
    switch (rotation_type(p))
      {
      case ROTATE_LEFT:         return *link = rotateLeft(p);
      case ROTATE_RIGHT:        return *link = rotateRight(p);
      case DOUBLE_ROTATE_LEFT:  return *link = doubleRotateLeft(p);
      case DOUBLE_ROTATE_RIGHT: return *link = doubleRotateRight(p); 

      default:
        ERROR("Invalid rotation type");
        break;

      }
    return NULL;
  }
  void restore_avl_after_insertion(const Key & key) 
  {
    Node *pp  = avl_stack.pop(); // padre del nodo insertado

    if (key > KEY(pp)) // ajuste el factor del padre del nodo insertado
      DIFF(pp)++;
    else
      DIFF(pp)--;

    if (DIFF(pp) == 0) 
      {    // en este caso, altura del ascendiente de pp no aumenta
        clean_avl_stack();                      
        return;
      }

    if (avl_stack_empty()) 
      return; // pp es raíz

    Node *gpp; // padre de pp

    do     // buscar nodo con factor igual a 0
      {
        gpp = avl_stack.pop(); 

            // actualizar factores de equilibrio
        if (key > KEY(gpp)) 
          DIFF(gpp)++;
        else
          DIFF(gpp)--;

        if (DIFF(gpp) == 0)
          break; // no se necesita reajuste
        else if (DIFF(gpp) == -2 or DIFF(gpp) == 2) // ¿se viola condición AVL?
          {      // se requiere reajuste
            Node *ggpp = avl_stack.pop();
            restore_avl(gpp, ggpp);
            break;
          }
      }
    while (not avl_stack_empty());

    clean_avl_stack();
  }
  Node* swapWithSuccessor(Node * p, Node *& pp)
  {
        // Referencia al tope de la pila, pues p será intercambiado con el
        // sucesor y la posición en la pila la ocupará el sucesor de p
    Node *& ref_to_stack_top = avl_stack.top();

        // encuentre el sucesor a la vez que actualiza la pila
    Node *fSucc = p;        // padre del sucesor
    Node *succ  = RLINK(p); // búsqueda comienza desde RLINK(p)
    avl_stack.push(succ);
    while (LLINK(succ) != Node::NullPtr) // descienda hasta el más a la izquierda
      {
        fSucc = succ;
        succ  = LLINK(succ);
        avl_stack.push(succ);
      }
        
        // actualice antigua entrada de pila ocupada por p. Estas operaciones 
        // son equivalentes a intercambiar el antiguo tope (antes de buscar 
        // sucesor) con el actual 
    ref_to_stack_top = succ; 
    avl_stack.top()  = p;    

        // actualice el nuevo hijo de pp (el sucesor)
    if (LLINK(pp) == p)
      LLINK(pp) = succ;
    else
      RLINK(pp) = succ;
      
        // intercambie las ramas izquierdas
    LLINK(succ) = LLINK(p);
    LLINK(p)    = Node::NullPtr; 

        // actualice ramas derechas
    if (RLINK(p) == succ) 
      {     // sucesor es exactamente el hijo derecho de p
        RLINK(p)    = RLINK(succ); 
        RLINK(succ) = p;
        pp          = succ;
      }
    else
      {     // sucesor es el descendiente más a la izquierda de RLINK(p)
        Node *succr  = RLINK(succ); 
        RLINK(succ)  = RLINK(p);
        LLINK(fSucc) = p;
        RLINK(p)     = succr;
        pp           = fSucc;
      }
    DIFF(succ) = DIFF(p); // intercambie factores de equilibrio

    return succ;
  }
  void restore_avl_after_deletion(const Key & key)
  {
    Node* pp = avl_stack.top(1); // padre de p

    Node* ppp = avl_stack.popn(3); // elimina de pila p, su padre y su abuelo

    while (true)
      {    // actualice factores de equilibrio
        if (key >= KEY(pp)) 
          DIFF(pp)--;
        else
          DIFF(pp)++;
            
        if (DIFF(pp) == -2 or DIFF(pp) == 2) // verifique una violación AVL
          pp = restore_avl(pp, ppp);

        if (DIFF(pp) != 0 or pp == root)
          break; // altura global del árbol no ha cambiado ==> terminar

        pp  = ppp; // avance al próximo ascendiente
        ppp = avl_stack.pop();
      }

      clean_avl_stack();
    }

public:

  Gen_Avl_Tree() : head_ptr(&head_node), root(RLINK (head_ptr))
  {
    avl_stack.push(head_ptr);
  }

  virtual ~Gen_Avl_Tree() { I(avl_stack_empty()); }

  Node *& getRoot() { return root; }

  Node * search(const Key& key) const 
  { 
    return searchInBinTree<Node, Compare>(root, key); 
  }
  Node * insert(Node * p)
  {
    if (root == Node::NullPtr)
      {
        root = p;
        return p;
      }
   
    Node *pp = search_and_stack_avl(KEY(p));

    if (cmp (KEY(p), KEY(pp))) 
      LLINK (pp) = p;
    else if (cmp (KEY(pp), KEY(p)))
      RLINK(pp) = p;
    else
      { // clave duplicada
        clean_avl_stack();

        return NULL;  
      }

    restore_avl_after_insertion(KEY(p));

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

    if (no_equals<Key, Compare> (KEY(p), key))
      {     // clave no fue encontrada
        clean_avl_stack();

        return NULL;
      }

    Key removed_key = KEY(p);
    Node * pp = avl_stack.top(1); // obtener padre de p
       
    while (true) 
      {
        if (LLINK(p) == Node::NullPtr) // ¿Está incompleto por la izquierda?
          {      // Sí, ate a pp el hijo de p 
            if (LLINK(pp) == p)
              LLINK(pp) = RLINK(p);
            else
              RLINK(pp) = RLINK(p);

            break;
          }

        if (RLINK(p) == Node::NullPtr) // ¿Está incompleto por la izquierda?
          {     // Sí, ate a pp el hijo de p 
            if (LLINK(pp) == p)
              LLINK(pp) = LLINK(p);
            else
              RLINK(pp) = LLINK(p);

            break;
          }

            // en este punto, p es un nodo completo ==> intercambiar por sucesor 
        Node * succ = swapWithSuccessor(p, pp);
        removed_key = KEY(succ);
      }

     p->reset();


     if (pp == head_ptr) // verifique si se eliminó la raíz
       {     // En este caso, los factores quedan inalterados y no se viola 
             // la condición AVL   
         clean_avl_stack();

         return p;
       }

    restore_avl_after_deletion(removed_key);

    return p;
  }
};

    template <typename Key, class Compare = Aleph::less<Key> >
class Avl_Tree : public Gen_Avl_Tree<AvlNode, Key, Compare>
{ /* empty */ };

    template <typename Key, class Compare = Aleph::less<Key> >
class Avl_Tree_Vtl : public Gen_Avl_Tree<AvlNodeVtl, Key, Compare>
{ /* empty */ };

} // end namespace Aleph
# endif // TPL_AVL_H

---