equal
deleted
inserted
replaced
52 /// efficient. This heap type can store only items with \e int priority. |
52 /// efficient. This heap type can store only items with \e int priority. |
53 /// In a heap one can change the priority of an item, add or erase an |
53 /// In a heap one can change the priority of an item, add or erase an |
54 /// item, but the priority cannot be decreased under the last removed |
54 /// item, but the priority cannot be decreased under the last removed |
55 /// item's priority. |
55 /// item's priority. |
56 /// |
56 /// |
57 /// \param _Item Type of the items to be stored. |
|
58 /// \param _ItemIntMap A read and writable Item int map, used internally |
57 /// \param _ItemIntMap A read and writable Item int map, used internally |
59 /// to handle the cross references. |
58 /// to handle the cross references. |
60 /// |
59 /// |
61 /// \see BinHeap |
60 /// \see BinHeap |
62 /// \see Dijkstra |
61 /// \see Dijkstra |
63 /// \author Balazs Dezso |
62 /// \author Balazs Dezso |
64 |
63 |
65 template <typename _Item, typename _ItemIntMap> |
64 template <typename _ItemIntMap> |
66 class RadixHeap { |
65 class RadixHeap { |
67 |
66 |
68 public: |
67 public: |
69 typedef _Item Item; |
68 typedef typename _ItemIntMap::Key Item; |
70 typedef int Prio; |
69 typedef int Prio; |
71 typedef _ItemIntMap ItemIntMap; |
70 typedef _ItemIntMap ItemIntMap; |
72 |
71 |
73 /// \brief Type to represent the items states. |
72 /// \brief Type to represent the items states. |
74 /// |
73 /// |
297 /// \brief Returns the item with minimum priority. |
296 /// \brief Returns the item with minimum priority. |
298 /// |
297 /// |
299 /// This method returns the item with minimum priority. |
298 /// This method returns the item with minimum priority. |
300 /// \pre The heap must be nonempty. |
299 /// \pre The heap must be nonempty. |
301 Item top() const { |
300 Item top() const { |
302 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown(); |
301 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); |
303 return data[boxes[0].first].item; |
302 return data[boxes[0].first].item; |
304 } |
303 } |
305 |
304 |
306 /// \brief Returns the minimum priority. |
305 /// \brief Returns the minimum priority. |
307 /// |
306 /// |
308 /// It returns the minimum priority. |
307 /// It returns the minimum priority. |
309 /// \pre The heap must be nonempty. |
308 /// \pre The heap must be nonempty. |
310 Prio prio() const { |
309 Prio prio() const { |
311 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown(); |
310 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); |
312 return data[boxes[0].first].prio; |
311 return data[boxes[0].first].prio; |
313 } |
312 } |
314 |
313 |
315 /// \brief Deletes the item with minimum priority. |
314 /// \brief Deletes the item with minimum priority. |
316 /// |
315 /// |