tpl_binHeap.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_BINHEAP_H
# define TPL_BINHEAP_H

# include <ahDefs.H>
# include <ahUtils.H>
# include <ahFunction.H>
# include <tpl_binNode.H>

namespace Aleph {

class BinHeapNode_Data
{
  struct Control_Fields // Definición de banderas de control
  {
    int is_leaf : 4; // true si el nodo es hoja
    int is_left : 4; // true si el nodo es hijo izquierdo
  };

  BinHeapNode_Data * pLink; // puntero al padre

  Control_Fields control_fields;

public:


  BinHeapNode_Data() : pLink(NULL)
  { 
    control_fields.is_leaf = true;
    control_fields.is_left = true;
  }

  BinHeapNode_Data *& getU() { return pLink; }

  Control_Fields & get_control_fields() { return control_fields; }

  void reset()
  {
    control_fields.is_leaf = true;
    control_fields.is_left = true;
  }
};

DECLARE_BINNODE(BinHeapNode, 64, BinHeapNode_Data);


# define PREV(p)      (p->getL())
# define NEXT(p)      (p->getR())
# define ULINK(p)     reinterpret_cast<Node*&>((p)->getU())
# define IS_LEAF(p)   ((p)->get_control_fields().is_leaf)
# define IS_LEFT(p)   ((p)->get_control_fields().is_left)
# define CTRL_BITS(p) ((p)->get_control_fields())

    template <template <class> class NodeType, 
              typename Key, 
              class Compare = Aleph::less<Key> >
class GenBinHeap
{

public:

  typedef NodeType<Key> Node;

private:

    Node     head_node;
    Node *   head;
    Node *&  root;
    Node *   last;
    size_t   num_nodes;
  static bool is_in_list(Node * p)
  {
    if (IS_LEAF(p))
      return true;

    return ULINK(LLINK(p)) == RLINK(LLINK(p));
  }
  static bool has_sibling(Node * p)
  {
    return ULINK(p) != RLINK(p);
  }
  void swap_with_parent(Node * p)
  {
    I(num_nodes >= 2);

    Node *pp = ULINK(p); // padre de p

    const bool p_has_sibling = has_sibling(p); 
    const bool p_is_in_list  = is_in_list(p);  // ¿p está en último nivel?
    const bool pp_is_in_list = is_in_list(pp); // ¿p == last & LLINK(pp) == last?
    const bool p_has_child   = not IS_LEAF(p); // ¿p tiene hijos?

    Aleph::swap(CTRL_BITS(pp), CTRL_BITS(p)); // swap de banderas

    Node *ppp = ULINK(pp); // abuelo de p; padre de pp

    ULINK(pp) = p;  // Actualizar ULINK
    ULINK(p) = ppp;

    if (LLINK(ppp) == pp)
      LLINK(ppp) = p;
    else
      RLINK(ppp) = p;

    Node *sp = NULL;  // guarda hermano de p
    if (p_has_sibling) 
      {
        sp = p == LLINK(pp) ? RLINK(pp) : LLINK(pp); // hermano de p
        I(ULINK(sp) == pp);
        ULINK(sp) = p;
      }

    if (p == last) // ¿actualizar last?
      last = pp;
    
    if (num_nodes == 2)
      return;

    Node *lcp = LLINK(p); // respaldo de hijos de p
    Node *rcp = RLINK(p);
   
    if (num_nodes == 3)
      {
        if (RLINK(pp) == p)
          {
            LLINK(lcp) = RLINK(lcp) = pp;
            RLINK(pp)  = lcp;
            RLINK(p)   = pp;
          }
        else
          {
            LLINK(rcp) = RLINK(rcp) = pp;
            LLINK(pp)  = rcp;
            LLINK(p)   = pp;
          }

        return;
      }

    if (not p_is_in_list)
      {
        ULINK(lcp) = ULINK(rcp) = pp;

        if (LLINK(pp) == p)
          {
            I(RLINK(pp) == sp);
            LLINK(p) = pp;
            RLINK(p) = RLINK(pp);
          }
        else
          {
            I(LLINK(pp) == sp);
            RLINK(p) = pp;
            LLINK(p) = LLINK(pp);
          }

        LLINK(pp) = lcp;
        RLINK(pp) = rcp;

        return;
      }
      
    if (not pp_is_in_list)
      {
        if (p_has_child)
          ULINK(LLINK(p)) = pp;

        RLINK(lcp) = LLINK(rcp) = pp;

        if (LLINK(pp) == p)
          {
            I(RLINK(pp) == sp);
            LLINK(p) = pp;
            RLINK(p) = RLINK(pp);
          }
        else
          {
            I(LLINK(pp) == sp);
            RLINK(p)  = pp;
            LLINK(p)  = LLINK(pp);
          }

        LLINK(pp) = lcp;
        RLINK(pp) = rcp;

        return;
      }
      
    RLINK(lcp)       = pp;
    LLINK(RLINK(pp)) = p;
    LLINK(pp)        = lcp;
    RLINK(p)         = RLINK(pp);
    RLINK(pp)        = p;
    LLINK(p)         = pp;
  }
  virtual void sift_up(Node * p)
  {
    while (p != root and Compare() (KEY(p), KEY(ULINK(p))))
      swap_with_parent(p);
  }

