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