Changeset 2110:4b8153513f34 in lemon0.x for lemon/bucket_heap.h
 Timestamp:
 06/26/06 17:40:35 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2807
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bucket_heap.h
r2089 r2110 603 603 if (free == 1) { 604 604 idx = data.size(); 605 data.push_back(BucketItem(i , p));605 data.push_back(BucketItem(i)); 606 606 } else { 607 607 idx = free; 608 608 free = data[idx].next; 609 data[idx].item = i; data[idx].value = p;609 data[idx].item = i; 610 610 } 611 611 index[i] = idx; … … 659 659 /// \brief Returns the priority of \c i. 660 660 /// 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. 662 665 /// \pre \c i must be in the heap. 663 666 /// \param i The item. 664 667 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; 667 678 } 668 679 … … 684 695 685 696 struct BucketItem { 686 BucketItem(const Item& _item , int _value)687 : item(_item) , value(_value){}697 BucketItem(const Item& _item) 698 : item(_item) {} 688 699 689 700 Item item; 690 int value;691 692 701 int next; 693 702 }; … … 737 746 if (free == 1) { 738 747 idx = data.size(); 739 data.push_back(BucketItem(i , p));748 data.push_back(BucketItem(i)); 740 749 } else { 741 750 idx = free; 742 751 free = data[idx].next; 743 data[idx].item = i; data[idx].value = p;752 data[idx].item = i; 744 753 } 745 754 index[i] = idx; … … 780 789 781 790 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; 784 801 } 785 802 … … 793 810 794 811 struct BucketItem { 795 BucketItem(const Item& _item, int _value) 796 : item(_item), value(_value) {} 812 BucketItem(const Item& _item) : item(_item) {} 797 813 798 814 Item item; 799 int value;800 815 801 816 int next;
Note: See TracChangeset
for help on using the changeset viewer.