|
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 /// \ingroup auxdat |
|
33 /// |
|
34 /// \brief A Bucket Heap implementation. |
|
35 /// |
|
36 /// This class implements the \e bucket \e heap data structure. A \e heap |
|
37 /// is a data structure for storing items with specified values called \e |
|
38 /// priorities in such a way that finding the item with minimum priority is |
|
39 /// efficient. The bucket heap is very simple implementation, it can store |
|
40 /// only integer priorities and it stores for each priority in the |
|
41 /// \f$ [0..C) \f$ range a list of items. So it should be used only when |
|
42 /// the priorities are small. It is not intended to use as dijkstra heap. |
|
43 /// |
|
44 /// \param _ItemIntMap A read and writable Item int map, used internally |
|
45 /// to handle the cross references. |
|
46 /// \param minimize If the given parameter is true then the heap gives back |
|
47 /// the lowest priority. |
|
48 template <typename _ItemIntMap, bool minimize = true > |
|
49 class BucketHeap { |
|
50 |
|
51 public: |
|
52 /// \e |
|
53 typedef typename _ItemIntMap::Key Item; |
|
54 /// \e |
|
55 typedef int Prio; |
|
56 /// \e |
|
57 typedef std::pair<Item, Prio> Pair; |
|
58 /// \e |
|
59 typedef _ItemIntMap ItemIntMap; |
|
60 |
|
61 /// \brief Type to represent the items states. |
|
62 /// |
|
63 /// Each Item element have a state associated to it. It may be "in heap", |
|
64 /// "pre heap" or "post heap". The latter two are indifferent from the |
|
65 /// heap's point of view, but may be useful to the user. |
|
66 /// |
|
67 /// The ItemIntMap \e should be initialized in such way that it maps |
|
68 /// PRE_HEAP (-1) to any element to be put in the heap... |
|
69 enum State { |
|
70 IN_HEAP = 0, |
|
71 PRE_HEAP = -1, |
|
72 POST_HEAP = -2 |
|
73 }; |
|
74 |
|
75 public: |
|
76 /// \brief The constructor. |
|
77 /// |
|
78 /// The constructor. |
|
79 /// \param _index should be given to the constructor, since it is used |
|
80 /// internally to handle the cross references. The value of the map |
|
81 /// should be PRE_HEAP (-1) for each element. |
|
82 explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {} |
|
83 |
|
84 /// The number of items stored in the heap. |
|
85 /// |
|
86 /// \brief Returns the number of items stored in the heap. |
|
87 int size() const { return data.size(); } |
|
88 |
|
89 /// \brief Checks if the heap stores no items. |
|
90 /// |
|
91 /// Returns \c true if and only if the heap stores no items. |
|
92 bool empty() const { return data.empty(); } |
|
93 |
|
94 /// \brief Make empty this heap. |
|
95 /// |
|
96 /// Make empty this heap. It does not change the cross reference |
|
97 /// map. If you want to reuse a heap what is not surely empty you |
|
98 /// should first clear the heap and after that you should set the |
|
99 /// cross reference map for each item to \c PRE_HEAP. |
|
100 void clear() { |
|
101 data.clear(); first.clear(); minimal = 0; |
|
102 } |
|
103 |
|
104 private: |
|
105 |
|
106 void relocate_last(int idx) { |
|
107 if (idx + 1 < int(data.size())) { |
|
108 data[idx] = data.back(); |
|
109 if (data[idx].prev != -1) { |
|
110 data[data[idx].prev].next = idx; |
|
111 } else { |
|
112 first[data[idx].value] = idx; |
|
113 } |
|
114 if (data[idx].next != -1) { |
|
115 data[data[idx].next].prev = idx; |
|
116 } |
|
117 index[data[idx].item] = idx; |
|
118 } |
|
119 data.pop_back(); |
|
120 } |
|
121 |
|
122 void unlace(int idx) { |
|
123 if (data[idx].prev != -1) { |
|
124 data[data[idx].prev].next = data[idx].next; |
|
125 } else { |
|
126 first[data[idx].value] = data[idx].next; |
|
127 } |
|
128 if (data[idx].next != -1) { |
|
129 data[data[idx].next].prev = data[idx].prev; |
|
130 } |
|
131 } |
|
132 |
|
133 void lace(int idx) { |
|
134 if (int(first.size()) <= data[idx].value) { |
|
135 first.resize(data[idx].value + 1, -1); |
|
136 } |
|
137 data[idx].next = first[data[idx].value]; |
|
138 if (data[idx].next != -1) { |
|
139 data[data[idx].next].prev = idx; |
|
140 } |
|
141 first[data[idx].value] = idx; |
|
142 data[idx].prev = -1; |
|
143 } |
|
144 |
|
145 public: |
|
146 /// \brief Insert a pair of item and priority into the heap. |
|
147 /// |
|
148 /// Adds \c p.first to the heap with priority \c p.second. |
|
149 /// \param p The pair to insert. |
|
150 void push(const Pair& p) { |
|
151 push(p.first, p.second); |
|
152 } |
|
153 |
|
154 /// \brief Insert an item into the heap with the given priority. |
|
155 /// |
|
156 /// Adds \c i to the heap with priority \c p. |
|
157 /// \param i The item to insert. |
|
158 /// \param p The priority of the item. |
|
159 void push(const Item &i, const Prio &p) { |
|
160 int idx = data.size(); |
|
161 index[i] = idx; |
|
162 data.push_back(BucketItem(i, p)); |
|
163 lace(idx); |
|
164 if (p < minimal) { |
|
165 minimal = p; |
|
166 } |
|
167 } |
|
168 |
|
169 /// \brief Returns the item with minimum priority. |
|
170 /// |
|
171 /// This method returns the item with minimum priority. |
|
172 /// \pre The heap must be nonempty. |
|
173 Item top() const { |
|
174 while (first[minimal] == -1) { |
|
175 ++minimal; |
|
176 } |
|
177 return data[first[minimal]].item; |
|
178 } |
|
179 |
|
180 /// \brief Returns the minimum priority. |
|
181 /// |
|
182 /// It returns the minimum priority. |
|
183 /// \pre The heap must be nonempty. |
|
184 Prio prio() const { |
|
185 while (first[minimal] == -1) { |
|
186 ++minimal; |
|
187 } |
|
188 return minimal; |
|
189 } |
|
190 |
|
191 /// \brief Deletes the item with minimum priority. |
|
192 /// |
|
193 /// This method deletes the item with minimum priority from the heap. |
|
194 /// \pre The heap must be non-empty. |
|
195 void pop() { |
|
196 while (first[minimal] == -1) { |
|
197 ++minimal; |
|
198 } |
|
199 int idx = first[minimal]; |
|
200 index[data[idx].item] = -2; |
|
201 unlace(idx); |
|
202 relocate_last(idx); |
|
203 } |
|
204 |
|
205 /// \brief Deletes \c i from the heap. |
|
206 /// |
|
207 /// This method deletes item \c i from the heap, if \c i was |
|
208 /// already stored in the heap. |
|
209 /// \param i The item to erase. |
|
210 void erase(const Item &i) { |
|
211 int idx = index[i]; |
|
212 index[data[idx].item] = -2; |
|
213 unlace(idx); |
|
214 relocate_last(idx); |
|
215 } |
|
216 |
|
217 |
|
218 /// \brief Returns the priority of \c i. |
|
219 /// |
|
220 /// This function returns the priority of item \c i. |
|
221 /// \pre \c i must be in the heap. |
|
222 /// \param i The item. |
|
223 Prio operator[](const Item &i) const { |
|
224 int idx = index[i]; |
|
225 return data[idx].value; |
|
226 } |
|
227 |
|
228 /// \brief \c i gets to the heap with priority \c p independently |
|
229 /// if \c i was already there. |
|
230 /// |
|
231 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
|
232 /// in the heap and sets the priority of \c i to \c p otherwise. |
|
233 /// \param i The item. |
|
234 /// \param p The priority. |
|
235 void set(const Item &i, const Prio &p) { |
|
236 int idx = index[i]; |
|
237 if (idx < 0) { |
|
238 push(i,p); |
|
239 } else if (p > data[idx].value) { |
|
240 increase(i, p); |
|
241 } else { |
|
242 decrease(i, p); |
|
243 } |
|
244 } |
|
245 |
|
246 /// \brief Decreases the priority of \c i to \c p. |
|
247 /// |
|
248 /// This method decreases the priority of item \c i to \c p. |
|
249 /// \pre \c i must be stored in the heap with priority at least \c |
|
250 /// p relative to \c Compare. |
|
251 /// \param i The item. |
|
252 /// \param p The priority. |
|
253 void decrease(const Item &i, const Prio &p) { |
|
254 int idx = index[i]; |
|
255 unlace(idx); |
|
256 data[idx].value = p; |
|
257 if (p < minimal) { |
|
258 minimal = p; |
|
259 } |
|
260 lace(idx); |
|
261 } |
|
262 |
|
263 /// \brief Increases the priority of \c i to \c p. |
|
264 /// |
|
265 /// This method sets the priority of item \c i to \c p. |
|
266 /// \pre \c i must be stored in the heap with priority at most \c |
|
267 /// p relative to \c Compare. |
|
268 /// \param i The item. |
|
269 /// \param p The priority. |
|
270 void increase(const Item &i, const Prio &p) { |
|
271 int idx = index[i]; |
|
272 unlace(idx); |
|
273 data[idx].value = p; |
|
274 lace(idx); |
|
275 } |
|
276 |
|
277 /// \brief Returns if \c item is in, has already been in, or has |
|
278 /// never been in the heap. |
|
279 /// |
|
280 /// This method returns PRE_HEAP if \c item has never been in the |
|
281 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
282 /// otherwise. In the latter case it is possible that \c item will |
|
283 /// get back to the heap again. |
|
284 /// \param i The item. |
|
285 State state(const Item &i) const { |
|
286 int idx = index[i]; |
|
287 if (idx >= 0) idx = 0; |
|
288 return State(idx); |
|
289 } |
|
290 |
|
291 /// \brief Sets the state of the \c item in the heap. |
|
292 /// |
|
293 /// Sets the state of the \c item in the heap. It can be used to |
|
294 /// manually clear the heap when it is important to achive the |
|
295 /// better time complexity. |
|
296 /// \param i The item. |
|
297 /// \param st The state. It should not be \c IN_HEAP. |
|
298 void state(const Item& i, State st) { |
|
299 switch (st) { |
|
300 case POST_HEAP: |
|
301 case PRE_HEAP: |
|
302 if (state(i) == IN_HEAP) { |
|
303 erase(i); |
|
304 } |
|
305 index[i] = st; |
|
306 break; |
|
307 case IN_HEAP: |
|
308 break; |
|
309 } |
|
310 } |
|
311 |
|
312 private: |
|
313 |
|
314 struct BucketItem { |
|
315 BucketItem(const Item& _item, int _value) |
|
316 : item(_item), value(_value) {} |
|
317 |
|
318 Item item; |
|
319 int value; |
|
320 |
|
321 int prev, next; |
|
322 }; |
|
323 |
|
324 ItemIntMap& index; |
|
325 std::vector<int> first; |
|
326 std::vector<BucketItem> data; |
|
327 mutable int minimal; |
|
328 |
|
329 }; // class BucketHeap |
|
330 |
|
331 |
|
332 template <typename _ItemIntMap> |
|
333 class BucketHeap<_ItemIntMap, false> { |
|
334 |
|
335 public: |
|
336 typedef typename _ItemIntMap::Key Item; |
|
337 typedef int Prio; |
|
338 typedef std::pair<Item, Prio> Pair; |
|
339 typedef _ItemIntMap ItemIntMap; |
|
340 |
|
341 enum State { |
|
342 IN_HEAP = 0, |
|
343 PRE_HEAP = -1, |
|
344 POST_HEAP = -2 |
|
345 }; |
|
346 |
|
347 public: |
|
348 |
|
349 explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {} |
|
350 |
|
351 int size() const { return data.size(); } |
|
352 bool empty() const { return data.empty(); } |
|
353 |
|
354 void clear() { |
|
355 data.clear(); first.clear(); maximal = -1; |
|
356 } |
|
357 |
|
358 private: |
|
359 |
|
360 void relocate_last(int idx) { |
|
361 if (idx + 1 != int(data.size())) { |
|
362 data[idx] = data.back(); |
|
363 if (data[idx].prev != -1) { |
|
364 data[data[idx].prev].next = idx; |
|
365 } else { |
|
366 first[data[idx].value] = idx; |
|
367 } |
|
368 if (data[idx].next != -1) { |
|
369 data[data[idx].next].prev = idx; |
|
370 } |
|
371 index[data[idx].item] = idx; |
|
372 } |
|
373 data.pop_back(); |
|
374 } |
|
375 |
|
376 void unlace(int idx) { |
|
377 if (data[idx].prev != -1) { |
|
378 data[data[idx].prev].next = data[idx].next; |
|
379 } else { |
|
380 first[data[idx].value] = data[idx].next; |
|
381 } |
|
382 if (data[idx].next != -1) { |
|
383 data[data[idx].next].prev = data[idx].prev; |
|
384 } |
|
385 } |
|
386 |
|
387 void lace(int idx) { |
|
388 if (int(first.size()) <= data[idx].value) { |
|
389 first.resize(data[idx].value + 1, -1); |
|
390 } |
|
391 data[idx].next = first[data[idx].value]; |
|
392 if (data[idx].next != -1) { |
|
393 data[data[idx].next].prev = idx; |
|
394 } |
|
395 first[data[idx].value] = idx; |
|
396 data[idx].prev = -1; |
|
397 } |
|
398 |
|
399 public: |
|
400 |
|
401 void push(const Pair& p) { |
|
402 push(p.first, p.second); |
|
403 } |
|
404 |
|
405 void push(const Item &i, const Prio &p) { |
|
406 int idx = data.size(); |
|
407 index[i] = idx; |
|
408 data.push_back(BucketItem(i, p)); |
|
409 lace(idx); |
|
410 if (data[idx].value > maximal) { |
|
411 maximal = data[idx].value; |
|
412 } |
|
413 } |
|
414 |
|
415 Item top() const { |
|
416 while (first[maximal] == -1) { |
|
417 --maximal; |
|
418 } |
|
419 return data[first[maximal]].item; |
|
420 } |
|
421 |
|
422 Prio prio() const { |
|
423 while (first[maximal] == -1) { |
|
424 --maximal; |
|
425 } |
|
426 return maximal; |
|
427 } |
|
428 |
|
429 void pop() { |
|
430 while (first[maximal] == -1) { |
|
431 --maximal; |
|
432 } |
|
433 int idx = first[maximal]; |
|
434 index[data[idx].item] = -2; |
|
435 unlace(idx); |
|
436 relocate_last(idx); |
|
437 } |
|
438 |
|
439 void erase(const Item &i) { |
|
440 int idx = index[i]; |
|
441 index[data[idx].item] = -2; |
|
442 unlace(idx); |
|
443 relocate_last(idx); |
|
444 } |
|
445 |
|
446 Prio operator[](const Item &i) const { |
|
447 int idx = index[i]; |
|
448 return data[idx].value; |
|
449 } |
|
450 |
|
451 void set(const Item &i, const Prio &p) { |
|
452 int idx = index[i]; |
|
453 if (idx < 0) { |
|
454 push(i,p); |
|
455 } else if (p > data[idx].value) { |
|
456 decrease(i, p); |
|
457 } else { |
|
458 increase(i, p); |
|
459 } |
|
460 } |
|
461 |
|
462 void decrease(const Item &i, const Prio &p) { |
|
463 int idx = index[i]; |
|
464 unlace(idx); |
|
465 data[idx].value = p; |
|
466 if (p > maximal) { |
|
467 maximal = p; |
|
468 } |
|
469 lace(idx); |
|
470 } |
|
471 |
|
472 void increase(const Item &i, const Prio &p) { |
|
473 int idx = index[i]; |
|
474 unlace(idx); |
|
475 data[idx].value = p; |
|
476 lace(idx); |
|
477 } |
|
478 |
|
479 State state(const Item &i) const { |
|
480 int idx = index[i]; |
|
481 if (idx >= 0) idx = 0; |
|
482 return State(idx); |
|
483 } |
|
484 |
|
485 void state(const Item& i, State st) { |
|
486 switch (st) { |
|
487 case POST_HEAP: |
|
488 case PRE_HEAP: |
|
489 if (state(i) == IN_HEAP) { |
|
490 erase(i); |
|
491 } |
|
492 index[i] = st; |
|
493 break; |
|
494 case IN_HEAP: |
|
495 break; |
|
496 } |
|
497 } |
|
498 |
|
499 private: |
|
500 |
|
501 struct BucketItem { |
|
502 BucketItem(const Item& _item, int _value) |
|
503 : item(_item), value(_value) {} |
|
504 |
|
505 Item item; |
|
506 int value; |
|
507 |
|
508 int prev, next; |
|
509 }; |
|
510 |
|
511 ItemIntMap& index; |
|
512 std::vector<int> first; |
|
513 std::vector<BucketItem> data; |
|
514 mutable int maximal; |
|
515 |
|
516 }; // class BucketHeap |
|
517 |
|
518 /// \ingroup auxdat |
|
519 /// |
|
520 /// \brief A Simplified Bucket Heap implementation. |
|
521 /// |
|
522 /// This class implements a simplified \e bucket \e heap data |
|
523 /// structure. It does not provide some functionality but it faster |
|
524 /// and simplier data structure than the BucketHeap. The main |
|
525 /// difference is that the BucketHeap stores for every key a double |
|
526 /// linked list while this class stores just simple lists. In the |
|
527 /// other way it does not supports erasing each elements just the |
|
528 /// minimal and it does not supports key increasing, decreasing. |
|
529 /// |
|
530 /// \param _ItemIntMap A read and writable Item int map, used internally |
|
531 /// to handle the cross references. |
|
532 /// \param minimize If the given parameter is true then the heap gives back |
|
533 /// the lowest priority. |
|
534 /// |
|
535 /// \sa BucketHeap |
|
536 template <typename _ItemIntMap, bool minimize = true > |
|
537 class SimpleBucketHeap { |
|
538 |
|
539 public: |
|
540 typedef typename _ItemIntMap::Key Item; |
|
541 typedef int Prio; |
|
542 typedef std::pair<Item, Prio> Pair; |
|
543 typedef _ItemIntMap ItemIntMap; |
|
544 |
|
545 /// \brief Type to represent the items states. |
|
546 /// |
|
547 /// Each Item element have a state associated to it. It may be "in heap", |
|
548 /// "pre heap" or "post heap". The latter two are indifferent from the |
|
549 /// heap's point of view, but may be useful to the user. |
|
550 /// |
|
551 /// The ItemIntMap \e should be initialized in such way that it maps |
|
552 /// PRE_HEAP (-1) to any element to be put in the heap... |
|
553 enum State { |
|
554 IN_HEAP = 0, |
|
555 PRE_HEAP = -1, |
|
556 POST_HEAP = -2 |
|
557 }; |
|
558 |
|
559 public: |
|
560 |
|
561 /// \brief The constructor. |
|
562 /// |
|
563 /// The constructor. |
|
564 /// \param _index should be given to the constructor, since it is used |
|
565 /// internally to handle the cross references. The value of the map |
|
566 /// should be PRE_HEAP (-1) for each element. |
|
567 explicit SimpleBucketHeap(ItemIntMap &_index) |
|
568 : index(_index), free(-1), num(0), minimal(0) {} |
|
569 |
|
570 /// \brief Returns the number of items stored in the heap. |
|
571 /// |
|
572 /// The number of items stored in the heap. |
|
573 int size() const { return num; } |
|
574 |
|
575 /// \brief Checks if the heap stores no items. |
|
576 /// |
|
577 /// Returns \c true if and only if the heap stores no items. |
|
578 bool empty() const { return num == 0; } |
|
579 |
|
580 /// \brief Make empty this heap. |
|
581 /// |
|
582 /// Make empty this heap. It does not change the cross reference |
|
583 /// map. If you want to reuse a heap what is not surely empty you |
|
584 /// should first clear the heap and after that you should set the |
|
585 /// cross reference map for each item to \c PRE_HEAP. |
|
586 void clear() { |
|
587 data.clear(); first.clear(); free = -1; num = 0; minimal = 0; |
|
588 } |
|
589 |
|
590 /// \brief Insert a pair of item and priority into the heap. |
|
591 /// |
|
592 /// Adds \c p.first to the heap with priority \c p.second. |
|
593 /// \param p The pair to insert. |
|
594 void push(const Pair& p) { |
|
595 push(p.first, p.second); |
|
596 } |
|
597 |
|
598 /// \brief Insert an item into the heap with the given priority. |
|
599 /// |
|
600 /// Adds \c i to the heap with priority \c p. |
|
601 /// \param i The item to insert. |
|
602 /// \param p The priority of the item. |
|
603 void push(const Item &i, const Prio &p) { |
|
604 int idx; |
|
605 if (free == -1) { |
|
606 idx = data.size(); |
|
607 data.push_back(BucketItem(i)); |
|
608 } else { |
|
609 idx = free; |
|
610 free = data[idx].next; |
|
611 data[idx].item = i; |
|
612 } |
|
613 index[i] = idx; |
|
614 if (p >= int(first.size())) first.resize(p + 1, -1); |
|
615 data[idx].next = first[p]; |
|
616 first[p] = idx; |
|
617 if (p < minimal) { |
|
618 minimal = p; |
|
619 } |
|
620 ++num; |
|
621 } |
|
622 |
|
623 /// \brief Returns the item with minimum priority. |
|
624 /// |
|
625 /// This method returns the item with minimum priority. |
|
626 /// \pre The heap must be nonempty. |
|
627 Item top() const { |
|
628 while (first[minimal] == -1) { |
|
629 ++minimal; |
|
630 } |
|
631 return data[first[minimal]].item; |
|
632 } |
|
633 |
|
634 /// \brief Returns the minimum priority. |
|
635 /// |
|
636 /// It returns the minimum priority. |
|
637 /// \pre The heap must be nonempty. |
|
638 Prio prio() const { |
|
639 while (first[minimal] == -1) { |
|
640 ++minimal; |
|
641 } |
|
642 return minimal; |
|
643 } |
|
644 |
|
645 /// \brief Deletes the item with minimum priority. |
|
646 /// |
|
647 /// This method deletes the item with minimum priority from the heap. |
|
648 /// \pre The heap must be non-empty. |
|
649 void pop() { |
|
650 while (first[minimal] == -1) { |
|
651 ++minimal; |
|
652 } |
|
653 int idx = first[minimal]; |
|
654 index[data[idx].item] = -2; |
|
655 first[minimal] = data[idx].next; |
|
656 data[idx].next = free; |
|
657 free = idx; |
|
658 --num; |
|
659 } |
|
660 |
|
661 /// \brief Returns the priority of \c i. |
|
662 /// |
|
663 /// This function returns the priority of item \c i. |
|
664 /// \warning This operator is not a constant time function |
|
665 /// because it scans the whole data structure to find the proper |
|
666 /// value. |
|
667 /// \pre \c i must be in the heap. |
|
668 /// \param i The item. |
|
669 Prio operator[](const Item &i) const { |
|
670 for (int k = 0; k < first.size(); ++k) { |
|
671 int idx = first[k]; |
|
672 while (idx != -1) { |
|
673 if (data[idx].item == i) { |
|
674 return k; |
|
675 } |
|
676 idx = data[idx].next; |
|
677 } |
|
678 } |
|
679 return -1; |
|
680 } |
|
681 |
|
682 /// \brief Returns if \c item is in, has already been in, or has |
|
683 /// never been in the heap. |
|
684 /// |
|
685 /// This method returns PRE_HEAP if \c item has never been in the |
|
686 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
687 /// otherwise. In the latter case it is possible that \c item will |
|
688 /// get back to the heap again. |
|
689 /// \param i The item. |
|
690 State state(const Item &i) const { |
|
691 int idx = index[i]; |
|
692 if (idx >= 0) idx = 0; |
|
693 return State(idx); |
|
694 } |
|
695 |
|
696 private: |
|
697 |
|
698 struct BucketItem { |
|
699 BucketItem(const Item& _item) |
|
700 : item(_item) {} |
|
701 |
|
702 Item item; |
|
703 int next; |
|
704 }; |
|
705 |
|
706 ItemIntMap& index; |
|
707 std::vector<int> first; |
|
708 std::vector<BucketItem> data; |
|
709 int free, num; |
|
710 mutable int minimal; |
|
711 |
|
712 }; // class SimpleBucketHeap |
|
713 |
|
714 template <typename _ItemIntMap> |
|
715 class SimpleBucketHeap<_ItemIntMap, false> { |
|
716 |
|
717 public: |
|
718 typedef typename _ItemIntMap::Key Item; |
|
719 typedef int Prio; |
|
720 typedef std::pair<Item, Prio> Pair; |
|
721 typedef _ItemIntMap ItemIntMap; |
|
722 |
|
723 enum State { |
|
724 IN_HEAP = 0, |
|
725 PRE_HEAP = -1, |
|
726 POST_HEAP = -2 |
|
727 }; |
|
728 |
|
729 public: |
|
730 |
|
731 explicit SimpleBucketHeap(ItemIntMap &_index) |
|
732 : index(_index), free(-1), num(0), maximal(0) {} |
|
733 |
|
734 int size() const { return num; } |
|
735 |
|
736 bool empty() const { return num == 0; } |
|
737 |
|
738 void clear() { |
|
739 data.clear(); first.clear(); free = -1; num = 0; maximal = 0; |
|
740 } |
|
741 |
|
742 void push(const Pair& p) { |
|
743 push(p.first, p.second); |
|
744 } |
|
745 |
|
746 void push(const Item &i, const Prio &p) { |
|
747 int idx; |
|
748 if (free == -1) { |
|
749 idx = data.size(); |
|
750 data.push_back(BucketItem(i)); |
|
751 } else { |
|
752 idx = free; |
|
753 free = data[idx].next; |
|
754 data[idx].item = i; |
|
755 } |
|
756 index[i] = idx; |
|
757 if (p >= int(first.size())) first.resize(p + 1, -1); |
|
758 data[idx].next = first[p]; |
|
759 first[p] = idx; |
|
760 if (p > maximal) { |
|
761 maximal = p; |
|
762 } |
|
763 ++num; |
|
764 } |
|
765 |
|
766 Item top() const { |
|
767 while (first[maximal] == -1) { |
|
768 --maximal; |
|
769 } |
|
770 return data[first[maximal]].item; |
|
771 } |
|
772 |
|
773 Prio prio() const { |
|
774 while (first[maximal] == -1) { |
|
775 --maximal; |
|
776 } |
|
777 return maximal; |
|
778 } |
|
779 |
|
780 void pop() { |
|
781 while (first[maximal] == -1) { |
|
782 --maximal; |
|
783 } |
|
784 int idx = first[maximal]; |
|
785 index[data[idx].item] = -2; |
|
786 first[maximal] = data[idx].next; |
|
787 data[idx].next = free; |
|
788 free = idx; |
|
789 --num; |
|
790 } |
|
791 |
|
792 Prio operator[](const Item &i) const { |
|
793 for (int k = 0; k < first.size(); ++k) { |
|
794 int idx = first[k]; |
|
795 while (idx != -1) { |
|
796 if (data[idx].item == i) { |
|
797 return k; |
|
798 } |
|
799 idx = data[idx].next; |
|
800 } |
|
801 } |
|
802 return -1; |
|
803 } |
|
804 |
|
805 State state(const Item &i) const { |
|
806 int idx = index[i]; |
|
807 if (idx >= 0) idx = 0; |
|
808 return State(idx); |
|
809 } |
|
810 |
|
811 private: |
|
812 |
|
813 struct BucketItem { |
|
814 BucketItem(const Item& _item) : item(_item) {} |
|
815 |
|
816 Item item; |
|
817 |
|
818 int next; |
|
819 }; |
|
820 |
|
821 ItemIntMap& index; |
|
822 std::vector<int> first; |
|
823 std::vector<BucketItem> data; |
|
824 int free, num; |
|
825 mutable int maximal; |
|
826 |
|
827 }; |
|
828 |
|
829 } |
|
830 |
|
831 #endif |