# HG changeset patch
# User deba
# Date 1151336435 0
# Node ID 4b8153513f34f08a0e0264cc5e2042d4856a57ce
# Parent  ffa70b2580fac6b6880d7aae827f9c62962eeb3a
Smaller Simple Bucket Heap
  - the list node does not store the value
  - trade off: linear time operator[]

diff -r ffa70b2580fa -r 4b8153513f34 lemon/bucket_heap.h
--- a/lemon/bucket_heap.h	Thu Jun 22 18:34:35 2006 +0000
+++ b/lemon/bucket_heap.h	Mon Jun 26 15:40:35 2006 +0000
@@ -602,11 +602,11 @@
       int idx;
       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;
       if (p >= (int)first.size()) first.resize(p + 1, -1);
@@ -658,12 +658,23 @@
     
     /// \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;
     }
 
     /// \brief Returns if \c item is in, has already been in, or has 
@@ -683,12 +694,10 @@
   private:
 
     struct BucketItem {
-      BucketItem(const Item& _item, int _value) 
-	: item(_item), value(_value) {}
+      BucketItem(const Item& _item) 
+	: item(_item) {}
 
       Item item;
-      int value;
-
       int next;
     };
 
@@ -736,11 +745,11 @@
       int idx;
       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;
       if (p >= (int)first.size()) first.resize(p + 1, -1);
@@ -779,8 +788,16 @@
     }
     
     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;
     }
 
     state_enum state(const Item &i) const {
@@ -792,11 +809,9 @@
   private:
 
     struct BucketItem {
-      BucketItem(const Item& _item, int _value) 
-	: item(_item), value(_value) {}
+      BucketItem(const Item& _item) : item(_item) {}
 
       Item item;
-      int value;
 
       int next;
     };