53 |
53 |
54 } |
54 } |
55 |
55 |
56 /// \ingroup auxdat |
56 /// \ingroup auxdat |
57 /// |
57 /// |
58 /// \brief A Bucket Heap implementation. |
58 /// \brief Bucket heap data structure. |
59 /// |
59 /// |
60 /// This class implements the \e bucket \e heap data structure. A \e heap |
60 /// This class implements the \e bucket \e heap data structure. |
61 /// is a data structure for storing items with specified values called \e |
61 /// It practically conforms to the \ref concepts::Heap "heap concept", |
62 /// priorities in such a way that finding the item with minimum priority is |
62 /// but it has some limitations. |
63 /// efficient. The bucket heap is very simple implementation, it can store |
63 /// |
64 /// only integer priorities and it stores for each priority in the |
64 /// The bucket heap is a very simple structure. It can store only |
65 /// \f$ [0..C) \f$ range a list of items. So it should be used only when |
65 /// \c int priorities and it maintains a list of items for each priority |
66 /// the priorities are small. It is not intended to use as dijkstra heap. |
66 /// in the range <tt>[0..C)</tt>. So it should only be used when the |
67 /// |
67 /// priorities are small. It is not intended to use as a Dijkstra heap. |
68 /// \param IM A read and write Item int map, used internally |
68 /// |
69 /// to handle the cross references. |
69 /// \tparam IM A read-writable item map with \c int values, used |
70 /// \param MIN If the given parameter is false then instead of the |
70 /// internally to handle the cross references. |
71 /// minimum value the maximum can be retrivied with the top() and |
71 /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. |
72 /// prio() member functions. |
72 /// The default is \e min-heap. If this parameter is set to \c false, |
|
73 /// then the comparison is reversed, so the top(), prio() and pop() |
|
74 /// functions deal with the item having maximum priority instead of the |
|
75 /// minimum. |
|
76 /// |
|
77 /// \sa SimpleBucketHeap |
73 template <typename IM, bool MIN = true> |
78 template <typename IM, bool MIN = true> |
74 class BucketHeap { |
79 class BucketHeap { |
75 |
80 |
76 public: |
81 public: |
77 /// \e |
82 |
78 typedef typename IM::Key Item; |
83 /// Type of the item-int map. |
79 /// \e |
84 typedef IM ItemIntMap; |
|
85 /// Type of the priorities. |
80 typedef int Prio; |
86 typedef int Prio; |
81 /// \e |
87 /// Type of the items stored in the heap. |
82 typedef std::pair<Item, Prio> Pair; |
88 typedef typename ItemIntMap::Key Item; |
83 /// \e |
89 /// Type of the item-priority pairs. |
84 typedef IM ItemIntMap; |
90 typedef std::pair<Item,Prio> Pair; |
85 |
91 |
86 private: |
92 private: |
87 |
93 |
88 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; |
94 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; |
89 |
95 |
90 public: |
96 public: |
91 |
97 |
92 /// \brief Type to represent the items states. |
98 /// \brief Type to represent the states of the items. |
93 /// |
99 /// |
94 /// Each Item element have a state associated to it. It may be "in heap", |
100 /// Each item has a state associated to it. It can be "in heap", |
95 /// "pre heap" or "post heap". The latter two are indifferent from the |
101 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
96 /// heap's point of view, but may be useful to the user. |
102 /// heap's point of view, but may be useful to the user. |
97 /// |
103 /// |
98 /// The item-int map must be initialized in such way that it assigns |
104 /// The item-int map must be initialized in such way that it assigns |
99 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
105 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
100 enum State { |
106 enum State { |
102 PRE_HEAP = -1, ///< = -1. |
108 PRE_HEAP = -1, ///< = -1. |
103 POST_HEAP = -2 ///< = -2. |
109 POST_HEAP = -2 ///< = -2. |
104 }; |
110 }; |
105 |
111 |
106 public: |
112 public: |
107 /// \brief The constructor. |
113 |
108 /// |
114 /// \brief Constructor. |
109 /// The constructor. |
115 /// |
110 /// \param map should be given to the constructor, since it is used |
116 /// Constructor. |
111 /// internally to handle the cross references. The value of the map |
117 /// \param map A map that assigns \c int values to the items. |
112 /// should be PRE_HEAP (-1) for each element. |
118 /// It is used internally to handle the cross references. |
|
119 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
113 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} |
120 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} |
114 |
121 |
115 /// The number of items stored in the heap. |
122 /// \brief The number of items stored in the heap. |
116 /// |
123 /// |
117 /// \brief Returns the number of items stored in the heap. |
124 /// This function returns the number of items stored in the heap. |
118 int size() const { return _data.size(); } |
125 int size() const { return _data.size(); } |
119 |
126 |
120 /// \brief Checks if the heap stores no items. |
127 /// \brief Check if the heap is empty. |
121 /// |
128 /// |
122 /// Returns \c true if and only if the heap stores no items. |
129 /// This function returns \c true if the heap is empty. |
123 bool empty() const { return _data.empty(); } |
130 bool empty() const { return _data.empty(); } |
124 |
131 |
125 /// \brief Make empty this heap. |
132 /// \brief Make the heap empty. |
126 /// |
133 /// |
127 /// Make empty this heap. It does not change the cross reference |
134 /// This functon makes the heap empty. |
128 /// 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 |
129 /// 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 |
130 /// cross reference map for each item to \c PRE_HEAP. |
137 /// then you should set the cross reference map to \c PRE_HEAP |
|
138 /// for each item. |
131 void clear() { |
139 void clear() { |
132 _data.clear(); _first.clear(); _minimum = 0; |
140 _data.clear(); _first.clear(); _minimum = 0; |
133 } |
141 } |
134 |
142 |
135 private: |
143 private: |
172 _first[_data[idx].value] = idx; |
180 _first[_data[idx].value] = idx; |
173 _data[idx].prev = -1; |
181 _data[idx].prev = -1; |
174 } |
182 } |
175 |
183 |
176 public: |
184 public: |
|
185 |
177 /// \brief Insert a pair of item and priority into the heap. |
186 /// \brief Insert a pair of item and priority into the heap. |
178 /// |
187 /// |
179 /// Adds \c p.first to the heap with priority \c p.second. |
188 /// This function inserts \c p.first to the heap with priority |
|
189 /// \c p.second. |
180 /// \param p The pair to insert. |
190 /// \param p The pair to insert. |
|
191 /// \pre \c p.first must not be stored in the heap. |
181 void push(const Pair& p) { |
192 void push(const Pair& p) { |
182 push(p.first, p.second); |
193 push(p.first, p.second); |
183 } |
194 } |
184 |
195 |
185 /// \brief Insert an item into the heap with the given priority. |
196 /// \brief Insert an item into the heap with the given priority. |
186 /// |
197 /// |
187 /// Adds \c i to the heap with priority \c p. |
198 /// This function inserts the given item into the heap with the |
|
199 /// given priority. |
188 /// \param i The item to insert. |
200 /// \param i The item to insert. |
189 /// \param p The priority of the item. |
201 /// \param p The priority of the item. |
|
202 /// \pre \e i must not be stored in the heap. |
190 void push(const Item &i, const Prio &p) { |
203 void push(const Item &i, const Prio &p) { |
191 int idx = _data.size(); |
204 int idx = _data.size(); |
192 _iim[i] = idx; |
205 _iim[i] = idx; |
193 _data.push_back(BucketItem(i, p)); |
206 _data.push_back(BucketItem(i, p)); |
194 lace(idx); |
207 lace(idx); |
195 if (Direction::less(p, _minimum)) { |
208 if (Direction::less(p, _minimum)) { |
196 _minimum = p; |
209 _minimum = p; |
197 } |
210 } |
198 } |
211 } |
199 |
212 |
200 /// \brief Returns the item with minimum priority. |
213 /// \brief Return the item having minimum priority. |
201 /// |
214 /// |
202 /// This method returns the item with minimum priority. |
215 /// This function returns the item having minimum priority. |
203 /// \pre The heap must be nonempty. |
216 /// \pre The heap must be non-empty. |
204 Item top() const { |
217 Item top() const { |
205 while (_first[_minimum] == -1) { |
218 while (_first[_minimum] == -1) { |
206 Direction::increase(_minimum); |
219 Direction::increase(_minimum); |
207 } |
220 } |
208 return _data[_first[_minimum]].item; |
221 return _data[_first[_minimum]].item; |
209 } |
222 } |
210 |
223 |
211 /// \brief Returns the minimum priority. |
224 /// \brief The minimum priority. |
212 /// |
225 /// |
213 /// It returns the minimum priority. |
226 /// This function returns the minimum priority. |
214 /// \pre The heap must be nonempty. |
227 /// \pre The heap must be non-empty. |
215 Prio prio() const { |
228 Prio prio() const { |
216 while (_first[_minimum] == -1) { |
229 while (_first[_minimum] == -1) { |
217 Direction::increase(_minimum); |
230 Direction::increase(_minimum); |
218 } |
231 } |
219 return _minimum; |
232 return _minimum; |
220 } |
233 } |
221 |
234 |
222 /// \brief Deletes the item with minimum priority. |
235 /// \brief Remove the item having minimum priority. |
223 /// |
236 /// |
224 /// This method deletes the item with minimum priority from the heap. |
237 /// This function removes the item having minimum priority. |
225 /// \pre The heap must be non-empty. |
238 /// \pre The heap must be non-empty. |
226 void pop() { |
239 void pop() { |
227 while (_first[_minimum] == -1) { |
240 while (_first[_minimum] == -1) { |
228 Direction::increase(_minimum); |
241 Direction::increase(_minimum); |
229 } |
242 } |
231 _iim[_data[idx].item] = -2; |
244 _iim[_data[idx].item] = -2; |
232 unlace(idx); |
245 unlace(idx); |
233 relocate_last(idx); |
246 relocate_last(idx); |
234 } |
247 } |
235 |
248 |
236 /// \brief Deletes \c i from the heap. |
249 /// \brief Remove the given item from the heap. |
237 /// |
250 /// |
238 /// This method deletes item \c i from the heap, if \c i was |
251 /// This function removes the given item from the heap if it is |
239 /// already stored in the heap. |
252 /// already stored. |
240 /// \param i The item to erase. |
253 /// \param i The item to delete. |
|
254 /// \pre \e i must be in the heap. |
241 void erase(const Item &i) { |
255 void erase(const Item &i) { |
242 int idx = _iim[i]; |
256 int idx = _iim[i]; |
243 _iim[_data[idx].item] = -2; |
257 _iim[_data[idx].item] = -2; |
244 unlace(idx); |
258 unlace(idx); |
245 relocate_last(idx); |
259 relocate_last(idx); |
246 } |
260 } |
247 |
261 |
248 |
262 /// \brief The priority of the given item. |
249 /// \brief Returns the priority of \c i. |
263 /// |
250 /// |
264 /// This function returns the priority of the given item. |
251 /// This function returns the priority of item \c i. |
265 /// \param i The item. |
252 /// \pre \c i must be in the heap. |
266 /// \pre \e i must be in the heap. |
253 /// \param i The item. |
|
254 Prio operator[](const Item &i) const { |
267 Prio operator[](const Item &i) const { |
255 int idx = _iim[i]; |
268 int idx = _iim[i]; |
256 return _data[idx].value; |
269 return _data[idx].value; |
257 } |
270 } |
258 |
271 |
259 /// \brief \c i gets to the heap with priority \c p independently |
272 /// \brief Set the priority of an item or insert it, if it is |
260 /// if \c i was already there. |
273 /// not stored in the heap. |
261 /// |
274 /// |
262 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
275 /// This method sets the priority of the given item if it is |
263 /// in the heap and sets the priority of \c i to \c p otherwise. |
276 /// already stored in the heap. Otherwise it inserts the given |
|
277 /// item into the heap with the given priority. |
264 /// \param i The item. |
278 /// \param i The item. |
265 /// \param p The priority. |
279 /// \param p The priority. |
266 void set(const Item &i, const Prio &p) { |
280 void set(const Item &i, const Prio &p) { |
267 int idx = _iim[i]; |
281 int idx = _iim[i]; |
268 if (idx < 0) { |
282 if (idx < 0) { |
272 } else { |
286 } else { |
273 increase(i, p); |
287 increase(i, p); |
274 } |
288 } |
275 } |
289 } |
276 |
290 |
277 /// \brief Decreases the priority of \c i to \c p. |
291 /// \brief Decrease the priority of an item to the given value. |
278 /// |
292 /// |
279 /// This method decreases the priority of item \c i to \c p. |
293 /// This function decreases the priority of an item to the given value. |
280 /// \pre \c i must be stored in the heap with priority at least \c |
|
281 /// p relative to \c Compare. |
|
282 /// \param i The item. |
294 /// \param i The item. |
283 /// \param p The priority. |
295 /// \param p The priority. |
|
296 /// \pre \e i must be stored in the heap with priority at least \e p. |
284 void decrease(const Item &i, const Prio &p) { |
297 void decrease(const Item &i, const Prio &p) { |
285 int idx = _iim[i]; |
298 int idx = _iim[i]; |
286 unlace(idx); |
299 unlace(idx); |
287 _data[idx].value = p; |
300 _data[idx].value = p; |
288 if (Direction::less(p, _minimum)) { |
301 if (Direction::less(p, _minimum)) { |
289 _minimum = p; |
302 _minimum = p; |
290 } |
303 } |
291 lace(idx); |
304 lace(idx); |
292 } |
305 } |
293 |
306 |
294 /// \brief Increases the priority of \c i to \c p. |
307 /// \brief Increase the priority of an item to the given value. |
295 /// |
308 /// |
296 /// This method sets the priority of item \c i to \c p. |
309 /// This function increases the priority of an item to the given value. |
297 /// \pre \c i must be stored in the heap with priority at most \c |
|
298 /// p relative to \c Compare. |
|
299 /// \param i The item. |
310 /// \param i The item. |
300 /// \param p The priority. |
311 /// \param p The priority. |
|
312 /// \pre \e i must be stored in the heap with priority at most \e p. |
301 void increase(const Item &i, const Prio &p) { |
313 void increase(const Item &i, const Prio &p) { |
302 int idx = _iim[i]; |
314 int idx = _iim[i]; |
303 unlace(idx); |
315 unlace(idx); |
304 _data[idx].value = p; |
316 _data[idx].value = p; |
305 lace(idx); |
317 lace(idx); |
306 } |
318 } |
307 |
319 |
308 /// \brief Returns if \c item is in, has already been in, or has |
320 /// \brief Return the state of an item. |
309 /// never been in the heap. |
321 /// |
310 /// |
322 /// This method returns \c PRE_HEAP if the given item has never |
311 /// This method returns PRE_HEAP if \c item has never been in the |
323 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
312 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
324 /// and \c POST_HEAP otherwise. |
313 /// otherwise. In the latter case it is possible that \c item will |
325 /// In the latter case it is possible that the item will get back |
314 /// get back to the heap again. |
326 /// to the heap again. |
315 /// \param i The item. |
327 /// \param i The item. |
316 State state(const Item &i) const { |
328 State state(const Item &i) const { |
317 int idx = _iim[i]; |
329 int idx = _iim[i]; |
318 if (idx >= 0) idx = 0; |
330 if (idx >= 0) idx = 0; |
319 return State(idx); |
331 return State(idx); |
320 } |
332 } |
321 |
333 |
322 /// \brief Sets the state of the \c item in the heap. |
334 /// \brief Set the state of an item in the heap. |
323 /// |
335 /// |
324 /// Sets the state of the \c item in the heap. It can be used to |
336 /// This function sets the state of the given item in the heap. |
325 /// manually clear the heap when it is important to achive the |
337 /// It can be used to manually clear the heap when it is important |
326 /// better time complexity. |
338 /// to achive better time complexity. |
327 /// \param i The item. |
339 /// \param i The item. |
328 /// \param st The state. It should not be \c IN_HEAP. |
340 /// \param st The state. It should not be \c IN_HEAP. |
329 void state(const Item& i, State st) { |
341 void state(const Item& i, State st) { |
330 switch (st) { |
342 switch (st) { |
331 case POST_HEAP: |
343 case POST_HEAP: |
359 |
371 |
360 }; // class BucketHeap |
372 }; // class BucketHeap |
361 |
373 |
362 /// \ingroup auxdat |
374 /// \ingroup auxdat |
363 /// |
375 /// |
364 /// \brief A Simplified Bucket Heap implementation. |
376 /// \brief Simplified bucket heap data structure. |
365 /// |
377 /// |
366 /// This class implements a simplified \e bucket \e heap data |
378 /// This class implements a simplified \e bucket \e heap data |
367 /// structure. It does not provide some functionality but it faster |
379 /// structure. It does not provide some functionality, but it is |
368 /// and simplier data structure than the BucketHeap. The main |
380 /// faster and simpler than BucketHeap. The main difference is |
369 /// difference is that the BucketHeap stores for every key a double |
381 /// that BucketHeap stores a doubly-linked list for each key while |
370 /// linked list while this class stores just simple lists. In the |
382 /// this class stores only simply-linked lists. It supports erasing |
371 /// other way it does not support erasing each elements just the |
383 /// only for the item having minimum priority and it does not support |
372 /// minimal and it does not supports key increasing, decreasing. |
384 /// key increasing and decreasing. |
373 /// |
385 /// |
374 /// \param IM A read and write Item int map, used internally |
386 /// Note that this implementation does not conform to the |
375 /// to handle the cross references. |
387 /// \ref concepts::Heap "heap concept" due to the lack of some |
376 /// \param MIN If the given parameter is false then instead of the |
388 /// functionality. |
377 /// minimum value the maximum can be retrivied with the top() and |
389 /// |
378 /// prio() member functions. |
390 /// \tparam IM A read-writable item map with \c int values, used |
|
391 /// internally to handle the cross references. |
|
392 /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. |
|
393 /// The default is \e min-heap. If this parameter is set to \c false, |
|
394 /// then the comparison is reversed, so the top(), prio() and pop() |
|
395 /// functions deal with the item having maximum priority instead of the |
|
396 /// minimum. |
379 /// |
397 /// |
380 /// \sa BucketHeap |
398 /// \sa BucketHeap |
381 template <typename IM, bool MIN = true > |
399 template <typename IM, bool MIN = true > |
382 class SimpleBucketHeap { |
400 class SimpleBucketHeap { |
383 |
401 |
384 public: |
402 public: |
385 typedef typename IM::Key Item; |
403 |
|
404 /// Type of the item-int map. |
|
405 typedef IM ItemIntMap; |
|
406 /// Type of the priorities. |
386 typedef int Prio; |
407 typedef int Prio; |
387 typedef std::pair<Item, Prio> Pair; |
408 /// Type of the items stored in the heap. |
388 typedef IM ItemIntMap; |
409 typedef typename ItemIntMap::Key Item; |
|
410 /// Type of the item-priority pairs. |
|
411 typedef std::pair<Item,Prio> Pair; |
389 |
412 |
390 private: |
413 private: |
391 |
414 |
392 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; |
415 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; |
393 |
416 |
394 public: |
417 public: |
395 |
418 |
396 /// \brief Type to represent the items states. |
419 /// \brief Type to represent the states of the items. |
397 /// |
420 /// |
398 /// Each Item element have a state associated to it. It may be "in heap", |
421 /// Each item has a state associated to it. It can be "in heap", |
399 /// "pre heap" or "post heap". The latter two are indifferent from the |
422 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
400 /// heap's point of view, but may be useful to the user. |
423 /// heap's point of view, but may be useful to the user. |
401 /// |
424 /// |
402 /// The item-int map must be initialized in such way that it assigns |
425 /// The item-int map must be initialized in such way that it assigns |
403 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
426 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
404 enum State { |
427 enum State { |
407 POST_HEAP = -2 ///< = -2. |
430 POST_HEAP = -2 ///< = -2. |
408 }; |
431 }; |
409 |
432 |
410 public: |
433 public: |
411 |
434 |
412 /// \brief The constructor. |
435 /// \brief Constructor. |
413 /// |
436 /// |
414 /// The constructor. |
437 /// Constructor. |
415 /// \param map should be given to the constructor, since it is used |
438 /// \param map A map that assigns \c int values to the items. |
416 /// internally to handle the cross references. The value of the map |
439 /// It is used internally to handle the cross references. |
417 /// should be PRE_HEAP (-1) for each element. |
440 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
418 explicit SimpleBucketHeap(ItemIntMap &map) |
441 explicit SimpleBucketHeap(ItemIntMap &map) |
419 : _iim(map), _free(-1), _num(0), _minimum(0) {} |
442 : _iim(map), _free(-1), _num(0), _minimum(0) {} |
420 |
443 |
421 /// \brief Returns the number of items stored in the heap. |
444 /// \brief The number of items stored in the heap. |
422 /// |
445 /// |
423 /// The number of items stored in the heap. |
446 /// This function returns the number of items stored in the heap. |
424 int size() const { return _num; } |
447 int size() const { return _num; } |
425 |
448 |
426 /// \brief Checks if the heap stores no items. |
449 /// \brief Check if the heap is empty. |
427 /// |
450 /// |
428 /// Returns \c true if and only if the heap stores no items. |
451 /// This function returns \c true if the heap is empty. |
429 bool empty() const { return _num == 0; } |
452 bool empty() const { return _num == 0; } |
430 |
453 |
431 /// \brief Make empty this heap. |
454 /// \brief Make the heap empty. |
432 /// |
455 /// |
433 /// Make empty this heap. It does not change the cross reference |
456 /// This functon makes the heap empty. |
434 /// map. If you want to reuse a heap what is not surely empty you |
457 /// It does not change the cross reference map. If you want to reuse |
435 /// should first clear the heap and after that you should set the |
458 /// a heap that is not surely empty, you should first clear it and |
436 /// cross reference map for each item to \c PRE_HEAP. |
459 /// then you should set the cross reference map to \c PRE_HEAP |
|
460 /// for each item. |
437 void clear() { |
461 void clear() { |
438 _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; |
462 _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; |
439 } |
463 } |
440 |
464 |
441 /// \brief Insert a pair of item and priority into the heap. |
465 /// \brief Insert a pair of item and priority into the heap. |
442 /// |
466 /// |
443 /// Adds \c p.first to the heap with priority \c p.second. |
467 /// This function inserts \c p.first to the heap with priority |
|
468 /// \c p.second. |
444 /// \param p The pair to insert. |
469 /// \param p The pair to insert. |
|
470 /// \pre \c p.first must not be stored in the heap. |
445 void push(const Pair& p) { |
471 void push(const Pair& p) { |
446 push(p.first, p.second); |
472 push(p.first, p.second); |
447 } |
473 } |
448 |
474 |
449 /// \brief Insert an item into the heap with the given priority. |
475 /// \brief Insert an item into the heap with the given priority. |
450 /// |
476 /// |
451 /// Adds \c i to the heap with priority \c p. |
477 /// This function inserts the given item into the heap with the |
|
478 /// given priority. |
452 /// \param i The item to insert. |
479 /// \param i The item to insert. |
453 /// \param p The priority of the item. |
480 /// \param p The priority of the item. |
|
481 /// \pre \e i must not be stored in the heap. |
454 void push(const Item &i, const Prio &p) { |
482 void push(const Item &i, const Prio &p) { |
455 int idx; |
483 int idx; |
456 if (_free == -1) { |
484 if (_free == -1) { |
457 idx = _data.size(); |
485 idx = _data.size(); |
458 _data.push_back(BucketItem(i)); |
486 _data.push_back(BucketItem(i)); |
469 _minimum = p; |
497 _minimum = p; |
470 } |
498 } |
471 ++_num; |
499 ++_num; |
472 } |
500 } |
473 |
501 |
474 /// \brief Returns the item with minimum priority. |
502 /// \brief Return the item having minimum priority. |
475 /// |
503 /// |
476 /// This method returns the item with minimum priority. |
504 /// This function returns the item having minimum priority. |
477 /// \pre The heap must be nonempty. |
505 /// \pre The heap must be non-empty. |
478 Item top() const { |
506 Item top() const { |
479 while (_first[_minimum] == -1) { |
507 while (_first[_minimum] == -1) { |
480 Direction::increase(_minimum); |
508 Direction::increase(_minimum); |
481 } |
509 } |
482 return _data[_first[_minimum]].item; |
510 return _data[_first[_minimum]].item; |
483 } |
511 } |
484 |
512 |
485 /// \brief Returns the minimum priority. |
513 /// \brief The minimum priority. |
486 /// |
514 /// |
487 /// It returns the minimum priority. |
515 /// This function returns the minimum priority. |
488 /// \pre The heap must be nonempty. |
516 /// \pre The heap must be non-empty. |
489 Prio prio() const { |
517 Prio prio() const { |
490 while (_first[_minimum] == -1) { |
518 while (_first[_minimum] == -1) { |
491 Direction::increase(_minimum); |
519 Direction::increase(_minimum); |
492 } |
520 } |
493 return _minimum; |
521 return _minimum; |
494 } |
522 } |
495 |
523 |
496 /// \brief Deletes the item with minimum priority. |
524 /// \brief Remove the item having minimum priority. |
497 /// |
525 /// |
498 /// This method deletes the item with minimum priority from the heap. |
526 /// This function removes the item having minimum priority. |
499 /// \pre The heap must be non-empty. |
527 /// \pre The heap must be non-empty. |
500 void pop() { |
528 void pop() { |
501 while (_first[_minimum] == -1) { |
529 while (_first[_minimum] == -1) { |
502 Direction::increase(_minimum); |
530 Direction::increase(_minimum); |
503 } |
531 } |
507 _data[idx].next = _free; |
535 _data[idx].next = _free; |
508 _free = idx; |
536 _free = idx; |
509 --_num; |
537 --_num; |
510 } |
538 } |
511 |
539 |
512 /// \brief Returns the priority of \c i. |
540 /// \brief The priority of the given item. |
513 /// |
541 /// |
514 /// This function returns the priority of item \c i. |
542 /// This function returns the priority of the given item. |
515 /// \warning This operator is not a constant time function |
543 /// \param i The item. |
516 /// because it scans the whole data structure to find the proper |
544 /// \pre \e i must be in the heap. |
517 /// value. |
545 /// \warning This operator is not a constant time function because |
518 /// \pre \c i must be in the heap. |
546 /// it scans the whole data structure to find the proper value. |
519 /// \param i The item. |
|
520 Prio operator[](const Item &i) const { |
547 Prio operator[](const Item &i) const { |
521 for (int k = 0; k < _first.size(); ++k) { |
548 for (int k = 0; k < int(_first.size()); ++k) { |
522 int idx = _first[k]; |
549 int idx = _first[k]; |
523 while (idx != -1) { |
550 while (idx != -1) { |
524 if (_data[idx].item == i) { |
551 if (_data[idx].item == i) { |
525 return k; |
552 return k; |
526 } |
553 } |
528 } |
555 } |
529 } |
556 } |
530 return -1; |
557 return -1; |
531 } |
558 } |
532 |
559 |
533 /// \brief Returns if \c item is in, has already been in, or has |
560 /// \brief Return the state of an item. |
534 /// never been in the heap. |
561 /// |
535 /// |
562 /// This method returns \c PRE_HEAP if the given item has never |
536 /// This method returns PRE_HEAP if \c item has never been in the |
563 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
537 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
564 /// and \c POST_HEAP otherwise. |
538 /// otherwise. In the latter case it is possible that \c item will |
565 /// In the latter case it is possible that the item will get back |
539 /// get back to the heap again. |
566 /// to the heap again. |
540 /// \param i The item. |
567 /// \param i The item. |
541 State state(const Item &i) const { |
568 State state(const Item &i) const { |
542 int idx = _iim[i]; |
569 int idx = _iim[i]; |
543 if (idx >= 0) idx = 0; |
570 if (idx >= 0) idx = 0; |
544 return State(idx); |
571 return State(idx); |