00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_UTIL_FIBONACCI_HEAP_HH
00027 # define MLN_UTIL_FIBONACCI_HEAP_HH
00028
00029
00030 # include <iostream>
00031 # include <mln/core/concept/object.hh>
00032 # include <mln/util/ord.hh>
00033
00034
00035
00036 namespace mln
00037 {
00038
00039 namespace util
00040 {
00041
00042
00043 namespace internal
00044 {
00045
00046
00047
00048
00049
00050 template <typename P, typename T>
00051 class fibonacci_heap_node
00052 {
00053
00054 public:
00056 fibonacci_heap_node();
00057
00059 fibonacci_heap_node(const P& priority, const T& value);
00060
00061 ~fibonacci_heap_node();
00062
00064 const T& value() const;
00065
00066 const P& priority() const;
00067
00068 fibonacci_heap_node<P,T> *left() const;
00069 fibonacci_heap_node<P,T> *right() const;
00070 fibonacci_heap_node<P,T> *parent() const;
00071 fibonacci_heap_node<P,T> *child() const;
00072
00073 short degree() const;
00074
00075 short mark() const;
00076
00077
00078 void set_value(const T&);
00079 void set_left(fibonacci_heap_node<P,T> *node);
00080 void set_right(fibonacci_heap_node<P,T> *node);
00081 void set_parent(fibonacci_heap_node<P,T> *node);
00082 void set_child(fibonacci_heap_node<P,T> *node);
00083 void set_degree(short degree);
00084 void set_mark(short mark);
00085
00086 void operator=(fibonacci_heap_node<P,T>& rhs);
00087 bool operator==(fibonacci_heap_node<P,T>& rhs);
00088 bool operator<(fibonacci_heap_node<P,T>& rhs);
00089
00090 void print_() const;
00091
00092
00093 private:
00094
00095 fibonacci_heap_node<P,T> *left_;
00096 fibonacci_heap_node<P,T> *right_;
00097 fibonacci_heap_node<P,T> *parent_;
00098 fibonacci_heap_node<P,T> *child_;
00099 short degree_;
00100 short mark_;
00101 P priority_;
00102 T value_;
00103 };
00104
00105 }
00106
00107
00108
00109
00110
00111
00112
00116 template <typename P, typename T>
00117 class fibonacci_heap : public Object< fibonacci_heap<P,T> >
00118 {
00119 public:
00120
00121 typedef T element;
00122
00124 fibonacci_heap();
00125
00129 fibonacci_heap(const fibonacci_heap<P,T>& node);
00130
00131 ~fibonacci_heap();
00132
00135 void push(const P& priority, const T& value);
00136
00139 void push(fibonacci_heap<P,T>& other_heap);
00140
00142 const T& front() const;
00143
00145 T pop_front();
00146
00148 bool is_empty() const;
00149
00151 bool is_valid() const;
00152
00154 unsigned nelements() const;
00155
00157 void clear();
00158
00163 fibonacci_heap<P,T>& operator=(fibonacci_heap<P,T>& rhs);
00164
00165
00166
00167 std::ostream& print_(std::ostream& cout,
00168 internal::fibonacci_heap_node<P,T> *tree = 0,
00169 internal::fibonacci_heap_node<P,T> *parent = 0) const;
00170
00171 private:
00172
00173
00174
00175
00180 int decrease_key(internal::fibonacci_heap_node<P,T> *node,
00181 internal::fibonacci_heap_node<P,T>& key);
00182
00187 int remove(internal::fibonacci_heap_node<P,T> *node);
00188
00190 void insert(internal::fibonacci_heap_node<P,T> *node);
00191
00193 void exchange(internal::fibonacci_heap_node<P,T>*& lhs,
00194 internal::fibonacci_heap_node<P,T>*& rhs);
00195
00211 void consolidate();
00212
00215 void link(internal::fibonacci_heap_node<P,T> *lhs,
00216 internal::fibonacci_heap_node<P,T> *rhs);
00217
00218 void add_to_root_list(internal::fibonacci_heap_node<P,T> *);
00219
00221 void cut(internal::fibonacci_heap_node<P,T> *lhs,
00222 internal::fibonacci_heap_node<P,T> *rhs);
00223
00231 void cascading_cut(internal::fibonacci_heap_node<P,T> *);
00232
00234 void soft_clear_();
00235
00238 mutable internal::fibonacci_heap_node<P,T> *min_root;
00239 mutable long num_nodes;
00240 mutable long num_trees;
00241 mutable long num_marked_nodes;
00242
00243 };
00244
00245
00246 template <typename P, typename T>
00247 std::ostream&
00248 operator<<(std::ostream& cout, const fibonacci_heap<P,T>& heap);
00249
00250
00251
00252 # ifndef MLN_INCLUDE_ONLY
00253
00254
00255 namespace internal
00256 {
00257
00258
00259
00260
00261
00262
00263
00264 template <typename P, typename T>
00265 inline
00266 fibonacci_heap_node<P,T>::fibonacci_heap_node()
00267 : left_(0), right_(0), parent_(0), child_(0),
00268 degree_(0), mark_(0), priority_(0)
00269
00270 {
00271 }
00272
00273
00274 template <typename P, typename T>
00275 inline
00276 fibonacci_heap_node<P,T>::fibonacci_heap_node(const P& priority,
00277 const T& new_value)
00278 : left_(0), right_(0), parent_(0), child_(0),
00279 degree_(0), mark_(0), priority_(priority), value_(new_value)
00280 {
00281 }
00282
00283
00284 template <typename P, typename T>
00285 inline
00286 fibonacci_heap_node<P,T>::~fibonacci_heap_node()
00287 {
00288 }
00289
00290
00291 template <typename P, typename T>
00292 inline
00293 const T&
00294 fibonacci_heap_node<P,T>::value() const
00295 {
00296 return value_;
00297 }
00298
00299
00300 template <typename P, typename T>
00301 inline
00302 const P&
00303 fibonacci_heap_node<P,T>::priority() const
00304 {
00305 return priority_;
00306 }
00307
00308
00309 template <typename P, typename T>
00310 inline
00311 fibonacci_heap_node<P,T> *
00312 fibonacci_heap_node<P,T>::left() const
00313 {
00314 return left_;
00315 }
00316
00317
00318 template <typename P, typename T>
00319 inline
00320 fibonacci_heap_node<P,T> *
00321 fibonacci_heap_node<P,T>::right() const
00322 {
00323 return right_;
00324 }
00325
00326
00327 template <typename P, typename T>
00328 inline
00329 fibonacci_heap_node<P,T> *
00330 fibonacci_heap_node<P,T>::parent() const
00331 {
00332 return parent_;
00333 }
00334
00335
00336 template <typename P, typename T>
00337 inline
00338 fibonacci_heap_node<P,T> *
00339 fibonacci_heap_node<P,T>::child() const
00340 {
00341 return child_;
00342 }
00343
00344
00345 template <typename P, typename T>
00346 inline
00347 short
00348 fibonacci_heap_node<P,T>::degree() const
00349 {
00350 return degree_;
00351 }
00352
00353
00354 template <typename P, typename T>
00355 inline
00356 short
00357 fibonacci_heap_node<P,T>::mark() const
00358 {
00359 return mark_;
00360 }
00361
00362
00363 template <typename P, typename T>
00364 inline
00365 void
00366 fibonacci_heap_node<P,T>::set_value(const T& value)
00367 {
00368 value_ = value;
00369 }
00370
00371
00372 template <typename P, typename T>
00373 inline
00374 void
00375 fibonacci_heap_node<P,T>::set_left(fibonacci_heap_node<P,T> *node)
00376 {
00377 left_ = node;
00378 }
00379
00380
00381 template <typename P, typename T>
00382 inline
00383 void
00384 fibonacci_heap_node<P,T>::set_right(fibonacci_heap_node<P,T> *node)
00385 {
00386 right_ = node;
00387 }
00388
00389
00390 template <typename P, typename T>
00391 inline
00392 void
00393 fibonacci_heap_node<P,T>::set_parent(fibonacci_heap_node<P,T> *node)
00394 {
00395 parent_ = node;
00396 }
00397
00398
00399 template <typename P, typename T>
00400 inline
00401 void
00402 fibonacci_heap_node<P,T>::set_child(fibonacci_heap_node<P,T> *node)
00403 {
00404 child_ = node;
00405 }
00406
00407
00408 template <typename P, typename T>
00409 inline
00410 void
00411 fibonacci_heap_node<P,T>::set_degree(short degree)
00412 {
00413 degree_ = degree;
00414 }
00415
00416
00417 template <typename P, typename T>
00418 inline
00419 void
00420 fibonacci_heap_node<P,T>::set_mark(short mark)
00421 {
00422 mark_ = mark;
00423 }
00424
00425
00426 template <typename P, typename T>
00427 inline
00428 void fibonacci_heap_node<P,T>::operator=(fibonacci_heap_node<P,T>& rhs)
00429 {
00430 priority_ = rhs.priority();
00431 value_ = rhs.value();
00432 }
00433
00434
00435 template <typename P, typename T>
00436 inline
00437 bool
00438 fibonacci_heap_node<P,T>::operator==(fibonacci_heap_node<P,T>& rhs)
00439 {
00440 return priority_ == rhs.priority() && value_ == rhs.value();
00441 }
00442
00443
00444 template <typename P, typename T>
00445 inline
00446 bool
00447 fibonacci_heap_node<P,T>::operator<(fibonacci_heap_node<P,T>& rhs)
00448 {
00449 return util::ord_strict(priority_, rhs.priority())
00450 || (priority_ == rhs.priority() && util::ord_strict(value_, rhs.value()));
00451 }
00452
00453
00454 template <typename P, typename T>
00455 inline
00456 void fibonacci_heap_node<P,T>::print_() const
00457 {
00458 std::cout << value_ << " (" << priority_ << ")";
00459 }
00460
00461
00462 }
00463
00464
00465
00466
00467
00468
00469
00470 template <typename P, typename T>
00471 inline
00472 fibonacci_heap<P,T>::fibonacci_heap()
00473 {
00474 soft_clear_();
00475 }
00476
00477
00478 template <typename P, typename T>
00479 inline
00480 fibonacci_heap<P,T>::fibonacci_heap(const fibonacci_heap<P,T>& rhs)
00481 : Object< fibonacci_heap<P,T> >()
00482 {
00483 min_root = rhs.min_root;
00484 num_nodes = rhs.num_nodes;
00485 num_trees = rhs.num_trees;
00486 num_marked_nodes = rhs.num_marked_nodes;
00487
00488
00489
00490 rhs.min_root = 0;
00491 rhs.num_nodes = 0;
00492 rhs.num_trees = 0;
00493 rhs.num_marked_nodes = 0;
00494 }
00495
00496
00497 template <typename P, typename T>
00498 inline
00499 fibonacci_heap<P,T>::~fibonacci_heap()
00500 {
00501 clear();
00502 }
00503
00504
00505 template <typename P, typename T>
00506 inline
00507 void
00508 fibonacci_heap<P,T>::push(const P& priority, const T& value)
00509 {
00510 typedef internal::fibonacci_heap_node<P,T> node_t;
00511 node_t *new_node = new node_t(priority, value);
00512
00513 insert(new_node);
00514 }
00515
00516
00517 template <typename P, typename T>
00518 inline
00519 void
00520 fibonacci_heap<P,T>::push(fibonacci_heap<P,T>& other_heap)
00521 {
00522 if (other_heap.is_empty() || &other_heap == this)
00523 return;
00524
00525 if (min_root != 0)
00526 {
00527 internal::fibonacci_heap_node<P,T> *min1, *min2, *next1, *next2;
00528
00529
00530
00531
00532
00533 min1 = min_root;
00534 min2 = other_heap.min_root;
00535 next1 = min1->right();
00536 next2 = min2->right();
00537
00538
00539
00540
00541
00542 min1->set_right(next2);
00543 next2->set_left(min1);
00544 min2->set_right(next1);
00545 next1->set_left(min2);
00546
00547
00548 if (*min2 < *min1)
00549 min_root = min2;
00550 }
00551 else
00552 min_root = other_heap.min_root;
00553
00554
00555 num_nodes += other_heap.num_nodes;
00556 num_marked_nodes += other_heap.num_marked_nodes;
00557 num_trees += other_heap.num_trees;
00558
00559
00560 other_heap.soft_clear_();
00561
00562 mln_postcondition(other_heap.is_empty());
00563 }
00564
00565
00566 template <typename P, typename T>
00567 inline
00568 const T&
00569 fibonacci_heap<P,T>::front() const
00570 {
00571 return min_root->value();
00572 }
00573
00574
00575 template <typename P, typename T>
00576 inline
00577 T
00578 fibonacci_heap<P,T>::pop_front()
00579 {
00580 mln_precondition(is_valid());
00581 mln_precondition(!is_empty());
00582
00583 internal::fibonacci_heap_node<P,T> *result = min_root;
00584 fibonacci_heap<P,T> *child_heap = 0;
00585
00586
00587 min_root = result->right();
00588 result->right()->set_left(result->left());
00589 result->left()->set_right(result->right());
00590 result->set_left(0);
00591 result->set_right(0);
00592
00593 --num_nodes;
00594 if (result->mark())
00595 {
00596 --num_marked_nodes;
00597 result->set_mark(0);
00598 }
00599 result->set_degree(0);
00600
00601
00602
00603 if (result->child() == 0)
00604 {
00605 if (min_root == result)
00606 min_root = 0;
00607 }
00608
00609
00610
00611
00612 else if (min_root == result)
00613 min_root = result->child();
00614
00615
00616
00617
00618 else
00619 {
00620 child_heap = new fibonacci_heap<P,T>();
00621 child_heap->min_root = result->child();
00622 }
00623
00624
00625 if (result->child() != 0)
00626 result->child()->set_parent(0);
00627 result->set_child(0);
00628 result->set_parent(0);
00629
00630
00631
00632 if (child_heap)
00633 {
00634 push(*child_heap);
00635 delete child_heap;
00636 }
00637
00638
00639 if (min_root != 0)
00640 consolidate();
00641
00642
00643
00644 T val = result->value();
00645 delete result;
00646
00647 return val;
00648 }
00649
00650
00651 template <typename P, typename T>
00652 inline
00653 int
00654 fibonacci_heap<P,T>::decrease_key(internal::fibonacci_heap_node<P,T> *node,
00655 internal::fibonacci_heap_node<P,T>& key)
00656 {
00657 internal::fibonacci_heap_node<P,T> *parent;
00658
00659 if (node == 0 || *node < key)
00660 return -1;
00661
00662 *node = key;
00663
00664 parent = node->parent();
00665 if (parent != 0 && *node < *parent)
00666 {
00667 cut(node, parent);
00668 cascading_cut(parent);
00669 }
00670
00671 if (*node < *min_root)
00672 min_root = node;
00673
00674 return 0;
00675 }
00676
00677
00678 template <typename P, typename T>
00679 inline
00680 int
00681 fibonacci_heap<P,T>::remove(internal::fibonacci_heap_node<P,T> *node)
00682 {
00683 internal::fibonacci_heap_node<P,T> temp;
00684 int result;
00685
00686 if (node == 0)
00687 return -1;
00688
00689 result = decrease_key(node, temp);
00690
00691 if (result == 0)
00692 if (pop_front() == 0)
00693 result = -1;
00694
00695 if (result == 0)
00696 delete node;
00697
00698 return result;
00699 }
00700
00701
00702 template <typename P, typename T>
00703 inline
00704 bool
00705 fibonacci_heap<P,T>::is_empty() const
00706 {
00707 return min_root == 0;
00708 }
00709
00710
00711 template <typename P, typename T>
00712 inline
00713 bool
00714 fibonacci_heap<P,T>::is_valid() const
00715 {
00716 return min_root != 0;
00717 }
00718
00719
00720 template <typename P, typename T>
00721 inline
00722 void
00723 fibonacci_heap<P,T>::clear()
00724 {
00725 while (min_root != 0)
00726 pop_front();
00727 }
00728
00729
00730 template <typename P, typename T>
00731 inline
00732 void
00733 fibonacci_heap<P,T>::soft_clear_()
00734 {
00735 min_root = 0;
00736 num_nodes = 0;
00737 num_trees = 0;
00738 num_marked_nodes = 0;
00739 }
00740
00741
00742 template <typename P, typename T>
00743 inline
00744 unsigned
00745 fibonacci_heap<P,T>::nelements() const
00746 {
00747 return num_nodes;
00748 };
00749
00750
00751 template <typename P, typename T>
00752 inline
00753 fibonacci_heap<P,T>&
00754 fibonacci_heap<P,T>::operator=(fibonacci_heap<P,T>& rhs)
00755 {
00756 if (&rhs != this)
00757 {
00758 min_root = rhs.min_root;
00759 num_nodes = rhs.num_nodes;
00760 num_trees = rhs.num_trees;
00761 num_marked_nodes = rhs.num_marked_nodes;
00762 rhs.soft_clear_();
00763 }
00764 return *this;
00765 }
00766
00767
00768 template <typename P, typename T>
00769 std::ostream&
00770 fibonacci_heap<P,T>::print_(std::ostream& cout,
00771 internal::fibonacci_heap_node<P,T> *tree,
00772 internal::fibonacci_heap_node<P,T> *parent) const
00773 {
00774 internal::fibonacci_heap_node<P,T>* temp = 0;
00775
00776 if (tree == 0)
00777 tree = min_root;
00778
00779 temp = tree;
00780 if (temp != 0)
00781 {
00782 do {
00783 if (temp->left() == 0)
00784 cout << "(left is 0)";
00785 temp->print_();
00786 if (temp->parent() != parent)
00787 cout << "(parent is incorrect)";
00788 if (temp->right() == 0)
00789 cout << "(right is 0)";
00790 else if (temp->right()->left() != temp)
00791 cout << "(Error in left link left) ->";
00792 else
00793 cout << " <-> ";
00794
00795 temp = temp->right();
00796
00797 } while (temp != 0 && temp != tree);
00798 }
00799 else
00800 cout << " <empty>" << std::endl;
00801 cout << std::endl;
00802
00803 temp = tree;
00804 if (temp != 0)
00805 {
00806 do {
00807 cout << "children of " << temp->value() << ": ";
00808 if (temp->child() == 0)
00809 cout << "NONE" << std::endl;
00810 else print_(cout, temp->child(), temp);
00811 temp = temp->right();
00812 } while (temp!=0 && temp != tree);
00813 }
00814
00815 return cout;
00816 }
00817
00818
00819 template <typename P, typename T>
00820 inline
00821 void fibonacci_heap<P,T>::consolidate()
00822 {
00823 internal::fibonacci_heap_node<P,T> *x, *y, *w;
00824 internal::fibonacci_heap_node<P,T> *a[1 + 8 * sizeof (long)];
00825 short dn = 1 + 8 * sizeof (long);
00826
00827
00828 for (int i = 0; i < dn; ++i)
00829 a[i] = 0;
00830
00831
00832
00833
00834
00835
00836
00837
00838
00839 min_root->left()->set_right(0);
00840 min_root->set_left(0);
00841 w = min_root;
00842
00843 short d;
00844 do {
00845 x = w;
00846 d = x->degree();
00847 w = w->right();
00848
00849
00850
00851 while (a[d] != 0)
00852 {
00853 y = a[d];
00854 if (*y < *x)
00855 exchange(x, y);
00856 if (w == y) w = y->right();
00857 link(y, x);
00858 a[d] = 0;
00859 ++d;
00860 }
00861 a[d] = x;
00862
00863 } while (w != 0);
00864
00865
00866
00867
00868 min_root = 0;
00869 num_trees = 0;
00870 for (int i = 0; i < dn; ++i)
00871 if (a[i] != 0)
00872 add_to_root_list(a[i]);
00873 }
00874
00875
00876 template <typename P, typename T>
00877 inline
00878 void
00879 fibonacci_heap<P,T>::link(internal::fibonacci_heap_node<P,T> *y,
00880 internal::fibonacci_heap_node<P,T> *x)
00881 {
00882
00883 if (y->right() != 0)
00884 y->right()->set_left(y->left());
00885 if (y->left() != 0)
00886 y->left()->set_right(y->right());
00887 --num_trees;
00888
00889
00890 y->set_left(y);
00891 y->set_right(y);
00892 y->set_parent(x);
00893
00894
00895 if (x->child() == 0)
00896 x->set_child(y);
00897
00898
00899 else
00900 {
00901 y->set_left(x->child());
00902 y->set_right(x->child()->right());
00903 x->child()->set_right(y);
00904 y->right()->set_left(y);
00905 }
00906
00907
00908 x->set_degree(x->degree() + 1);
00909
00910
00911 if (y->mark())
00912 --num_marked_nodes;
00913 y->set_mark(0);
00914 }
00915
00916
00917 template <typename P, typename T>
00918 inline
00919 void
00920 fibonacci_heap<P,T>::add_to_root_list(internal::fibonacci_heap_node<P,T> *x)
00921 {
00922 if (x->mark())
00923 --num_marked_nodes;
00924 x->set_mark(0);
00925
00926 --num_nodes;
00927 insert(x);
00928 }
00929
00930
00931 template <typename P, typename T>
00932 inline
00933 void
00934 fibonacci_heap<P,T>::cut(internal::fibonacci_heap_node<P,T> *x,
00935 internal::fibonacci_heap_node<P,T> *y)
00936 {
00937 if (y->child() == x)
00938 y->child() = x->right();
00939 if (y->child() == x)
00940 y->child() = 0;
00941
00942 y->set_degree(y->degree() - 1);
00943
00944 x->left()->right() = x->right();
00945 x->right()->left() = x->left();
00946
00947 add_to_root_list(x);
00948 }
00949
00950
00951 template <typename P, typename T>
00952 inline
00953 void
00954 fibonacci_heap<P,T>::cascading_cut(internal::fibonacci_heap_node<P,T> *y)
00955 {
00956 internal::fibonacci_heap_node<P,T> *z = y->parent();
00957
00958 while (z != 0)
00959 {
00960 if (y->mark() == 0)
00961 {
00962 y->mark() = 1;
00963 ++num_marked_nodes;
00964 z = 0;
00965 }
00966 else
00967 {
00968 cut(y, z);
00969 y = z;
00970 z = y->parent();
00971 }
00972 }
00973 }
00974
00975
00976 template <typename P, typename T>
00977 inline
00978 void
00979 fibonacci_heap<P,T>::insert(internal::fibonacci_heap_node<P,T> *node)
00980 {
00981 if (node == 0)
00982 return;
00983
00984
00985
00986 if (min_root == 0)
00987 {
00988 min_root = node;
00989 node->set_left(node);
00990 node->set_right(node);
00991 }
00992 else
00993 {
00994
00995
00996 node->set_right(min_root->right());
00997 node->set_left(min_root);
00998
00999
01000 node->left()->set_right(node);
01001 node->right()->set_left(node);
01002
01003
01004
01005 if (*node < *min_root)
01006 min_root = node;
01007 }
01008
01009
01010 ++num_nodes;
01011 ++num_trees;
01012 node->set_parent(0);
01013 }
01014
01015
01016 template <typename P, typename T>
01017 inline
01018 void
01019 fibonacci_heap<P,T>::exchange(internal::fibonacci_heap_node<P,T>*& n1,
01020 internal::fibonacci_heap_node<P,T>*& n2)
01021 {
01022 internal::fibonacci_heap_node<P,T> *temp;
01023
01024 temp = n1;
01025 n1 = n2;
01026 n2 = temp;
01027 }
01028
01029
01030 template <typename P, typename T>
01031 std::ostream&
01032 operator<<(std::ostream& cout, const fibonacci_heap<P,T>& heap)
01033 {
01034 return heap.print_(cout);
01035 }
01036
01037 # endif // ! MLN_INCLUDE_ONLY
01038
01039
01040
01041 }
01042
01043 }
01044
01045 #endif // ! MLN_UTIL_FIBONACCI_HEAP_HH