1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_BUCKET_HEAP_H |
|
20 #define LEMON_BUCKET_HEAP_H |
|
21 |
|
22 ///\ingroup auxdat |
|
23 ///\file |
|
24 ///\brief Bucket Heap implementation. |
|
25 |
|
26 #include <vector> |
|
27 #include <utility> |
|
28 #include <functional> |
|
29 |
|
30 namespace lemon { |
|
31 |
|
32 namespace _bucket_heap_bits { |
|
33 |
|
34 template <bool MIN> |
|
35 struct DirectionTraits { |
|
36 static bool less(int left, int right) { |
|
37 return left < right; |
|
38 } |
|
39 static void increase(int& value) { |
|
40 ++value; |
|
41 } |
|
42 }; |
|
43 |
|
44 template <> |
|
45 struct DirectionTraits<false> { |
|
46 static bool less(int left, int right) { |
|
47 return left > right; |
|
48 } |
|
49 static void increase(int& value) { |
|
50 --value; |
|
51 } |
|
52 }; |
|
53 |
|
54 } |
|
55 |
|
56 /// \ingroup auxdat |
|
57 /// |
|
58 /// \brief A Bucket Heap implementation. |
|
59 /// |
|
60 /// This class implements the \e bucket \e heap data structure. A \e heap |
|
61 /// is a data structure for storing items with specified values called \e |
|
62 /// priorities in such a way that finding the item with minimum priority is |
|
63 /// efficient. The bucket heap is very simple implementation, it can store |
|
64 /// only integer priorities and it stores for each priority in the |
|
65 /// \f$ [0..C) \f$ range a list of items. So it should be used only when |
|
66 /// the priorities are small. It is not intended to use as dijkstra heap. |
|
67 /// |
|
68 /// \param IM A read and write Item int map, used internally |
|
69 /// to handle the cross references. |
|
70 /// \param MIN If the given parameter is false then instead of the |
|
71 /// minimum value the maximum can be retrivied with the top() and |
|
72 /// prio() member functions. |
|
73 template <typename IM, bool MIN = true> |
|
74 class BucketHeap { |
|
75 |
|
76 public: |
|
77 /// \e |
|
78 typedef typename IM::Key Item; |
|
79 /// \e |
|
80 typedef int Prio; |
|
81 /// \e |
|
82 typedef std::pair<Item, Prio> Pair; |
|
83 /// \e |
|
84 typedef IM ItemIntMap; |
|
85 |
|
86 private: |
|
87 |
|
88 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; |
|
89 |
|
90 public: |
|
91 |
|
92 /// \brief Type to represent the items states. |
|
93 /// |
|
94 /// Each Item element have a state associated to it. It may be "in heap", |
|
95 /// "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. |
|
97 /// |
|
98 /// 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. |
|
100 enum State { |
|
101 IN_HEAP = 0, ///< = 0. |
|
102 PRE_HEAP = -1, ///< = -1. |
|
103 POST_HEAP = -2 ///< = -2. |
|
104 }; |
|
105 |
|
106 public: |
|
107 /// \brief The constructor. |
|
108 /// |
|
109 /// The constructor. |
|
110 /// \param map should be given to the constructor, since it is used |
|
111 /// internally to handle the cross references. The value of the map |
|
112 /// should be PRE_HEAP (-1) for each element. |
|
113 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} |
|
114 |
|
115 /// The number of items stored in the heap. |
|
116 /// |
|
117 /// \brief Returns the number of items stored in the heap. |
|
118 int size() const { return _data.size(); } |
|
119 |
|
120 /// \brief Checks if the heap stores no items. |
|
121 /// |
|
122 /// Returns \c true if and only if the heap stores no items. |
|
123 bool empty() const { return _data.empty(); } |
|
124 |
|
125 /// \brief Make empty this heap. |
|
126 /// |
|
127 /// Make empty this heap. It does not change the cross reference |
|
128 /// map. If you want to reuse a heap what is not surely empty you |
|
129 /// should first clear the heap and after that you should set the |
|
130 /// cross reference map for each item to \c PRE_HEAP. |
|
131 void clear() { |
|
132 _data.clear(); _first.clear(); _minimum = 0; |
|
133 } |
|
134 |
|
135 private: |
|
136 |
|
137 void relocate_last(int idx) { |
|
138 if (idx + 1 < int(_data.size())) { |
|
139 _data[idx] = _data.back(); |
|
140 if (_data[idx].prev != -1) { |
|
141 _data[_data[idx].prev].next = idx; |
|
142 } else { |
|
143 _first[_data[idx].value] = idx; |
|
144 } |
|
145 if (_data[idx].next != -1) { |
|
146 _data[_data[idx].next].prev = idx; |
|
147 } |
|
148 _iim[_data[idx].item] = idx; |
|
149 } |
|
150 _data.pop_back(); |
|
151 } |
|
152 |
|
153 void unlace(int idx) { |
|
154 if (_data[idx].prev != -1) { |
|
155 _data[_data[idx].prev].next = _data[idx].next; |
|
156 } else { |
|
157 _first[_data[idx].value] = _data[idx].next; |
|
158 } |
|
159 if (_data[idx].next != -1) { |
|
160 _data[_data[idx].next].prev = _data[idx].prev; |
|
161 } |
|
162 } |
|
163 |
|
164 void lace(int idx) { |
|
165 if (int(_first.size()) <= _data[idx].value) { |
|
166 _first.resize(_data[idx].value + 1, -1); |
|
167 } |
|
168 _data[idx].next = _first[_data[idx].value]; |
|
169 if (_data[idx].next != -1) { |
|
170 _data[_data[idx].next].prev = idx; |
|
171 } |
|
172 _first[_data[idx].value] = idx; |
|
173 _data[idx].prev = -1; |
|
174 } |
|
175 |
|
176 public: |
|
177 /// \brief Insert a pair of item and priority into the heap. |
|
178 /// |
|
179 /// Adds \c p.first to the heap with priority \c p.second. |
|
180 /// \param p The pair to insert. |
|
181 void push(const Pair& p) { |
|
182 push(p.first, p.second); |
|
183 } |
|
184 |
|
185 /// \brief Insert an item into the heap with the given priority. |
|
186 /// |
|
187 /// Adds \c i to the heap with priority \c p. |
|
188 /// \param i The item to insert. |
|
189 /// \param p The priority of the item. |
|
190 void push(const Item &i, const Prio &p) { |
|
191 int idx = _data.size(); |
|
192 _iim[i] = idx; |
|
193 _data.push_back(BucketItem(i, p)); |
|
194 lace(idx); |
|
195 if (Direction::less(p, _minimum)) { |
|
196 _minimum = p; |
|
197 } |
|
198 } |
|
199 |
|
200 /// \brief Returns the item with minimum priority. |
|
201 /// |
|
202 /// This method returns the item with minimum priority. |
|
203 /// \pre The heap must be nonempty. |
|
204 Item top() const { |
|
205 while (_first[_minimum] == -1) { |
|
206 Direction::increase(_minimum); |
|
207 } |
|
208 return _data[_first[_minimum]].item; |
|
209 } |
|
210 |
|
211 /// \brief Returns the minimum priority. |
|
212 /// |
|
213 /// It returns the minimum priority. |
|
214 /// \pre The heap must be nonempty. |
|
215 Prio prio() const { |
|
216 while (_first[_minimum] == -1) { |
|
217 Direction::increase(_minimum); |
|
218 } |
|
219 return _minimum; |
|
220 } |
|
221 |
|
222 /// \brief Deletes the item with minimum priority. |
|
223 /// |
|
224 /// This method deletes the item with minimum priority from the heap. |
|
225 /// \pre The heap must be non-empty. |
|
226 void pop() { |
|
227 while (_first[_minimum] == -1) { |
|
228 Direction::increase(_minimum); |
|
229 } |
|
230 int idx = _first[_minimum]; |
|
231 _iim[_data[idx].item] = -2; |
|
232 unlace(idx); |
|
233 relocate_last(idx); |
|
234 } |
|
235 |
|
236 /// \brief Deletes \c i from the heap. |
|
237 /// |
|
238 /// This method deletes item \c i from the heap, if \c i was |
|
239 /// already stored in the heap. |
|
240 /// \param i The item to erase. |
|
241 void erase(const Item &i) { |
|
242 int idx = _iim[i]; |
|
243 _iim[_data[idx].item] = -2; |
|
244 unlace(idx); |
|
245 relocate_last(idx); |
|
246 } |
|
247 |
|
248 |
|
249 /// \brief Returns the priority of \c i. |
|
250 /// |
|
251 /// This function returns the priority of item \c i. |
|
252 /// \pre \c i must be in the heap. |
|
253 /// \param i The item. |
|
254 Prio operator[](const Item &i) const { |
|
255 int idx = _iim[i]; |
|
256 return _data[idx].value; |
|
257 } |
|
258 |
|
259 /// \brief \c i gets to the heap with priority \c p independently |
|
260 /// if \c i was already there. |
|
261 /// |
|
262 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
|
263 /// in the heap and sets the priority of \c i to \c p otherwise. |
|
264 /// \param i The item. |
|
265 /// \param p The priority. |
|
266 void set(const Item &i, const Prio &p) { |
|
267 int idx = _iim[i]; |
|
268 if (idx < 0) { |
|
269 push(i, p); |
|
270 } else if (Direction::less(p, _data[idx].value)) { |
|
271 decrease(i, p); |
|
272 } else { |
|
273 increase(i, p); |
|
274 } |
|
275 } |
|
276 |
|
277 /// \brief Decreases the priority of \c i to \c p. |
|
278 /// |
|
279 /// This method decreases the priority of item \c i to \c p. |
|
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. |
|
283 /// \param p The priority. |
|
284 void decrease(const Item &i, const Prio &p) { |
|
285 int idx = _iim[i]; |
|
286 unlace(idx); |
|
287 _data[idx].value = p; |
|
288 if (Direction::less(p, _minimum)) { |
|
289 _minimum = p; |
|
290 } |
|
291 lace(idx); |
|
292 } |
|
293 |
|
294 /// \brief Increases the priority of \c i to \c p. |
|
295 /// |
|
296 /// This method sets the priority of item \c i to \c p. |
|
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. |
|
300 /// \param p The priority. |
|
301 void increase(const Item &i, const Prio &p) { |
|
302 int idx = _iim[i]; |
|
303 unlace(idx); |
|
304 _data[idx].value = p; |
|
305 lace(idx); |
|
306 } |
|
307 |
|
308 /// \brief Returns if \c item is in, has already been in, or has |
|
309 /// never been in the heap. |
|
310 /// |
|
311 /// This method returns PRE_HEAP if \c item has never been in the |
|
312 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
313 /// otherwise. In the latter case it is possible that \c item will |
|
314 /// get back to the heap again. |
|
315 /// \param i The item. |
|
316 State state(const Item &i) const { |
|
317 int idx = _iim[i]; |
|
318 if (idx >= 0) idx = 0; |
|
319 return State(idx); |
|
320 } |
|
321 |
|
322 /// \brief Sets the state of the \c item in the heap. |
|
323 /// |
|
324 /// Sets the state of the \c item in the heap. It can be used to |
|
325 /// manually clear the heap when it is important to achive the |
|
326 /// better time complexity. |
|
327 /// \param i The item. |
|
328 /// \param st The state. It should not be \c IN_HEAP. |
|
329 void state(const Item& i, State st) { |
|
330 switch (st) { |
|
331 case POST_HEAP: |
|
332 case PRE_HEAP: |
|
333 if (state(i) == IN_HEAP) { |
|
334 erase(i); |
|
335 } |
|
336 _iim[i] = st; |
|
337 break; |
|
338 case IN_HEAP: |
|
339 break; |
|
340 } |
|
341 } |
|
342 |
|
343 private: |
|
344 |
|
345 struct BucketItem { |
|
346 BucketItem(const Item& _item, int _value) |
|
347 : item(_item), value(_value) {} |
|
348 |
|
349 Item item; |
|
350 int value; |
|
351 |
|
352 int prev, next; |
|
353 }; |
|
354 |
|
355 ItemIntMap& _iim; |
|
356 std::vector<int> _first; |
|
357 std::vector<BucketItem> _data; |
|
358 mutable int _minimum; |
|
359 |
|
360 }; // class BucketHeap |
|
361 |
|
362 /// \ingroup auxdat |
|
363 /// |
|
364 /// \brief A Simplified Bucket Heap implementation. |
|
365 /// |
|
366 /// This class implements a simplified \e bucket \e heap data |
|
367 /// structure. It does not provide some functionality but it faster |
|
368 /// and simplier data structure than the BucketHeap. The main |
|
369 /// difference is that the BucketHeap stores for every key a double |
|
370 /// linked list while this class stores just simple lists. In the |
|
371 /// other way it does not support erasing each elements just the |
|
372 /// minimal and it does not supports key increasing, decreasing. |
|
373 /// |
|
374 /// \param IM A read and write Item int map, used internally |
|
375 /// to handle the cross references. |
|
376 /// \param MIN If the given parameter is false then instead of the |
|
377 /// minimum value the maximum can be retrivied with the top() and |
|
378 /// prio() member functions. |
|
379 /// |
|
380 /// \sa BucketHeap |
|
381 template <typename IM, bool MIN = true > |
|
382 class SimpleBucketHeap { |
|
383 |
|
384 public: |
|
385 typedef typename IM::Key Item; |
|
386 typedef int Prio; |
|
387 typedef std::pair<Item, Prio> Pair; |
|
388 typedef IM ItemIntMap; |
|
389 |
|
390 private: |
|
391 |
|
392 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; |
|
393 |
|
394 public: |
|
395 |
|
396 /// \brief Type to represent the items states. |
|
397 /// |
|
398 /// Each Item element have a state associated to it. It may be "in heap", |
|
399 /// "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. |
|
401 /// |
|
402 /// 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. |
|
404 enum State { |
|
405 IN_HEAP = 0, ///< = 0. |
|
406 PRE_HEAP = -1, ///< = -1. |
|
407 POST_HEAP = -2 ///< = -2. |
|
408 }; |
|
409 |
|
410 public: |
|
411 |
|
412 /// \brief The constructor. |
|
413 /// |
|
414 /// The constructor. |
|
415 /// \param map should be given to the constructor, since it is used |
|
416 /// internally to handle the cross references. The value of the map |
|
417 /// should be PRE_HEAP (-1) for each element. |
|
418 explicit SimpleBucketHeap(ItemIntMap &map) |
|
419 : _iim(map), _free(-1), _num(0), _minimum(0) {} |
|
420 |
|
421 /// \brief Returns the number of items stored in the heap. |
|
422 /// |
|
423 /// The number of items stored in the heap. |
|
424 int size() const { return _num; } |
|
425 |
|
426 /// \brief Checks if the heap stores no items. |
|
427 /// |
|
428 /// Returns \c true if and only if the heap stores no items. |
|
429 bool empty() const { return _num == 0; } |
|
430 |
|
431 /// \brief Make empty this heap. |
|
432 /// |
|
433 /// Make empty this heap. It does not change the cross reference |
|
434 /// map. If you want to reuse a heap what is not surely empty you |
|
435 /// should first clear the heap and after that you should set the |
|
436 /// cross reference map for each item to \c PRE_HEAP. |
|
437 void clear() { |
|
438 _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; |
|
439 } |
|
440 |
|
441 /// \brief Insert a pair of item and priority into the heap. |
|
442 /// |
|
443 /// Adds \c p.first to the heap with priority \c p.second. |
|
444 /// \param p The pair to insert. |
|
445 void push(const Pair& p) { |
|
446 push(p.first, p.second); |
|
447 } |
|
448 |
|
449 /// \brief Insert an item into the heap with the given priority. |
|
450 /// |
|
451 /// Adds \c i to the heap with priority \c p. |
|
452 /// \param i The item to insert. |
|
453 /// \param p The priority of the item. |
|
454 void push(const Item &i, const Prio &p) { |
|
455 int idx; |
|
456 if (_free == -1) { |
|
457 idx = _data.size(); |
|
458 _data.push_back(BucketItem(i)); |
|
459 } else { |
|
460 idx = _free; |
|
461 _free = _data[idx].next; |
|
462 _data[idx].item = i; |
|
463 } |
|
464 _iim[i] = idx; |
|
465 if (p >= int(_first.size())) _first.resize(p + 1, -1); |
|
466 _data[idx].next = _first[p]; |
|
467 _first[p] = idx; |
|
468 if (Direction::less(p, _minimum)) { |
|
469 _minimum = p; |
|
470 } |
|
471 ++_num; |
|
472 } |
|
473 |
|
474 /// \brief Returns the item with minimum priority. |
|
475 /// |
|
476 /// This method returns the item with minimum priority. |
|
477 /// \pre The heap must be nonempty. |
|
478 Item top() const { |
|
479 while (_first[_minimum] == -1) { |
|
480 Direction::increase(_minimum); |
|
481 } |
|
482 return _data[_first[_minimum]].item; |
|
483 } |
|
484 |
|
485 /// \brief Returns the minimum priority. |
|
486 /// |
|
487 /// It returns the minimum priority. |
|
488 /// \pre The heap must be nonempty. |
|
489 Prio prio() const { |
|
490 while (_first[_minimum] == -1) { |
|
491 Direction::increase(_minimum); |
|
492 } |
|
493 return _minimum; |
|
494 } |
|
495 |
|
496 /// \brief Deletes the item with minimum priority. |
|
497 /// |
|
498 /// This method deletes the item with minimum priority from the heap. |
|
499 /// \pre The heap must be non-empty. |
|
500 void pop() { |
|
501 while (_first[_minimum] == -1) { |
|
502 Direction::increase(_minimum); |
|
503 } |
|
504 int idx = _first[_minimum]; |
|
505 _iim[_data[idx].item] = -2; |
|
506 _first[_minimum] = _data[idx].next; |
|
507 _data[idx].next = _free; |
|
508 _free = idx; |
|
509 --_num; |
|
510 } |
|
511 |
|
512 /// \brief Returns the priority of \c i. |
|
513 /// |
|
514 /// This function returns the priority of item \c i. |
|
515 /// \warning This operator is not a constant time function |
|
516 /// because it scans the whole data structure to find the proper |
|
517 /// value. |
|
518 /// \pre \c i must be in the heap. |
|
519 /// \param i The item. |
|
520 Prio operator[](const Item &i) const { |
|
521 for (int k = 0; k < _first.size(); ++k) { |
|
522 int idx = _first[k]; |
|
523 while (idx != -1) { |
|
524 if (_data[idx].item == i) { |
|
525 return k; |
|
526 } |
|
527 idx = _data[idx].next; |
|
528 } |
|
529 } |
|
530 return -1; |
|
531 } |
|
532 |
|
533 /// \brief Returns if \c item is in, has already been in, or has |
|
534 /// never been in the heap. |
|
535 /// |
|
536 /// This method returns PRE_HEAP if \c item has never been in the |
|
537 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
538 /// otherwise. In the latter case it is possible that \c item will |
|
539 /// get back to the heap again. |
|
540 /// \param i The item. |
|
541 State state(const Item &i) const { |
|
542 int idx = _iim[i]; |
|
543 if (idx >= 0) idx = 0; |
|
544 return State(idx); |
|
545 } |
|
546 |
|
547 private: |
|
548 |
|
549 struct BucketItem { |
|
550 BucketItem(const Item& _item) |
|
551 : item(_item) {} |
|
552 |
|
553 Item item; |
|
554 int next; |
|
555 }; |
|
556 |
|
557 ItemIntMap& _iim; |
|
558 std::vector<int> _first; |
|
559 std::vector<BucketItem> _data; |
|
560 int _free, _num; |
|
561 mutable int _minimum; |
|
562 |
|
563 }; // class SimpleBucketHeap |
|
564 |
|
565 } |
|
566 |
|
567 #endif |
|