  virtual void sift_down(Node * p)
  {
    Node *cp; // guarda el menor hijo de p

    while (not IS_LEAF(p))
      {
        cp = LLINK(p); 
        
        if (has_sibling(cp))
          if (Compare() (KEY(RLINK(p)), KEY(LLINK(p))))
            cp = RLINK(p);
          
        if (Compare() (KEY(p), KEY(cp)))
          return;

        swap_with_parent(cp);
      }
  }
  void swap_root_with_last()
  {
    I(num_nodes > 1);
    I(ULINK(root) == head);
    I(not IS_LEAF(root));
    I(IS_LEAF(last));

    if (num_nodes > 3) // caso general
      {
        Node * lRoot     = LLINK(root);
        Node * rRoot     = RLINK(root);
        Node * f_last    = ULINK(last);
        Node * prev_last = LLINK(last);
        Node * next_last = RLINK(last);

        if (LLINK(f_last) == last)
          LLINK(f_last) = root;
        else
          RLINK(f_last) = root;       
          
        if (RLINK(root) != last)
          Aleph::swap(ULINK(root), ULINK(last));
        else
          {
            ULINK(root) = last;
            ULINK(root) = head;
          }

        Aleph::swap(LLINK(root), LLINK(last));
        Aleph::swap(RLINK(root), RLINK(last));
        
        ULINK(lRoot) = ULINK(rRoot) = last;

        LLINK(last) = lRoot;
        RLINK(last) = rRoot;

        PREV(root) = prev_last;
        NEXT(root) = next_last;

        NEXT(prev_last) = PREV(next_last) = root;
      }      
    else if (num_nodes == 3) // caso particular con 3 nodos
      {
        I(RLINK(root) == last);
        I(LLINK(last) == LLINK(root) and RLINK(last) == LLINK(root));

        ULINK(last) = ULINK(root);
        ULINK(root) = last;

        Node *s_last  = LLINK(last);
        ULINK(s_last) = last;

        LLINK(last) = s_last;
        RLINK(last) = root;

        LLINK(root) = RLINK(root) = s_last;
        RLINK(s_last) = LLINK(s_last) = root;
      }
    else // casos particulares con num_nodes < 3
      {
        I(LLINK(root) == last);

        ULINK(last) = ULINK(root);
        ULINK(root) = last;
        RLINK(last) = LLINK(last) = root;
        RLINK(root) = LLINK(root) = last;
      }

    Aleph::swap(CTRL_BITS(root), CTRL_BITS(last));
    Aleph::swap(root, last);
  }
  Node * remove_last()
  {

    I(last != root and num_nodes > 0);
    I(IS_LEAF(last));

    Node * ret_val  = last;
    Node * pp       = ULINK(last);
    Node * new_last = LLINK(last);

    if (IS_LEFT(last))
      {
        IS_LEAF(pp) = true;
        LLINK(pp)   = new_last;
      }
    else
      {
        RLINK(pp)          = RLINK(last);
        LLINK(RLINK(last)) = pp;
      }

    RLINK(LLINK(last)) = pp;
    last = new_last;

    num_nodes--;

    ret_val->reset();

    return ret_val;
  }
  void replace_node(Node * node, Node * new_node)
  {
    I(node != new_node);
    I(node != last);

        // guardar los parientes inmediatos de node
    Node * parent = ULINK(node);
    Node * left_child  = LLINK(node);
    Node * right_child = RLINK(node);
      
        // actualizar los punteros pertenecientes a new_node
    ULINK(new_node) = parent;
    LLINK(new_node) = left_child;
    RLINK(new_node) = right_child;

        // actualizar padre
    if (IS_LEFT(node))
      {
        I(LLINK(parent) == node);
        LLINK(parent) = new_node;
      }
    else 
      {
        I(RLINK(parent) == node);
        RLINK(parent) = new_node;
      }

        // actualizar hijos
    if (IS_LEAF(node))
      {
        RLINK(left_child)  = new_node;
        LLINK(right_child) = new_node;
      }
    else 
      {
        ULINK(left_child) = new_node;

        if (ULINK(right_child) == node) // node pudiera tener sólo un hijo
          ULINK(right_child) = new_node;
        else
          {
            I(left_child == last);
            RLINK(left_child)  = new_node;
            LLINK(right_child) = new_node;
          }
      }
      
    CTRL_BITS(new_node) = CTRL_BITS(node);
  }
  static void __postorder_delete(Node * p, Node * incomplete_node)
  {
    if (IS_LEAF(p))
      {
        delete p;

        return;
      }

    __postorder_delete(LLINK(p), incomplete_node);

    if (p != incomplete_node)
      __postorder_delete(RLINK(p), incomplete_node); 

    delete p;
  }

public:

