1.1 --- a/lemon/bucket_heap.h	Thu Jun 22 18:34:35 2006 +0000
     1.2 +++ b/lemon/bucket_heap.h	Mon Jun 26 15:40:35 2006 +0000
     1.3 @@ -602,11 +602,11 @@
     1.4        int idx;
     1.5        if (free == -1) {
     1.6          idx = data.size();
     1.7 -        data.push_back(BucketItem(i, p));
     1.8 +        data.push_back(BucketItem(i));
     1.9        } else {
    1.10          idx = free;
    1.11          free = data[idx].next;
    1.12 -        data[idx].item = i; data[idx].value = p;
    1.13 +        data[idx].item = i;
    1.14        }
    1.15        index[i] = idx;
    1.16        if (p >= (int)first.size()) first.resize(p + 1, -1);
    1.17 @@ -658,12 +658,23 @@
    1.18      
    1.19      /// \brief Returns the priority of \c i.
    1.20      ///
    1.21 -    /// This function returns the priority of item \c i.  
    1.22 +    /// This function returns the priority of item \c i.
    1.23 +    /// \warning This operator is not a constant time function
    1.24 +    /// because it scans the whole data structure to find the proper
    1.25 +    /// value.  
    1.26      /// \pre \c i must be in the heap.
    1.27      /// \param i The item.
    1.28      Prio operator[](const Item &i) const {
    1.29 -      int idx = index[i];
    1.30 -      return data[idx].value;
    1.31 +      for (int k = 0; k < first.size(); ++k) {
    1.32 +        int idx = first[k];
    1.33 +        while (idx != -1) {
    1.34 +          if (data[idx].item == i) {
    1.35 +            return k;
    1.36 +          }
    1.37 +          idx = data[idx].next;
    1.38 +        }
    1.39 +      }
    1.40 +      return -1;
    1.41      }
    1.42  
    1.43      /// \brief Returns if \c item is in, has already been in, or has 
    1.44 @@ -683,12 +694,10 @@
    1.45    private:
    1.46  
    1.47      struct BucketItem {
    1.48 -      BucketItem(const Item& _item, int _value) 
    1.49 -	: item(_item), value(_value) {}
    1.50 +      BucketItem(const Item& _item) 
    1.51 +	: item(_item) {}
    1.52  
    1.53        Item item;
    1.54 -      int value;
    1.55 -
    1.56        int next;
    1.57      };
    1.58  
    1.59 @@ -736,11 +745,11 @@
    1.60        int idx;
    1.61        if (free == -1) {
    1.62          idx = data.size();
    1.63 -        data.push_back(BucketItem(i, p));
    1.64 +        data.push_back(BucketItem(i));
    1.65        } else {
    1.66          idx = free;
    1.67          free = data[idx].next;
    1.68 -        data[idx].item = i; data[idx].value = p;
    1.69 +        data[idx].item = i;
    1.70        }
    1.71        index[i] = idx;
    1.72        if (p >= (int)first.size()) first.resize(p + 1, -1);
    1.73 @@ -779,8 +788,16 @@
    1.74      }
    1.75      
    1.76      Prio operator[](const Item &i) const {
    1.77 -      int idx = index[i];
    1.78 -      return data[idx].value;
    1.79 +      for (int k = 0; k < first.size(); ++k) {
    1.80 +        int idx = first[k];
    1.81 +        while (idx != -1) {
    1.82 +          if (data[idx].item == i) {
    1.83 +            return k;
    1.84 +          }
    1.85 +          idx = data[idx].next;
    1.86 +        }
    1.87 +      }
    1.88 +      return -1;
    1.89      }
    1.90  
    1.91      state_enum state(const Item &i) const {
    1.92 @@ -792,11 +809,9 @@
    1.93    private:
    1.94  
    1.95      struct BucketItem {
    1.96 -      BucketItem(const Item& _item, int _value) 
    1.97 -	: item(_item), value(_value) {}
    1.98 +      BucketItem(const Item& _item) : item(_item) {}
    1.99  
   1.100        Item item;
   1.101 -      int value;
   1.102  
   1.103        int next;
   1.104      };