jacint@159: // -*- C++ -*-
jacint@159: /*
jacint@159:  *template <typename Item, 
jacint@159:  *          typename Prio, 
jacint@159:  *          typename ItemIntMap, 
jacint@159:  *          typename Compare = std::less<Prio> >
jacint@159:  * 
jacint@159:  *constructors:
jacint@159:  *
jacint@159:  *FibHeap(ItemIntMap),   FibHeap(ItemIntMap, Compare)
jacint@159:  *
jacint@159:  *Member functions:
jacint@159:  *
jacint@159:  *int size() : returns the number of elements in the heap
jacint@159:  *
jacint@159:  *bool empty() : true iff size()=0
jacint@159:  *
jacint@161:  *void set(Item, Prio) : calls push(Item, Prio) if Item is not
jacint@161:  *     in the heap, and calls decrease/increase(Item, Prio) otherwise
jacint@161:  *
jacint@161:  *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
jacint@161:  *     mustn't be in the heap.
jacint@159:  *
jacint@159:  *Item top() : returns the Item with least Prio
jacint@159:  *
jacint@159:  *Prio prio() : returns the least Prio
jacint@159:  *  
jacint@159:  *Prio get(Item) : returns Prio of Item
jacint@159:  *
jacint@159:  *void pop() : deletes the Item with least Prio
jacint@159:  *
jacint@159:  *void erase(Item) : deletes Item from the heap if it was already there
jacint@159:  *
jacint@161:  *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap 
jacint@161:  *     with prio at least P.
jacint@159:  *
jacint@161:  *void increase(Item, P) : sets prio of Item to P. 
jacint@159:  *
jacint@159:  *
jacint@159:  *In Fibonacci heaps, increase and erase are not efficient, in case of
jacint@159:  *many calls to these operations, it is better to use bin_heap.
jacint@159:  */
jacint@159: 
jacint@159: #ifndef FIB_HEAP_H
jacint@159: #define FIB_HEAP_H
jacint@159: 
jacint@159: #include <vector>
jacint@159: #include <functional>
jacint@159: #include <math.h>
jacint@159: 
jacint@159: namespace hugo {
jacint@159:   
jacint@159:   template <typename Item, typename Prio, typename ItemIntMap, 
jacint@159:     typename Compare = std::less<Prio> >
jacint@159:  
jacint@159:   class FibHeap {
jacint@159:   
jacint@159:     typedef Prio PrioType;
jacint@159:     
jacint@159:     class store;
jacint@159:     
jacint@159:     std::vector<store> container;
jacint@159:     int minimum;
jacint@159:     bool blank;
jacint@159:     ItemIntMap &iimap;
jacint@159:     Compare comp;
jacint@159:     
jacint@159:   public :
jacint@159:     
jacint@159:     FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {} 
jacint@159:     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 
jacint@159:       blank(true), iimap(_iimap), comp(_comp) {}
jacint@159:     
jacint@159:     
jacint@159:     int size() const {
jacint@159:       int s=0;
jacint@159:       for ( unsigned int i=0; i!=container.size(); ++i )
jacint@159: 	if ( container[i].in ) ++s;
jacint@159:       return s; 
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@161:     bool empty() const { return blank; }
jacint@161: 
jacint@161: 
jacint@161:     void set (Item const it, PrioType const value) {
jacint@161:       int i=iimap.get(it);
jacint@161:       if ( i >= 0 && container[i].in ) {
jacint@161: 	if ( !comp(container[i].prio, value) ) decrease(it, value); 
jacint@161: 	if ( comp(container[i].prio, value) ) increase(it, value); 
jacint@161:       } else push(it, value);
jacint@161:     }
jacint@159:     
jacint@161: 
jacint@161:     void push (Item const it, PrioType const value) {
jacint@161:       int i=iimap.get(it);      
jacint@161:       if ( i < 0 ) {
jacint@161: 	int s=container.size();
jacint@161: 	iimap.set( it, s );	
jacint@161: 	store st;
jacint@161: 	st.name=it;
jacint@161: 	container.push_back(st);
jacint@161: 	i=s;
jacint@161:       }
jacint@161:       
jacint@161:       if ( !blank ) {
jacint@161: 	container[container[minimum].right_neighbor].left_neighbor=i;
jacint@161: 	container[i].right_neighbor=container[minimum].right_neighbor;
jacint@161: 	container[minimum].right_neighbor=i;
jacint@161: 	container[i].left_neighbor=minimum;
jacint@161: 	if ( !comp( container[minimum].prio, value) ) minimum=i; 
jacint@161: 	
jacint@161:       } else {
jacint@161: 	container[i].right_neighbor=container[i].left_neighbor=i;
jacint@161: 	minimum=i;	
jacint@161: 	blank=false;
jacint@161:       }
jacint@161:       container[i].prio=value;
jacint@161:     }
jacint@159:     
jacint@159: 
jacint@159: 
jacint@159:     Item top() const {
jacint@159:       if ( !blank ) { 
jacint@159: 	return container[minimum].name;
jacint@159:       } else {
jacint@159: 	return Item();
jacint@159:       }
jacint@159:     }
jacint@159:     
jacint@159:     
jacint@159:     PrioType prio() const {
jacint@159:       if ( !blank ) { 
jacint@159: 	return container[minimum].prio;
jacint@159:       } else {
jacint@159: 	return PrioType();
jacint@159:       }
jacint@159:     }
jacint@159:     
jacint@159: 
jacint@159:     const PrioType get(const Item& it) const
jacint@159:     {
jacint@159:       int i=iimap.get(it);
jacint@159:       
jacint@159:       if ( i >= 0 && container[i].in ) { 
jacint@159: 	return container[i].prio;
jacint@159:       } else {
jacint@159: 	return PrioType();
jacint@159:       }
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@159:     void pop() {
jacint@159:       if ( !blank ) {
jacint@159: 	
jacint@159: 	/*The first case is that there are only one root.*/
jacint@159: 	if ( container[minimum].left_neighbor==minimum ) {
jacint@159: 	  container[minimum].in=false;
jacint@159: 	  if ( container[minimum].degree==0 ) blank=true; 
jacint@159: 	  else { 
jacint@159: 	    makeroot(container[minimum].child);
jacint@159: 	    minimum=container[minimum].child;
jacint@159: 	    balance();
jacint@159: 	  } 
jacint@159:        } else {
jacint@159: 	 int right=container[minimum].right_neighbor;
jacint@159: 	 unlace(minimum);
jacint@159: 	 container[minimum].in=false;
jacint@159: 	 if ( container[minimum].degree > 0 ) {
jacint@159: 	   int left=container[minimum].left_neighbor;
jacint@159: 	   int child=container[minimum].child;
jacint@159: 	   int last_child=container[child].left_neighbor;
jacint@159: 	   
jacint@159: 	   container[left].right_neighbor=child;
jacint@159: 	   container[child].left_neighbor=left;
jacint@159: 	   container[right].left_neighbor=last_child;
jacint@159: 	   container[last_child].right_neighbor=right;
jacint@159: 	   
jacint@159: 	   makeroot(child);
jacint@159: 	 }
jacint@159: 	 minimum=right;
jacint@159: 	 balance();
jacint@159:        } // the case where there are more roots
jacint@159:      } 
jacint@159:    }
jacint@159: 
jacint@159:     
jacint@159:    void erase (const Item& it) {
jacint@159:      int i=iimap.get(it);
jacint@159:      
jacint@159:      if ( i >= 0 && container[i].in ) { 
jacint@159: 	
jacint@159:        if ( container[i].parent!=-1 ) {
jacint@159: 	 int p=container[i].parent;
jacint@159: 	 cut(i,p);	    
jacint@159: 	 cascade(p);
jacint@159: 	 minimum=i;     //As if its prio would be -infinity
jacint@159:        }
jacint@159:        pop();
jacint@159:      }
jacint@159:    }
jacint@159:     
jacint@159: 
jacint@161:     void decrease (Item it, PrioType const value) {
jacint@161:       int i=iimap.get(it);
jacint@161:       container[i].prio=value;
jacint@161:       int p=container[i].parent;
jacint@161:  
jacint@161:       if ( p!=-1 && comp(value, container[p].prio) ) {
jacint@161: 	cut(i,p);	    
jacint@161: 	cascade(p);
jacint@161: 	if ( comp(value, container[minimum].prio) ) minimum=i; 
jacint@161:       }
jacint@161:     }
jacint@159:    
jacint@159: 
jacint@159:     void increase (Item it, PrioType const value) {
jacint@161:       erase(it);
jacint@161:       push(it, value);
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@159:   private:
jacint@159:     
jacint@159:     void balance() {      
jacint@159:     int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
jacint@159:   
jacint@159:     std::vector<int> A(maxdeg,-1); 
jacint@159:     
jacint@159:     /*
jacint@159:      *Recall that now minimum does not point to the minimum prio element.
jacint@159:      *We set minimum to this during balance().
jacint@159:      */
jacint@159:     int anchor=container[minimum].left_neighbor; 
jacint@159:     int next=minimum; 
jacint@159:     bool end=false; 
jacint@159:     	
jacint@159:        do {
jacint@159: 	int active=next;
jacint@159: 	int d=container[active].degree;
jacint@159: 	if ( anchor==active ) end=true;
jacint@159: 	next = container[active].right_neighbor;
jacint@159: 	if ( !comp(container[minimum].prio, container[active].prio) )
jacint@159: 	  minimum=active;
jacint@159: 
jacint@159: 	while (A[d]!=-1) {
jacint@159: 	  
jacint@159: 	  if( comp(container[active].prio, container[A[d]].prio) ) {
jacint@159: 	    fuse(active,A[d]); 
jacint@159: 	  } else { 
jacint@159: 	    fuse(A[d],active);
jacint@159: 	    active=A[d];
jacint@159: 	  } 
jacint@159: 	  A[d]=-1;
jacint@159: 	  ++d;
jacint@159: 	}
jacint@159: 	
jacint@159: 	A[d]=active;
jacint@159:        } while ( !end );
jacint@159:   }
jacint@159: 
jacint@159: 
jacint@159: 
jacint@159: 
jacint@159:     /*
jacint@159:      *All the siblings of a are made roots.
jacint@159:      */
jacint@159:     void makeroot (int c)  
jacint@159:     {
jacint@159:       int s=c;
jacint@159:       do {  
jacint@159: 	container[s].parent=-1;
jacint@159: 	s=container[s].right_neighbor;
jacint@159:       } while ( s != c );
jacint@159:     }
jacint@159:     
jacint@159: 
jacint@159:     void cut (int a, int b) 
jacint@159:     {    
jacint@159: 
jacint@159:       /*
jacint@159:        *Replacing a from the children of b.
jacint@159:        */
jacint@159:       --container[b].degree;
jacint@159: 
jacint@159:       if ( container[b].degree !=0 ) {
jacint@159:       int child=container[b].child;
jacint@159:       if ( child==a ) 
jacint@159: 	container[b].child=container[child].right_neighbor;
jacint@159:       
jacint@159:       unlace(a);
jacint@159: 	
jacint@159:       }
jacint@159:     
jacint@159: 
jacint@159:       /*Lacing i to the roots.*/
jacint@159:       int right=container[minimum].right_neighbor;
jacint@159:       container[minimum].right_neighbor=a;
jacint@159:       container[a].left_neighbor=minimum;
jacint@159:       container[a].right_neighbor=right;
jacint@159:       container[right].left_neighbor=a;
jacint@159: 
jacint@159:       container[a].parent=-1;
jacint@159:       container[a].marked=false;
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@159:     void cascade (int a) 
jacint@159:     {
jacint@159:       if ( container[a].parent!=-1 ) {
jacint@159: 	int p=container[a].parent;
jacint@159: 	
jacint@159: 	if ( container[a].marked==false ) container[a].marked=true;
jacint@159: 	else {
jacint@159: 	  cut(a,p);
jacint@159: 	  cascade(p);
jacint@159: 	}
jacint@159:       }
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@159:     void fuse (int a, int b) 
jacint@159:     {
jacint@159:       
jacint@159:       unlace(b);
jacint@159: 
jacint@159:       
jacint@159:       /*Lacing b under a.*/
jacint@159:       container[b].parent=a;
jacint@159: 
jacint@159:       if (container[a].degree==0) {
jacint@159: 	container[b].left_neighbor=b;
jacint@159: 	container[b].right_neighbor=b;
jacint@159: 	container[a].child=b;	
jacint@159:       } else {
jacint@159: 	int child=container[a].child;
jacint@159: 	int last_child=container[child].left_neighbor;
jacint@159: 	container[child].left_neighbor=b;
jacint@159: 	container[b].right_neighbor=child;
jacint@159: 	container[last_child].right_neighbor=b;
jacint@159: 	container[b].left_neighbor=last_child;
jacint@159:       }
jacint@159: 
jacint@159:       ++container[a].degree;
jacint@159:       
jacint@159:       container[b].marked=false;
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@159:     /*
jacint@159:      *It is invoked only if a has siblings.
jacint@159:      */
jacint@159: 
jacint@159:     void unlace (int a) {      
jacint@159:       int leftn=container[a].left_neighbor;
jacint@159:       int rightn=container[a].right_neighbor;
jacint@159:       container[leftn].right_neighbor=rightn;
jacint@159:       container[rightn].left_neighbor=leftn;
jacint@159:     }
jacint@159: 
jacint@159: 
jacint@159:     class store {
jacint@159:       friend class FibHeap;
jacint@159:       
jacint@159:       Item name;
jacint@159:       int parent;
jacint@159:       int left_neighbor;
jacint@159:       int right_neighbor;
jacint@159:       int child;
jacint@159:       int degree;  
jacint@159:       bool marked;
jacint@159:       bool in;
jacint@159:       PrioType prio;
jacint@159: 
jacint@159:       store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
jacint@159:     };
jacint@159:     
jacint@159:   };
jacint@159:   
jacint@159: } //namespace hugo
jacint@159: #endif 
jacint@159: 
jacint@159: 
jacint@159: 
jacint@159: 
jacint@159: 
jacint@159: