Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 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 | Fibonacci Heap node Class | 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_(std::ostream& ostr) 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 } // end of namespace mln::util::internal 00106 00107 00108 00109 /*---------------------\ 00110 | Fibonacci Heap Class | 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& ostr, 00168 internal::fibonacci_heap_node<P,T> *tree = 0, 00169 internal::fibonacci_heap_node<P,T> *parent = 0) const; 00170 00171 private: 00172 00173 // Internal functions that help to implement the Standard Operations 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& ostr, const fibonacci_heap<P,T>& heap); 00249 00250 00251 00252 # ifndef MLN_INCLUDE_ONLY 00253 00254 00255 namespace internal 00256 { 00257 00258 00259 /*--------------------\ 00260 | fibonacci_heap_node | 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 // FIXME: don't we want to initialize priority with literal::zero? 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_(std::ostream& ostr) const 00457 { 00458 ostr << value_ << " (" << priority_ << ")"; 00459 } 00460 00461 00462 } // end of namespace mln::util::internal 00463 00464 00465 00466 /*---------------\ 00467 | fibonacci_heap | 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 // rhs is const, we cannot call that method. 00489 // rhs.soft_clear_(); 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 // We join the two circular lists by cutting each list between its 00530 // min node and the node after the min. This code just pulls those 00531 // nodes into temporary variables so we don't get lost as changes 00532 // are made. 00533 min1 = min_root; 00534 min2 = other_heap.min_root; 00535 next1 = min1->right(); 00536 next2 = min2->right(); 00537 00538 // To join the two circles, we join the minimum nodes to the next 00539 // nodes on the opposite chains. Conceptually, it looks like the way 00540 // two bubbles join to form one larger bubble. They meet at one point 00541 // of contact, then expand out to make the bigger circle. 00542 min1->set_right(next2); 00543 next2->set_left(min1); 00544 min2->set_right(next1); 00545 next1->set_left(min2); 00546 00547 // Choose the new minimum for the heap 00548 if (*min2 < *min1) 00549 min_root = min2; 00550 } 00551 else 00552 min_root = other_heap.min_root; 00553 00554 // Set the amortized analysis statistics and size of the new heap 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 // Complete the union by setting the other heap to emptiness 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 // Remove minimum node and set min_root to next node 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 // Attach child list of minimum node to the root list of the heap 00602 // If there is no child list, then do no work 00603 if (result->child() == 0) 00604 { 00605 if (min_root == result) 00606 min_root = 0; 00607 } 00608 00609 // If min_root==result then there was only one root tree, so the 00610 // root list is simply the child list of that node (which is 00611 // 0 if this is the last node in the list) 00612 else if (min_root == result) 00613 min_root = result->child(); 00614 00615 // If min_root is different, then the child list is pushed into a 00616 // new temporary heap, which is then merged by union() onto the 00617 // root list of this heap. 00618 else 00619 { 00620 child_heap = new fibonacci_heap<P,T>(); 00621 child_heap->min_root = result->child(); 00622 } 00623 00624 // Complete the disassociation of the result node from the heap 00625 if (result->child() != 0) 00626 result->child()->set_parent(0); 00627 result->set_child(0); 00628 result->set_parent(0); 00629 00630 // If there was a child list, then we now merge it with the 00631 // rest of the root list 00632 if (child_heap) 00633 { 00634 push(*child_heap); 00635 delete child_heap; 00636 } 00637 00638 // Consolidate heap to find new minimum and do reorganize work 00639 if (min_root != 0) 00640 consolidate(); 00641 00642 // Return the minimum node, which is now disassociated with the heap 00643 // It has left, right, parent, child, mark and degree cleared. 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& ostr, 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 ostr << "(left is 0)"; 00785 temp->print_(); 00786 if (temp->parent() != parent) 00787 ostr << "(parent is incorrect)"; 00788 if (temp->right() == 0) 00789 ostr << "(right is 0)"; 00790 else if (temp->right()->left() != temp) 00791 ostr << "(Error in left link left) ->"; 00792 else 00793 ostr << " <-> "; 00794 00795 temp = temp->right(); 00796 00797 } while (temp != 0 && temp != tree); 00798 } 00799 else 00800 ostr << " <empty>" << std::endl; 00801 ostr << std::endl; 00802 00803 temp = tree; 00804 if (temp != 0) 00805 { 00806 do { 00807 ostr << "children of " << temp->value() << ": "; 00808 if (temp->child() == 0) 00809 ostr << "NONE" << std::endl; 00810 else print_(ostr, temp->child(), temp); 00811 temp = temp->right(); 00812 } while (temp!=0 && temp != tree); 00813 } 00814 00815 return ostr; 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)]; // 1+lg(n) 00825 short dn = 1 + 8 * sizeof (long); 00826 00827 // Initialize the consolidation detection array 00828 for (int i = 0; i < dn; ++i) 00829 a[i] = 0; 00830 00831 // We need to loop through all elements on root list. 00832 // When a collision of degree is found, the two trees 00833 // are consolidated in favor of the one with the lesser 00834 // element key value. We first need to break the circle 00835 // so that we can have a stopping condition (we can't go 00836 // around until we reach the tree we started with 00837 // because all root trees are subject to becoming a 00838 // child during the consolidation). 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 // We need another loop here because the consolidated result 00850 // may collide with another large tree on the root list. 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 // Now we rebuild the root list, find the new minimum, 00866 // set all root list nodes' parent pointers to 0 and 00867 // count the number of subtrees. 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 // Remove node y from root list 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 // Make node y a singleton circular list with a parent of x 00890 y->set_left(y); 00891 y->set_right(y); 00892 y->set_parent(x); 00893 00894 // If node x has no children, then list y is its new child list 00895 if (x->child() == 0) 00896 x->set_child(y); 00897 00898 // Otherwise, node y must be added to node x's child list 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 // Increase the degree of node x because it's now a bigger tree 00908 x->set_degree(x->degree() + 1); 00909 00910 // node y has just been made a child, so clear its mark 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 // If the heap is currently empty, then new node becomes singleton 00985 // circular root list 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 // Pointers from node set to insert between min_root and 00995 // min_root->right() 00996 node->set_right(min_root->right()); 00997 node->set_left(min_root); 00998 00999 // Set Pointers to node 01000 node->left()->set_right(node); 01001 node->right()->set_left(node); 01002 01003 // The new node becomes new min_root if it is less than current 01004 // min_root 01005 if (*node < *min_root) 01006 min_root = node; 01007 } 01008 01009 // We have one more node in the heap, and it is a tree on the root list 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& ostr, const fibonacci_heap<P,T>& heap) 01033 { 01034 return heap.print_(ostr); 01035 } 01036 01037 # endif // ! MLN_INCLUDE_ONLY 01038 01039 01040 01041 } // end of namespace mln::util 01042 01043 } // end of namespace mln 01044 01045 #endif // ! MLN_UTIL_FIBONACCI_HEAP_HH