tpl_binHeap.H

# ifndef TPL_BINHEAP_H
# define TPL_BINHEAP_H

# include <ahDefs.H>
# include <ahUtils.H>
# include <ahFunction.H>
# include <tpl_binNode.H>
# include <tpl_dynListQueue.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
{
  Compare & cmp;

public:

  typedef NodeType<Key> Node;

  Compare & key_comp() { return cmp; }

  Compare & get_compare() { return cmp; }

private:

    Node     head_node;
    Node *   head;
    Node *&  root;
    Node *   last;
    size_t   num_nodes;

public:

  void swap(GenBinHeap & h)
  {
    std::swap(root, h.root);
    std::swap(last, h.last);
    std::swap(num_nodes, h.num_nodes);
    std::swap(cmp, h.cmp);
  }

private:

  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);
    I(p != root);

    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?

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

    if (pp == root) 
      root = p;

    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 cmp (KEY(p), KEY(ULINK(p))))
      swap_with_parent(p);
  }

  virtual void sift_down(Node * p)
  {
    while (not IS_LEAF(p))
      {
        Node * cp = LLINK(p);  // guarda el menor hijo de p
        if (has_sibling(cp))
          if (cmp (KEY(RLINK(p)), KEY(LLINK(p))))
            cp = RLINK(p);

        if (cmp (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)
          std::swap(ULINK(root), ULINK(last));
        else
          {
            ULINK(root) = last;
            ULINK(root) = head;
          }

        std::swap(LLINK(root), LLINK(last));
        std::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;
      }

    std::swap(CTRL_BITS(root), CTRL_BITS(last));
    std::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:

  Node * getRoot() { return root; }

  Node * getRoot() const { return const_cast<Node*>(root); }

  template <class Op>
  void for_each_in_preorder(Node * p, Op & op)
  {
    if (p == NULL)
      return;

    op(p);

    for_each_in_preorder(advance_left(p), op);
    for_each_in_preorder(advance_right(p), op);    
  }

  template <class Op>
  void for_each_in_preorder(Node * p, Op && op())
  {
    return for_each_in_preorder<Op>(p, op);
  }

private:

  template <class Op>
  bool __level_traverse(Node * root, Op & operation)
  {
    if (root == NULL)
      return true;

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

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

        if (not operation(p))
          return false;

        Node * c = advance_left(p);
        if (c == NULL)
          continue;

        queue.put(c);

        c = advance_right(p);
        if (c != NULL)
          queue.put(c);
      }

    return true;
  }

public:

  template <class Op>
  bool level_traverse(Node * root, Op & operation)
  {
    return __level_traverse(root, operation);
  }

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

  template <class Op>
  bool level_traverse(Node * root, Op & operation) const
  {
    return const_cast<GenBinHeap&>(*this).__level_traverse(root, operation);
  }

  template <class Op>
  bool level_traverse(Node * root, Op && operation = Op()) const
  {
    return const_cast<GenBinHeap&>(*this).__level_traverse(root, operation);
  }

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

  GenBinHeap(Compare && __cmp = Compare()) 
    : GenBinHeap(__cmp)
  {
    // 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;
  }

  Node * getMax() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  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);

    root = NULL; // reiniciar como si fuese constructor
    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 (cmp (KEY(left_link), KEY(p))) 
      return false;

    Node * right_link = advance_right(p);

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

    if (cmp (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> >
struct BinHeap : public GenBinHeap<BinHeapNode, Key, Compare>
{
  typedef BinHeapNode<Key> Node;

  using GenBinHeap<BinHeapNode, Key, Compare>::GenBinHeap;
};

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

  using GenBinHeap<BinHeapNodeVtl, Key, Compare>::GenBinHeap;
};

# undef PREV
# undef NEXT
# undef ULINK
# undef IS_LEAF
# undef IS_LEFT
# undef CTRL_BITS
} // end namespace Aleph
# endif //  TPL_BINHEAP_H