Changeset 161:743fa50c442e in lemon-0.x for src/work/jacint/fib_heap.h

Timestamp:

03/09/04 19:42:14 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

* empty log message *

File:

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

src/work/jacint/fib_heap.h

@@ -16 +16 @@
  *bool empty() : true iff size()=0
  *
- *void push(Item, Prio) : pushes Item to the heap with priority Prio. If
- *     Item was already in the heap, it calls decrease(Item, Prio) 
+ *void set(Item, Prio) : calls push(Item, Prio) if Item is not
+ *     in the heap, and calls decrease/increase(Item, Prio) otherwise
+ *
+ *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
+ *     mustn't be in the heap.
  *
  *Item top() : returns the Item with least Prio
@@ -29 +32 @@
  *void erase(Item) : deletes Item from the heap if it was already there
  *
- *void decrease(Item, P) : If Item was not in the heap, then it calls 
- *     push(Item, P). If item is in the heap with Prio more than P
- *     then sets its Prio to P.
- *
- *void increase(Item, P) : If Item was not in the heap, then it calls 
- *     push(Item, P). If item is in the heap with Prio less than P
- *     then sets its Prio to P.
+ *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap 
+ *     with prio at least P.
+ *
+ *void increase(Item, P) : sets prio of Item to P. 
  *
  *
@@ -81 +81 @@
 
 
-   bool empty() const { return blank; }
-    
-    
-   void push (Item const it, PrioType const value) 
-   {
-   
-     int i=iimap.get(it);
-      
-     if ( i >= 0 && container[i].in ) decrease(it, value); 
-     else {
-       if ( i < 0 ) {
-         int s=container.size();
-         iimap.set( it, s );    
-         store st;
-         st.name=it;
-         container.push_back(st);
-         i=s;
-       }
-       
-       if ( !blank ) {
-         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; 
-
-
-
-       } else {
-         container[i].right_neighbor=container[i].left_neighbor=i;
-         minimum=i;     
-         blank=false;
-       }
-       container[i].prio=value;
-     }
-   }
+    bool empty() const { return blank; }
+
+
+    void set (Item const it, PrioType const value) {
+      int i=iimap.get(it);
+      if ( i >= 0 && container[i].in ) {
+        if ( !comp(container[i].prio, value) ) 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.get(it);      
+      if ( i < 0 ) {
+        int s=container.size();
+        iimap.set( it, s );     
+        store st;
+        st.name=it;
+        container.push_back(st);
+        i=s;
+      }
+      
+      if ( !blank ) {
+        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; 
+        
+      } else {
+        container[i].right_neighbor=container[i].left_neighbor=i;
+        minimum=i;      
+        blank=false;
+      }
+      container[i].prio=value;
+    }
+    
 
 
@@ -200 +202 @@
     
 
-   void decrease (Item it, PrioType const value) {
-     int i=iimap.get(it);
-     if ( i >= 0 && container[i].in ) { 
-       
-       if ( comp(value, container[i].prio) ) {
-         container[i].prio=value;
-         
-         if ( container[i].parent!=-1 ) {
-           int p=container[i].parent;
-            
-           if ( !comp(container[p].prio, value) ) { 
-             cut(i,p);      
-             cascade(p);
-             if ( comp(value, container[minimum].prio) ) minimum=i; 
-           }
-         } 
-       }
-     } else push(it, value);
-   }
+    void decrease (Item it, PrioType const value) {
+      int i=iimap.get(it);
+      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; 
+      }
+    }
    
 
     void increase (Item it, PrioType const value) {
-      int i=iimap.get(it);
-      
-      if ( i >= 0 && container[i].in ) { 
-        if ( comp(container[i].prio, value) ) { 
-          erase(it);
-          push(it, value);
-        }
-      } else push(it, value);
+      erase(it);
+      push(it, value);
     }