... | ... |
@@ -26,12 +26,36 @@ |
26 | 26 |
#include <vector> |
27 | 27 |
#include <utility> |
28 | 28 |
#include <functional> |
29 | 29 |
|
30 | 30 |
namespace lemon { |
31 | 31 |
|
32 |
namespace _bucket_heap_bits { |
|
33 |
|
|
34 |
template <bool minimize> |
|
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 |
|
|
32 | 56 |
/// \ingroup auxdat |
33 | 57 |
/// |
34 | 58 |
/// \brief A Bucket Heap implementation. |
35 | 59 |
/// |
36 | 60 |
/// This class implements the \e bucket \e heap data structure. A \e heap |
37 | 61 |
/// is a data structure for storing items with specified values called \e |
... | ... |
@@ -42,25 +66,31 @@ |
42 | 66 |
/// the priorities are small. It is not intended to use as dijkstra heap. |
43 | 67 |
/// |
44 | 68 |
/// \param _ItemIntMap A read and writable Item int map, used internally |
45 | 69 |
/// to handle the cross references. |
46 | 70 |
/// \param minimize If the given parameter is true then the heap gives back |
47 | 71 |
/// the lowest priority. |
48 |
template <typename _ItemIntMap, bool minimize = true |
|
72 |
template <typename _ItemIntMap, bool minimize = true> |
|
49 | 73 |
class BucketHeap { |
50 | 74 |
|
51 | 75 |
public: |
52 | 76 |
/// \e |
53 | 77 |
typedef typename _ItemIntMap::Key Item; |
54 | 78 |
/// \e |
55 | 79 |
typedef int Prio; |
56 | 80 |
/// \e |
57 | 81 |
typedef std::pair<Item, Prio> Pair; |
58 | 82 |
/// \e |
59 | 83 |
typedef _ItemIntMap ItemIntMap; |
60 | 84 |
|
85 |
private: |
|
86 |
|
|
87 |
typedef _bucket_heap_bits::DirectionTraits<minimize> Direction; |
|
88 |
|
|
89 |
public: |
|
90 |
|
|
61 | 91 |
/// \brief Type to represent the items states. |
62 | 92 |
/// |
63 | 93 |
/// Each Item element have a state associated to it. It may be "in heap", |
64 | 94 |
/// "pre heap" or "post heap". The latter two are indifferent from the |
65 | 95 |
/// heap's point of view, but may be useful to the user. |
66 | 96 |
/// |
... | ... |
@@ -158,46 +188,46 @@ |
158 | 188 |
/// \param p The priority of the item. |
159 | 189 |
void push(const Item &i, const Prio &p) { |
160 | 190 |
int idx = data.size(); |
161 | 191 |
index[i] = idx; |
162 | 192 |
data.push_back(BucketItem(i, p)); |
163 | 193 |
lace(idx); |
164 |
if (p |
|
194 |
if (Direction::less(p, minimal)) { |
|
165 | 195 |
minimal = p; |
166 | 196 |
} |
167 | 197 |
} |
168 | 198 |
|
169 | 199 |
/// \brief Returns the item with minimum priority. |
170 | 200 |
/// |
171 | 201 |
/// This method returns the item with minimum priority. |
172 | 202 |
/// \pre The heap must be nonempty. |
173 | 203 |
Item top() const { |
174 | 204 |
while (first[minimal] == -1) { |
175 |
|
|
205 |
Direction::increase(minimal); |
|
176 | 206 |
} |
177 | 207 |
return data[first[minimal]].item; |
178 | 208 |
} |
179 | 209 |
|
180 | 210 |
/// \brief Returns the minimum priority. |
181 | 211 |
/// |
182 | 212 |
/// It returns the minimum priority. |
183 | 213 |
/// \pre The heap must be nonempty. |
184 | 214 |
Prio prio() const { |
185 | 215 |
while (first[minimal] == -1) { |
186 |
|
|
216 |
Direction::increase(minimal); |
|
187 | 217 |
} |
188 | 218 |
return minimal; |
189 | 219 |
} |
190 | 220 |
|
191 | 221 |
/// \brief Deletes the item with minimum priority. |
192 | 222 |
/// |
193 | 223 |
/// This method deletes the item with minimum priority from the heap. |
194 | 224 |
/// \pre The heap must be non-empty. |
195 | 225 |
void pop() { |
196 | 226 |
while (first[minimal] == -1) { |
197 |
|
|
227 |
Direction::increase(minimal); |
|
198 | 228 |
} |
199 | 229 |
int idx = first[minimal]; |
200 | 230 |
index[data[idx].item] = -2; |
201 | 231 |
unlace(idx); |
202 | 232 |
relocate_last(idx); |
203 | 233 |
} |
... | ... |
@@ -232,17 +262,17 @@ |
232 | 262 |
/// in the heap and sets the priority of \c i to \c p otherwise. |
233 | 263 |
/// \param i The item. |
234 | 264 |
/// \param p The priority. |
235 | 265 |
void set(const Item &i, const Prio &p) { |
236 | 266 |
int idx = index[i]; |
237 | 267 |
if (idx < 0) { |
238 |
push(i,p); |
|
239 |
} else if (p > data[idx].value) { |
|
268 |
push(i, p); |
|
269 |
} else if (Direction::less(p, data[idx].value)) { |
|
270 |
decrease(i, p); |
|
271 |
} else { |
|
240 | 272 |
increase(i, p); |
241 |
} else { |
|
242 |
decrease(i, p); |
|
243 | 273 |
} |
244 | 274 |
} |
245 | 275 |
|
246 | 276 |
/// \brief Decreases the priority of \c i to \c p. |
247 | 277 |
/// |
248 | 278 |
/// This method decreases the priority of item \c i to \c p. |
... | ... |
@@ -251,13 +281,13 @@ |
251 | 281 |
/// \param i The item. |
252 | 282 |
/// \param p The priority. |
253 | 283 |
void decrease(const Item &i, const Prio &p) { |
254 | 284 |
int idx = index[i]; |
255 | 285 |
unlace(idx); |
256 | 286 |
data[idx].value = p; |
257 |
if (p |
|
287 |
if (Direction::less(p, minimal)) { |
|
258 | 288 |
minimal = p; |
259 | 289 |
} |
260 | 290 |
lace(idx); |
261 | 291 |
} |
262 | 292 |
|
263 | 293 |
/// \brief Increases the priority of \c i to \c p. |
... | ... |
@@ -325,209 +355,22 @@ |
325 | 355 |
std::vector<int> first; |
326 | 356 |
std::vector<BucketItem> data; |
327 | 357 |
mutable int minimal; |
328 | 358 |
|
329 | 359 |
}; // class BucketHeap |
330 | 360 |
|
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 | 361 |
/// \ingroup auxdat |
519 | 362 |
/// |
520 | 363 |
/// \brief A Simplified Bucket Heap implementation. |
521 | 364 |
/// |
522 | 365 |
/// This class implements a simplified \e bucket \e heap data |
523 | 366 |
/// structure. It does not provide some functionality but it faster |
524 | 367 |
/// and simplier data structure than the BucketHeap. The main |
525 | 368 |
/// difference is that the BucketHeap stores for every key a double |
526 | 369 |
/// linked list while this class stores just simple lists. In the |
527 |
/// other way it does not |
|
370 |
/// other way it does not support erasing each elements just the |
|
528 | 371 |
/// minimal and it does not supports key increasing, decreasing. |
529 | 372 |
/// |
530 | 373 |
/// \param _ItemIntMap A read and writable Item int map, used internally |
531 | 374 |
/// to handle the cross references. |
532 | 375 |
/// \param minimize If the given parameter is true then the heap gives back |
533 | 376 |
/// the lowest priority. |
... | ... |
@@ -539,12 +382,18 @@ |
539 | 382 |
public: |
540 | 383 |
typedef typename _ItemIntMap::Key Item; |
541 | 384 |
typedef int Prio; |
542 | 385 |
typedef std::pair<Item, Prio> Pair; |
543 | 386 |
typedef _ItemIntMap ItemIntMap; |
544 | 387 |
|
388 |
private: |
|
389 |
|
|
390 |
typedef _bucket_heap_bits::DirectionTraits<minimize> Direction; |
|
391 |
|
|
392 |
public: |
|
393 |
|
|
545 | 394 |
/// \brief Type to represent the items states. |
546 | 395 |
/// |
547 | 396 |
/// Each Item element have a state associated to it. It may be "in heap", |
548 | 397 |
/// "pre heap" or "post heap". The latter two are indifferent from the |
549 | 398 |
/// heap's point of view, but may be useful to the user. |
550 | 399 |
/// |
... | ... |
@@ -611,47 +460,47 @@ |
611 | 460 |
data[idx].item = i; |
612 | 461 |
} |
613 | 462 |
index[i] = idx; |
614 | 463 |
if (p >= int(first.size())) first.resize(p + 1, -1); |
615 | 464 |
data[idx].next = first[p]; |
616 | 465 |
first[p] = idx; |
617 |
if (p |
|
466 |
if (Direction::less(p, minimal)) { |
|
618 | 467 |
minimal = p; |
619 | 468 |
} |
620 | 469 |
++num; |
621 | 470 |
} |
622 | 471 |
|
623 | 472 |
/// \brief Returns the item with minimum priority. |
624 | 473 |
/// |
625 | 474 |
/// This method returns the item with minimum priority. |
626 | 475 |
/// \pre The heap must be nonempty. |
627 | 476 |
Item top() const { |
628 | 477 |
while (first[minimal] == -1) { |
629 |
|
|
478 |
Direction::increase(minimal); |
|
630 | 479 |
} |
631 | 480 |
return data[first[minimal]].item; |
632 | 481 |
} |
633 | 482 |
|
634 | 483 |
/// \brief Returns the minimum priority. |
635 | 484 |
/// |
636 | 485 |
/// It returns the minimum priority. |
637 | 486 |
/// \pre The heap must be nonempty. |
638 | 487 |
Prio prio() const { |
639 | 488 |
while (first[minimal] == -1) { |
640 |
|
|
489 |
Direction::increase(minimal); |
|
641 | 490 |
} |
642 | 491 |
return minimal; |
643 | 492 |
} |
644 | 493 |
|
645 | 494 |
/// \brief Deletes the item with minimum priority. |
646 | 495 |
/// |
647 | 496 |
/// This method deletes the item with minimum priority from the heap. |
648 | 497 |
/// \pre The heap must be non-empty. |
649 | 498 |
void pop() { |
650 | 499 |
while (first[minimal] == -1) { |
651 |
|
|
500 |
Direction::increase(minimal); |
|
652 | 501 |
} |
653 | 502 |
int idx = first[minimal]; |
654 | 503 |
index[data[idx].item] = -2; |
655 | 504 |
first[minimal] = data[idx].next; |
656 | 505 |
data[idx].next = free; |
657 | 506 |
free = idx; |
... | ... |
@@ -708,124 +557,9 @@ |
708 | 557 |
std::vector<BucketItem> data; |
709 | 558 |
int free, num; |
710 | 559 |
mutable int minimal; |
711 | 560 |
|
712 | 561 |
}; // class SimpleBucketHeap |
713 | 562 |
|
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 | 563 |
} |
830 | 564 |
|
831 | 565 |
#endif |
0 comments (0 inline)