47 /// the lowest priority. |
47 /// the lowest priority. |
48 template <typename _ItemIntMap, bool minimize = true > |
48 template <typename _ItemIntMap, bool minimize = true > |
49 class BucketHeap { |
49 class BucketHeap { |
50 |
50 |
51 public: |
51 public: |
|
52 /// \e |
52 typedef typename _ItemIntMap::Key Item; |
53 typedef typename _ItemIntMap::Key Item; |
|
54 /// \e |
53 typedef int Prio; |
55 typedef int Prio; |
|
56 /// \e |
54 typedef std::pair<Item, Prio> Pair; |
57 typedef std::pair<Item, Prio> Pair; |
|
58 /// \e |
55 typedef _ItemIntMap ItemIntMap; |
59 typedef _ItemIntMap ItemIntMap; |
56 |
60 |
57 /// \brief Type to represent the items states. |
61 /// \brief Type to represent the items states. |
58 /// |
62 /// |
59 /// Each Item element have a state associated to it. It may be "in heap", |
63 /// Each Item element have a state associated to it. It may be "in heap", |
60 /// "pre heap" or "post heap". The latter two are indifferent from the |
64 /// "pre heap" or "post heap". The latter two are indifferent from the |
61 /// heap's point of view, but may be useful to the user. |
65 /// heap's point of view, but may be useful to the user. |
62 /// |
66 /// |
63 /// The ItemIntMap \e should be initialized in such way that it maps |
67 /// The ItemIntMap \e should be initialized in such way that it maps |
64 /// PRE_HEAP (-1) to any element to be put in the heap... |
68 /// PRE_HEAP (-1) to any element to be put in the heap... |
65 enum state_enum { |
69 enum State { |
66 IN_HEAP = 0, |
70 IN_HEAP = 0, |
67 PRE_HEAP = -1, |
71 PRE_HEAP = -1, |
68 POST_HEAP = -2 |
72 POST_HEAP = -2 |
69 }; |
73 }; |
70 |
74 |
276 /// This method returns PRE_HEAP if \c item has never been in the |
280 /// This method returns PRE_HEAP if \c item has never been in the |
277 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
281 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
278 /// otherwise. In the latter case it is possible that \c item will |
282 /// otherwise. In the latter case it is possible that \c item will |
279 /// get back to the heap again. |
283 /// get back to the heap again. |
280 /// \param i The item. |
284 /// \param i The item. |
281 state_enum state(const Item &i) const { |
285 State state(const Item &i) const { |
282 int idx = index[i]; |
286 int idx = index[i]; |
283 if (idx >= 0) idx = 0; |
287 if (idx >= 0) idx = 0; |
284 return state_enum(idx); |
288 return State(idx); |
285 } |
289 } |
286 |
290 |
287 /// \brief Sets the state of the \c item in the heap. |
291 /// \brief Sets the state of the \c item in the heap. |
288 /// |
292 /// |
289 /// Sets the state of the \c item in the heap. It can be used to |
293 /// Sets the state of the \c item in the heap. It can be used to |
290 /// manually clear the heap when it is important to achive the |
294 /// manually clear the heap when it is important to achive the |
291 /// better time complexity. |
295 /// better time complexity. |
292 /// \param i The item. |
296 /// \param i The item. |
293 /// \param st The state. It should not be \c IN_HEAP. |
297 /// \param st The state. It should not be \c IN_HEAP. |
294 void state(const Item& i, state_enum st) { |
298 void state(const Item& i, State st) { |
295 switch (st) { |
299 switch (st) { |
296 case POST_HEAP: |
300 case POST_HEAP: |
297 case PRE_HEAP: |
301 case PRE_HEAP: |
298 if (state(i) == IN_HEAP) { |
302 if (state(i) == IN_HEAP) { |
299 erase(i); |
303 erase(i); |
544 /// "pre heap" or "post heap". The latter two are indifferent from the |
548 /// "pre heap" or "post heap". The latter two are indifferent from the |
545 /// heap's point of view, but may be useful to the user. |
549 /// heap's point of view, but may be useful to the user. |
546 /// |
550 /// |
547 /// The ItemIntMap \e should be initialized in such way that it maps |
551 /// The ItemIntMap \e should be initialized in such way that it maps |
548 /// PRE_HEAP (-1) to any element to be put in the heap... |
552 /// PRE_HEAP (-1) to any element to be put in the heap... |
549 enum state_enum { |
553 enum State { |
550 IN_HEAP = 0, |
554 IN_HEAP = 0, |
551 PRE_HEAP = -1, |
555 PRE_HEAP = -1, |
552 POST_HEAP = -2 |
556 POST_HEAP = -2 |
553 }; |
557 }; |
554 |
558 |
681 /// This method returns PRE_HEAP if \c item has never been in the |
685 /// This method returns PRE_HEAP if \c item has never been in the |
682 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
686 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
683 /// otherwise. In the latter case it is possible that \c item will |
687 /// otherwise. In the latter case it is possible that \c item will |
684 /// get back to the heap again. |
688 /// get back to the heap again. |
685 /// \param i The item. |
689 /// \param i The item. |
686 state_enum state(const Item &i) const { |
690 State state(const Item &i) const { |
687 int idx = index[i]; |
691 int idx = index[i]; |
688 if (idx >= 0) idx = 0; |
692 if (idx >= 0) idx = 0; |
689 return state_enum(idx); |
693 return State(idx); |
690 } |
694 } |
691 |
695 |
692 private: |
696 private: |
693 |
697 |
694 struct BucketItem { |
698 struct BucketItem { |