Changeset 387:4406c93c862b in lemon-0.x

Timestamp:

04/23/04 21:41:01 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@517

Message:

Documentation added.

File:

• src/include/fib_heap.h (modified) (21 diffs)

src/include/fib_heap.h

@@ -16 +16 @@
 
   /**
-     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.
-
-     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.
+     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
+     \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>.
 
@@ -47 +47 @@
 #endif
   class FibHeap {
-  public: 
+  public:     
     typedef Prio PrioType;
     
@@ -68 +68 @@
     };
     
-  public :
-    
     FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
@@ -77 +75 @@
 
     /**
-    Returns the number of items stored in the heap.
+       Returns the number of items stored in the heap.
     */
     int size() const { return num_items; }
@@ -84 +82 @@
     
     /**
-       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.
-
-    /**
-       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.
-    */
-    void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
+    ///\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. 
@@ -103 +101 @@
        \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);
     
     
@@ -130 +128 @@
        \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.
@@ -138 +138 @@
        \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; 
     }
 
@@ -158 +158 @@
        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.
@@ -167 +167 @@
        value w.r.t.  Compare.
     */
-    void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
+    void decrease (Item item, PrioType const value); 
 
 
@@ -175 +175 @@
        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);
-    }
-
-
-    ///Tells if \c item is in, was in, or has not been in the heap.
+    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.
 
     /**
@@ -193 +193 @@
        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) {} 
+    };
+  };    
+ 
 
 
@@ -201 +235 @@
     // **********************************************************************
     
-
-    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);
-    }
-    
-
-    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>::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( it, s );     
+        iimap.set( item, s );   
         store st;
-        st.name=it;
+        st.name=item;
         container.push_back(st);
         i=s;
@@ -241 +280 @@
     }
     
-
-    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 ) {
@@ -273 +313 @@
     }
 
-    
-    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 ) {        
@@ -286 +329 @@
         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;
@@ -299 +344 @@
       }      
       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;
@@ -357 +392 @@
     }
 
-
-    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 {  
@@ -365 +402 @@
       } while ( s != c );
     }
-    
-
-    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>::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 ) {
@@ -407 +450 @@
 
 
-    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);
       
@@ -431 +477 @@
     }
 
-
-    /*
-     *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