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