tpl_splay_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_SPLAY_TREE_H
# define TPL_SPLAY_TREE_H

# include <tpl_binNode.H>
# include <tpl_binNodeUtils.H>
# include <tpl_arrayStack.H> 

using namespace Aleph;

namespace Aleph {

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

public:

  typedef NodeType<Key> Node;

private:

  Gen_Splay_Tree(const Gen_Splay_Tree&);

  Gen_Splay_Tree& operator = (const Gen_Splay_Tree&);

  static Node * zig_zig_right(Node* p)
  {
    Node * q = LLINK(p);
    Node * r = LLINK(q);
    LLINK(p) = RLINK(q);
    LLINK(q) = RLINK(r);
    RLINK(q) = p;
    RLINK(r) = q;

    return r;
  }

  static Node * zig_zig_left(Node* p)
  {
    Node * q = RLINK(p);
    Node * r = RLINK(q);
    RLINK(p) = LLINK(q);
    RLINK(q) = LLINK(r);
    LLINK(q) = p;
    LLINK(r) = q;

    return r;
  }

  static Node * zig_zag_right(Node* p)
  {
    LLINK(p) = rotate_to_left(LLINK(p));
    return rotate_to_right(p);
  } 

  static Node * zig_zag_left(Node* p)
  {
    RLINK(p) = rotate_to_right(RLINK(p));
    return rotate_to_left(p);
  } 


  struct Node_Desc
  {
    Node *  node;
    Node ** node_parent;

    Node_Desc() { /* empty */ }

    Node_Desc(Node * p, Node ** pp) : node(p), node_parent(pp) { /* empty */ }

  };
  ArrayStack<Node_Desc, Node::MaxHeight> splay_stack;
  void push_in_splay_stack(Node * p, Node ** pp)
  {
    try 
      {
        splay_stack.push(Node_Desc(p, pp));
      }
    catch (std::overflow_error) 
      {
        splay_stack.empty();
        throw;
      }
  }    
  void search_and_push_in_splay_stack(const Key & key) 
  {
    splay_stack.empty();

    Node ** pp = &RLINK(head);
    Node * p   = root;
      
    while (p != NULL) // buscar iterativamente key
      {
        push_in_splay_stack(p, pp);
   
        if (Compare()(key, KEY(p)))
          {
            pp = &LLINK(p); 
            p  = LLINK(p); 
          }
        else if (Compare()(KEY(p), key))
          {
            pp = &RLINK(p); 
            p  = RLINK(p); 
          }
        else
          return;
      }
  }
  Node  head_node;  
  Node  *head;     
  Node *&root;
  enum Zig_Type { ZIG_LEFT, ZIG_RIGHT, ZIG_ZAG_LEFT, ZIG_ZAG_RIGHT, 
                  ZIG_ZIG_LEFT, ZIG_ZIG_RIGHT };

  Zig_Type zig_type(Node *& p, Node **& pp) 
  { 

    I(splay_stack.size() >= 2);

    Node_Desc first  = splay_stack.pop();
    Node_Desc second = splay_stack.pop();
    
    Zig_Type ret_val = 
      Compare()(KEY(second.node), KEY(first.node)) ? ZIG_LEFT : ZIG_RIGHT; 
       
    if (splay_stack.is_empty())
      { /* última etapa y es un zig */
        p  = second.node;
        pp = second.node_parent;

        return ret_val;
      }
   
    Node_Desc third = splay_stack.pop();
       
    pp = third.node_parent;
    p  = third.node;
    
    if (ret_val == ZIG_LEFT)
      return Compare()(KEY(third.node), KEY(second.node)) 
        ? ZIG_ZIG_LEFT : ZIG_ZAG_RIGHT;

    return Compare()(KEY(second.node), KEY(third.node))
      ? ZIG_ZIG_RIGHT : ZIG_ZAG_LEFT;
  }
  void splay()
  {
    if (splay_stack.is_empty() or splay_stack.top().node == root)
      return;

    Node **pp, *p; 
    while (true)
      {
        switch (zig_type(p, pp))
          {
          case ZIG_LEFT:      *pp = rotate_to_left(p);  break;
          case ZIG_RIGHT:     *pp = rotate_to_right(p); break;
          case ZIG_ZIG_LEFT:  *pp = zig_zig_left(p);  break;
          case ZIG_ZIG_RIGHT: *pp = zig_zig_right(p); break;
          case ZIG_ZAG_LEFT:  *pp = zig_zag_left(p);  break;
          case ZIG_ZAG_RIGHT: *pp = zig_zag_right(p); break;

          default: ERROR("Invalid rotation type");

          }
        
        if (splay_stack.is_empty())
          break;

        push_in_splay_stack(p, pp);
      }
  }

public:

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

  Node*& getRoot() const { return root; }

  Gen_Splay_Tree() : head(&head_node), root(RLINK(head)) { /* Empty */ }
  Node * search(const Key & key)
  {
    if (root == NULL)
      return NULL;

    search_and_push_in_splay_stack(key);

    splay();

    if (are_equals<Key, Compare>(key, KEY(root)))
      return root;

    return NULL;
  }
  Node * insert(Node * p)
  {
    if (root == NULL)
      { 
        root = p;
        return root;
      }

    search_and_push_in_splay_stack(KEY(p)); 

    Node * pp = splay_stack.top().node;

        // meter p en la pila
    if (Compare()(KEY(p), KEY(pp))) 
      {
        LLINK(pp) = p;
        push_in_splay_stack(p, &LLINK(pp));
      }
    else if (Compare()(KEY(pp), KEY(p)))
      {
        RLINK(pp) = p;
        push_in_splay_stack(p, &RLINK(pp));
      }
    else
      {     // clave duplicada
        splay(); // de todos modos hacemos el splay
        
        return NULL; 
      }

    splay();

    return root;
  }
  Node * remove(const Key & key)
  {
    search_and_push_in_splay_stack(key);

    splay(); // Suba el nodo hasta la raíz mediante el splay
   
    if (no_equals<Key, Compare>(KEY(root), key)) // ¿se encontró key?
      return NULL; // no

    Node * p = root;
    root = join_exclusive(LLINK(root), RLINK(root)); 
    p->reset();

    return p;
  }
};

    template <typename Key, class Compare = Aleph::less<Key> >
struct Splay_Tree : public Gen_Splay_Tree<BinNode, Key, Compare>
{ /* Empty */ };

    template <typename Key, class Compare = Aleph::less<Key> >
struct Splay_Tree_Vtl : public Gen_Splay_Tree<BinNodeVtl, Key, Compare>
{ /* Empty */ };


} // end namespace Aleph
# endif /* TPL_SPLAY_TREE_H */

---