source: lemon-0.x/src/hugo/fib_heap.h @ 803:c3d832275e69

// -*- C++ -*-

#ifndef HUGO_FIB_HEAP_H
#define HUGO_FIB_HEAP_H

///\ingroup auxdat
///\file
///\brief Fibonacci Heap implementation.

#include <vector>
#include <functional>
#include <math.h>

namespace hugo {
  
  /// \addtogroup auxdat
  /// @{

  /// An implementation of the Fibonacci Heap.

  /**
     This class implements the \e Fibonacci \e heap data structure. A \e heap
     is a data structure for storing items with specified values called \e
     priorities, such that finding the item with minimum priority with respect
     to \e Compare is efficient. In a heap one can change the priority of an
     item, add or erase an item, etc.

     The methods \ref increase and \ref erase are not efficient in a Fibonacci
     heap. In case of many calls to these operations, it is better to use a
     \e binary \e heap.
     
     \param Item The type of the items to be stored.  
     \param Prio The type of the priority of the items.
     \param ItemIntMap A read and writable Item int map, for the usage of
     the heap.
     \param Compare A class for the comparison of the priorities. The
     default is \c std::less<Prio>.

  */

#ifdef DOXYGEN
  template <typename Item, 
            typename Prio, 
            typename ItemIntMap, 
            typename Compare>
#else
  template <typename Item, 
            typename Prio, 
            typename ItemIntMap, 
            typename Compare = std::less<Prio> >
#endif
  class FibHeap {
  public:     
    typedef Prio PrioType;
    
  private:
    class store;
    
    std::vector<store> container;
    int minimum;
    ItemIntMap &iimap;
    Compare comp;
    int num_items;
    
  public:
    enum state_enum {
      IN_HEAP = 0,
      PRE_HEAP = -1,
      POST_HEAP = -2
    };
    
    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
      iimap(_iimap), comp(_comp), num_items() {}
    
    ///The number of items stored in the heap.

    /**
       Returns the number of items stored in the heap.
    */
    int size() const { return num_items; }

    ///Checks if the heap stores no items.
    
    /**
       Returns \c true iff the heap stores no items.
    */
    bool empty() const { return num_items==0; }

    ///\c item gets to the heap with priority \c value independently if \c item was already there.

    /**
       This method calls \ref push(\c item, \c value) if \c item is not
       stored in the heap and it calls \ref decrease(\c item, \c value) or
       \ref increase(\c item, \c value) otherwise.
    */
    void set (Item const item, PrioType const value); 
    
    ///Adds \c item to the heap with priority \c value. 
    
    /**
       Adds \c item to the heap with priority \c value. 
       \pre \c item must not be stored in the heap. 
    */
    void push (Item const item, PrioType const value);
    
    
    ///Returns the item having the minimum priority w.r.t.  Compare.
    
    /**
       This method returns the item having the minimum priority w.r.t.  Compare. 
       \pre The heap must be nonempty.
    */
    Item top() const { return container[minimum].name; }
    

    ///Returns the minimum priority w.r.t.  Compare.

    /**
       It returns the minimum priority w.r.t.  Compare.
       \pre The heap must be nonempty.
    */
    PrioType prio() const { return container[minimum].prio; }
    

    ///Returns the priority of \c item.

    /**
       It returns the priority of \c item.
       \pre \c item must be in the heap.
    */
    PrioType& operator[](const Item& item) { 
      return container[iimap[item]].prio; 
    }
    
    ///Returns the priority of \c item.
    
    /**
       It returns the priority of \c item.
       \pre \c item must be in the heap.
    */
    const PrioType& operator[](const Item& item) const { 
      return container[iimap[item]].prio; 
    }


    ///Deletes the item with minimum priority w.r.t.  Compare.

    /**
    This method deletes the item with minimum priority w.r.t. 
    Compare from the heap.
    \pre The heap must be non-empty.
    */
    void pop();

    ///Deletes \c item from the heap.

    /**
       This method deletes \c item from the heap, if \c item was already
       stored in the heap. It is quite inefficient in Fibonacci heaps.
    */
    void erase (const Item& item); 

    ///Decreases the priority of \c item to \c value.

    /**
       This method decreases the priority of \c item to \c value.
       \pre \c item must be stored in the heap with priority at least \c
       value w.r.t.  Compare.
    */
    void decrease (Item item, PrioType const value); 


    ///Increases the priority of \c item to \c value.

    /**
       This method sets the priority of \c item to \c value. Though
       there is no precondition on the priority of \c item, this
       method should be used only if there is a need to really \e increase
       (w.r.t.  Compare) the priority of \c item, because this
       method is inefficient.
    */
    void increase (Item item, PrioType const value) {
      erase(item);
      push(item, value);
    }


    ///Tells if \c item is in, was already in, or has never been in the heap.

    /**
       This method returns PRE_HEAP if \c item has never been in the
       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
       otherwise. In the latter case it is possible that \c item will
       get back to the heap again.
    */
    state_enum state(const Item &item) const {
      int i=iimap[item];
      if( i>=0 ) {
        if ( container[i].in ) i=0;
        else i=-2; 
      }
      return state_enum(i);
    }    
    
  private:
    
    void balance();
    void makeroot(int c);
    void cut(int a, int b);
    void cascade(int a);
    void fuse(int a, int b);
    void unlace(int a);


    class store {
      friend class FibHeap;
      
      Item name;
      int parent;
      int left_neighbor;
      int right_neighbor;
      int child;
      int degree;  
      bool marked;
      bool in;
      PrioType prio;
      
      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
    };
  };    
 


