equal
deleted
inserted
replaced
600 /// \param p The priority of the item. |
600 /// \param p The priority of the item. |
601 void push(const Item &i, const Prio &p) { |
601 void push(const Item &i, const Prio &p) { |
602 int idx; |
602 int idx; |
603 if (free == -1) { |
603 if (free == -1) { |
604 idx = data.size(); |
604 idx = data.size(); |
605 data.push_back(BucketItem(i, p)); |
605 data.push_back(BucketItem(i)); |
606 } else { |
606 } else { |
607 idx = free; |
607 idx = free; |
608 free = data[idx].next; |
608 free = data[idx].next; |
609 data[idx].item = i; data[idx].value = p; |
609 data[idx].item = i; |
610 } |
610 } |
611 index[i] = idx; |
611 index[i] = idx; |
612 if (p >= (int)first.size()) first.resize(p + 1, -1); |
612 if (p >= (int)first.size()) first.resize(p + 1, -1); |
613 data[idx].next = first[p]; |
613 data[idx].next = first[p]; |
614 first[p] = idx; |
614 first[p] = idx; |
656 --num; |
656 --num; |
657 } |
657 } |
658 |
658 |
659 /// \brief Returns the priority of \c i. |
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 /// \pre \c i must be in the heap. |
665 /// \pre \c i must be in the heap. |
663 /// \param i The item. |
666 /// \param i The item. |
664 Prio operator[](const Item &i) const { |
667 Prio operator[](const Item &i) const { |
665 int idx = index[i]; |
668 for (int k = 0; k < first.size(); ++k) { |
666 return data[idx].value; |
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 |
669 /// \brief Returns if \c item is in, has already been in, or has |
680 /// \brief Returns if \c item is in, has already been in, or has |
670 /// never been in the heap. |
681 /// never been in the heap. |
671 /// |
682 /// |
681 } |
692 } |
682 |
693 |
683 private: |
694 private: |
684 |
695 |
685 struct BucketItem { |
696 struct BucketItem { |
686 BucketItem(const Item& _item, int _value) |
697 BucketItem(const Item& _item) |
687 : item(_item), value(_value) {} |
698 : item(_item) {} |
688 |
699 |
689 Item item; |
700 Item item; |
690 int value; |
|
691 |
|
692 int next; |
701 int next; |
693 }; |
702 }; |
694 |
703 |
695 ItemIntMap& index; |
704 ItemIntMap& index; |
696 std::vector<int> first; |
705 std::vector<int> first; |
734 |
743 |
735 void push(const Item &i, const Prio &p) { |
744 void push(const Item &i, const Prio &p) { |
736 int idx; |
745 int idx; |
737 if (free == -1) { |
746 if (free == -1) { |
738 idx = data.size(); |
747 idx = data.size(); |
739 data.push_back(BucketItem(i, p)); |
748 data.push_back(BucketItem(i)); |
740 } else { |
749 } else { |
741 idx = free; |
750 idx = free; |
742 free = data[idx].next; |
751 free = data[idx].next; |
743 data[idx].item = i; data[idx].value = p; |
752 data[idx].item = i; |
744 } |
753 } |
745 index[i] = idx; |
754 index[i] = idx; |
746 if (p >= (int)first.size()) first.resize(p + 1, -1); |
755 if (p >= (int)first.size()) first.resize(p + 1, -1); |
747 data[idx].next = first[p]; |
756 data[idx].next = first[p]; |
748 first[p] = idx; |
757 first[p] = idx; |
777 free = idx; |
786 free = idx; |
778 --num; |
787 --num; |
779 } |
788 } |
780 |
789 |
781 Prio operator[](const Item &i) const { |
790 Prio operator[](const Item &i) const { |
782 int idx = index[i]; |
791 for (int k = 0; k < first.size(); ++k) { |
783 return data[idx].value; |
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 |
786 state_enum state(const Item &i) const { |
803 state_enum state(const Item &i) const { |
787 int idx = index[i]; |
804 int idx = index[i]; |
788 if (idx >= 0) idx = 0; |
805 if (idx >= 0) idx = 0; |
790 } |
807 } |
791 |
808 |
792 private: |
809 private: |
793 |
810 |
794 struct BucketItem { |
811 struct BucketItem { |
795 BucketItem(const Item& _item, int _value) |
812 BucketItem(const Item& _item) : item(_item) {} |
796 : item(_item), value(_value) {} |
|
797 |
813 |
798 Item item; |
814 Item item; |
799 int value; |
|
800 |
815 |
801 int next; |
816 int next; |
802 }; |
817 }; |
803 |
818 |
804 ItemIntMap& index; |
819 ItemIntMap& index; |