ceph/src/boost/boost/heap/d_ary_heap.hpp

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