  GenBinHeap() 
    : head(&head_node), root(RLINK(head)), last(&head_node), num_nodes(0)
  { /* empty */ }

  virtual ~GenBinHeap() { /* Empty */ }
  Node * insert(Node * p)
  {

    I(IS_LEAF(p));

    if (root == NULL) // ¿heap está vacío?
      { // Sí, inicialice

        I(num_nodes == 0);

        root       = p;
        LLINK(p)   = RLINK(p) = p;
        ULINK(p)   = head;
        IS_LEAF(p) = true;
        IS_LEFT(p) = false; /* root is right child of header node */
        last      = root;
        num_nodes = 1;

        return p;
      }

     // inserción general

    Node * pp = RLINK(last); // padre de actual last

    LLINK(p) = last;
    ULINK(p) = pp;
      
    if (IS_LEFT(last)) 
      { // p será hijo derecho
        IS_LEFT(p)       = false;
        RLINK(p)         = RLINK(pp);
        LLINK(RLINK(pp)) = p;
        RLINK(pp)        = p;
      }
    else
      { // p será hijo izquierdo
        IS_LEFT(p) = true;
        RLINK(p)   = pp;
        IS_LEAF(pp) = false; // si p es izquierdo ==> pp era hoja
        LLINK(pp)   = p;
      }


    I(not IS_LEAF(pp));

    RLINK(last) = p;
    last        = p;

    num_nodes++;

    sift_up(last);

    return p;
  }
  Node * getMin() 

    throw(std::exception, std::underflow_error)

  {

    if (root == NULL)
      throw std::underflow_error ("Heap is empty");

    Node *ret_val = root;

    if (num_nodes == 1)
      {
        root = NULL;
        ret_val->reset();
        num_nodes = 0;
        return ret_val;
      }

    swap_root_with_last();

    remove_last();

    sift_down(root);

    ret_val->reset();

    return ret_val;
  }
  void update(Node * p)
  {
    sift_down(p);
    sift_up(p);
  }
  Node * remove(Node * node) throw(std::exception, std::underflow_error)
  {

    if (root == NULL)
      throw std::underflow_error ("Heap is empty");

    if (node == root)
      return getMin();

    if (node == last)
      return remove_last();

    Node * p = remove_last();

    if (node == last)
      {
        remove_last();
        insert(p);

        return node;
      }

    replace_node(node, p);

    update(p);

    node->reset();

    return node;
  }
  void remove_all_and_delete()
  {
    if (root == NULL)
      return;

    if (num_nodes <= 3)
      {
        while (not this->is_empty()) 
          delete getMin(); 

        return;
      }

    if (IS_LEFT(last))
      __postorder_delete(root, ULINK(last));
    else
      __postorder_delete(root, NULL);

        // reiniciar como si se hubiese llamado a constructor
    root = NULL;
    last = &head_node;
    num_nodes = 0;
  }
  Node * top() const throw(std::exception, std::underflow_error)
  {
    if (root == NULL)
      throw std::underflow_error ("Heap is empty");

    return root;
  }
  const size_t & size() const { return num_nodes; }

  bool is_empty() const { return size() == 0; }
  protected:

  Node * advance_left(Node * p)
  {
    if (IS_LEAF(p))
      return NULL;

    return LLINK(p);
  }

  Node * advance_right(Node * p)
  {
    I(not IS_LEAF(p));

    if (not has_sibling(LLINK(p)))
      return NULL;

    return RLINK(p);
  }

  virtual bool verify_heap(Node * p)
  {
    Node * left_link = advance_left(p);

    if (left_link == NULL)
      {
        I(IS_LEAF(p));

        return true;
      }

    if (Compare () (KEY(left_link), KEY(p)))
      return false;

    Node * right_link = advance_right(p);

    if (right_link == NULL)
      return verify_heap(left_link);

    if (Compare () (KEY(right_link), KEY(p)))
      return false;

    return verify_heap(right_link);
  }

  public:

  bool verify_heap()
  {
    if (root == NULL)
      return true;

    return verify_heap(root);
  }
};

    template <class Key, typename Compare = Aleph::less<Key> >
class BinHeap : public GenBinHeap<BinHeapNode, Key, Compare>
{

public:

  typedef BinHeapNode<Key> Node;
};
 
    template <class Key, typename Compare = Aleph::less<Key> >
class BinHeapVtl : public GenBinHeap<BinHeapNodeVtl, Key, Compare>
{

public:

  typedef BinHeapNodeVtl<Key> Node;
};

# undef PREV
# undef NEXT
# undef ULINK
# undef IS_LEAF
# undef IS_LEFT
# undef CTRL_BITS

} // end namespace Aleph
# endif //  TPL_BINHEAP_H

---