Changeset 2089:fce8db723736 in lemon-0.x for lemon
- Timestamp:
- 05/17/06 11:07:24 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2756
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bucket_heap.h
r2050 r2089 31 31 32 32 /// \ingroup auxdat 33 33 /// 34 34 /// \brief A Bucket Heap implementation. 35 35 /// … … 242 242 243 243 /// \brief Decreases the priority of \c i to \c p. 244 244 /// 245 245 /// This method decreases the priority of item \c i to \c p. 246 246 /// \pre \c i must be stored in the heap with priority at least \c … … 513 513 }; // class BucketHeap 514 514 515 /// \ingroup auxdat 516 /// 517 /// \brief A Simplified Bucket Heap implementation. 518 /// 519 /// This class implements a simplified \e bucket \e heap data 520 /// structure. It does not provide some functionality but it faster 521 /// and simplier data structure than the BucketHeap. The main 522 /// difference is that the BucketHeap stores for every key a double 523 /// linked list while this class stores just simple lists. In the 524 /// other way it does not supports erasing each elements just the 525 /// minimal and it does not supports key increasing, decreasing. 526 /// 527 /// \param _Item Type of the items to be stored. 528 /// \param _ItemIntMap A read and writable Item int map, used internally 529 /// to handle the cross references. 530 /// \param minimize If the given parameter is true then the heap gives back 531 /// the lowest priority. 532 /// 533 /// \sa BucketHeap 534 template <typename _Item, typename _ItemIntMap, bool minimize = true > 535 class SimpleBucketHeap { 536 537 public: 538 typedef _Item Item; 539 typedef int Prio; 540 typedef std::pair<Item, Prio> Pair; 541 typedef _ItemIntMap ItemIntMap; 542 543 /// \brief Type to represent the items states. 544 /// 545 /// Each Item element have a state associated to it. It may be "in heap", 546 /// "pre heap" or "post heap". The latter two are indifferent from the 547 /// heap's point of view, but may be useful to the user. 548 /// 549 /// The ItemIntMap \e should be initialized in such way that it maps 550 /// PRE_HEAP (-1) to any element to be put in the heap... 551 enum state_enum { 552 IN_HEAP = 0, 553 PRE_HEAP = -1, 554 POST_HEAP = -2 555 }; 556 557 public: 558 559 /// \brief The constructor. 560 /// 561 /// The constructor. 562 /// \param _index should be given to the constructor, since it is used 563 /// internally to handle the cross references. The value of the map 564 /// should be PRE_HEAP (-1) for each element. 565 explicit SimpleBucketHeap(ItemIntMap &_index) 566 : index(_index), free(-1), num(0), minimal(0) {} 567 568 /// \brief Returns the number of items stored in the heap. 569 /// 570 /// The number of items stored in the heap. 571 int size() const { return num; } 572 573 /// \brief Checks if the heap stores no items. 574 /// 575 /// Returns \c true if and only if the heap stores no items. 576 bool empty() const { return num == 0; } 577 578 /// \brief Make empty this heap. 579 /// 580 /// Make empty this heap. It does not change the cross reference 581 /// map. If you want to reuse a heap what is not surely empty you 582 /// should first clear the heap and after that you should set the 583 /// cross reference map for each item to \c PRE_HEAP. 584 void clear() { 585 data.clear(); first.clear(); free = -1; num = 0; minimal = 0; 586 } 587 588 /// \brief Insert a pair of item and priority into the heap. 589 /// 590 /// Adds \c p.first to the heap with priority \c p.second. 591 /// \param p The pair to insert. 592 void push(const Pair& p) { 593 push(p.first, p.second); 594 } 595 596 /// \brief Insert an item into the heap with the given priority. 597 /// 598 /// Adds \c i to the heap with priority \c p. 599 /// \param i The item to insert. 600 /// \param p The priority of the item. 601 void push(const Item &i, const Prio &p) { 602 int idx; 603 if (free == -1) { 604 idx = data.size(); 605 data.push_back(BucketItem(i, p)); 606 } else { 607 idx = free; 608 free = data[idx].next; 609 data[idx].item = i; data[idx].value = p; 610 } 611 index[i] = idx; 612 if (p >= (int)first.size()) first.resize(p + 1, -1); 613 data[idx].next = first[p]; 614 first[p] = idx; 615 if (p < minimal) { 616 minimal = p; 617 } 618 ++num; 619 } 620 621 /// \brief Returns the item with minimum priority. 622 /// 623 /// This method returns the item with minimum priority. 624 /// \pre The heap must be nonempty. 625 Item top() const { 626 while (first[minimal] == -1) { 627 ++minimal; 628 } 629 return data[first[minimal]].item; 630 } 631 632 /// \brief Returns the minimum priority. 633 /// 634 /// It returns the minimum priority. 635 /// \pre The heap must be nonempty. 636 Prio prio() const { 637 while (first[minimal] == -1) { 638 ++minimal; 639 } 640 return minimal; 641 } 642 643 /// \brief Deletes the item with minimum priority. 644 /// 645 /// This method deletes the item with minimum priority from the heap. 646 /// \pre The heap must be non-empty. 647 void pop() { 648 while (first[minimal] == -1) { 649 ++minimal; 650 } 651 int idx = first[minimal]; 652 index[data[idx].item] = -2; 653 first[minimal] = data[idx].next; 654 data[idx].next = free; 655 free = idx; 656 --num; 657 } 658 659 /// \brief Returns the priority of \c i. 660 /// 661 /// This function returns the priority of item \c i. 662 /// \pre \c i must be in the heap. 663 /// \param i The item. 664 Prio operator[](const Item &i) const { 665 int idx = index[i]; 666 return data[idx].value; 667 } 668 669 /// \brief Returns if \c item is in, has already been in, or has 670 /// never been in the heap. 671 /// 672 /// This method returns PRE_HEAP if \c item has never been in the 673 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 674 /// otherwise. In the latter case it is possible that \c item will 675 /// get back to the heap again. 676 /// \param i The item. 677 state_enum state(const Item &i) const { 678 int idx = index[i]; 679 if (idx >= 0) idx = 0; 680 return state_enum(idx); 681 } 682 683 private: 684 685 struct BucketItem { 686 BucketItem(const Item& _item, int _value) 687 : item(_item), value(_value) {} 688 689 Item item; 690 int value; 691 692 int next; 693 }; 694 695 ItemIntMap& index; 696 std::vector<int> first; 697 std::vector<BucketItem> data; 698 int free, num; 699 mutable int minimal; 700 701 }; // class SimpleBucketHeap 702 703 template <typename _Item, typename _ItemIntMap> 704 class SimpleBucketHeap<_Item, _ItemIntMap, false> { 705 706 public: 707 typedef _Item Item; 708 typedef int Prio; 709 typedef std::pair<Item, Prio> Pair; 710 typedef _ItemIntMap ItemIntMap; 711 712 enum state_enum { 713 IN_HEAP = 0, 714 PRE_HEAP = -1, 715 POST_HEAP = -2 716 }; 717 718 public: 719 720 explicit SimpleBucketHeap(ItemIntMap &_index) 721 : index(_index), free(-1), num(0), maximal(0) {} 722 723 int size() const { return num; } 724 725 bool empty() const { return num == 0; } 726 727 void clear() { 728 data.clear(); first.clear(); free = -1; num = 0; maximal = 0; 729 } 730 731 void push(const Pair& p) { 732 push(p.first, p.second); 733 } 734 735 void push(const Item &i, const Prio &p) { 736 int idx; 737 if (free == -1) { 738 idx = data.size(); 739 data.push_back(BucketItem(i, p)); 740 } else { 741 idx = free; 742 free = data[idx].next; 743 data[idx].item = i; data[idx].value = p; 744 } 745 index[i] = idx; 746 if (p >= (int)first.size()) first.resize(p + 1, -1); 747 data[idx].next = first[p]; 748 first[p] = idx; 749 if (p > maximal) { 750 maximal = p; 751 } 752 ++num; 753 } 754 755 Item top() const { 756 while (first[maximal] == -1) { 757 --maximal; 758 } 759 return data[first[maximal]].item; 760 } 761 762 Prio prio() const { 763 while (first[maximal] == -1) { 764 --maximal; 765 } 766 return maximal; 767 } 768 769 void pop() { 770 while (first[maximal] == -1) { 771 --maximal; 772 } 773 int idx = first[maximal]; 774 index[data[idx].item] = -2; 775 first[maximal] = data[idx].next; 776 data[idx].next = free; 777 free = idx; 778 --num; 779 } 780 781 Prio operator[](const Item &i) const { 782 int idx = index[i]; 783 return data[idx].value; 784 } 785 786 state_enum state(const Item &i) const { 787 int idx = index[i]; 788 if (idx >= 0) idx = 0; 789 return state_enum(idx); 790 } 791 792 private: 793 794 struct BucketItem { 795 BucketItem(const Item& _item, int _value) 796 : item(_item), value(_value) {} 797 798 Item item; 799 int value; 800 801 int next; 802 }; 803 804 ItemIntMap& index; 805 std::vector<int> first; 806 std::vector<BucketItem> data; 807 int free, num; 808 mutable int maximal; 809 810 }; 811 515 812 } 516 813
Note: See TracChangeset
for help on using the changeset viewer.