COIN-OR::LEMON - Graph Library

Changeset 2110:4b8153513f34 in lemon-0.x


Ignore:
Timestamp:
06/26/06 17:40:35 (18 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:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bucket_heap.h

    r2089 r2110  
    603603      if (free == -1) {
    604604        idx = data.size();
    605         data.push_back(BucketItem(i, p));
     605        data.push_back(BucketItem(i));
    606606      } else {
    607607        idx = free;
    608608        free = data[idx].next;
    609         data[idx].item = i; data[idx].value = p;
     609        data[idx].item = i;
    610610      }
    611611      index[i] = idx;
     
    659659    /// \brief Returns the priority of \c i.
    660660    ///
    661     /// This function returns the priority of item \c i. 
     661    /// This function returns the priority of item \c i.
     662    /// \warning This operator is not a constant time function
     663    /// because it scans the whole data structure to find the proper
     664    /// value. 
    662665    /// \pre \c i must be in the heap.
    663666    /// \param i The item.
    664667    Prio operator[](const Item &i) const {
    665       int idx = index[i];
    666       return data[idx].value;
     668      for (int k = 0; k < first.size(); ++k) {
     669        int idx = first[k];
     670        while (idx != -1) {
     671          if (data[idx].item == i) {
     672            return k;
     673          }
     674          idx = data[idx].next;
     675        }
     676      }
     677      return -1;
    667678    }
    668679
     
    684695
    685696    struct BucketItem {
    686       BucketItem(const Item& _item, int _value)
    687         : item(_item), value(_value) {}
     697      BucketItem(const Item& _item)
     698        : item(_item) {}
    688699
    689700      Item item;
    690       int value;
    691 
    692701      int next;
    693702    };
     
    737746      if (free == -1) {
    738747        idx = data.size();
    739         data.push_back(BucketItem(i, p));
     748        data.push_back(BucketItem(i));
    740749      } else {
    741750        idx = free;
    742751        free = data[idx].next;
    743         data[idx].item = i; data[idx].value = p;
     752        data[idx].item = i;
    744753      }
    745754      index[i] = idx;
     
    780789   
    781790    Prio operator[](const Item &i) const {
    782       int idx = index[i];
    783       return data[idx].value;
     791      for (int k = 0; k < first.size(); ++k) {
     792        int idx = first[k];
     793        while (idx != -1) {
     794          if (data[idx].item == i) {
     795            return k;
     796          }
     797          idx = data[idx].next;
     798        }
     799      }
     800      return -1;
    784801    }
    785802
     
    793810
    794811    struct BucketItem {
    795       BucketItem(const Item& _item, int _value)
    796         : item(_item), value(_value) {}
     812      BucketItem(const Item& _item) : item(_item) {}
    797813
    798814      Item item;
    799       int value;
    800815
    801816      int next;
Note: See TracChangeset for help on using the changeset viewer.