Changeset 2110:4b8153513f34 in lemon-0.x

Timestamp:

06/26/06 17:40:35 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Smaller Simple Bucket Heap

• the list node does not store the value
• trade off: linear time operator[]

File:

• lemon/bucket_heap.h (modified) (6 diffs)

lemon/bucket_heap.h

@@ -603 +603 @@
       if (free == -1) {
         idx = data.size();
-        data.push_back(BucketItem(i, p));
+        data.push_back(BucketItem(i));
       } else {
         idx = free;
         free = data[idx].next;
-        data[idx].item = i; data[idx].value = p;
+        data[idx].item = i;
       }
       index[i] = idx;
@@ -659 +659 @@
     /// \brief Returns the priority of \c i.
     ///
-    /// This function returns the priority of item \c i.  
+    /// This function returns the priority of item \c i.
+    /// \warning This operator is not a constant time function
+    /// because it scans the whole data structure to find the proper
+    /// value.  
     /// \pre \c i must be in the heap.
     /// \param i The item.
     Prio operator[](const Item &i) const {
-      int idx = index[i];
-      return data[idx].value;
+      for (int k = 0; k < first.size(); ++k) {
+        int idx = first[k];
+        while (idx != -1) {
+          if (data[idx].item == i) {
+            return k;
+          }
+          idx = data[idx].next;
+        }
+      }
+      return -1;
     }
 
@@ -684 +695 @@
 
     struct BucketItem {
-      BucketItem(const Item& _item, int _value) 
-        : item(_item), value(_value) {}
+      BucketItem(const Item& _item) 
+        : item(_item) {}
 
       Item item;
-      int value;
-
       int next;
     };
@@ -737 +746 @@
       if (free == -1) {
         idx = data.size();
-        data.push_back(BucketItem(i, p));
+        data.push_back(BucketItem(i));
       } else {
         idx = free;
         free = data[idx].next;
-        data[idx].item = i; data[idx].value = p;
+        data[idx].item = i;
       }
       index[i] = idx;
@@ -780 +789 @@
     
     Prio operator[](const Item &i) const {
-      int idx = index[i];
-      return data[idx].value;
+      for (int k = 0; k < first.size(); ++k) {
+        int idx = first[k];
+        while (idx != -1) {
+          if (data[idx].item == i) {
+            return k;
+          }
+          idx = data[idx].next;
+        }
+      }
+      return -1;
     }
 
@@ -793 +810 @@
 
     struct BucketItem {
-      BucketItem(const Item& _item, int _value) 
-        : item(_item), value(_value) {}
+      BucketItem(const Item& _item) : item(_item) {}
 
       Item item;
-      int value;
 
       int next;