24 #include <vector> |
24 #include <vector> |
25 #include <lemon/error.h> |
25 #include <lemon/error.h> |
26 |
26 |
27 namespace lemon { |
27 namespace lemon { |
28 |
28 |
29 /// \addtogroup auxdat |
|
30 /// @{ |
|
31 |
|
32 /// \brief Exception thrown by RadixHeap. |
29 /// \brief Exception thrown by RadixHeap. |
33 /// |
30 /// |
34 /// This Exception is thrown when a smaller priority |
31 /// This Exception is thrown when a smaller priority |
35 /// is inserted into the \e RadixHeap then the last time erased. |
32 /// is inserted into the \e RadixHeap then the last time erased. |
36 /// \see RadixHeap |
33 /// \see RadixHeap |
41 virtual const char* exceptionName() const { |
38 virtual const char* exceptionName() const { |
42 return "lemon::UnderFlowPriorityError"; |
39 return "lemon::UnderFlowPriorityError"; |
43 } |
40 } |
44 }; |
41 }; |
45 |
42 |
|
43 /// \ingroup auxdata |
|
44 /// |
46 /// \brief A Radix Heap implementation. |
45 /// \brief A Radix Heap implementation. |
47 /// |
46 /// |
48 /// This class implements the \e radix \e heap data structure. A \e heap |
47 /// This class implements the \e radix \e heap data structure. A \e heap |
49 /// is a data structure for storing items with specified values called \e |
48 /// is a data structure for storing items with specified values called \e |
50 /// priorities in such a way that finding the item with minimum priority is |
49 /// priorities in such a way that finding the item with minimum priority is |
106 |
105 |
107 public: |
106 public: |
108 /// \brief The constructor. |
107 /// \brief The constructor. |
109 /// |
108 /// |
110 /// The constructor. |
109 /// The constructor. |
111 /// \param _iim should be given to the constructor, since it is used |
|
112 /// internally to handle the cross references. The value of the map |
|
113 /// should be PRE_HEAP (-1) for each element. |
|
114 explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) { |
|
115 boxes.push_back(RadixBox(0, 1)); |
|
116 boxes.push_back(RadixBox(1, 1)); |
|
117 } |
|
118 |
|
119 /// \brief The constructor. |
|
120 /// |
|
121 /// The constructor. |
|
122 /// |
110 /// |
123 /// \param _iim It should be given to the constructor, since it is used |
111 /// \param _iim It should be given to the constructor, since it is used |
124 /// internally to handle the cross references. The value of the map |
112 /// internally to handle the cross references. The value of the map |
125 /// should be PRE_HEAP (-1) for each element. |
113 /// should be PRE_HEAP (-1) for each element. |
126 /// |
114 /// |
|
115 /// \param minimal The initial minimal value of the heap. |
127 /// \param capacity It determines the initial capacity of the heap. |
116 /// \param capacity It determines the initial capacity of the heap. |
128 RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) { |
117 RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0) |
129 boxes.push_back(RadixBox(0, 1)); |
118 : iim(_iim) { |
130 boxes.push_back(RadixBox(1, 1)); |
119 boxes.push_back(RadixBox(minimal, 1)); |
131 while (upper(boxes.back(), capacity)) { |
120 boxes.push_back(RadixBox(minimal + 1, 1)); |
|
121 while (lower(boxes.size() - 1, capacity + minimal - 1)) { |
132 extend(); |
122 extend(); |
133 } |
123 } |
134 } |
124 } |
135 |
125 |
136 /// The number of items stored in the heap. |
126 /// The number of items stored in the heap. |
139 int size() const { return data.size(); } |
129 int size() const { return data.size(); } |
140 /// \brief Checks if the heap stores no items. |
130 /// \brief Checks if the heap stores no items. |
141 /// |
131 /// |
142 /// Returns \c true if and only if the heap stores no items. |
132 /// Returns \c true if and only if the heap stores no items. |
143 bool empty() const { return data.empty(); } |
133 bool empty() const { return data.empty(); } |
|
134 |
|
135 /// \brief Make empty this heap. |
|
136 /// |
|
137 /// Make empty this heap. |
|
138 void clear(int minimal = 0, int capacity = 0) { |
|
139 for (int i = 0; i < (int)data.size(); ++i) { |
|
140 iim[data[i].item] = -2; |
|
141 } |
|
142 data.clear(); boxes.clear(); |
|
143 boxes.push_back(RadixBox(minimal, 1)); |
|
144 boxes.push_back(RadixBox(minimal + 1, 1)); |
|
145 while (lower(boxes.size() - 1, capacity + minimal - 1)) { |
|
146 extend(); |
|
147 } |
|
148 } |
144 |
149 |
145 private: |
150 private: |
146 |
151 |
147 bool upper(int box, Prio prio) { |
152 bool upper(int box, Prio prio) { |
148 return prio < boxes[box].min; |
153 return prio < boxes[box].min; |
269 data.pop_back(); |
274 data.pop_back(); |
270 } |
275 } |
271 |
276 |
272 public: |
277 public: |
273 |
278 |
274 /// \brief Insert an item into the heap with the given heap. |
279 /// \brief Insert an item into the heap with the given priority. |
275 /// |
280 /// |
276 /// Adds \c i to the heap with priority \c p. |
281 /// Adds \c i to the heap with priority \c p. |
277 /// \param i The item to insert. |
282 /// \param i The item to insert. |
278 /// \param p The priority of the item. |
283 /// \param p The priority of the item. |
279 void push(const Item &i, const Prio &p) { |
284 void push(const Item &i, const Prio &p) { |
290 /// \brief Returns the item with minimum priority. |
295 /// \brief Returns the item with minimum priority. |
291 /// |
296 /// |
292 /// This method returns the item with minimum priority. |
297 /// This method returns the item with minimum priority. |
293 /// \pre The heap must be nonempty. |
298 /// \pre The heap must be nonempty. |
294 Item top() const { |
299 Item top() const { |
295 const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown(); |
300 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown(); |
296 return data[boxes[0].first].item; |
301 return data[boxes[0].first].item; |
297 } |
302 } |
298 |
303 |
299 /// \brief Returns the minimum priority. |
304 /// \brief Returns the minimum priority. |
300 /// |
305 /// |
301 /// It returns the minimum priority. |
306 /// It returns the minimum priority. |
302 /// \pre The heap must be nonempty. |
307 /// \pre The heap must be nonempty. |
303 Prio prio() const { |
308 Prio prio() const { |
304 const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown(); |
309 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown(); |
305 return data[boxes[0].first].prio; |
310 return data[boxes[0].first].prio; |
306 } |
311 } |
307 |
312 |
308 /// \brief Deletes the item with minimum priority. |
313 /// \brief Deletes the item with minimum priority. |
309 /// |
314 /// |