1 // boost heap: pairing 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_PAIRING_HEAP_HPP 10 #define BOOST_HEAP_PAIRING_HEAP_HPP 11 12 #include <algorithm> 13 #include <utility> 14 #include <vector> 15 16 #include <boost/assert.hpp> 17 18 #include <boost/heap/detail/heap_comparison.hpp> 19 #include <boost/heap/detail/heap_node.hpp> 20 #include <boost/heap/policies.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 > pairing_heap_signature; 47 48 template <typename T, typename Parspec> 49 struct make_pairing_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 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type; 56 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument; 57 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument; 58 59 typedef heap_node<typename base_type::internal_type, false> 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_pairing_heap_base::type67 type(compare_argument const & arg): 68 base_type(arg) 69 {} 70 71 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES typeboost::heap::detail::make_pairing_heap_base::type72 type(type const & rhs): 73 base_type(rhs), allocator_type(rhs) 74 {} 75 typeboost::heap::detail::make_pairing_heap_base::type76 type(type && rhs): 77 base_type(std::move(static_cast<base_type&>(rhs))), 78 allocator_type(std::move(static_cast<allocator_type&>(rhs))) 79 {} 80 operator =boost::heap::detail::make_pairing_heap_base::type81 type & operator=(type && rhs) 82 { 83 base_type::operator=(std::move(static_cast<base_type&>(rhs))); 84 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs))); 85 return *this; 86 } 87 operator =boost::heap::detail::make_pairing_heap_base::type88 type & operator=(type const & rhs) 89 { 90 base_type::operator=(static_cast<base_type const &>(rhs)); 91 allocator_type::operator=(static_cast<const allocator_type&>(rhs)); 92 return *this; 93 } 94 #endif 95 }; 96 }; 97 98 } 99 100 /** 101 * \class pairing_heap 102 * \brief pairing heap 103 * 104 * Pairing heaps are self-adjusting binary heaps. Although design and implementation are rather simple, 105 * the complexity analysis is yet unsolved. For details, consult: 106 * 107 * Pettie, Seth (2005), "Towards a final analysis of pairing heaps", 108 * Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174-183 109 * 110 * The template parameter T is the type to be managed by the container. 111 * The user can specify additional options and if no options are provided default options are used. 112 * 113 * The container supports the following options: 114 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > 115 * - \c boost::heap::stable<>, defaults to \c stable<false> 116 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> 117 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > 118 * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true> 119 * 120 * 121 */ 122 #ifdef BOOST_DOXYGEN_INVOKED 123 template<class T, class ...Options> 124 #else 125 template <typename T, 126 class A0 = boost::parameter::void_, 127 class A1 = boost::parameter::void_, 128 class A2 = boost::parameter::void_, 129 class A3 = boost::parameter::void_, 130 class A4 = boost::parameter::void_ 131 > 132 #endif 133 class pairing_heap: 134 private detail::make_pairing_heap_base<T, 135 typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type 136 >::type 137 { 138 typedef typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args; 139 typedef detail::make_pairing_heap_base<T, bound_args> base_maker; 140 typedef typename base_maker::type super_t; 141 142 typedef typename super_t::internal_type internal_type; 143 typedef typename super_t::size_holder_type size_holder; 144 typedef typename base_maker::allocator_argument allocator_argument; 145 146 private: 147 template <typename Heap1, typename Heap2> 148 friend struct heap_merge_emulate; 149 150 #ifndef BOOST_DOXYGEN_INVOKED 151 struct implementation_defined: 152 detail::extract_allocator_types<typename base_maker::allocator_argument> 153 { 154 typedef T value_type; 155 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type; 156 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference; 157 158 typedef typename base_maker::compare_argument value_compare; 159 typedef typename base_maker::allocator_type allocator_type; 160 161 typedef typename allocator_type::pointer node_pointer; 162 typedef typename allocator_type::const_pointer const_node_pointer; 163 164 typedef detail::heap_node_list node_list_type; 165 typedef typename node_list_type::iterator node_list_iterator; 166 typedef typename node_list_type::const_iterator node_list_const_iterator; 167 168 typedef typename base_maker::node_type node; 169 170 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor; 171 typedef typename super_t::internal_compare internal_compare; 172 typedef detail::node_handle<node_pointer, super_t, reference> handle_type; 173 174 typedef detail::tree_iterator<node, 175 const value_type, 176 allocator_type, 177 value_extractor, 178 detail::pointer_to_reference<node>, 179 false, 180 false, 181 value_compare 182 > iterator; 183 184 typedef iterator const_iterator; 185 186 typedef detail::tree_iterator<node, 187 const value_type, 188 allocator_type, 189 value_extractor, 190 detail::pointer_to_reference<node>, 191 false, 192 true, 193 value_compare 194 > ordered_iterator; 195 }; 196 197 typedef typename implementation_defined::node node; 198 typedef typename implementation_defined::node_pointer node_pointer; 199 typedef typename implementation_defined::node_list_type node_list_type; 200 typedef typename implementation_defined::node_list_iterator node_list_iterator; 201 typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator; 202 typedef typename implementation_defined::internal_compare internal_compare; 203 204 typedef boost::intrusive::list<detail::heap_node_base<true>, 205 boost::intrusive::constant_time_size<false> 206 > node_child_list; 207 #endif 208 209 public: 210 typedef T value_type; 211 212 typedef typename implementation_defined::size_type size_type; 213 typedef typename implementation_defined::difference_type difference_type; 214 typedef typename implementation_defined::value_compare value_compare; 215 typedef typename implementation_defined::allocator_type allocator_type; 216 typedef typename implementation_defined::reference reference; 217 typedef typename implementation_defined::const_reference const_reference; 218 typedef typename implementation_defined::pointer pointer; 219 typedef typename implementation_defined::const_pointer const_pointer; 220 /// \copydoc boost::heap::priority_queue::iterator 221 typedef typename implementation_defined::iterator iterator; 222 typedef typename implementation_defined::const_iterator const_iterator; 223 typedef typename implementation_defined::ordered_iterator ordered_iterator; 224 225 typedef typename implementation_defined::handle_type handle_type; 226 227 static const bool constant_time_size = super_t::constant_time_size; 228 static const bool has_ordered_iterators = true; 229 static const bool is_mergable = true; 230 static const bool is_stable = detail::extract_stable<bound_args>::value; 231 static const bool has_reserve = false; 232 233 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) pairing_heap(value_compare const & cmp=value_compare ())234 explicit pairing_heap(value_compare const & cmp = value_compare()): 235 super_t(cmp), root(NULL) 236 {} 237 238 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) pairing_heap(pairing_heap const & rhs)239 pairing_heap(pairing_heap const & rhs): 240 super_t(rhs), root(NULL) 241 { 242 if (rhs.empty()) 243 return; 244 245 clone_tree(rhs); 246 size_holder::set_size(rhs.get_size()); 247 } 248 249 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES 250 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) pairing_heap(pairing_heap && rhs)251 pairing_heap(pairing_heap && rhs): 252 super_t(std::move(rhs)), root(rhs.root) 253 { 254 rhs.root = NULL; 255 } 256 257 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) operator =(pairing_heap && rhs)258 pairing_heap & operator=(pairing_heap && rhs) 259 { 260 super_t::operator=(std::move(rhs)); 261 root = rhs.root; 262 rhs.root = NULL; 263 return *this; 264 } 265 #endif 266 267 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs) operator =(pairing_heap const & rhs)268 pairing_heap & operator=(pairing_heap const & rhs) 269 { 270 clear(); 271 size_holder::set_size(rhs.get_size()); 272 static_cast<super_t&>(*this) = rhs; 273 274 clone_tree(rhs); 275 return *this; 276 } 277 ~pairing_heap(void)278 ~pairing_heap(void) 279 { 280 while (!empty()) 281 pop(); 282 } 283 284 /// \copydoc boost::heap::priority_queue::empty empty(void) const285 bool empty(void) const 286 { 287 return root == NULL; 288 } 289 290 /// \copydoc boost::heap::binomial_heap::size size(void) const291 size_type size(void) const 292 { 293 if (constant_time_size) 294 return size_holder::get_size(); 295 296 if (root == NULL) 297 return 0; 298 else 299 return detail::count_nodes(root); 300 } 301 302 /// \copydoc boost::heap::priority_queue::max_size max_size(void) const303 size_type max_size(void) const 304 { 305 return allocator_type::max_size(); 306 } 307 308 /// \copydoc boost::heap::priority_queue::clear clear(void)309 void clear(void) 310 { 311 if (empty()) 312 return; 313 314 root->template clear_subtree<allocator_type>(*this); 315 root->~node(); 316 allocator_type::deallocate(root, 1); 317 root = NULL; 318 size_holder::set_size(0); 319 } 320 321 /// \copydoc boost::heap::priority_queue::get_allocator get_allocator(void) const322 allocator_type get_allocator(void) const 323 { 324 return *this; 325 } 326 327 /// \copydoc boost::heap::priority_queue::swap swap(pairing_heap & rhs)328 void swap(pairing_heap & rhs) 329 { 330 super_t::swap(rhs); 331 std::swap(root, rhs.root); 332 } 333 334 335 /// \copydoc boost::heap::priority_queue::top top(void) const336 const_reference top(void) const 337 { 338 BOOST_ASSERT(!empty()); 339 340 return super_t::get_value(root->value); 341 } 342 343 /** 344 * \b Effects: Adds a new element to the priority queue. Returns handle to element 345 * 346 * \cond 347 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 348 * \endcond 349 * 350 * \b Complexity: 2**2*log(log(N)) (amortized). 351 * 352 * */ push(value_type const & v)353 handle_type push(value_type const & v) 354 { 355 size_holder::increment(); 356 357 node_pointer n = allocator_type::allocate(1); 358 359 new(n) node(super_t::make_node(v)); 360 361 merge_node(n); 362 return handle_type(n); 363 } 364 365 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 366 /** 367 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element. 368 * 369 * \cond 370 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 371 * \endcond 372 * 373 * \b Complexity: 2**2*log(log(N)) (amortized). 374 * 375 * */ 376 template <class... Args> emplace(Args &&...args)377 handle_type emplace(Args&&... args) 378 { 379 size_holder::increment(); 380 381 node_pointer n = allocator_type::allocate(1); 382 383 new(n) node(super_t::make_node(std::forward<Args>(args)...)); 384 385 merge_node(n); 386 return handle_type(n); 387 } 388 #endif 389 390 /** 391 * \b Effects: Removes the top element from the priority queue. 392 * 393 * \b Complexity: Logarithmic (amortized). 394 * 395 * */ pop(void)396 void pop(void) 397 { 398 BOOST_ASSERT(!empty()); 399 400 erase(handle_type(root)); 401 } 402 403 /** 404 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 405 * 406 * \cond 407 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 408 * \endcond 409 * 410 * \b Complexity: 2**2*log(log(N)) (amortized). 411 * 412 * */ update(handle_type handle,const_reference v)413 void update (handle_type handle, const_reference v) 414 { 415 handle.node_->value = super_t::make_node(v); 416 update(handle); 417 } 418 419 /** 420 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 421 * 422 * \cond 423 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 424 * \endcond 425 * 426 * \b Complexity: 2**2*log(log(N)) (amortized). 427 * 428 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 429 * */ update(handle_type handle)430 void update (handle_type handle) 431 { 432 node_pointer n = handle.node_; 433 434 n->unlink(); 435 if (!n->children.empty()) 436 n = merge_nodes(n, merge_node_list(n->children)); 437 438 if (n != root) 439 merge_node(n); 440 } 441 442 /** 443 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 444 * 445 * \cond 446 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 447 * \endcond 448 * 449 * \b Complexity: 2**2*log(log(N)) (amortized). 450 * 451 * \b Note: The new value is expected to be greater than the current one 452 * */ increase(handle_type handle,const_reference v)453 void increase (handle_type handle, const_reference v) 454 { 455 update(handle, v); 456 } 457 458 /** 459 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 460 * 461 * \cond 462 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 463 * \endcond 464 * 465 * \b Complexity: 2**2*log(log(N)) (amortized). 466 * 467 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 468 * */ increase(handle_type handle)469 void increase (handle_type handle) 470 { 471 update(handle); 472 } 473 474 /** 475 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 476 * 477 * \cond 478 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 479 * \endcond 480 * 481 * \b Complexity: 2**2*log(log(N)) (amortized). 482 * 483 * \b Note: The new value is expected to be less than the current one 484 * */ decrease(handle_type handle,const_reference v)485 void decrease (handle_type handle, const_reference v) 486 { 487 update(handle, v); 488 } 489 490 /** 491 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 492 * 493 * \cond 494 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 495 * \endcond 496 * 497 * \b Complexity: 2**2*log(log(N)) (amortized). 498 * 499 * \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! 500 * */ decrease(handle_type handle)501 void decrease (handle_type handle) 502 { 503 update(handle); 504 } 505 506 /** 507 * \b Effects: Removes the element handled by \c handle from the priority_queue. 508 * 509 * \cond 510 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 511 * \endcond 512 * 513 * \b Complexity: 2**2*log(log(N)) (amortized). 514 * */ erase(handle_type handle)515 void erase(handle_type handle) 516 { 517 node_pointer n = handle.node_; 518 if (n != root) { 519 n->unlink(); 520 if (!n->children.empty()) 521 merge_node(merge_node_list(n->children)); 522 } else { 523 if (!n->children.empty()) 524 root = merge_node_list(n->children); 525 else 526 root = NULL; 527 } 528 529 size_holder::decrement(); 530 n->~node(); 531 allocator_type::deallocate(n, 1); 532 } 533 534 /// \copydoc boost::heap::priority_queue::begin begin(void) const535 iterator begin(void) const 536 { 537 return iterator(root, super_t::value_comp()); 538 } 539 540 /// \copydoc boost::heap::priority_queue::end end(void) const541 iterator end(void) const 542 { 543 return iterator(super_t::value_comp()); 544 } 545 546 /// \copydoc boost::heap::fibonacci_heap::ordered_begin ordered_begin(void) const547 ordered_iterator ordered_begin(void) const 548 { 549 return ordered_iterator(root, super_t::value_comp()); 550 } 551 552 /// \copydoc boost::heap::fibonacci_heap::ordered_begin ordered_end(void) const553 ordered_iterator ordered_end(void) const 554 { 555 return ordered_iterator(NULL, super_t::value_comp()); 556 } 557 558 559 /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator s_handle_from_iterator(iterator const & it)560 static handle_type s_handle_from_iterator(iterator const & it) 561 { 562 node * ptr = const_cast<node *>(it.get_node()); 563 return handle_type(ptr); 564 } 565 566 /** 567 * \b Effects: Merge all elements from rhs into this 568 * 569 * \cond 570 * \b Complexity: \f$2^2log(log(N))\f$ (amortized). 571 * \endcond 572 * 573 * \b Complexity: 2**2*log(log(N)) (amortized). 574 * 575 * */ merge(pairing_heap & rhs)576 void merge(pairing_heap & rhs) 577 { 578 if (rhs.empty()) 579 return; 580 581 merge_node(rhs.root); 582 583 size_holder::add(rhs.get_size()); 584 rhs.set_size(0); 585 rhs.root = NULL; 586 587 super_t::set_stability_count((std::max)(super_t::get_stability_count(), 588 rhs.get_stability_count())); 589 rhs.set_stability_count(0); 590 } 591 592 /// \copydoc boost::heap::priority_queue::value_comp value_comp(void) const593 value_compare const & value_comp(void) const 594 { 595 return super_t::value_comp(); 596 } 597 598 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const 599 template <typename HeapType> operator <(HeapType const & rhs) const600 bool operator<(HeapType const & rhs) const 601 { 602 return detail::heap_compare(*this, rhs); 603 } 604 605 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const 606 template <typename HeapType> operator >(HeapType const & rhs) const607 bool operator>(HeapType const & rhs) const 608 { 609 return detail::heap_compare(rhs, *this); 610 } 611 612 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const 613 template <typename HeapType> operator >=(HeapType const & rhs) const614 bool operator>=(HeapType const & rhs) const 615 { 616 return !operator<(rhs); 617 } 618 619 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const 620 template <typename HeapType> operator <=(HeapType const & rhs) const621 bool operator<=(HeapType const & rhs) const 622 { 623 return !operator>(rhs); 624 } 625 626 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const 627 template <typename HeapType> operator ==(HeapType const & rhs) const628 bool operator==(HeapType const & rhs) const 629 { 630 return detail::heap_equality(*this, rhs); 631 } 632 633 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const 634 template <typename HeapType> operator !=(HeapType const & rhs) const635 bool operator!=(HeapType const & rhs) const 636 { 637 return !(*this == rhs); 638 } 639 640 private: 641 #if !defined(BOOST_DOXYGEN_INVOKED) clone_tree(pairing_heap const & rhs)642 void clone_tree(pairing_heap const & rhs) 643 { 644 BOOST_HEAP_ASSERT(root == NULL); 645 if (rhs.empty()) 646 return; 647 648 root = allocator_type::allocate(1); 649 650 new(root) node(static_cast<node const &>(*rhs.root), static_cast<allocator_type&>(*this)); 651 } 652 merge_node(node_pointer other)653 void merge_node(node_pointer other) 654 { 655 BOOST_HEAP_ASSERT(other); 656 if (root != NULL) 657 root = merge_nodes(root, other); 658 else 659 root = other; 660 } 661 merge_node_list(node_child_list & children)662 node_pointer merge_node_list(node_child_list & children) 663 { 664 BOOST_HEAP_ASSERT(!children.empty()); 665 node_pointer merged = merge_first_pair(children); 666 if (children.empty()) 667 return merged; 668 669 node_child_list node_list; 670 node_list.push_back(*merged); 671 672 do { 673 node_pointer next_merged = merge_first_pair(children); 674 node_list.push_back(*next_merged); 675 } while (!children.empty()); 676 677 return merge_node_list(node_list); 678 } 679 merge_first_pair(node_child_list & children)680 node_pointer merge_first_pair(node_child_list & children) 681 { 682 BOOST_HEAP_ASSERT(!children.empty()); 683 node_pointer first_child = static_cast<node_pointer>(&children.front()); 684 children.pop_front(); 685 if (children.empty()) 686 return first_child; 687 688 node_pointer second_child = static_cast<node_pointer>(&children.front()); 689 children.pop_front(); 690 691 return merge_nodes(first_child, second_child); 692 } 693 merge_nodes(node_pointer node1,node_pointer node2)694 node_pointer merge_nodes(node_pointer node1, node_pointer node2) 695 { 696 if (super_t::operator()(node1->value, node2->value)) 697 std::swap(node1, node2); 698 699 node2->unlink(); 700 node1->children.push_front(*node2); 701 return node1; 702 } 703 704 node_pointer root; 705 #endif 706 }; 707 708 709 } /* namespace heap */ 710 } /* namespace boost */ 711 712 #undef BOOST_HEAP_ASSERT 713 #endif /* BOOST_HEAP_PAIRING_HEAP_HPP */ 714