equal
deleted
inserted
replaced
50 template <typename _Prio, typename _ItemIntMap, |
50 template <typename _Prio, typename _ItemIntMap, |
51 typename _Compare = std::less<_Prio> > |
51 typename _Compare = std::less<_Prio> > |
52 class BinHeap { |
52 class BinHeap { |
53 |
53 |
54 public: |
54 public: |
|
55 ///\e |
55 typedef _ItemIntMap ItemIntMap; |
56 typedef _ItemIntMap ItemIntMap; |
|
57 ///\e |
56 typedef _Prio Prio; |
58 typedef _Prio Prio; |
|
59 ///\e |
57 typedef typename ItemIntMap::Key Item; |
60 typedef typename ItemIntMap::Key Item; |
|
61 ///\e |
58 typedef std::pair<Item,Prio> Pair; |
62 typedef std::pair<Item,Prio> Pair; |
|
63 ///\e |
59 typedef _Compare Compare; |
64 typedef _Compare Compare; |
60 |
65 |
61 /// \brief Type to represent the items states. |
66 /// \brief Type to represent the items states. |
62 /// |
67 /// |
63 /// Each Item element have a state associated to it. It may be "in heap", |
68 /// Each Item element have a state associated to it. It may be "in heap", |
319 case IN_HEAP: |
324 case IN_HEAP: |
320 break; |
325 break; |
321 } |
326 } |
322 } |
327 } |
323 |
328 |
|
329 /// \brief Replaces an item in the heap. |
|
330 /// |
|
331 /// The \c i item is replaced with \c j item. The \c i item should |
|
332 /// be in the heap, while the \c j should be out of the heap. The |
|
333 /// \c i item will out of the heap and \c j will be in the heap |
|
334 /// with the same prioriority as prevoiusly the \c i item. |
|
335 void replace(const Item& i, const Item& j) { |
|
336 int idx = iim[i]; |
|
337 iim.set(i, iim[j]); |
|
338 iim.set(j, idx); |
|
339 data[idx].first = j; |
|
340 } |
|
341 |
324 }; // class BinHeap |
342 }; // class BinHeap |
325 |
343 |
326 } // namespace lemon |
344 } // namespace lemon |
327 |
345 |
328 #endif // LEMON_BIN_HEAP_H |
346 #endif // LEMON_BIN_HEAP_H |