19 #ifndef LEMON_RADIX_HEAP_H |
19 #ifndef LEMON_RADIX_HEAP_H |
20 #define LEMON_RADIX_HEAP_H |
20 #define LEMON_RADIX_HEAP_H |
21 |
21 |
22 ///\ingroup auxdat |
22 ///\ingroup auxdat |
23 ///\file |
23 ///\file |
24 ///\brief Radix Heap implementation. |
24 ///\brief Radix heap implementation. |
25 |
25 |
26 #include <vector> |
26 #include <vector> |
27 #include <lemon/error.h> |
27 #include <lemon/error.h> |
28 |
28 |
29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 |
31 |
32 /// \ingroup auxdata |
32 /// \ingroup auxdat |
33 /// |
33 /// |
34 /// \brief A Radix Heap implementation. |
34 /// \brief Radix heap data structure. |
35 /// |
35 /// |
36 /// This class implements the \e radix \e heap data structure. A \e heap |
36 /// This class implements the \e radix \e heap data structure. |
37 /// is a data structure for storing items with specified values called \e |
37 /// It practically conforms to the \ref concepts::Heap "heap concept", |
38 /// priorities in such a way that finding the item with minimum priority is |
38 /// but it has some limitations due its special implementation. |
39 /// efficient. This heap type can store only items with \e int priority. |
39 /// The type of the priorities must be \c int and the priority of an |
40 /// In a heap one can change the priority of an item, add or erase an |
40 /// item cannot be decreased under the priority of the last removed item. |
41 /// item, but the priority cannot be decreased under the last removed |
|
42 /// item's priority. |
|
43 /// |
41 /// |
44 /// \param IM A read and writable Item int map, used internally |
42 /// \tparam IM A read-writable item map with \c int values, used |
45 /// to handle the cross references. |
43 /// internally to handle the cross references. |
46 /// |
|
47 /// \see BinHeap |
|
48 /// \see Dijkstra |
|
49 template <typename IM> |
44 template <typename IM> |
50 class RadixHeap { |
45 class RadixHeap { |
51 |
46 |
52 public: |
47 public: |
53 typedef typename IM::Key Item; |
48 |
|
49 /// Type of the item-int map. |
|
50 typedef IM ItemIntMap; |
|
51 /// Type of the priorities. |
54 typedef int Prio; |
52 typedef int Prio; |
55 typedef IM ItemIntMap; |
53 /// Type of the items stored in the heap. |
|
54 typedef typename ItemIntMap::Key Item; |
56 |
55 |
57 /// \brief Exception thrown by RadixHeap. |
56 /// \brief Exception thrown by RadixHeap. |
58 /// |
57 /// |
59 /// This Exception is thrown when a smaller priority |
58 /// This exception is thrown when an item is inserted into a |
60 /// is inserted into the \e RadixHeap then the last time erased. |
59 /// RadixHeap with a priority smaller than the last erased one. |
61 /// \see RadixHeap |
60 /// \see RadixHeap |
62 |
|
63 class UnderFlowPriorityError : public Exception { |
61 class UnderFlowPriorityError : public Exception { |
64 public: |
62 public: |
65 virtual const char* what() const throw() { |
63 virtual const char* what() const throw() { |
66 return "lemon::RadixHeap::UnderFlowPriorityError"; |
64 return "lemon::RadixHeap::UnderFlowPriorityError"; |
67 } |
65 } |
68 }; |
66 }; |
69 |
67 |
70 /// \brief Type to represent the items states. |
68 /// \brief Type to represent the states of the items. |
71 /// |
69 /// |
72 /// Each Item element have a state associated to it. It may be "in heap", |
70 /// Each item has a state associated to it. It can be "in heap", |
73 /// "pre heap" or "post heap". The latter two are indifferent from the |
71 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
74 /// heap's point of view, but may be useful to the user. |
72 /// heap's point of view, but may be useful to the user. |
75 /// |
73 /// |
76 /// The ItemIntMap \e should be initialized in such way that it maps |
74 /// The item-int map must be initialized in such way that it assigns |
77 /// PRE_HEAP (-1) to any element to be put in the heap... |
75 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
78 enum State { |
76 enum State { |
79 IN_HEAP = 0, |
77 IN_HEAP = 0, ///< = 0. |
80 PRE_HEAP = -1, |
78 PRE_HEAP = -1, ///< = -1. |
81 POST_HEAP = -2 |
79 POST_HEAP = -2 ///< = -2. |
82 }; |
80 }; |
83 |
81 |
84 private: |
82 private: |
85 |
83 |
86 struct RadixItem { |
84 struct RadixItem { |
99 std::vector<RadixItem> data; |
97 std::vector<RadixItem> data; |
100 std::vector<RadixBox> boxes; |
98 std::vector<RadixBox> boxes; |
101 |
99 |
102 ItemIntMap &_iim; |
100 ItemIntMap &_iim; |
103 |
101 |
104 |
|
105 public: |
102 public: |
106 /// \brief The constructor. |
103 |
107 /// |
104 /// \brief Constructor. |
108 /// The constructor. |
105 /// |
109 /// |
106 /// Constructor. |
110 /// \param map It should be given to the constructor, since it is used |
107 /// \param map A map that assigns \c int values to the items. |
111 /// internally to handle the cross references. The value of the map |
108 /// It is used internally to handle the cross references. |
112 /// should be PRE_HEAP (-1) for each element. |
109 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
113 /// |
110 /// \param minimum The initial minimum value of the heap. |
114 /// \param minimal The initial minimal value of the heap. |
111 /// \param capacity The initial capacity of the heap. |
115 /// \param capacity It determines the initial capacity of the heap. |
112 RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0) |
116 RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0) |
113 : _iim(map) |
117 : _iim(map) { |
114 { |
118 boxes.push_back(RadixBox(minimal, 1)); |
115 boxes.push_back(RadixBox(minimum, 1)); |
119 boxes.push_back(RadixBox(minimal + 1, 1)); |
116 boxes.push_back(RadixBox(minimum + 1, 1)); |
120 while (lower(boxes.size() - 1, capacity + minimal - 1)) { |
117 while (lower(boxes.size() - 1, capacity + minimum - 1)) { |
121 extend(); |
118 extend(); |
122 } |
119 } |
123 } |
120 } |
124 |
121 |
125 /// The number of items stored in the heap. |
122 /// \brief The number of items stored in the heap. |
126 /// |
123 /// |
127 /// \brief Returns the number of items stored in the heap. |
124 /// This function returns the number of items stored in the heap. |
128 int size() const { return data.size(); } |
125 int size() const { return data.size(); } |
129 /// \brief Checks if the heap stores no items. |
126 |
130 /// |
127 /// \brief Check if the heap is empty. |
131 /// Returns \c true if and only if the heap stores no items. |
128 /// |
|
129 /// This function returns \c true if the heap is empty. |
132 bool empty() const { return data.empty(); } |
130 bool empty() const { return data.empty(); } |
133 |
131 |
134 /// \brief Make empty this heap. |
132 /// \brief Make the heap empty. |
135 /// |
133 /// |
136 /// Make empty this heap. It does not change the cross reference |
134 /// This functon makes the heap empty. |
137 /// map. If you want to reuse a heap what is not surely empty you |
135 /// It does not change the cross reference map. If you want to reuse |
138 /// should first clear the heap and after that you should set the |
136 /// a heap that is not surely empty, you should first clear it and |
139 /// cross reference map for each item to \c PRE_HEAP. |
137 /// then you should set the cross reference map to \c PRE_HEAP |
140 void clear(int minimal = 0, int capacity = 0) { |
138 /// for each item. |
|
139 /// \param minimum The minimum value of the heap. |
|
140 /// \param capacity The capacity of the heap. |
|
141 void clear(int minimum = 0, int capacity = 0) { |
141 data.clear(); boxes.clear(); |
142 data.clear(); boxes.clear(); |
142 boxes.push_back(RadixBox(minimal, 1)); |
143 boxes.push_back(RadixBox(minimum, 1)); |
143 boxes.push_back(RadixBox(minimal + 1, 1)); |
144 boxes.push_back(RadixBox(minimum + 1, 1)); |
144 while (lower(boxes.size() - 1, capacity + minimal - 1)) { |
145 while (lower(boxes.size() - 1, capacity + minimum - 1)) { |
145 extend(); |
146 extend(); |
146 } |
147 } |
147 } |
148 } |
148 |
149 |
149 private: |
150 private: |
180 boxes[box].first = index; |
181 boxes[box].first = index; |
181 } |
182 } |
182 data[index].box = box; |
183 data[index].box = box; |
183 } |
184 } |
184 |
185 |
185 /// \brief Add a new box to the box list. |
186 // Add a new box to the box list |
186 void extend() { |
187 void extend() { |
187 int min = boxes.back().min + boxes.back().size; |
188 int min = boxes.back().min + boxes.back().size; |
188 int bs = 2 * boxes.back().size; |
189 int bs = 2 * boxes.back().size; |
189 boxes.push_back(RadixBox(min, bs)); |
190 boxes.push_back(RadixBox(min, bs)); |
190 } |
191 } |
191 |
192 |
192 /// \brief Move an item up into the proper box. |
193 // Move an item up into the proper box. |
193 void bubble_up(int index) { |
194 void bubble_up(int index) { |
194 if (!lower(data[index].box, data[index].prio)) return; |
195 if (!lower(data[index].box, data[index].prio)) return; |
195 remove(index); |
196 remove(index); |
196 int box = findUp(data[index].box, data[index].prio); |
197 int box = findUp(data[index].box, data[index].prio); |
197 insert(box, index); |
198 insert(box, index); |
198 } |
199 } |
199 |
200 |
200 /// \brief Find up the proper box for the item with the given prio. |
201 // Find up the proper box for the item with the given priority |
201 int findUp(int start, int pr) { |
202 int findUp(int start, int pr) { |
202 while (lower(start, pr)) { |
203 while (lower(start, pr)) { |
203 if (++start == int(boxes.size())) { |
204 if (++start == int(boxes.size())) { |
204 extend(); |
205 extend(); |
205 } |
206 } |
206 } |
207 } |
207 return start; |
208 return start; |
208 } |
209 } |
209 |
210 |
210 /// \brief Move an item down into the proper box. |
211 // Move an item down into the proper box |
211 void bubble_down(int index) { |
212 void bubble_down(int index) { |
212 if (!upper(data[index].box, data[index].prio)) return; |
213 if (!upper(data[index].box, data[index].prio)) return; |
213 remove(index); |
214 remove(index); |
214 int box = findDown(data[index].box, data[index].prio); |
215 int box = findDown(data[index].box, data[index].prio); |
215 insert(box, index); |
216 insert(box, index); |
216 } |
217 } |
217 |
218 |
218 /// \brief Find up the proper box for the item with the given prio. |
219 // Find down the proper box for the item with the given priority |
219 int findDown(int start, int pr) { |
220 int findDown(int start, int pr) { |
220 while (upper(start, pr)) { |
221 while (upper(start, pr)) { |
221 if (--start < 0) throw UnderFlowPriorityError(); |
222 if (--start < 0) throw UnderFlowPriorityError(); |
222 } |
223 } |
223 return start; |
224 return start; |
224 } |
225 } |
225 |
226 |
226 /// \brief Find the first not empty box. |
227 // Find the first non-empty box |
227 int findFirst() { |
228 int findFirst() { |
228 int first = 0; |
229 int first = 0; |
229 while (boxes[first].first == -1) ++first; |
230 while (boxes[first].first == -1) ++first; |
230 return first; |
231 return first; |
231 } |
232 } |
232 |
233 |
233 /// \brief Gives back the minimal prio of the box. |
234 // Gives back the minimum priority of the given box |
234 int minValue(int box) { |
235 int minValue(int box) { |
235 int min = data[boxes[box].first].prio; |
236 int min = data[boxes[box].first].prio; |
236 for (int k = boxes[box].first; k != -1; k = data[k].next) { |
237 for (int k = boxes[box].first; k != -1; k = data[k].next) { |
237 if (data[k].prio < min) min = data[k].prio; |
238 if (data[k].prio < min) min = data[k].prio; |
238 } |
239 } |
239 return min; |
240 return min; |
240 } |
241 } |
241 |
242 |
242 /// \brief Rearrange the items of the heap and makes the |
243 // Rearrange the items of the heap and make the first box non-empty |
243 /// first box not empty. |
|
244 void moveDown() { |
244 void moveDown() { |
245 int box = findFirst(); |
245 int box = findFirst(); |
246 if (box == 0) return; |
246 if (box == 0) return; |
247 int min = minValue(box); |
247 int min = minValue(box); |
248 for (int i = 0; i <= box; ++i) { |
248 for (int i = 0; i <= box; ++i) { |
275 |
275 |
276 public: |
276 public: |
277 |
277 |
278 /// \brief Insert an item into the heap with the given priority. |
278 /// \brief Insert an item into the heap with the given priority. |
279 /// |
279 /// |
280 /// Adds \c i to the heap with priority \c p. |
280 /// This function inserts the given item into the heap with the |
|
281 /// given priority. |
281 /// \param i The item to insert. |
282 /// \param i The item to insert. |
282 /// \param p The priority of the item. |
283 /// \param p The priority of the item. |
|
284 /// \pre \e i must not be stored in the heap. |
|
285 /// \warning This method may throw an \c UnderFlowPriorityException. |
283 void push(const Item &i, const Prio &p) { |
286 void push(const Item &i, const Prio &p) { |
284 int n = data.size(); |
287 int n = data.size(); |
285 _iim.set(i, n); |
288 _iim.set(i, n); |
286 data.push_back(RadixItem(i, p)); |
289 data.push_back(RadixItem(i, p)); |
287 while (lower(boxes.size() - 1, p)) { |
290 while (lower(boxes.size() - 1, p)) { |
289 } |
292 } |
290 int box = findDown(boxes.size() - 1, p); |
293 int box = findDown(boxes.size() - 1, p); |
291 insert(box, n); |
294 insert(box, n); |
292 } |
295 } |
293 |
296 |
294 /// \brief Returns the item with minimum priority. |
297 /// \brief Return the item having minimum priority. |
295 /// |
298 /// |
296 /// This method returns the item with minimum priority. |
299 /// This function returns the item having minimum priority. |
297 /// \pre The heap must be nonempty. |
300 /// \pre The heap must be non-empty. |
298 Item top() const { |
301 Item top() const { |
299 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); |
302 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); |
300 return data[boxes[0].first].item; |
303 return data[boxes[0].first].item; |
301 } |
304 } |
302 |
305 |
303 /// \brief Returns the minimum priority. |
306 /// \brief The minimum priority. |
304 /// |
307 /// |
305 /// It returns the minimum priority. |
308 /// This function returns the minimum priority. |
306 /// \pre The heap must be nonempty. |
309 /// \pre The heap must be non-empty. |
307 Prio prio() const { |
310 Prio prio() const { |
308 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); |
311 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); |
309 return data[boxes[0].first].prio; |
312 return data[boxes[0].first].prio; |
310 } |
313 } |
311 |
314 |
312 /// \brief Deletes the item with minimum priority. |
315 /// \brief Remove the item having minimum priority. |
313 /// |
316 /// |
314 /// This method deletes the item with minimum priority. |
317 /// This function removes the item having minimum priority. |
315 /// \pre The heap must be non-empty. |
318 /// \pre The heap must be non-empty. |
316 void pop() { |
319 void pop() { |
317 moveDown(); |
320 moveDown(); |
318 int index = boxes[0].first; |
321 int index = boxes[0].first; |
319 _iim[data[index].item] = POST_HEAP; |
322 _iim[data[index].item] = POST_HEAP; |
320 remove(index); |
323 remove(index); |
321 relocate_last(index); |
324 relocate_last(index); |
322 } |
325 } |
323 |
326 |
324 /// \brief Deletes \c i from the heap. |
327 /// \brief Remove the given item from the heap. |
325 /// |
328 /// |
326 /// This method deletes item \c i from the heap, if \c i was |
329 /// This function removes the given item from the heap if it is |
327 /// already stored in the heap. |
330 /// already stored. |
328 /// \param i The item to erase. |
331 /// \param i The item to delete. |
|
332 /// \pre \e i must be in the heap. |
329 void erase(const Item &i) { |
333 void erase(const Item &i) { |
330 int index = _iim[i]; |
334 int index = _iim[i]; |
331 _iim[i] = POST_HEAP; |
335 _iim[i] = POST_HEAP; |
332 remove(index); |
336 remove(index); |
333 relocate_last(index); |
337 relocate_last(index); |
334 } |
338 } |
335 |
339 |
336 /// \brief Returns the priority of \c i. |
340 /// \brief The priority of the given item. |
337 /// |
341 /// |
338 /// This function returns the priority of item \c i. |
342 /// This function returns the priority of the given item. |
339 /// \pre \c i must be in the heap. |
343 /// \param i The item. |
340 /// \param i The item. |
344 /// \pre \e i must be in the heap. |
341 Prio operator[](const Item &i) const { |
345 Prio operator[](const Item &i) const { |
342 int idx = _iim[i]; |
346 int idx = _iim[i]; |
343 return data[idx].prio; |
347 return data[idx].prio; |
344 } |
348 } |
345 |
349 |
346 /// \brief \c i gets to the heap with priority \c p independently |
350 /// \brief Set the priority of an item or insert it, if it is |
347 /// if \c i was already there. |
351 /// not stored in the heap. |
348 /// |
352 /// |
349 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
353 /// This method sets the priority of the given item if it is |
350 /// in the heap and sets the priority of \c i to \c p otherwise. |
354 /// already stored in the heap. Otherwise it inserts the given |
351 /// It may throw an \e UnderFlowPriorityException. |
355 /// item into the heap with the given priority. |
352 /// \param i The item. |
356 /// \param i The item. |
353 /// \param p The priority. |
357 /// \param p The priority. |
|
358 /// \pre \e i must be in the heap. |
|
359 /// \warning This method may throw an \c UnderFlowPriorityException. |
354 void set(const Item &i, const Prio &p) { |
360 void set(const Item &i, const Prio &p) { |
355 int idx = _iim[i]; |
361 int idx = _iim[i]; |
356 if( idx < 0 ) { |
362 if( idx < 0 ) { |
357 push(i, p); |
363 push(i, p); |
358 } |
364 } |
363 data[idx].prio = p; |
369 data[idx].prio = p; |
364 bubble_down(idx); |
370 bubble_down(idx); |
365 } |
371 } |
366 } |
372 } |
367 |
373 |
368 |
374 /// \brief Decrease the priority of an item to the given value. |
369 /// \brief Decreases the priority of \c i to \c p. |
375 /// |
370 /// |
376 /// This function decreases the priority of an item to the given value. |
371 /// This method decreases the priority of item \c i to \c p. |
|
372 /// \pre \c i must be stored in the heap with priority at least \c p, and |
|
373 /// \c should be greater or equal to the last removed item's priority. |
|
374 /// \param i The item. |
377 /// \param i The item. |
375 /// \param p The priority. |
378 /// \param p The priority. |
|
379 /// \pre \e i must be stored in the heap with priority at least \e p. |
|
380 /// \warning This method may throw an \c UnderFlowPriorityException. |
376 void decrease(const Item &i, const Prio &p) { |
381 void decrease(const Item &i, const Prio &p) { |
377 int idx = _iim[i]; |
382 int idx = _iim[i]; |
378 data[idx].prio = p; |
383 data[idx].prio = p; |
379 bubble_down(idx); |
384 bubble_down(idx); |
380 } |
385 } |
381 |
386 |
382 /// \brief Increases the priority of \c i to \c p. |
387 /// \brief Increase the priority of an item to the given value. |
383 /// |
388 /// |
384 /// This method sets the priority of item \c i to \c p. |
389 /// This function increases the priority of an item to the given value. |
385 /// \pre \c i must be stored in the heap with priority at most \c p |
|
386 /// \param i The item. |
390 /// \param i The item. |
387 /// \param p The priority. |
391 /// \param p The priority. |
|
392 /// \pre \e i must be stored in the heap with priority at most \e p. |
388 void increase(const Item &i, const Prio &p) { |
393 void increase(const Item &i, const Prio &p) { |
389 int idx = _iim[i]; |
394 int idx = _iim[i]; |
390 data[idx].prio = p; |
395 data[idx].prio = p; |
391 bubble_up(idx); |
396 bubble_up(idx); |
392 } |
397 } |
393 |
398 |
394 /// \brief Returns if \c item is in, has already been in, or has |
399 /// \brief Return the state of an item. |
395 /// never been in the heap. |
400 /// |
396 /// |
401 /// This method returns \c PRE_HEAP if the given item has never |
397 /// This method returns PRE_HEAP if \c item has never been in the |
402 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
398 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
403 /// and \c POST_HEAP otherwise. |
399 /// otherwise. In the latter case it is possible that \c item will |
404 /// In the latter case it is possible that the item will get back |
400 /// get back to the heap again. |
405 /// to the heap again. |
401 /// \param i The item. |
406 /// \param i The item. |
402 State state(const Item &i) const { |
407 State state(const Item &i) const { |
403 int s = _iim[i]; |
408 int s = _iim[i]; |
404 if( s >= 0 ) s = 0; |
409 if( s >= 0 ) s = 0; |
405 return State(s); |
410 return State(s); |
406 } |
411 } |
407 |
412 |
408 /// \brief Sets the state of the \c item in the heap. |
413 /// \brief Set the state of an item in the heap. |
409 /// |
414 /// |
410 /// Sets the state of the \c item in the heap. It can be used to |
415 /// This function sets the state of the given item in the heap. |
411 /// manually clear the heap when it is important to achive the |
416 /// It can be used to manually clear the heap when it is important |
412 /// better time complexity. |
417 /// to achive better time complexity. |
413 /// \param i The item. |
418 /// \param i The item. |
414 /// \param st The state. It should not be \c IN_HEAP. |
419 /// \param st The state. It should not be \c IN_HEAP. |
415 void state(const Item& i, State st) { |
420 void state(const Item& i, State st) { |
416 switch (st) { |
421 switch (st) { |
417 case POST_HEAP: |
422 case POST_HEAP: |