    // **********************************************************************
    //  IMPLEMENTATIONS
    // **********************************************************************
    
  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
  (Item const item, PrioType const value) 
  {
    int i=iimap[item];
    if ( i >= 0 && container[i].in ) {
      if ( comp(value, container[i].prio) ) decrease(item, value); 
      if ( comp(container[i].prio, value) ) increase(item, value); 
    } else push(item, value);
  }
    
  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
  (Item const item, PrioType const value) {
      int i=iimap[item];      
      if ( i < 0 ) {
        int s=container.size();
        iimap.set( item, s );   
        store st;
        st.name=item;
        container.push_back(st);
        i=s;
      } else {
        container[i].parent=container[i].child=-1;
        container[i].degree=0;
        container[i].in=true;
        container[i].marked=false;
      }

      if ( num_items ) {
        container[container[minimum].right_neighbor].left_neighbor=i;
        container[i].right_neighbor=container[minimum].right_neighbor;
        container[minimum].right_neighbor=i;
        container[i].left_neighbor=minimum;
        if ( comp( value, container[minimum].prio) ) minimum=i; 
      } else {
        container[i].right_neighbor=container[i].left_neighbor=i;
        minimum=i;      
      }
      container[i].prio=value;
      ++num_items;
    }
    
  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
      /*The first case is that there are only one root.*/
      if ( container[minimum].left_neighbor==minimum ) {
        container[minimum].in=false;
        if ( container[minimum].degree!=0 ) { 
          makeroot(container[minimum].child);
          minimum=container[minimum].child;
          balance();
        }
      } else {
        int right=container[minimum].right_neighbor;
        unlace(minimum);
        container[minimum].in=false;
        if ( container[minimum].degree > 0 ) {
          int left=container[minimum].left_neighbor;
          int child=container[minimum].child;
          int last_child=container[child].left_neighbor;
        
          makeroot(child);
          
          container[left].right_neighbor=child;
          container[child].left_neighbor=left;
          container[right].left_neighbor=last_child;
          container[last_child].right_neighbor=right;
        }
        minimum=right;
        balance();
      } // the case where there are more roots
      --num_items;   
    }


  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
  (const Item& item) {
      int i=iimap[item];
      
      if ( i >= 0 && container[i].in ) {        
        if ( container[i].parent!=-1 ) {
          int p=container[i].parent;
          cut(i,p);         
          cascade(p);
        }
        minimum=i;     //As if its prio would be -infinity
        pop();
      }
  }
    
  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
  (Item item, PrioType const value) {
      int i=iimap[item];
      container[i].prio=value;
      int p=container[i].parent;
      
      if ( p!=-1 && comp(value, container[p].prio) ) {
        cut(i,p);           
        cascade(p);
      }      
      if ( comp(value, container[minimum].prio) ) minimum=i; 
  }
 

  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      

    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
  
    std::vector<int> A(maxdeg,-1); 
    
    /*
     *Recall that now minimum does not point to the minimum prio element.
     *We set minimum to this during balance().
     */
    int anchor=container[minimum].left_neighbor; 
    int next=minimum; 
    bool end=false; 
        
       do {
        int active=next;
        if ( anchor==active ) end=true;
        int d=container[active].degree;
        next=container[active].right_neighbor;

        while (A[d]!=-1) {        
          if( comp(container[active].prio, container[A[d]].prio) ) {
            fuse(active,A[d]); 
          } else { 
            fuse(A[d],active);
            active=A[d];
          } 
          A[d]=-1;
          ++d;
        }       
        A[d]=active;
       } while ( !end );


       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
       int s=minimum;
       int m=minimum;
       do {  
         if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
         s=container[s].right_neighbor;
       } while ( s != m );
    }

  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
  (int c) {
      int s=c;
      do {  
        container[s].parent=-1;
        s=container[s].right_neighbor;
      } while ( s != c );
    }
  
  
  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
  (int a, int b) {    
    /*
     *Replacing a from the children of b.
     */
    --container[b].degree;
    
    if ( container[b].degree !=0 ) {
      int child=container[b].child;
      if ( child==a ) 
        container[b].child=container[child].right_neighbor;
      unlace(a);
    }
    
    
    /*Lacing a to the roots.*/
    int right=container[minimum].right_neighbor;
    container[minimum].right_neighbor=a;
    container[a].left_neighbor=minimum;
    container[a].right_neighbor=right;
    container[right].left_neighbor=a;
    
    container[a].parent=-1;
    container[a].marked=false;
  }
  

  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
  (int a) 
    {
      if ( container[a].parent!=-1 ) {
        int p=container[a].parent;
        
        if ( container[a].marked==false ) container[a].marked=true;
        else {
          cut(a,p);
          cascade(p);
        }
      }
    }


  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
  (int a, int b) {
      unlace(b);
      
      /*Lacing b under a.*/
      container[b].parent=a;

      if (container[a].degree==0) {
        container[b].left_neighbor=b;
        container[b].right_neighbor=b;
        container[a].child=b;   
      } else {
        int child=container[a].child;
        int last_child=container[child].left_neighbor;
        container[child].left_neighbor=b;
        container[b].right_neighbor=child;
        container[last_child].right_neighbor=b;
        container[b].left_neighbor=last_child;
      }

      ++container[a].degree;
      
      container[b].marked=false;
    }

  
  /*
   *It is invoked only if a has siblings.
   */
  template <typename Item, typename Prio, typename ItemIntMap, 
    typename Compare>
  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
  (int a) {      
      int leftn=container[a].left_neighbor;
      int rightn=container[a].right_neighbor;
      container[leftn].right_neighbor=rightn;
      container[rightn].left_neighbor=leftn;
  }
  
  ///@}

} //namespace hugo

#endif //HUGO_FIB_HEAP_H