1 // // boost heap: d-ary heap as container adaptor 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_D_ARY_HEAP_HPP 10 #define BOOST_HEAP_D_ARY_HEAP_HPP 11 12 #include <algorithm> 13 #include <utility> 14 #include <vector> 15 16 #include <boost/assert.hpp> 17 18 #include <boost/mem_fn.hpp> 19 #include <boost/heap/detail/heap_comparison.hpp> 20 #include <boost/heap/detail/ordered_adaptor_iterator.hpp> 21 #include <boost/heap/detail/stable_heap.hpp> 22 #include <boost/heap/detail/mutable_heap.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 struct nop_index_updater 42 { 43 template <typename T> runboost::heap::detail::nop_index_updater44 static void run(T &, std::size_t) 45 {} 46 }; 47 48 typedef parameter::parameters<boost::parameter::required<tag::arity>, 49 boost::parameter::optional<tag::allocator>, 50 boost::parameter::optional<tag::compare>, 51 boost::parameter::optional<tag::stable>, 52 boost::parameter::optional<tag::stability_counter_type>, 53 boost::parameter::optional<tag::constant_time_size> 54 > d_ary_heap_signature; 55 56 57 /* base class for d-ary heap */ 58 template <typename T, 59 class BoundArgs, 60 class IndexUpdater> 61 class d_ary_heap: 62 private make_heap_base<T, BoundArgs, false>::type 63 { 64 typedef make_heap_base<T, BoundArgs, false> heap_base_maker; 65 66 typedef typename heap_base_maker::type super_t; 67 typedef typename super_t::internal_type internal_type; 68 69 typedef typename boost::allocator_rebind<typename heap_base_maker::allocator_argument, internal_type>::type internal_type_allocator; 70 typedef std::vector<internal_type, internal_type_allocator> container_type; 71 typedef typename container_type::const_iterator container_iterator; 72 73 typedef IndexUpdater index_updater; 74 75 container_type q_; 76 77 static const unsigned int D = parameter::binding<BoundArgs, tag::arity>::type::value; 78 79 template <typename Heap1, typename Heap2> 80 friend struct heap_merge_emulate; 81 82 struct implementation_defined: 83 extract_allocator_types<typename heap_base_maker::allocator_argument> 84 { 85 typedef T value_type; 86 typedef typename detail::extract_allocator_types<typename heap_base_maker::allocator_argument>::size_type size_type; 87 88 typedef typename heap_base_maker::compare_argument value_compare; 89 typedef typename heap_base_maker::allocator_argument allocator_type; 90 91 struct ordered_iterator_dispatcher 92 { max_indexboost::heap::detail::d_ary_heap::implementation_defined::ordered_iterator_dispatcher93 static size_type max_index(const d_ary_heap * heap) 94 { 95 return heap->q_.size() - 1; 96 } 97 is_leafboost::heap::detail::d_ary_heap::implementation_defined::ordered_iterator_dispatcher98 static bool is_leaf(const d_ary_heap * heap, size_type index) 99 { 100 return !heap->not_leaf(index); 101 } 102 get_child_nodesboost::heap::detail::d_ary_heap::implementation_defined::ordered_iterator_dispatcher103 static std::pair<size_type, size_type> get_child_nodes(const d_ary_heap * heap, size_type index) 104 { 105 BOOST_HEAP_ASSERT(!is_leaf(heap, index)); 106 return std::make_pair(d_ary_heap::first_child_index(index), 107 heap->last_child_index(index)); 108 } 109 get_internal_valueboost::heap::detail::d_ary_heap::implementation_defined::ordered_iterator_dispatcher110 static internal_type const & get_internal_value(const d_ary_heap * heap, size_type index) 111 { 112 return heap->q_[index]; 113 } 114 get_valueboost::heap::detail::d_ary_heap::implementation_defined::ordered_iterator_dispatcher115 static value_type const & get_value(internal_type const & arg) 116 { 117 return super_t::get_value(arg); 118 } 119 }; 120 121 typedef detail::ordered_adaptor_iterator<const value_type, 122 internal_type, 123 d_ary_heap, 124 allocator_type, 125 typename super_t::internal_compare, 126 ordered_iterator_dispatcher 127 > ordered_iterator; 128 129 typedef detail::stable_heap_iterator<const value_type, container_iterator, super_t> iterator; 130 typedef iterator const_iterator; 131 typedef void * handle_type; 132 133 }; 134 135 typedef typename implementation_defined::ordered_iterator_dispatcher ordered_iterator_dispatcher; 136 137 public: 138 typedef T value_type; 139 140 typedef typename implementation_defined::size_type size_type; 141 typedef typename implementation_defined::difference_type difference_type; 142 typedef typename implementation_defined::value_compare value_compare; 143 typedef typename implementation_defined::allocator_type allocator_type; 144 typedef typename implementation_defined::reference reference; 145 typedef typename implementation_defined::const_reference const_reference; 146 typedef typename implementation_defined::pointer pointer; 147 typedef typename implementation_defined::const_pointer const_pointer; 148 typedef typename implementation_defined::iterator iterator; 149 typedef typename implementation_defined::const_iterator const_iterator; 150 typedef typename implementation_defined::ordered_iterator ordered_iterator; 151 typedef typename implementation_defined::handle_type handle_type; 152 153 static const bool is_stable = extract_stable<BoundArgs>::value; 154 d_ary_heap(value_compare const & cmp=value_compare ())155 explicit d_ary_heap(value_compare const & cmp = value_compare()): 156 super_t(cmp) 157 {} 158 d_ary_heap(d_ary_heap const & rhs)159 d_ary_heap(d_ary_heap const & rhs): 160 super_t(rhs), q_(rhs.q_) 161 {} 162 163 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES d_ary_heap(d_ary_heap && rhs)164 d_ary_heap(d_ary_heap && rhs): 165 super_t(std::move(rhs)), q_(std::move(rhs.q_)) 166 {} 167 operator =(d_ary_heap && rhs)168 d_ary_heap & operator=(d_ary_heap && rhs) 169 { 170 super_t::operator=(std::move(rhs)); 171 q_ = std::move(rhs.q_); 172 return *this; 173 } 174 #endif 175 operator =(d_ary_heap const & rhs)176 d_ary_heap & operator=(d_ary_heap const & rhs) 177 { 178 static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs); 179 q_ = rhs.q_; 180 return *this; 181 } 182 empty(void) const183 bool empty(void) const 184 { 185 return q_.empty(); 186 } 187 size(void) const188 size_type size(void) const 189 { 190 return q_.size(); 191 } 192 max_size(void) const193 size_type max_size(void) const 194 { 195 return q_.max_size(); 196 } 197 clear(void)198 void clear(void) 199 { 200 q_.clear(); 201 } 202 get_allocator(void) const203 allocator_type get_allocator(void) const 204 { 205 return q_.get_allocator(); 206 } 207 top(void) const208 value_type const & top(void) const 209 { 210 BOOST_ASSERT(!empty()); 211 return super_t::get_value(q_.front()); 212 } 213 push(value_type const & v)214 void push(value_type const & v) 215 { 216 q_.push_back(super_t::make_node(v)); 217 reset_index(size() - 1, size() - 1); 218 siftup(q_.size() - 1); 219 } 220 221 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 222 template <class... Args> emplace(Args &&...args)223 void emplace(Args&&... args) 224 { 225 q_.emplace_back(super_t::make_node(std::forward<Args>(args)...)); 226 reset_index(size() - 1, size() - 1); 227 siftup(q_.size() - 1); 228 } 229 #endif pop(void)230 void pop(void) 231 { 232 BOOST_ASSERT(!empty()); 233 std::swap(q_.front(), q_.back()); 234 q_.pop_back(); 235 236 if (q_.empty()) 237 return; 238 239 reset_index(0, 0); 240 siftdown(0); 241 } 242 swap(d_ary_heap & rhs)243 void swap(d_ary_heap & rhs) 244 { 245 super_t::swap(rhs); 246 q_.swap(rhs.q_); 247 } 248 begin(void) const249 iterator begin(void) const 250 { 251 return iterator(q_.begin()); 252 } 253 end(void) const254 iterator end(void) const 255 { 256 return iterator(q_.end()); 257 } 258 ordered_begin(void) const259 ordered_iterator ordered_begin(void) const 260 { 261 return ordered_iterator(0, this, super_t::get_internal_cmp()); 262 } 263 ordered_end(void) const264 ordered_iterator ordered_end(void) const 265 { 266 return ordered_iterator(size(), this, super_t::get_internal_cmp()); 267 } 268 reserve(size_type element_count)269 void reserve (size_type element_count) 270 { 271 q_.reserve(element_count); 272 } 273 value_comp(void) const274 value_compare const & value_comp(void) const 275 { 276 return super_t::value_comp(); 277 } 278 279 private: reset_index(size_type index,size_type new_index)280 void reset_index(size_type index, size_type new_index) 281 { 282 BOOST_HEAP_ASSERT(index < q_.size()); 283 index_updater::run(q_[index], new_index); 284 } 285 siftdown(size_type index)286 void siftdown(size_type index) 287 { 288 while (not_leaf(index)) { 289 size_type max_child_index = top_child_index(index); 290 if (!super_t::operator()(q_[max_child_index], q_[index])) { 291 reset_index(index, max_child_index); 292 reset_index(max_child_index, index); 293 std::swap(q_[max_child_index], q_[index]); 294 index = max_child_index; 295 } 296 else 297 return; 298 } 299 } 300 301 /* returns new index */ siftup(size_type index)302 void siftup(size_type index) 303 { 304 while (index != 0) { 305 size_type parent = parent_index(index); 306 307 if (super_t::operator()(q_[parent], q_[index])) { 308 reset_index(index, parent); 309 reset_index(parent, index); 310 std::swap(q_[parent], q_[index]); 311 index = parent; 312 } 313 else 314 return; 315 } 316 } 317 not_leaf(size_type index) const318 bool not_leaf(size_type index) const 319 { 320 const size_t first_child = first_child_index(index); 321 return first_child < q_.size(); 322 } 323 top_child_index(size_type index) const324 size_type top_child_index(size_type index) const 325 { 326 // invariant: index is not a leaf, so the iterator range is not empty 327 328 const size_t first_index = first_child_index(index); 329 typedef typename container_type::const_iterator container_iterator; 330 331 const container_iterator first_child = q_.begin() + first_index; 332 const container_iterator end = q_.end(); 333 334 const size_type max_elements = std::distance(first_child, end); 335 336 const container_iterator last_child = (max_elements > D) ? first_child + D 337 : end; 338 339 const container_iterator min_element = std::max_element(first_child, last_child, static_cast<super_t const &>(*this)); 340 341 return min_element - q_.begin(); 342 } 343 parent_index(size_type index)344 static size_type parent_index(size_type index) 345 { 346 return (index - 1) / D; 347 } 348 first_child_index(size_type index)349 static size_type first_child_index(size_type index) 350 { 351 return index * D + 1; 352 } 353 last_child_index(size_type index) const354 size_type last_child_index(size_type index) const 355 { 356 const size_t first_index = first_child_index(index); 357 const size_type last_index = (std::min)(first_index + D - 1, size() - 1); 358 359 return last_index; 360 } 361 362 template<typename U, 363 typename V, 364 typename W, 365 typename X> 366 struct rebind { 367 typedef d_ary_heap<U, typename d_ary_heap_signature::bind<boost::heap::stable<heap_base_maker::is_stable>, 368 boost::heap::stability_counter_type<typename heap_base_maker::stability_counter_type>, 369 boost::heap::arity<D>, 370 boost::heap::compare<V>, 371 boost::heap::allocator<W> 372 >::type, 373 X 374 > other; 375 }; 376 377 template <class U> friend class priority_queue_mutable_wrapper; 378 update(size_type index)379 void update(size_type index) 380 { 381 if (index == 0) { 382 siftdown(index); 383 return; 384 } 385 size_type parent = parent_index(index); 386 387 if (super_t::operator()(q_[parent], q_[index])) 388 siftup(index); 389 else 390 siftdown(index); 391 } 392 erase(size_type index)393 void erase(size_type index) 394 { 395 while (index != 0) 396 { 397 size_type parent = parent_index(index); 398 399 reset_index(index, parent); 400 reset_index(parent, index); 401 std::swap(q_[parent], q_[index]); 402 index = parent; 403 } 404 pop(); 405 } 406 increase(size_type index)407 void increase(size_type index) 408 { 409 siftup(index); 410 } 411 decrease(size_type index)412 void decrease(size_type index) 413 { 414 siftdown(index); 415 } 416 }; 417 418 419 template <typename T, typename BoundArgs> 420 struct select_dary_heap 421 { 422 static const bool is_mutable = extract_mutable<BoundArgs>::value; 423 424 typedef typename boost::conditional< is_mutable, 425 priority_queue_mutable_wrapper<d_ary_heap<T, BoundArgs, nop_index_updater > >, 426 d_ary_heap<T, BoundArgs, nop_index_updater > 427 >::type type; 428 }; 429 430 } /* namespace detail */ 431 432 433 434 /** 435 * \class d_ary_heap 436 * \brief d-ary heap class 437 * 438 * This class implements an immutable priority queue. Internally, the d-ary heap is represented 439 * as dynamically sized array (std::vector), that directly stores the values. 440 * 441 * The template parameter T is the type to be managed by the container. 442 * The user can specify additional options and if no options are provided default options are used. 443 * 444 * The container supports the following options: 445 * - \c boost::heap::arity<>, required 446 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > 447 * - \c boost::heap::stable<>, defaults to \c stable<false> 448 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> 449 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > 450 * - \c boost::heap::mutable_<>, defaults to \c mutable_<false> 451 * 452 */ 453 #ifdef BOOST_DOXYGEN_INVOKED 454 template<class T, class ...Options> 455 #else 456 template <typename T, 457 class A0 = boost::parameter::void_, 458 class A1 = boost::parameter::void_, 459 class A2 = boost::parameter::void_, 460 class A3 = boost::parameter::void_, 461 class A4 = boost::parameter::void_, 462 class A5 = boost::parameter::void_ 463 > 464 #endif 465 class d_ary_heap: 466 public detail::select_dary_heap<T, typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type>::type 467 { 468 typedef typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type bound_args; 469 typedef typename detail::select_dary_heap<T, bound_args>::type super_t; 470 471 template <typename Heap1, typename Heap2> 472 friend struct heap_merge_emulate; 473 474 #ifndef BOOST_DOXYGEN_INVOKED 475 static const bool is_mutable = detail::extract_mutable<bound_args>::value; 476 477 #define BOOST_HEAP_TYPEDEF_FROM_SUPER_T(NAME) \ 478 typedef typename super_t::NAME NAME; 479 480 struct implementation_defined 481 { 482 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(size_type) 483 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(difference_type) 484 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(value_compare) 485 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(allocator_type) 486 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(reference) 487 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_reference) 488 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(pointer) 489 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_pointer) 490 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(iterator) 491 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_iterator) 492 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(ordered_iterator) 493 BOOST_HEAP_TYPEDEF_FROM_SUPER_T(handle_type) 494 }; 495 #undef BOOST_HEAP_TYPEDEF_FROM_SUPER_T 496 497 #endif 498 public: 499 static const bool constant_time_size = true; 500 static const bool has_ordered_iterators = true; 501 static const bool is_mergable = false; 502 static const bool has_reserve = true; 503 static const bool is_stable = super_t::is_stable; 504 505 typedef T value_type; 506 typedef typename implementation_defined::size_type size_type; 507 typedef typename implementation_defined::difference_type difference_type; 508 typedef typename implementation_defined::value_compare value_compare; 509 typedef typename implementation_defined::allocator_type allocator_type; 510 typedef typename implementation_defined::reference reference; 511 typedef typename implementation_defined::const_reference const_reference; 512 typedef typename implementation_defined::pointer pointer; 513 typedef typename implementation_defined::const_pointer const_pointer; 514 /// \copydoc boost::heap::priority_queue::iterator 515 typedef typename implementation_defined::iterator iterator; 516 typedef typename implementation_defined::const_iterator const_iterator; 517 typedef typename implementation_defined::ordered_iterator ordered_iterator; 518 typedef typename implementation_defined::handle_type handle_type; 519 520 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) d_ary_heap(value_compare const & cmp=value_compare ())521 explicit d_ary_heap(value_compare const & cmp = value_compare()): 522 super_t(cmp) 523 {} 524 525 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) d_ary_heap(d_ary_heap const & rhs)526 d_ary_heap(d_ary_heap const & rhs): 527 super_t(rhs) 528 {} 529 530 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES 531 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) d_ary_heap(d_ary_heap && rhs)532 d_ary_heap(d_ary_heap && rhs): 533 super_t(std::move(rhs)) 534 {} 535 536 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) operator =(d_ary_heap && rhs)537 d_ary_heap & operator=(d_ary_heap && rhs) 538 { 539 super_t::operator=(std::move(rhs)); 540 return *this; 541 } 542 #endif 543 544 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &) operator =(d_ary_heap const & rhs)545 d_ary_heap & operator=(d_ary_heap const & rhs) 546 { 547 super_t::operator=(rhs); 548 return *this; 549 } 550 551 /// \copydoc boost::heap::priority_queue::empty empty(void) const552 bool empty(void) const 553 { 554 return super_t::empty(); 555 } 556 557 /// \copydoc boost::heap::priority_queue::size size(void) const558 size_type size(void) const 559 { 560 return super_t::size(); 561 } 562 563 /// \copydoc boost::heap::priority_queue::max_size max_size(void) const564 size_type max_size(void) const 565 { 566 return super_t::max_size(); 567 } 568 569 /// \copydoc boost::heap::priority_queue::clear clear(void)570 void clear(void) 571 { 572 super_t::clear(); 573 } 574 575 /// \copydoc boost::heap::priority_queue::get_allocator get_allocator(void) const576 allocator_type get_allocator(void) const 577 { 578 return super_t::get_allocator(); 579 } 580 581 /// \copydoc boost::heap::priority_queue::top top(void) const582 value_type const & top(void) const 583 { 584 return super_t::top(); 585 } 586 587 /// \copydoc boost::heap::priority_queue::push push(value_type const & v)588 typename boost::conditional<is_mutable, handle_type, void>::type push(value_type const & v) 589 { 590 return super_t::push(v); 591 } 592 593 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 594 /// \copydoc boost::heap::priority_queue::emplace 595 template <class... Args> emplace(Args &&...args)596 typename boost::conditional<is_mutable, handle_type, void>::type emplace(Args&&... args) 597 { 598 return super_t::emplace(std::forward<Args>(args)...); 599 } 600 #endif 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 detail::heap_compare(*this, 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_compare(rhs, *this); 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 !operator<(rhs); 621 } 622 623 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const 624 template <typename HeapType> operator <=(HeapType const & rhs) const625 bool operator<=(HeapType const & rhs) const 626 { 627 return !operator>(rhs); 628 } 629 630 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const 631 template <typename HeapType> operator ==(HeapType const & rhs) const632 bool operator==(HeapType const & rhs) const 633 { 634 return detail::heap_equality(*this, rhs); 635 } 636 637 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const 638 template <typename HeapType> operator !=(HeapType const & rhs) const639 bool operator!=(HeapType const & rhs) const 640 { 641 return !(*this == rhs); 642 } 643 644 /** 645 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 646 * 647 * \b Complexity: Logarithmic. 648 * 649 * \b Requirement: data structure must be configured as mutable 650 * */ update(handle_type handle,const_reference v)651 void update(handle_type handle, const_reference v) 652 { 653 BOOST_STATIC_ASSERT(is_mutable); 654 super_t::update(handle, v); 655 } 656 657 /** 658 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 659 * 660 * \b Complexity: Logarithmic. 661 * 662 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 663 * 664 * \b Requirement: data structure must be configured as mutable 665 * */ update(handle_type handle)666 void update(handle_type handle) 667 { 668 BOOST_STATIC_ASSERT(is_mutable); 669 super_t::update(handle); 670 } 671 672 /** 673 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 674 * 675 * \b Complexity: Logarithmic. 676 * 677 * \b Note: The new value is expected to be greater than the current one 678 * 679 * \b Requirement: data structure must be configured as mutable 680 * */ increase(handle_type handle,const_reference v)681 void increase(handle_type handle, const_reference v) 682 { 683 BOOST_STATIC_ASSERT(is_mutable); 684 super_t::increase(handle, v); 685 } 686 687 /** 688 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 689 * 690 * \b Complexity: Logarithmic. 691 * 692 * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 693 * 694 * \b Requirement: data structure must be configured as mutable 695 * */ increase(handle_type handle)696 void increase(handle_type handle) 697 { 698 BOOST_STATIC_ASSERT(is_mutable); 699 super_t::increase(handle); 700 } 701 702 /** 703 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 704 * 705 * \b Complexity: Logarithmic. 706 * 707 * \b Note: The new value is expected to be less than the current one 708 * 709 * \b Requirement: data structure must be configured as mutable 710 * */ decrease(handle_type handle,const_reference v)711 void decrease(handle_type handle, const_reference v) 712 { 713 BOOST_STATIC_ASSERT(is_mutable); 714 super_t::decrease(handle, v); 715 } 716 717 /** 718 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 719 * 720 * \b Complexity: Logarithmic. 721 * 722 * \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! 723 * 724 * \b Requirement: data structure must be configured as mutable 725 * */ decrease(handle_type handle)726 void decrease(handle_type handle) 727 { 728 BOOST_STATIC_ASSERT(is_mutable); 729 super_t::decrease(handle); 730 } 731 732 /** 733 * \b Effects: Removes the element handled by \c handle from the priority_queue. 734 * 735 * \b Complexity: Logarithmic. 736 * 737 * \b Requirement: data structure must be configured as mutable 738 * */ erase(handle_type handle)739 void erase(handle_type handle) 740 { 741 BOOST_STATIC_ASSERT(is_mutable); 742 super_t::erase(handle); 743 } 744 745 /** 746 * \b Effects: Casts an iterator to a node handle. 747 * 748 * \b Complexity: Constant. 749 * 750 * \b Requirement: data structure must be configured as mutable 751 * */ s_handle_from_iterator(iterator const & it)752 static handle_type s_handle_from_iterator(iterator const & it) 753 { 754 BOOST_STATIC_ASSERT(is_mutable); 755 return super_t::s_handle_from_iterator(it); 756 } 757 758 /// \copydoc boost::heap::priority_queue::pop pop(void)759 void pop(void) 760 { 761 super_t::pop(); 762 } 763 764 /// \copydoc boost::heap::priority_queue::swap swap(d_ary_heap & rhs)765 void swap(d_ary_heap & rhs) 766 { 767 super_t::swap(rhs); 768 } 769 770 /// \copydoc boost::heap::priority_queue::begin begin(void) const771 const_iterator begin(void) const 772 { 773 return super_t::begin(); 774 } 775 776 /// \copydoc boost::heap::priority_queue::begin begin(void)777 iterator begin(void) 778 { 779 return super_t::begin(); 780 } 781 782 /// \copydoc boost::heap::priority_queue::end end(void)783 iterator end(void) 784 { 785 return super_t::end(); 786 } 787 788 /// \copydoc boost::heap::priority_queue::end end(void) const789 const_iterator end(void) const 790 { 791 return super_t::end(); 792 } 793 794 /// \copydoc boost::heap::fibonacci_heap::ordered_begin ordered_begin(void) const795 ordered_iterator ordered_begin(void) const 796 { 797 return super_t::ordered_begin(); 798 } 799 800 /// \copydoc boost::heap::fibonacci_heap::ordered_end ordered_end(void) const801 ordered_iterator ordered_end(void) const 802 { 803 return super_t::ordered_end(); 804 } 805 806 /// \copydoc boost::heap::priority_queue::reserve reserve(size_type element_count)807 void reserve (size_type element_count) 808 { 809 super_t::reserve(element_count); 810 } 811 812 /// \copydoc boost::heap::priority_queue::value_comp value_comp(void) const813 value_compare const & value_comp(void) const 814 { 815 return super_t::value_comp(); 816 } 817 }; 818 819 } /* namespace heap */ 820 } /* namespace boost */ 821 822 #undef BOOST_HEAP_ASSERT 823 824 #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */ 825