1 // boost heap: fibonacci heap 2 // 3 // Copyright (C) 2010 Tim Blechmann 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 9 #ifndef BOOST_HEAP_FIBONACCI_HEAP_HPP 10 #define BOOST_HEAP_FIBONACCI_HEAP_HPP 11 12 #include <algorithm> 13 #include <utility> 14 #include <vector> 15 16 #include <boost/array.hpp> 17 #include <boost/assert.hpp> 18 19 #include <boost/heap/detail/heap_comparison.hpp> 20 #include <boost/heap/detail/heap_node.hpp> 21 #include <boost/heap/detail/stable_heap.hpp> 22 #include <boost/heap/detail/tree_iterator.hpp> 23 24 #ifdef BOOST_HAS_PRAGMA_ONCE 25 #pragma once 26 #endif 27 28 29 #ifndef BOOST_DOXYGEN_INVOKED 30 #ifdef BOOST_HEAP_SANITYCHECKS 31 #define BOOST_HEAP_ASSERT BOOST_ASSERT 32 #else 33 #define BOOST_HEAP_ASSERT(expression) 34 #endif 35 #endif 36 37 namespace boost { 38 namespace heap { 39 namespace detail { 40 41 typedef parameter::parameters<boost::parameter::optional<tag::allocator>, 42 boost::parameter::optional<tag::compare>, 43 boost::parameter::optional<tag::stable>, 44 boost::parameter::optional<tag::constant_time_size>, 45 boost::parameter::optional<tag::stability_counter_type> 46 > fibonacci_heap_signature; 47 48 template <typename T, typename Parspec> 49 struct make_fibonacci_heap_base 50 { 51 static const bool constant_time_size = parameter::binding<Parspec, 52 tag::constant_time_size, 53 boost::mpl::true_ 54 >::type::value; 55 56 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type; 57 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument; 58 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument; 59 typedef marked_heap_node<typename base_type::internal_type> node_type; 60 61 typedef typename allocator_argument::template rebind<node_type>::other allocator_type; 62 63 struct type: 64 base_type, 65 allocator_type 66 { typeboost::heap::detail::make_fibonacci_heap_base::type67 type(compare_argument const & arg): 68 base_type(arg) 69 {} 70 typeboost::heap::detail::make_fibonacci_heap_base::type71 type(type const & rhs): 72 base_type(static_cast<base_type const &>(rhs)), 73 allocator_type(static_cast<allocator_type const &>(rhs)) 74 {} 75 operator =boost::heap::detail::make_fibonacci_heap_base::type76 type & operator=(type const & rhs) 77 { 78 base_type::operator=(static_cast<base_type const &>(rhs)); 79 allocator_type::operator=(static_cast<allocator_type const &>(rhs)); 80 return *this; 81 } 82 83 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES typeboost::heap::detail::make_fibonacci_heap_base::type84 type(type && rhs): 85 base_type(std::move(static_cast<base_type&>(rhs))), 86 allocator_type(std::move(static_cast<allocator_type&>(rhs))) 87 {} 88 operator =boost::heap::detail::make_fibonacci_heap_base::type89 type & operator=(type && rhs) 90 { 91 base_type::operator=(std::move(static_cast<base_type&>(rhs))); 92 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs))); 93 return *this; 94 } 95 #endif 96 }; 97 }; 98 99 } 100 101 102 103 /** 104 * \class fibonacci_heap 105 * \brief fibonacci heap 106 * 107 * The template parameter T is the type to be managed by the container. 108 * The user can specify additional options and if no options are provided default options are used. 109 * 110 * The container supports the following options: 111 * - \c boost::heap::stable<>, defaults to \c stable<false> 112 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > 113 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > 114 * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true> 115 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> 116 * 117 */ 118 #ifdef BOOST_DOXYGEN_INVOKED 119 template<class T, class ...Options> 120 #else 121 template <typename T, 122 class A0 = boost::parameter::void_, 123 class A1 = boost::parameter::void_, 124 class A2 = boost::parameter::void_, 125 class A3 = boost::parameter::void_, 126 class A4 = boost::parameter::void_ 127 > 128 #endif 129 class fibonacci_heap: 130 private detail::make_fibonacci_heap_base<T, 131 typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type 132 >::type 133 { 134 typedef typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args; 135 typedef detail::make_fibonacci_heap_base<T, bound_args> base_maker; 136 typedef typename base_maker::type super_t; 137 138 typedef typename super_t::size_holder_type size_holder; 139 typedef typename super_t::internal_type internal_type; 140 typedef typename base_maker::allocator_argument allocator_argument; 141 142 template <typename Heap1, typename Heap2> 143 friend struct heap_merge_emulate; 144 145 private: 146 #ifndef BOOST_DOXYGEN_INVOKED 147 struct implementation_defined: 148 detail::extract_allocator_types<typename base_maker::allocator_argument> 149 { 150 typedef T value_type; 151 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type; 152 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference; 153 154 typedef typename base_maker::compare_argument value_compare; 155 typedef typename base_maker::allocator_type allocator_type; 156 157 typedef typename allocator_type::pointer node_pointer; 158 typedef typename allocator_type::const_pointer const_node_pointer; 159 160 typedef detail::heap_node_list node_list_type; 161 typedef typename node_list_type::iterator node_list_iterator; 162 typedef typename node_list_type::const_iterator node_list_const_iterator; 163 164 typedef typename base_maker::node_type node; 165 166 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor; 167 typedef typename super_t::internal_compare internal_compare; 168 typedef detail::node_handle<node_pointer, super_t, reference> handle_type; 169 170 typedef detail::recursive_tree_iterator<node, 171 node_list_const_iterator, 172 const value_type, 173 value_extractor, 174 detail::list_iterator_converter<node, node_list_type> 175 > iterator; 176 typedef iterator const_iterator; 177 178 typedef detail::tree_iterator<node, 179 const value_type, 180 allocator_type, 181 value_extractor, 182 detail::list_iterator_converter<node, node_list_type>, 183 true, 184 true, 185 value_compare 186 > ordered_iterator; 187 }; 188 189 typedef typename implementation_defined::node node; 190 typedef typename implementation_defined::node_pointer node_pointer; 191 typedef typename implementation_defined::node_list_type node_list_type; 192 typedef typename implementation_defined::node_list_iterator node_list_iterator; 193 typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator; 194 typedef typename implementation_defined::internal_compare internal_compare; 195 #endif 196 197 public: 198 typedef T value_type; 199 200 typedef typename implementation_defined::size_type size_type; 201 typedef typename implementation_defined::difference_type difference_type; 202 typedef typename implementation_defined::value_compare value_compare; 203 typedef typename implementation_defined::allocator_type allocator_type; 204 typedef typename implementation_defined::reference reference; 205 typedef typename implementation_defined::const_reference const_reference; 206 typedef typename implementation_defined::pointer pointer; 207 typedef typename implementation_defined::const_pointer const_pointer; 208 /// \copydoc boost::heap::priority_queue::iterator 209 typedef typename implementation_defined::iterator iterator; 210 typedef typename implementation_defined::const_iterator const_iterator; 211 typedef typename implementation_defined::ordered_iterator ordered_iterator; 212 213 typedef typename implementation_defined::handle_type handle_type; 214 215 static const bool constant_time_size = base_maker::constant_time_size; 216 static const bool has_ordered_iterators = true; 217 static const bool is_mergable = true; 218 static const bool is_stable = detail::extract_stable<bound_args>::value; 219 static const bool has_reserve = false; 220 221 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) fibonacci_heap(value_compare const & cmp=value_compare ())222 explicit fibonacci_heap(value_compare const & cmp = value_compare()): 223 super_t(cmp), top_element(0) 224 {} 225 226 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) fibonacci_heap(fibonacci_heap const & rhs)227 fibonacci_heap(fibonacci_heap const & rhs): 228 super_t(rhs), top_element(0) 229 { 230 if (rhs.empty()) 231 return; 232 233 clone_forest(rhs); 234 size_holder::set_size(rhs.size()); 235 } 236 237 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES 238 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) fibonacci_heap(fibonacci_heap && rhs)239 fibonacci_heap(fibonacci_heap && rhs): 240 super_t(std::move(rhs)), top_element(rhs.top_element) 241 { 242 roots.splice(roots.begin(), rhs.roots); 243 rhs.top_element = NULL; 244 } 245 246 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) operator =(fibonacci_heap && rhs)247 fibonacci_heap & operator=(fibonacci_heap && rhs) 248 { 249 clear(); 250 251 super_t::operator=(std::move(rhs)); 252 roots.splice(roots.begin(), rhs.roots); 253 top_element = rhs.top_element; 254 rhs.top_element = NULL; 255 return *this; 256 } 257 #endif 258 259 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &) operator =(fibonacci_heap const & rhs)260 fibonacci_heap & operator=(fibonacci_heap const & rhs) 261 { 262 clear(); 263 size_holder::set_size(rhs.size()); 264 static_cast<super_t&>(*this) = rhs; 265 266 if (rhs.empty()) 267 top_element = NULL; 268 else 269 clone_forest(rhs); 270 return *this; 271 } 272 ~fibonacci_heap(void)273 ~fibonacci_heap(void) 274 { 275 clear(); 276 } 277 278 /// \copydoc boost::heap::priority_queue::empty empty(void) const279 bool empty(void) const 280 { 281 if (constant_time_size) 282 return size() == 0; 283 else 284 return roots.empty(); 285 } 286 287 /// \copydoc boost::heap::priority_queue::size size(void) const288 size_type size(void) const 289 { 290 if (constant_time_size) 291 return size_holder::get_size(); 292 293 if (empty()) 294 return 0; 295 else 296 return detail::count_list_nodes<node, node_list_type>(roots); 297 } 298 299 /// \copydoc boost::heap::priority_queue::max_size max_size(void) const300 size_type max_size(void) const 301 { 302 return allocator_type::max_size(); 303 } 304 305 /// \copydoc boost::heap::priority_queue::clear clear(void)306 void clear(void) 307 { 308 typedef detail::node_disposer<node, typename node_list_type::value_type, allocator_type> disposer; 309 roots.clear_and_dispose(disposer(*this)); 310 311 size_holder::set_size(0); 312 top_element = NULL; 313 } 314 315 /// \copydoc boost::heap::priority_queue::get_allocator get_allocator(void) const316 allocator_type get_allocator(void) const 317 { 318 return *this; 319 } 320 321 /// \copydoc boost::heap::priority_queue::swap swap(fibonacci_heap & rhs)322 void swap(fibonacci_heap & rhs) 323 { 324 super_t::swap(rhs); 325 std::swap(top_element, rhs.top_element); 326 roots.swap(rhs.roots); 327 } 328 329 330 /// \copydoc boost::heap::priority_queue::top top(void) const331 value_type const & top(void) const 332 { 333 BOOST_ASSERT(!empty()); 334 335 return super_t::get_value(top_element->value); 336 } 337 338 /** 339 * \b Effects: Adds a new element to the priority queue. Returns handle to element 340 * 341 * \b Complexity: Constant. 342 * 343 * \b Note: Does not invalidate iterators. 344 * 345 * */ push(value_type const & v)346 handle_type push(value_type const & v) 347 { 348 size_holder::increment(); 349 350 node_pointer n = allocator_type::allocate(1); 351 352 new(n) node(super_t::make_node(v)); 353 roots.push_front(*n); 354 355 if (!top_element || super_t::operator()(top_element->value, n->value)) 356 top_element = n; 357 return handle_type(n); 358 } 359 360 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 361 /** 362 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element. 363 * 364 * \b Complexity: Constant. 365 * 366 * \b Note: Does not invalidate iterators. 367 * 368 * */ 369 template <class... Args> emplace(Args &&...args)370 handle_type emplace(Args&&... args) 371 { 372 size_holder::increment(); 373 374 node_pointer n = allocator_type::allocate(1); 375 376 new(n) node(super_t::make_node(std::forward<Args>(args)...)); 377 roots.push_front(*n); 378 379 if (!top_element || super_t::operator()(top_element->value, n->value)) 380 top_element = n; 381 return handle_type(n); 382 } 383 #endif 384 385 /** 386 * \b Effects: Removes the top element from the priority queue. 387 * 388 * \b Complexity: Logarithmic (amortized). Linear (worst case). 389 * 390 * */ pop(void)391 void pop(void) 392 { 393 BOOST_ASSERT(!empty()); 394 395 node_pointer element = top_element; 396 roots.erase(node_list_type::s_iterator_to(*element)); 397 398 finish_erase_or_pop(element); 399 } 400 401 /** 402 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 403 * 404 * \b Complexity: Logarithmic if current value < v, Constant otherwise. 405 * 406 * */ update(handle_type handle,const_reference v)407 void update (handle_type handle, const_reference v) 408 { 409 if (super_t::operator()(super_t::get_value(handle.node_->value), v)) 410 increase(handle, v); 411 else 412 decrease(handle, v); 413 } 414 415 /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference) 416 * 417 * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates 418 * the iterator to the object referred to by the handle. 419 * */ update_lazy(handle_type handle,const_reference v)420 void update_lazy(handle_type handle, const_reference v) 421 { 422 handle.node_->value = super_t::make_node(v); 423 update_lazy(handle); 424 } 425 426 /** 427 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 428 * 429 * \b Complexity: Logarithmic. 430 * 431 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 432 * */ update(handle_type handle)433 void update (handle_type handle) 434 { 435 update_lazy(handle); 436 consolidate(); 437 } 438 439 /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle) 440 * 441 * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates 442 * the iterator to the object referred to by the handle. 443 * */ update_lazy(handle_type handle)444 void update_lazy (handle_type handle) 445 { 446 node_pointer n = handle.node_; 447 node_pointer parent = n->get_parent(); 448 449 if (parent) { 450 n->parent = NULL; 451 roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n)); 452 } 453 add_children_to_root(n); 454 455 if (super_t::operator()(top_element->value, n->value)) 456 top_element = n; 457 } 458 459 460 /** 461 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 462 * 463 * \b Complexity: Constant. 464 * 465 * \b Note: The new value is expected to be greater than the current one 466 * */ increase(handle_type handle,const_reference v)467 void increase (handle_type handle, const_reference v) 468 { 469 handle.node_->value = super_t::make_node(v); 470 increase(handle); 471 } 472 473 /** 474 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 475 * 476 * \b Complexity: Constant. 477 * 478 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 479 * */ increase(handle_type handle)480 void increase (handle_type handle) 481 { 482 node_pointer n = handle.node_; 483 484 if (n->parent) { 485 if (super_t::operator()(n->get_parent()->value, n->value)) { 486 node_pointer parent = n->get_parent(); 487 cut(n); 488 cascading_cut(parent); 489 } 490 } 491 492 if (super_t::operator()(top_element->value, n->value)) { 493 top_element = n; 494 return; 495 } 496 } 497 498 /** 499 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 500 * 501 * \b Complexity: Logarithmic. 502 * 503 * \b Note: The new value is expected to be less than the current one 504 * */ decrease(handle_type handle,const_reference v)505 void decrease (handle_type handle, const_reference v) 506 { 507 handle.node_->value = super_t::make_node(v); 508 decrease(handle); 509 } 510 511 /** 512 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 513 * 514 * \b Complexity: Logarithmic. 515 * 516 * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 517 * */ decrease(handle_type handle)518 void decrease (handle_type handle) 519 { 520 update(handle); 521 } 522 523 /** 524 * \b Effects: Removes the element handled by \c handle from the priority_queue. 525 * 526 * \b Complexity: Logarithmic. 527 * */ erase(handle_type const & handle)528 void erase(handle_type const & handle) 529 { 530 node_pointer element = handle.node_; 531 node_pointer parent = element->get_parent(); 532 533 if (parent) 534 parent->children.erase(node_list_type::s_iterator_to(*element)); 535 else 536 roots.erase(node_list_type::s_iterator_to(*element)); 537 538 finish_erase_or_pop(element); 539 } 540 541 /// \copydoc boost::heap::priority_queue::begin begin(void) const542 iterator begin(void) const 543 { 544 return iterator(roots.begin()); 545 } 546 547 /// \copydoc boost::heap::priority_queue::end end(void) const548 iterator end(void) const 549 { 550 return iterator(roots.end()); 551 } 552 553 554 /** 555 * \b Effects: Returns an ordered iterator to the first element contained in the priority queue. 556 * 557 * \b Note: Ordered iterators traverse the priority queue in heap order. 558 * */ ordered_begin(void) const559 ordered_iterator ordered_begin(void) const 560 { 561 return ordered_iterator(roots.begin(), roots.end(), top_element, super_t::value_comp()); 562 } 563 564 /** 565 * \b Effects: Returns an ordered iterator to the end of the priority queue. 566 * 567 * \b Note: Ordered iterators traverse the priority queue in heap order. 568 * */ ordered_end(void) const569 ordered_iterator ordered_end(void) const 570 { 571 return ordered_iterator(NULL, super_t::value_comp()); 572 } 573 574 /** 575 * \b Effects: Merge with priority queue rhs. 576 * 577 * \b Complexity: Constant. 578 * 579 * */ merge(fibonacci_heap & rhs)580 void merge(fibonacci_heap & rhs) 581 { 582 size_holder::add(rhs.get_size()); 583 584 if (!top_element || 585 (rhs.top_element && super_t::operator()(top_element->value, rhs.top_element->value))) 586 top_element = rhs.top_element; 587 588 roots.splice(roots.end(), rhs.roots); 589 590 rhs.top_element = NULL; 591 rhs.set_size(0); 592 593 super_t::set_stability_count((std::max)(super_t::get_stability_count(), 594 rhs.get_stability_count())); 595 rhs.set_stability_count(0); 596 } 597 598 /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator s_handle_from_iterator(iterator const & it)599 static handle_type s_handle_from_iterator(iterator const & it) 600 { 601 node * ptr = const_cast<node *>(it.get_node()); 602 return handle_type(ptr); 603 } 604 605 /// \copydoc boost::heap::priority_queue::value_comp value_comp(void) const606 value_compare const & value_comp(void) const 607 { 608 return super_t::value_comp(); 609 } 610 611 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const 612 template <typename HeapType> operator <(HeapType const & rhs) const613 bool operator<(HeapType const & rhs) const 614 { 615 return detail::heap_compare(*this, rhs); 616 } 617 618 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const 619 template <typename HeapType> operator >(HeapType const & rhs) const620 bool operator>(HeapType const & rhs) const 621 { 622 return detail::heap_compare(rhs, *this); 623 } 624 625 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const 626 template <typename HeapType> operator >=(HeapType const & rhs) const627 bool operator>=(HeapType const & rhs) const 628 { 629 return !operator<(rhs); 630 } 631 632 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const 633 template <typename HeapType> operator <=(HeapType const & rhs) const634 bool operator<=(HeapType const & rhs) const 635 { 636 return !operator>(rhs); 637 } 638 639 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const 640 template <typename HeapType> operator ==(HeapType const & rhs) const641 bool operator==(HeapType const & rhs) const 642 { 643 return detail::heap_equality(*this, rhs); 644 } 645 646 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const 647 template <typename HeapType> operator !=(HeapType const & rhs) const648 bool operator!=(HeapType const & rhs) const 649 { 650 return !(*this == rhs); 651 } 652 653 private: 654 #if !defined(BOOST_DOXYGEN_INVOKED) clone_forest(fibonacci_heap const & rhs)655 void clone_forest(fibonacci_heap const & rhs) 656 { 657 BOOST_HEAP_ASSERT(roots.empty()); 658 typedef typename node::template node_cloner<allocator_type> node_cloner; 659 roots.clone_from(rhs.roots, node_cloner(*this, NULL), detail::nop_disposer()); 660 661 top_element = detail::find_max_child<node_list_type, node, internal_compare>(roots, super_t::get_internal_cmp()); 662 } 663 cut(node_pointer n)664 void cut(node_pointer n) 665 { 666 node_pointer parent = n->get_parent(); 667 roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n)); 668 n->parent = 0; 669 n->mark = false; 670 } 671 cascading_cut(node_pointer n)672 void cascading_cut(node_pointer n) 673 { 674 node_pointer parent = n->get_parent(); 675 676 if (parent) { 677 if (!parent->mark) 678 parent->mark = true; 679 else { 680 cut(n); 681 cascading_cut(parent); 682 } 683 } 684 } 685 add_children_to_root(node_pointer n)686 void add_children_to_root(node_pointer n) 687 { 688 for (node_list_iterator it = n->children.begin(); it != n->children.end(); ++it) { 689 node_pointer child = static_cast<node_pointer>(&*it); 690 child->parent = 0; 691 } 692 693 roots.splice(roots.end(), n->children); 694 } 695 consolidate(void)696 void consolidate(void) 697 { 698 if (roots.empty()) 699 return; 700 701 static const size_type max_log2 = sizeof(size_type) * 8; 702 boost::array<node_pointer, max_log2> aux; 703 aux.assign(NULL); 704 705 node_list_iterator it = roots.begin(); 706 top_element = static_cast<node_pointer>(&*it); 707 708 do { 709 node_pointer n = static_cast<node_pointer>(&*it); 710 ++it; 711 size_type node_rank = n->child_count(); 712 713 if (aux[node_rank] == NULL) 714 aux[node_rank] = n; 715 else { 716 do { 717 node_pointer other = aux[node_rank]; 718 if (super_t::operator()(n->value, other->value)) 719 std::swap(n, other); 720 721 if (other->parent) 722 n->children.splice(n->children.end(), other->parent->children, node_list_type::s_iterator_to(*other)); 723 else 724 n->children.splice(n->children.end(), roots, node_list_type::s_iterator_to(*other)); 725 726 other->parent = n; 727 728 aux[node_rank] = NULL; 729 node_rank = n->child_count(); 730 } while (aux[node_rank] != NULL); 731 aux[node_rank] = n; 732 } 733 734 if (!super_t::operator()(n->value, top_element->value)) 735 top_element = n; 736 } 737 while (it != roots.end()); 738 } 739 finish_erase_or_pop(node_pointer erased_node)740 void finish_erase_or_pop(node_pointer erased_node) 741 { 742 add_children_to_root(erased_node); 743 744 erased_node->~node(); 745 allocator_type::deallocate(erased_node, 1); 746 747 size_holder::decrement(); 748 if (!empty()) 749 consolidate(); 750 else 751 top_element = NULL; 752 } 753 754 mutable node_pointer top_element; 755 node_list_type roots; 756 #endif 757 }; 758 759 } /* namespace heap */ 760 } /* namespace boost */ 761 762 #undef BOOST_HEAP_ASSERT 763 764 #endif /* BOOST_HEAP_FIBONACCI_HEAP_HPP */ 765