159 void push(const Item &i, const Prio &p) { |
189 void push(const Item &i, const Prio &p) { |
160 int idx = data.size(); |
190 int idx = data.size(); |
161 index[i] = idx; |
191 index[i] = idx; |
162 data.push_back(BucketItem(i, p)); |
192 data.push_back(BucketItem(i, p)); |
163 lace(idx); |
193 lace(idx); |
164 if (p < minimal) { |
194 if (Direction::less(p, minimal)) { |
165 minimal = p; |
195 minimal = p; |
166 } |
196 } |
167 } |
197 } |
168 |
198 |
169 /// \brief Returns the item with minimum priority. |
199 /// \brief Returns the item with minimum priority. |
170 /// |
200 /// |
171 /// This method returns the item with minimum priority. |
201 /// This method returns the item with minimum priority. |
172 /// \pre The heap must be nonempty. |
202 /// \pre The heap must be nonempty. |
173 Item top() const { |
203 Item top() const { |
174 while (first[minimal] == -1) { |
204 while (first[minimal] == -1) { |
175 ++minimal; |
205 Direction::increase(minimal); |
176 } |
206 } |
177 return data[first[minimal]].item; |
207 return data[first[minimal]].item; |
178 } |
208 } |
179 |
209 |
180 /// \brief Returns the minimum priority. |
210 /// \brief Returns the minimum priority. |
181 /// |
211 /// |
182 /// It returns the minimum priority. |
212 /// It returns the minimum priority. |
183 /// \pre The heap must be nonempty. |
213 /// \pre The heap must be nonempty. |
184 Prio prio() const { |
214 Prio prio() const { |
185 while (first[minimal] == -1) { |
215 while (first[minimal] == -1) { |
186 ++minimal; |
216 Direction::increase(minimal); |
187 } |
217 } |
188 return minimal; |
218 return minimal; |
189 } |
219 } |
190 |
220 |
191 /// \brief Deletes the item with minimum priority. |
221 /// \brief Deletes the item with minimum priority. |
192 /// |
222 /// |
193 /// This method deletes the item with minimum priority from the heap. |
223 /// This method deletes the item with minimum priority from the heap. |
194 /// \pre The heap must be non-empty. |
224 /// \pre The heap must be non-empty. |
195 void pop() { |
225 void pop() { |
196 while (first[minimal] == -1) { |
226 while (first[minimal] == -1) { |
197 ++minimal; |
227 Direction::increase(minimal); |
198 } |
228 } |
199 int idx = first[minimal]; |
229 int idx = first[minimal]; |
200 index[data[idx].item] = -2; |
230 index[data[idx].item] = -2; |
201 unlace(idx); |
231 unlace(idx); |
202 relocate_last(idx); |
232 relocate_last(idx); |
326 std::vector<BucketItem> data; |
356 std::vector<BucketItem> data; |
327 mutable int minimal; |
357 mutable int minimal; |
328 |
358 |
329 }; // class BucketHeap |
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 /// \ingroup auxdat |
361 /// \ingroup auxdat |
519 /// |
362 /// |
520 /// \brief A Simplified Bucket Heap implementation. |
363 /// \brief A Simplified Bucket Heap implementation. |
521 /// |
364 /// |
522 /// This class implements a simplified \e bucket \e heap data |
365 /// This class implements a simplified \e bucket \e heap data |
523 /// structure. It does not provide some functionality but it faster |
366 /// structure. It does not provide some functionality but it faster |
524 /// and simplier data structure than the BucketHeap. The main |
367 /// and simplier data structure than the BucketHeap. The main |
525 /// difference is that the BucketHeap stores for every key a double |
368 /// difference is that the BucketHeap stores for every key a double |
526 /// linked list while this class stores just simple lists. In the |
369 /// linked list while this class stores just simple lists. In the |
527 /// other way it does not supports erasing each elements just the |
370 /// other way it does not support erasing each elements just the |
528 /// minimal and it does not supports key increasing, decreasing. |
371 /// minimal and it does not supports key increasing, decreasing. |
529 /// |
372 /// |
530 /// \param _ItemIntMap A read and writable Item int map, used internally |
373 /// \param _ItemIntMap A read and writable Item int map, used internally |
531 /// to handle the cross references. |
374 /// to handle the cross references. |
532 /// \param minimize If the given parameter is true then the heap gives back |
375 /// \param minimize If the given parameter is true then the heap gives back |
624 /// |
473 /// |
625 /// This method returns the item with minimum priority. |
474 /// This method returns the item with minimum priority. |
626 /// \pre The heap must be nonempty. |
475 /// \pre The heap must be nonempty. |
627 Item top() const { |
476 Item top() const { |
628 while (first[minimal] == -1) { |
477 while (first[minimal] == -1) { |
629 ++minimal; |
478 Direction::increase(minimal); |
630 } |
479 } |
631 return data[first[minimal]].item; |
480 return data[first[minimal]].item; |
632 } |
481 } |
633 |
482 |
634 /// \brief Returns the minimum priority. |
483 /// \brief Returns the minimum priority. |
635 /// |
484 /// |
636 /// It returns the minimum priority. |
485 /// It returns the minimum priority. |
637 /// \pre The heap must be nonempty. |
486 /// \pre The heap must be nonempty. |
638 Prio prio() const { |
487 Prio prio() const { |
639 while (first[minimal] == -1) { |
488 while (first[minimal] == -1) { |
640 ++minimal; |
489 Direction::increase(minimal); |
641 } |
490 } |
642 return minimal; |
491 return minimal; |
643 } |
492 } |
644 |
493 |
645 /// \brief Deletes the item with minimum priority. |
494 /// \brief Deletes the item with minimum priority. |
646 /// |
495 /// |
647 /// This method deletes the item with minimum priority from the heap. |
496 /// This method deletes the item with minimum priority from the heap. |
648 /// \pre The heap must be non-empty. |
497 /// \pre The heap must be non-empty. |
649 void pop() { |
498 void pop() { |
650 while (first[minimal] == -1) { |
499 while (first[minimal] == -1) { |
651 ++minimal; |
500 Direction::increase(minimal); |
652 } |
501 } |
653 int idx = first[minimal]; |
502 int idx = first[minimal]; |
654 index[data[idx].item] = -2; |
503 index[data[idx].item] = -2; |
655 first[minimal] = data[idx].next; |
504 first[minimal] = data[idx].next; |
656 data[idx].next = free; |
505 data[idx].next = free; |
709 int free, num; |
558 int free, num; |
710 mutable int minimal; |
559 mutable int minimal; |
711 |
560 |
712 }; // class SimpleBucketHeap |
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 #endif |
565 #endif |