ceph/src/boost/libs/heap/include/boost/heap/skew_heap.hpp

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