Changeset 729:bb8c4cd57900 in lemon for lemon/bucket_heap.h
 Timestamp:
 06/11/09 22:16:11 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bucket_heap.h
r728 r729 30 30 namespace lemon { 31 31 32 namespace _bucket_heap_bits { 33 34 template <bool minimize> 35 struct DirectionTraits { 36 static bool less(int left, int right) { 37 return left < right; 38 } 39 static void increase(int& value) { 40 ++value; 41 } 42 }; 43 44 template <> 45 struct DirectionTraits<false> { 46 static bool less(int left, int right) { 47 return left > right; 48 } 49 static void increase(int& value) { 50 value; 51 } 52 }; 53 54 } 55 32 56 /// \ingroup auxdat 33 57 /// … … 46 70 /// \param minimize If the given parameter is true then the heap gives back 47 71 /// the lowest priority. 48 template <typename _ItemIntMap, bool minimize = true 72 template <typename _ItemIntMap, bool minimize = true> 49 73 class BucketHeap { 50 74 … … 58 82 /// \e 59 83 typedef _ItemIntMap ItemIntMap; 84 85 private: 86 87 typedef _bucket_heap_bits::DirectionTraits<minimize> Direction; 88 89 public: 60 90 61 91 /// \brief Type to represent the items states. … … 162 192 data.push_back(BucketItem(i, p)); 163 193 lace(idx); 164 if ( p < minimal) {194 if (Direction::less(p, minimal)) { 165 195 minimal = p; 166 196 } … … 173 203 Item top() const { 174 204 while (first[minimal] == 1) { 175 ++minimal;205 Direction::increase(minimal); 176 206 } 177 207 return data[first[minimal]].item; … … 184 214 Prio prio() const { 185 215 while (first[minimal] == 1) { 186 ++minimal;216 Direction::increase(minimal); 187 217 } 188 218 return minimal; … … 195 225 void pop() { 196 226 while (first[minimal] == 1) { 197 ++minimal;227 Direction::increase(minimal); 198 228 } 199 229 int idx = first[minimal]; … … 236 266 int idx = index[i]; 237 267 if (idx < 0) { 238 push(i,p); 239 } else if (p > data[idx].value) { 268 push(i, p); 269 } else if (Direction::less(p, data[idx].value)) { 270 decrease(i, p); 271 } else { 240 272 increase(i, p); 241 } else {242 decrease(i, p);243 273 } 244 274 } … … 255 285 unlace(idx); 256 286 data[idx].value = p; 257 if ( p < minimal) {287 if (Direction::less(p, minimal)) { 258 288 minimal = p; 259 289 } … … 329 359 }; // class BucketHeap 330 360 331 332 template <typename _ItemIntMap>333 class BucketHeap<_ItemIntMap, false> {334 335 public:336 typedef typename _ItemIntMap::Key Item;337 typedef int Prio;338 typedef std::pair<Item, Prio> Pair;339 typedef _ItemIntMap ItemIntMap;340 341 enum State {342 IN_HEAP = 0,343 PRE_HEAP = 1,344 POST_HEAP = 2345 };346 347 public:348 349 explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(1) {}350 351 int size() const { return data.size(); }352 bool empty() const { return data.empty(); }353 354 void clear() {355 data.clear(); first.clear(); maximal = 1;356 }357 358 private:359 360 void relocate_last(int idx) {361 if (idx + 1 != int(data.size())) {362 data[idx] = data.back();363 if (data[idx].prev != 1) {364 data[data[idx].prev].next = idx;365 } else {366 first[data[idx].value] = idx;367 }368 if (data[idx].next != 1) {369 data[data[idx].next].prev = idx;370 }371 index[data[idx].item] = idx;372 }373 data.pop_back();374 }375 376 void unlace(int idx) {377 if (data[idx].prev != 1) {378 data[data[idx].prev].next = data[idx].next;379 } else {380 first[data[idx].value] = data[idx].next;381 }382 if (data[idx].next != 1) {383 data[data[idx].next].prev = data[idx].prev;384 }385 }386 387 void lace(int idx) {388 if (int(first.size()) <= data[idx].value) {389 first.resize(data[idx].value + 1, 1);390 }391 data[idx].next = first[data[idx].value];392 if (data[idx].next != 1) {393 data[data[idx].next].prev = idx;394 }395 first[data[idx].value] = idx;396 data[idx].prev = 1;397 }398 399 public:400 401 void push(const Pair& p) {402 push(p.first, p.second);403 }404 405 void push(const Item &i, const Prio &p) {406 int idx = data.size();407 index[i] = idx;408 data.push_back(BucketItem(i, p));409 lace(idx);410 if (data[idx].value > maximal) {411 maximal = data[idx].value;412 }413 }414 415 Item top() const {416 while (first[maximal] == 1) {417 maximal;418 }419 return data[first[maximal]].item;420 }421 422 Prio prio() const {423 while (first[maximal] == 1) {424 maximal;425 }426 return maximal;427 }428 429 void pop() {430 while (first[maximal] == 1) {431 maximal;432 }433 int idx = first[maximal];434 index[data[idx].item] = 2;435 unlace(idx);436 relocate_last(idx);437 }438 439 void erase(const Item &i) {440 int idx = index[i];441 index[data[idx].item] = 2;442 unlace(idx);443 relocate_last(idx);444 }445 446 Prio operator[](const Item &i) const {447 int idx = index[i];448 return data[idx].value;449 }450 451 void set(const Item &i, const Prio &p) {452 int idx = index[i];453 if (idx < 0) {454 push(i,p);455 } else if (p > data[idx].value) {456 decrease(i, p);457 } else {458 increase(i, p);459 }460 }461 462 void decrease(const Item &i, const Prio &p) {463 int idx = index[i];464 unlace(idx);465 data[idx].value = p;466 if (p > maximal) {467 maximal = p;468 }469 lace(idx);470 }471 472 void increase(const Item &i, const Prio &p) {473 int idx = index[i];474 unlace(idx);475 data[idx].value = p;476 lace(idx);477 }478 479 State state(const Item &i) const {480 int idx = index[i];481 if (idx >= 0) idx = 0;482 return State(idx);483 }484 485 void state(const Item& i, State st) {486 switch (st) {487 case POST_HEAP:488 case PRE_HEAP:489 if (state(i) == IN_HEAP) {490 erase(i);491 }492 index[i] = st;493 break;494 case IN_HEAP:495 break;496 }497 }498 499 private:500 501 struct BucketItem {502 BucketItem(const Item& _item, int _value)503 : item(_item), value(_value) {}504 505 Item item;506 int value;507 508 int prev, next;509 };510 511 ItemIntMap& index;512 std::vector<int> first;513 std::vector<BucketItem> data;514 mutable int maximal;515 516 }; // class BucketHeap517 518 361 /// \ingroup auxdat 519 362 /// … … 525 368 /// difference is that the BucketHeap stores for every key a double 526 369 /// linked list while this class stores just simple lists. In the 527 /// other way it does not support serasing each elements just the370 /// other way it does not support erasing each elements just the 528 371 /// minimal and it does not supports key increasing, decreasing. 529 372 /// … … 542 385 typedef std::pair<Item, Prio> Pair; 543 386 typedef _ItemIntMap ItemIntMap; 387 388 private: 389 390 typedef _bucket_heap_bits::DirectionTraits<minimize> Direction; 391 392 public: 544 393 545 394 /// \brief Type to represent the items states. … … 615 464 data[idx].next = first[p]; 616 465 first[p] = idx; 617 if ( p < minimal) {466 if (Direction::less(p, minimal)) { 618 467 minimal = p; 619 468 } … … 627 476 Item top() const { 628 477 while (first[minimal] == 1) { 629 ++minimal;478 Direction::increase(minimal); 630 479 } 631 480 return data[first[minimal]].item; … … 638 487 Prio prio() const { 639 488 while (first[minimal] == 1) { 640 ++minimal;489 Direction::increase(minimal); 641 490 } 642 491 return minimal; … … 649 498 void pop() { 650 499 while (first[minimal] == 1) { 651 ++minimal;500 Direction::increase(minimal); 652 501 } 653 502 int idx = first[minimal]; … … 712 561 }; // class SimpleBucketHeap 713 562 714 template <typename _ItemIntMap>715 class SimpleBucketHeap<_ItemIntMap, false> {716 717 public:718 typedef typename _ItemIntMap::Key Item;719 typedef int Prio;720 typedef std::pair<Item, Prio> Pair;721 typedef _ItemIntMap ItemIntMap;722 723 enum State {724 IN_HEAP = 0,725 PRE_HEAP = 1,726 POST_HEAP = 2727 };728 729 public:730 731 explicit SimpleBucketHeap(ItemIntMap &_index)732 : index(_index), free(1), num(0), maximal(0) {}733 734 int size() const { return num; }735 736 bool empty() const { return num == 0; }737 738 void clear() {739 data.clear(); first.clear(); free = 1; num = 0; maximal = 0;740 }741 742 void push(const Pair& p) {743 push(p.first, p.second);744 }745 746 void push(const Item &i, const Prio &p) {747 int idx;748 if (free == 1) {749 idx = data.size();750 data.push_back(BucketItem(i));751 } else {752 idx = free;753 free = data[idx].next;754 data[idx].item = i;755 }756 index[i] = idx;757 if (p >= int(first.size())) first.resize(p + 1, 1);758 data[idx].next = first[p];759 first[p] = idx;760 if (p > maximal) {761 maximal = p;762 }763 ++num;764 }765 766 Item top() const {767 while (first[maximal] == 1) {768 maximal;769 }770 return data[first[maximal]].item;771 }772 773 Prio prio() const {774 while (first[maximal] == 1) {775 maximal;776 }777 return maximal;778 }779 780 void pop() {781 while (first[maximal] == 1) {782 maximal;783 }784 int idx = first[maximal];785 index[data[idx].item] = 2;786 first[maximal] = data[idx].next;787 data[idx].next = free;788 free = idx;789 num;790 }791 792 Prio operator[](const Item &i) const {793 for (int k = 0; k < first.size(); ++k) {794 int idx = first[k];795 while (idx != 1) {796 if (data[idx].item == i) {797 return k;798 }799 idx = data[idx].next;800 }801 }802 return 1;803 }804 805 State state(const Item &i) const {806 int idx = index[i];807 if (idx >= 0) idx = 0;808 return State(idx);809 }810 811 private:812 813 struct BucketItem {814 BucketItem(const Item& _item) : item(_item) {}815 816 Item item;817 818 int next;819 };820 821 ItemIntMap& index;822 std::vector<int> first;823 std::vector<BucketItem> data;824 int free, num;825 mutable int maximal;826 827 };828 829 563 } 830 564
Note: See TracChangeset
for help on using the changeset viewer.