Changeset 2110:4b8153513f34 in lemon-0.x for lemon/bucket_heap.h

Ignore:
Timestamp:
06/26/06 17:40:35 (14 years ago)
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

Unmodified
Removed
• lemon/bucket_heap.h

 r2089 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; /// \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; } struct BucketItem { BucketItem(const Item& _item, int _value) : item(_item), value(_value) {} BucketItem(const Item& _item) : item(_item) {} Item item; int value; int next; }; 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; 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; } struct BucketItem { BucketItem(const Item& _item, int _value) : item(_item), value(_value) {} BucketItem(const Item& _item) : item(_item) {} Item item; int value; int next;
Note: See TracChangeset for help on using the changeset viewer.