Changeset 173:de9849252e78 in lemon-0.x for src/work/jacint/fib_heap.h

Timestamp:

03/12/04 00:31:13 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

* empty log message *

File:

• src/work/jacint/fib_heap.h (modified) (11 diffs)

src/work/jacint/fib_heap.h

@@ -22 +22 @@
  *     mustn't be in the heap.
  *
- *Item top() : returns the Item with least Prio
+ *Item top() : returns the Item with least Prio. 
+ *     Must be called only if heap is nonempty.
  *
  *Prio prio() : returns the least Prio
- *  
+ *     Must be called only if heap is nonempty.
+ *
  *Prio get(Item) : returns Prio of Item
+ *     Must be called only if Item is in heap.
  *
  *void pop() : deletes the Item with least Prio
@@ -66 +69 @@
     std::vector<store> container;
     int minimum;
-    bool blank;
     ItemIntMap &iimap;
     Compare comp;
+    int num_items;
 
     enum state_enum {
@@ -78 +81 @@
   public :
     
-    FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {} 
+    FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} 
     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 
-      blank(true), iimap(_iimap), comp(_comp) {}
+      iimap(_iimap), comp(_comp), num_items() {}
     
     
     int size() const {
-      int s=0;
-      for ( unsigned int i=0; i!=container.size(); ++i )
-        if ( container[i].in ) ++s;
-      return s; 
-    }
-
-
-    bool empty() const { return blank; }
+      return num_items; 
+    }
+
+
+    bool empty() const { return num_items==0; }
 
 
@@ -97 +97 @@
       int i=iimap.get(it);
       if ( i >= 0 && container[i].in ) {
-        if ( !comp(container[i].prio, value) ) decrease(it, value); 
+        if ( comp(value, container[i].prio) ) decrease(it, value); 
         if ( comp(container[i].prio, value) ) increase(it, value); 
       } else push(it, value);
@@ -119 +119 @@
       }
 
-      if ( !blank ) {
+      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( container[minimum].prio, value) ) minimum=i; 
+        if ( comp( value, container[minimum].prio) ) minimum=i; 
       } else {
         container[i].right_neighbor=container[i].left_neighbor=i;
         minimum=i;      
-        blank=false;
       }
       container[i].prio=value;
+      ++num_items;
     }
     
 
     Item top() const {
-      if ( !blank ) { 
-        return container[minimum].name;
-      } else {
-        return Item();
-      }
+      return container[minimum].name;
     }
     
     
     PrioType prio() const {
-      if ( !blank ) { 
-        return container[minimum].prio;
-      } else {
-        return PrioType();
-      }
+      return container[minimum].prio;
     }
     
 
     const PrioType get(const Item& it) const {
-      int i=iimap.get(it);
-      
-      if ( i >= 0 && container[i].in ) { 
-        return container[i].prio;
-      } else {
-        return PrioType();
-      }
-    }
-
-
+      return container[iimap.get(it)].prio;
+    }
 
 
@@ -169 +153 @@
       if ( container[minimum].left_neighbor==minimum ) {
         container[minimum].in=false;
-        if ( container[minimum].degree==0 ) blank=true; 
-        else { 
+        if ( container[minimum].degree!=0 ) { 
           makeroot(container[minimum].child);
           minimum=container[minimum].child;
           balance();
-        } 
+        }
       } else {
         int right=container[minimum].right_neighbor;
@@ -194 +177 @@
         balance();
       } // the case where there are more roots
+      --num_items;   
     }
 
@@ -200 +184 @@
       int i=iimap.get(it);
       
-      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();
-     }
-   }
+      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();
+      }
+    }
     
 
@@ -221 +204 @@
         cut(i,p);           
         cascade(p);
-        if ( comp(value, container[minimum].prio) ) minimum=i; 
-      }
+      }      
+      if ( comp(value, container[minimum].prio) ) minimum=i; 
     }
    
@@ -311 +294 @@
       
       
-      /*Lacing i to the roots.*/
+      /*Lacing a to the roots.*/
       int right=container[minimum].right_neighbor;
       container[minimum].right_neighbor=a;
@@ -393 +376 @@
 } //namespace hugo
 #endif 
-
-
-
-
-
-