# HG changeset patch
# User jacint
# Date 1082749261 0
# Node ID 4406c93c862bf9e3dead6eab74c61103934a44ae
# Parent  0bdc7c279e79c96c068dfa63e9437b0ef4993da5
Documentation added.

diff -r 0bdc7c279e79 -r 4406c93c862b src/include/fib_heap.h
--- a/src/include/fib_heap.h	Fri Apr 23 19:15:55 2004 +0000
+++ b/src/include/fib_heap.h	Fri Apr 23 19:41:01 2004 +0000
@@ -15,21 +15,21 @@
   /// 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 priorities,
-     such that finding the item with minimum priority is efficient. In a
-     heap one can change the priority of an item, and to add or erase an
-     item.
+     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
-     case of many calls to these operations, it is better to use
-     a binary heap.
+     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
+     \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
+     \param Compare A class for the comparison of the priorities. The
      default is \c std::less<Prio>.
 
   */
@@ -46,7 +46,7 @@
 	    typename Compare = std::less<Prio> >
 #endif
   class FibHeap {
-  public: 
+  public:     
     typedef Prio PrioType;
     
   private:
@@ -67,8 +67,6 @@
       POST_HEAP = -2
     };
     
-  public :
-    
     FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
       iimap(_iimap), comp(_comp), num_items() {}
@@ -76,25 +74,25 @@
     ///The number of items stored in the heap.
 
     /**
-    Returns 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 true iff the heap stores no items.
+       Returns \c true iff the heap stores no items.
     */
     bool empty() const { return num_items==0; }
 
-    ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
+    ///\c item gets to the heap with priority \c value independently if \c item was already there.
 
     /**
-       This method calls \ref push(item, value) if \c item is not
-       stored in the heap, and it calls \ref decrease(it, \c value) or
-       \ref increase(it, \c value) otherwise.
+       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); //vigyazat: az implementacioban it van
+    void set (Item const item, PrioType const value); 
     
     ///Adds \c item to the heap with priority \c value. 
     
@@ -102,7 +100,7 @@
        Adds \c item to the heap with priority \c value. 
        \pre \c item must not be stored in the heap. 
     */
-    void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
+    void push (Item const item, PrioType const value);
     
     
     ///Returns the item having the minimum priority w.r.t.  Compare.
@@ -129,7 +127,9 @@
        It returns the priority of \c item.
        \pre \c item must be in the heap.
     */
-    PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
+    PrioType& operator[](const Item& item) { 
+      return container[iimap[item]].prio; 
+    }
     
     ///Returns the priority of \c item.
     
@@ -137,8 +137,8 @@
        It returns the priority of \c item.
        \pre \c item must be in the heap.
     */
-    const PrioType& operator[](const Item& it) const { 
-      return container[iimap[it]].prio; 
+    const PrioType& operator[](const Item& item) const { 
+      return container[iimap[item]].prio; 
     }
 
 
@@ -157,7 +157,7 @@
        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); /*vigyazat: az implementacioban it van*/
+    void erase (const Item& item); 
 
     ///Decreases the priority of \c item to \c value.
 
@@ -166,7 +166,7 @@
        \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); /*vigyazat: az implementacioban it van*/
+    void decrease (Item item, PrioType const value); 
 
 
     ///Increases the priority of \c item to \c value.
@@ -174,17 +174,17 @@
     /**
        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 one wants to \e increase
+       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 it, PrioType const value) {
-      erase(it);
-      push(it, value);
+    void increase (Item item, PrioType const value) {
+      erase(item);
+      push(item, value);
     }
 
 
-    ///Tells if \c item is in, was in, or has not been in the heap.
+    ///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
@@ -192,31 +192,70 @@
        otherwise. In the latter case it is possible that \c item will
        get back to the heap again.
     */
-    state_enum state(const Item &it);  /*vigyazat: az implementacioban it van*/
+    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
     // **********************************************************************
     
-
-    void set (Item const it, PrioType const value) {
-      int i=iimap[it];
-      if ( i >= 0 && container[i].in ) {
-	if ( comp(value, container[i].prio) ) decrease(it, value); 
-	if ( comp(container[i].prio, value) ) increase(it, value); 
-      } else push(it, value);
-    }
+  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);
+  }
     
-
-    void push (Item const it, PrioType const value) {
-      int i=iimap[it];      
+  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( it, s );	
+	iimap.set( item, s );	
 	store st;
-	st.name=it;
+	st.name=item;
 	container.push_back(st);
 	i=s;
       } else {
@@ -240,8 +279,9 @@
       ++num_items;
     }
     
-
-    void pop() {
+  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;
@@ -272,9 +312,12 @@
       --num_items;   
     }
 
-    
-    void erase (const Item& it) {
-      int i=iimap[it];
+
+  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 ) {
@@ -285,11 +328,13 @@
 	minimum=i;     //As if its prio would be -infinity
 	pop();
       }
-    }
+  }
     
-
-    void decrease (Item it, PrioType const value) {
-      int i=iimap[it];
+  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;
       
@@ -298,22 +343,12 @@
 	cascade(p);
       }      
       if ( comp(value, container[minimum].prio) ) minimum=i; 
-    }
-   
+  }
+ 
 
-    state_enum state(const Item &it) const {
-      int i=iimap[it];
-      if( i>=0 ) {
-	if ( container[i].in ) i=0;
-	else i=-2; 
-      }
-      return state_enum(i);
-    }
-
-
-  private:
-    
-    void balance() {      
+  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;
   
@@ -356,43 +391,51 @@
        } while ( s != m );
     }
 
-
-    void makeroot (int c) {
+  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;
+  }
+  
 
-    void 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;
-    }
-
-
-    void cascade (int a) 
+  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;
@@ -406,7 +449,10 @@
     }
 
 
-    void fuse (int a, int b) {
+  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.*/
@@ -430,35 +476,19 @@
       container[b].marked=false;
     }
 
-
-    /*
-     *It is invoked only if a has siblings.
-     */
-    void unlace (int a) {      
+  
+  /*
+   *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;
-    }
-
-
-    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) {} 
-    };
-    
-  };
+  }
   
 } //namespace hugo
 #endif