1 // boost heap: skew 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_SKEW_HEAP_HPP 10 #define BOOST_HEAP_SKEW_HEAP_HPP 11 12 #include <algorithm> 13 #include <utility> 14 #include <vector> 15 16 #include <boost/assert.hpp> 17 #include <boost/array.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 #ifndef BOOST_DOXYGEN_INVOKED 29 #ifdef BOOST_HEAP_SANITYCHECKS 30 #define BOOST_HEAP_ASSERT BOOST_ASSERT 31 #else 32 #define BOOST_HEAP_ASSERT(expression) 33 #endif 34 #endif 35 36 namespace boost { 37 namespace heap { 38 namespace detail { 39 40 template <typename node_pointer, bool store_parent_pointer> 41 struct parent_holder 42 { parent_holderboost::heap::detail::parent_holder43 parent_holder(void): 44 parent_(NULL) 45 {} 46 set_parentboost::heap::detail::parent_holder47 void set_parent(node_pointer parent) 48 { 49 BOOST_HEAP_ASSERT(static_cast<node_pointer>(this) != parent); 50 parent_ = parent; 51 } 52 get_parentboost::heap::detail::parent_holder53 node_pointer get_parent(void) const 54 { 55 return parent_; 56 } 57 58 node_pointer parent_; 59 }; 60 61 template <typename node_pointer> 62 struct parent_holder<node_pointer, false> 63 { set_parentboost::heap::detail::parent_holder64 void set_parent(node_pointer parent) 65 {} 66 get_parentboost::heap::detail::parent_holder67 node_pointer get_parent(void) const 68 { 69 return NULL; 70 } 71 }; 72 73 74 template <typename value_type, bool store_parent_pointer> 75 struct skew_heap_node: 76 parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer> 77 { 78 typedef parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer> super_t; 79 80 typedef boost::array<skew_heap_node*, 2> child_list_type; 81 typedef typename child_list_type::iterator child_iterator; 82 typedef typename child_list_type::const_iterator const_child_iterator; 83 skew_heap_nodeboost::heap::detail::skew_heap_node84 skew_heap_node(value_type const & v): 85 value(v) 86 { 87 children.assign(0); 88 } 89 90 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES skew_heap_nodeboost::heap::detail::skew_heap_node91 skew_heap_node(value_type && v): 92 value(v) 93 { 94 children.assign(0); 95 } 96 #endif 97 98 template <typename Alloc> skew_heap_nodeboost::heap::detail::skew_heap_node99 skew_heap_node (skew_heap_node const & rhs, Alloc & allocator, skew_heap_node * parent): 100 value(rhs.value) 101 { 102 super_t::set_parent(parent); 103 node_cloner<skew_heap_node, skew_heap_node, Alloc> cloner(allocator); 104 clone_child(0, rhs, cloner); 105 clone_child(1, rhs, cloner); 106 } 107 108 template <typename Cloner> clone_childboost::heap::detail::skew_heap_node109 void clone_child(int index, skew_heap_node const & rhs, Cloner & cloner) 110 { 111 if (rhs.children[index]) 112 children[index] = cloner(*rhs.children[index], this); 113 else 114 children[index] = NULL; 115 } 116 117 template <typename Alloc> clear_subtreeboost::heap::detail::skew_heap_node118 void clear_subtree(Alloc & alloc) 119 { 120 node_disposer<skew_heap_node, skew_heap_node, Alloc> disposer(alloc); 121 dispose_child(children[0], disposer); 122 dispose_child(children[1], disposer); 123 } 124 125 template <typename Disposer> dispose_childboost::heap::detail::skew_heap_node126 void dispose_child(skew_heap_node * node, Disposer & disposer) 127 { 128 if (node) 129 disposer(node); 130 } 131 count_childrenboost::heap::detail::skew_heap_node132 std::size_t count_children(void) const 133 { 134 size_t ret = 1; 135 if (children[0]) 136 ret += children[0]->count_children(); 137 if (children[1]) 138 ret += children[1]->count_children(); 139 140 return ret; 141 } 142 143 template <typename HeapBase> is_heapboost::heap::detail::skew_heap_node144 bool is_heap(typename HeapBase::value_compare const & cmp) const 145 { 146 for (const_child_iterator it = children.begin(); it != children.end(); ++it) { 147 const skew_heap_node * child = *it; 148 149 if (child == NULL) 150 continue; 151 152 if (store_parent_pointer) 153 BOOST_HEAP_ASSERT(child->get_parent() == this); 154 155 if (cmp(HeapBase::get_value(value), HeapBase::get_value(child->value)) || 156 !child->is_heap<HeapBase>(cmp)) 157 return false; 158 } 159 return true; 160 } 161 162 value_type value; 163 boost::array<skew_heap_node*, 2> children; 164 }; 165 166 167 typedef parameter::parameters<boost::parameter::optional<tag::allocator>, 168 boost::parameter::optional<tag::compare>, 169 boost::parameter::optional<tag::stable>, 170 boost::parameter::optional<tag::store_parent_pointer>, 171 boost::parameter::optional<tag::stability_counter_type>, 172 boost::parameter::optional<tag::constant_time_size>, 173 boost::parameter::optional<tag::mutable_> 174 > skew_heap_signature; 175 176 template <typename T, typename BoundArgs> 177 struct make_skew_heap_base 178 { 179 static const bool constant_time_size = parameter::binding<BoundArgs, 180 tag::constant_time_size, 181 boost::mpl::true_ 182 >::type::value; 183 184 typedef typename make_heap_base<T, BoundArgs, constant_time_size>::type base_type; 185 typedef typename make_heap_base<T, BoundArgs, constant_time_size>::allocator_argument allocator_argument; 186 typedef typename make_heap_base<T, BoundArgs, constant_time_size>::compare_argument compare_argument; 187 188 static const bool is_mutable = extract_mutable<BoundArgs>::value; 189 static const bool store_parent_pointer = parameter::binding<BoundArgs, 190 tag::store_parent_pointer, 191 boost::mpl::false_>::type::value || is_mutable; 192 193 typedef skew_heap_node<typename base_type::internal_type, store_parent_pointer> node_type; 194 195 typedef typename allocator_argument::template rebind<node_type>::other allocator_type; 196 197 struct type: 198 base_type, 199 allocator_type 200 { typeboost::heap::detail::make_skew_heap_base::type201 type(compare_argument const & arg): 202 base_type(arg) 203 {} 204 205 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES typeboost::heap::detail::make_skew_heap_base::type206 type(type && rhs): 207 base_type(std::move(static_cast<base_type&>(rhs))), 208 allocator_type(std::move(static_cast<allocator_type&>(rhs))) 209 {} 210 typeboost::heap::detail::make_skew_heap_base::type211 type(type const & rhs): 212 base_type(rhs), 213 allocator_type(rhs) 214 {} 215 operator =boost::heap::detail::make_skew_heap_base::type216 type & operator=(type && rhs) 217 { 218 base_type::operator=(std::move(static_cast<base_type&>(rhs))); 219 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs))); 220 return *this; 221 } 222 operator =boost::heap::detail::make_skew_heap_base::type223 type & operator=(type const & rhs) 224 { 225 base_type::operator=(static_cast<base_type const &>(rhs)); 226 allocator_type::operator=(static_cast<allocator_type const &>(rhs)); 227 return *this; 228 } 229 #endif 230 }; 231 }; 232 233 } /* namespace detail */ 234 235 /** 236 * \class skew_heap 237 * \brief skew heap 238 * 239 * 240 * The template parameter T is the type to be managed by the container. 241 * The user can specify additional options and if no options are provided default options are used. 242 * 243 * The container supports the following options: 244 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > 245 * - \c boost::heap::stable<>, defaults to \c stable<false> 246 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> 247 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > 248 * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true> 249 * - \c boost::heap::store_parent_pointer<>, defaults to \c store_parent_pointer<true>. Maintaining a parent pointer adds some 250 * maintenance and size overhead, but iterating a heap is more efficient. 251 * - \c boost::heap::mutable<>, defaults to \c mutable<false>. 252 * 253 */ 254 #ifdef BOOST_DOXYGEN_INVOKED 255 template<class T, class ...Options> 256 #else 257 template <typename T, 258 class A0 = boost::parameter::void_, 259 class A1 = boost::parameter::void_, 260 class A2 = boost::parameter::void_, 261 class A3 = boost::parameter::void_, 262 class A4 = boost::parameter::void_, 263 class A5 = boost::parameter::void_, 264 class A6 = boost::parameter::void_ 265 > 266 #endif 267 class skew_heap: 268 private detail::make_skew_heap_base<T, 269 typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type 270 >::type 271 { 272 typedef typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type bound_args; 273 typedef detail::make_skew_heap_base<T, bound_args> base_maker; 274 typedef typename base_maker::type super_t; 275 276 typedef typename super_t::internal_type internal_type; 277 typedef typename super_t::size_holder_type size_holder; 278 typedef typename base_maker::allocator_argument allocator_argument; 279 280 static const bool store_parent_pointer = base_maker::store_parent_pointer; 281 template <typename Heap1, typename Heap2> 282 friend struct heap_merge_emulate; 283 284 struct implementation_defined: 285 detail::extract_allocator_types<typename base_maker::allocator_argument> 286 { 287 typedef T value_type; 288 289 typedef typename base_maker::compare_argument value_compare; 290 typedef typename base_maker::allocator_type allocator_type; 291 292 typedef typename base_maker::node_type node; 293 typedef typename allocator_type::pointer node_pointer; 294 typedef typename allocator_type::const_pointer const_node_pointer; 295 296 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor; 297 298 typedef boost::array<node_pointer, 2> child_list_type; 299 typedef typename child_list_type::iterator child_list_iterator; 300 301 typedef typename boost::mpl::if_c<false, 302 detail::recursive_tree_iterator<node, 303 child_list_iterator, 304 const value_type, 305 value_extractor, 306 detail::list_iterator_converter<node, 307 child_list_type 308 > 309 >, 310 detail::tree_iterator<node, 311 const value_type, 312 allocator_type, 313 value_extractor, 314 detail::dereferencer<node>, 315 true, 316 false, 317 value_compare 318 > 319 >::type iterator; 320 321 typedef iterator const_iterator; 322 323 typedef detail::tree_iterator<node, 324 const value_type, 325 allocator_type, 326 value_extractor, 327 detail::dereferencer<node>, 328 true, 329 true, 330 value_compare 331 > ordered_iterator; 332 333 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference; 334 typedef detail::node_handle<node_pointer, super_t, reference> handle_type; 335 }; 336 337 typedef typename implementation_defined::value_extractor value_extractor; 338 typedef typename implementation_defined::node node; 339 typedef typename implementation_defined::node_pointer node_pointer; 340 341 public: 342 typedef T value_type; 343 344 typedef typename implementation_defined::size_type size_type; 345 typedef typename implementation_defined::difference_type difference_type; 346 typedef typename implementation_defined::value_compare value_compare; 347 typedef typename implementation_defined::allocator_type allocator_type; 348 typedef typename implementation_defined::reference reference; 349 typedef typename implementation_defined::const_reference const_reference; 350 typedef typename implementation_defined::pointer pointer; 351 typedef typename implementation_defined::const_pointer const_pointer; 352 353 /// \copydoc boost::heap::priority_queue::iterator 354 typedef typename implementation_defined::iterator iterator; 355 typedef typename implementation_defined::const_iterator const_iterator; 356 typedef typename implementation_defined::ordered_iterator ordered_iterator; 357 358 static const bool constant_time_size = super_t::constant_time_size; 359 static const bool has_ordered_iterators = true; 360 static const bool is_mergable = true; 361 static const bool is_stable = detail::extract_stable<bound_args>::value; 362 static const bool has_reserve = false; 363 static const bool is_mutable = detail::extract_mutable<bound_args>::value; 364 365 typedef typename mpl::if_c<is_mutable, typename implementation_defined::handle_type, void*>::type handle_type; 366 367 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) skew_heap(value_compare const & cmp=value_compare ())368 explicit skew_heap(value_compare const & cmp = value_compare()): 369 super_t(cmp), root(NULL) 370 {} 371 372 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) skew_heap(skew_heap const & rhs)373 skew_heap(skew_heap const & rhs): 374 super_t(rhs), root(0) 375 { 376 if (rhs.empty()) 377 return; 378 379 clone_tree(rhs); 380 size_holder::set_size(rhs.get_size()); 381 } 382 383 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs) operator =(skew_heap const & rhs)384 skew_heap & operator=(skew_heap const & rhs) 385 { 386 clear(); 387 size_holder::set_size(rhs.get_size()); 388 static_cast<super_t&>(*this) = rhs; 389 390 clone_tree(rhs); 391 return *this; 392 } 393 394 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES 395 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) skew_heap(skew_heap && rhs)396 skew_heap(skew_heap && rhs): 397 super_t(std::move(rhs)), root(rhs.root) 398 { 399 rhs.root = NULL; 400 } 401 402 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) operator =(skew_heap && rhs)403 skew_heap & operator=(skew_heap && rhs) 404 { 405 super_t::operator=(std::move(rhs)); 406 root = rhs.root; 407 rhs.root = NULL; 408 return *this; 409 } 410 #endif 411 ~skew_heap(void)412 ~skew_heap(void) 413 { 414 clear(); 415 } 416 417 /** 418 * \b Effects: Adds a new element to the priority queue. 419 * 420 * \b Complexity: Logarithmic (amortized). 421 * 422 * */ push(value_type const & v)423 typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v) 424 { 425 typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper; 426 return push_helper::push(this, v); 427 } 428 429 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 430 /** 431 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. 432 * 433 * \b Complexity: Logarithmic (amortized). 434 * 435 * */ 436 template <typename... Args> emplace(Args &&...args)437 typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args) 438 { 439 typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper; 440 return push_helper::emplace(this, std::forward<Args>(args)...); 441 } 442 #endif 443 444 /// \copydoc boost::heap::priority_queue::empty empty(void) const445 bool empty(void) const 446 { 447 return root == NULL; 448 } 449 450 /// \copydoc boost::heap::binomial_heap::size size(void) const451 size_type size(void) const 452 { 453 if (constant_time_size) 454 return size_holder::get_size(); 455 456 if (root == NULL) 457 return 0; 458 else 459 return root->count_children(); 460 } 461 462 /// \copydoc boost::heap::priority_queue::max_size max_size(void) const463 size_type max_size(void) const 464 { 465 return allocator_type::max_size(); 466 } 467 468 /// \copydoc boost::heap::priority_queue::clear clear(void)469 void clear(void) 470 { 471 if (empty()) 472 return; 473 474 root->template clear_subtree<allocator_type>(*this); 475 root->~node(); 476 allocator_type::deallocate(root, 1); 477 478 root = NULL; 479 size_holder::set_size(0); 480 } 481 482 /// \copydoc boost::heap::priority_queue::get_allocator get_allocator(void) const483 allocator_type get_allocator(void) const 484 { 485 return *this; 486 } 487 488 /// \copydoc boost::heap::priority_queue::swap swap(skew_heap & rhs)489 void swap(skew_heap & rhs) 490 { 491 super_t::swap(rhs); 492 std::swap(root, rhs.root); 493 } 494 495 /// \copydoc boost::heap::priority_queue::top top(void) const496 const_reference top(void) const 497 { 498 BOOST_ASSERT(!empty()); 499 500 return super_t::get_value(root->value); 501 } 502 503 /** 504 * \b Effects: Removes the top element from the priority queue. 505 * 506 * \b Complexity: Logarithmic (amortized). 507 * 508 * */ pop(void)509 void pop(void) 510 { 511 BOOST_ASSERT(!empty()); 512 513 node_pointer top = root; 514 515 root = merge_children(root); 516 size_holder::decrement(); 517 518 if (root) 519 BOOST_HEAP_ASSERT(root->get_parent() == NULL); 520 else 521 BOOST_HEAP_ASSERT(size_holder::get_size() == 0); 522 523 top->~node(); 524 allocator_type::deallocate(top, 1); 525 sanity_check(); 526 } 527 528 /// \copydoc boost::heap::priority_queue::begin begin(void) const529 iterator begin(void) const 530 { 531 return iterator(root, super_t::value_comp()); 532 } 533 534 /// \copydoc boost::heap::priority_queue::end end(void) const535 iterator end(void) const 536 { 537 return iterator(); 538 } 539 540 /// \copydoc boost::heap::fibonacci_heap::ordered_begin ordered_begin(void) const541 ordered_iterator ordered_begin(void) const 542 { 543 return ordered_iterator(root, super_t::value_comp()); 544 } 545 546 /// \copydoc boost::heap::fibonacci_heap::ordered_begin ordered_end(void) const547 ordered_iterator ordered_end(void) const 548 { 549 return ordered_iterator(0, super_t::value_comp()); 550 } 551 552 /** 553 * \b Effects: Merge all elements from rhs into this 554 * 555 * \b Complexity: Logarithmic (amortized). 556 * 557 * */ merge(skew_heap & rhs)558 void merge(skew_heap & rhs) 559 { 560 if (rhs.empty()) 561 return; 562 563 merge_node(rhs.root); 564 565 size_holder::add(rhs.get_size()); 566 rhs.set_size(0); 567 rhs.root = NULL; 568 sanity_check(); 569 570 super_t::set_stability_count((std::max)(super_t::get_stability_count(), 571 rhs.get_stability_count())); 572 rhs.set_stability_count(0); 573 } 574 575 /// \copydoc boost::heap::priority_queue::value_comp value_comp(void) const576 value_compare const & value_comp(void) const 577 { 578 return super_t::value_comp(); 579 } 580 581 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const 582 template <typename HeapType> operator <(HeapType const & rhs) const583 bool operator<(HeapType const & rhs) const 584 { 585 return detail::heap_compare(*this, rhs); 586 } 587 588 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const 589 template <typename HeapType> operator >(HeapType const & rhs) const590 bool operator>(HeapType const & rhs) const 591 { 592 return detail::heap_compare(rhs, *this); 593 } 594 595 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const 596 template <typename HeapType> operator >=(HeapType const & rhs) const597 bool operator>=(HeapType const & rhs) const 598 { 599 return !operator<(rhs); 600 } 601 602 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const 603 template <typename HeapType> operator <=(HeapType const & rhs) const604 bool operator<=(HeapType const & rhs) const 605 { 606 return !operator>(rhs); 607 } 608 609 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const 610 template <typename HeapType> operator ==(HeapType const & rhs) const611 bool operator==(HeapType const & rhs) const 612 { 613 return detail::heap_equality(*this, rhs); 614 } 615 616 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const 617 template <typename HeapType> operator !=(HeapType const & rhs) const618 bool operator!=(HeapType const & rhs) const 619 { 620 return !(*this == rhs); 621 } 622 623 624 /// \copydoc boost::heap::d_ary_heap::s_handle_from_iterator s_handle_from_iterator(iterator const & it)625 static handle_type s_handle_from_iterator(iterator const & it) 626 { 627 node * ptr = const_cast<node *>(it.get_node()); 628 return handle_type(ptr); 629 } 630 631 /** 632 * \b Effects: Removes the element handled by \c handle from the priority_queue. 633 * 634 * \b Complexity: Logarithmic (amortized). 635 * */ erase(handle_type object)636 void erase (handle_type object) 637 { 638 BOOST_STATIC_ASSERT(is_mutable); 639 node_pointer this_node = object.node_; 640 641 unlink_node(this_node); 642 size_holder::decrement(); 643 644 sanity_check(); 645 this_node->~node(); 646 allocator_type::deallocate(this_node, 1); 647 } 648 649 /** 650 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 651 * 652 * \b Complexity: Logarithmic (amortized). 653 * 654 * */ update(handle_type handle,const_reference v)655 void update (handle_type handle, const_reference v) 656 { 657 BOOST_STATIC_ASSERT(is_mutable); 658 if (super_t::operator()(super_t::get_value(handle.node_->value), v)) 659 increase(handle, v); 660 else 661 decrease(handle, v); 662 } 663 664 /** 665 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 666 * 667 * \b Complexity: Logarithmic (amortized). 668 * 669 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 670 * */ update(handle_type handle)671 void update (handle_type handle) 672 { 673 BOOST_STATIC_ASSERT(is_mutable); 674 node_pointer this_node = handle.node_; 675 676 if (this_node->get_parent()) { 677 if (super_t::operator()(super_t::get_value(this_node->get_parent()->value), 678 super_t::get_value(this_node->value))) 679 increase(handle); 680 else 681 decrease(handle); 682 } 683 else 684 decrease(handle); 685 } 686 687 /** 688 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 689 * 690 * \b Complexity: Logarithmic (amortized). 691 * 692 * \b Note: The new value is expected to be greater than the current one 693 * */ increase(handle_type handle,const_reference v)694 void increase (handle_type handle, const_reference v) 695 { 696 BOOST_STATIC_ASSERT(is_mutable); 697 handle.node_->value = super_t::make_node(v); 698 increase(handle); 699 } 700 701 /** 702 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 703 * 704 * \b Complexity: Logarithmic (amortized). 705 * 706 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 707 * */ increase(handle_type handle)708 void increase (handle_type handle) 709 { 710 BOOST_STATIC_ASSERT(is_mutable); 711 node_pointer this_node = handle.node_; 712 713 if (this_node == root) 714 return; 715 716 node_pointer parent = this_node->get_parent(); 717 718 if (this_node == parent->children[0]) 719 parent->children[0] = NULL; 720 else 721 parent->children[1] = NULL; 722 723 this_node->set_parent(NULL); 724 merge_node(this_node); 725 } 726 727 /** 728 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 729 * 730 * \b Complexity: Logarithmic (amortized). 731 * 732 * \b Note: The new value is expected to be less than the current one 733 * */ decrease(handle_type handle,const_reference v)734 void decrease (handle_type handle, const_reference v) 735 { 736 BOOST_STATIC_ASSERT(is_mutable); 737 handle.node_->value = super_t::make_node(v); 738 decrease(handle); 739 } 740 741 /** 742 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 743 * 744 * \b Complexity: Logarithmic (amortized). 745 * 746 * \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! 747 * */ decrease(handle_type handle)748 void decrease (handle_type handle) 749 { 750 BOOST_STATIC_ASSERT(is_mutable); 751 node_pointer this_node = handle.node_; 752 753 unlink_node(this_node); 754 this_node->children.assign(0); 755 this_node->set_parent(NULL); 756 merge_node(this_node); 757 } 758 759 private: 760 #if !defined(BOOST_DOXYGEN_INVOKED) 761 struct push_void 762 { pushboost::heap::skew_heap::push_void763 static void push(skew_heap * self, const_reference v) 764 { 765 self->push_internal(v); 766 } 767 768 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 769 template <class... Args> emplaceboost::heap::skew_heap::push_void770 static void emplace(skew_heap * self, Args&&... args) 771 { 772 self->emplace_internal(std::forward<Args>(args)...); 773 } 774 #endif 775 }; 776 777 struct push_handle 778 { pushboost::heap::skew_heap::push_handle779 static handle_type push(skew_heap * self, const_reference v) 780 { 781 return handle_type(self->push_internal(v)); 782 } 783 784 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 785 template <class... Args> emplaceboost::heap::skew_heap::push_handle786 static handle_type emplace(skew_heap * self, Args&&... args) 787 { 788 return handle_type(self->emplace_internal(std::forward<Args>(args)...)); 789 } 790 #endif 791 }; 792 push_internal(const_reference v)793 node_pointer push_internal(const_reference v) 794 { 795 size_holder::increment(); 796 797 node_pointer n = super_t::allocate(1); 798 new(n) node(super_t::make_node(v)); 799 800 merge_node(n); 801 return n; 802 } 803 804 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 805 template <class... Args> emplace_internal(Args &&...args)806 node_pointer emplace_internal(Args&&... args) 807 { 808 size_holder::increment(); 809 810 node_pointer n = super_t::allocate(1); 811 new(n) node(super_t::make_node(std::forward<Args>(args)...)); 812 813 merge_node(n); 814 return n; 815 } 816 #endif 817 unlink_node(node_pointer node)818 void unlink_node(node_pointer node) 819 { 820 node_pointer parent = node->get_parent(); 821 node_pointer merged_children = merge_children(node); 822 823 if (parent) { 824 if (node == parent->children[0]) 825 parent->children[0] = merged_children; 826 else 827 parent->children[1] = merged_children; 828 } 829 else 830 root = merged_children; 831 } 832 clone_tree(skew_heap const & rhs)833 void clone_tree(skew_heap const & rhs) 834 { 835 BOOST_HEAP_ASSERT(root == NULL); 836 if (rhs.empty()) 837 return; 838 839 root = allocator_type::allocate(1); 840 841 new(root) node(*rhs.root, static_cast<allocator_type&>(*this), NULL); 842 } 843 merge_node(node_pointer other)844 void merge_node(node_pointer other) 845 { 846 BOOST_HEAP_ASSERT(other); 847 if (root != NULL) 848 root = merge_nodes(root, other, NULL); 849 else 850 root = other; 851 } 852 merge_nodes(node_pointer node1,node_pointer node2,node_pointer new_parent)853 node_pointer merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent) 854 { 855 if (node1 == NULL) { 856 if (node2) 857 node2->set_parent(new_parent); 858 return node2; 859 } 860 if (node2 == NULL) { 861 node1->set_parent(new_parent); 862 return node1; 863 } 864 865 node_pointer merged = merge_nodes_recursive(node1, node2, new_parent); 866 return merged; 867 } 868 merge_children(node_pointer node)869 node_pointer merge_children(node_pointer node) 870 { 871 node_pointer parent = node->get_parent(); 872 node_pointer merged_children = merge_nodes(node->children[0], node->children[1], parent); 873 874 return merged_children; 875 } 876 merge_nodes_recursive(node_pointer node1,node_pointer node2,node_pointer new_parent)877 node_pointer merge_nodes_recursive(node_pointer node1, node_pointer node2, node_pointer new_parent) 878 { 879 if (super_t::operator()(node1->value, node2->value)) 880 std::swap(node1, node2); 881 882 node * parent = node1; 883 node * child = node2; 884 885 if (parent->children[1]) { 886 node * merged = merge_nodes(parent->children[1], child, parent); 887 parent->children[1] = merged; 888 merged->set_parent(parent); 889 } else { 890 parent->children[1] = child; 891 child->set_parent(parent); 892 } 893 894 895 std::swap(parent->children[0], parent->children[1]); 896 parent->set_parent(new_parent); 897 return parent; 898 } 899 sanity_check(void)900 void sanity_check(void) 901 { 902 #ifdef BOOST_HEAP_SANITYCHECKS 903 if (root) 904 BOOST_HEAP_ASSERT( root->template is_heap<super_t>(super_t::value_comp()) ); 905 906 if (constant_time_size) { 907 size_type stored_size = size_holder::get_size(); 908 909 size_type counted_size; 910 if (root == NULL) 911 counted_size = 0; 912 else 913 counted_size = root->count_children(); 914 915 BOOST_HEAP_ASSERT(counted_size == stored_size); 916 } 917 #endif 918 } 919 920 node_pointer root; 921 #endif 922 }; 923 924 } /* namespace heap */ 925 } /* namespace boost */ 926 927 #undef BOOST_HEAP_ASSERT 928 #endif /* BOOST_HEAP_SKEW_HEAP_HPP */ 929