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 {
parent_holderboost::heap::detail::parent_holder43     parent_holder(void):
44         parent_(NULL)
45     {}
46 
set_parentboost::heap::detail::parent_holder47     void set_parent(node_pointer parent)
48     {
49         BOOST_HEAP_ASSERT(static_cast<node_pointer>(this) != parent);
50         parent_ = parent;
51     }
52 
get_parentboost::heap::detail::parent_holder53     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 {
set_parentboost::heap::detail::parent_holder64     void set_parent(node_pointer parent)
65     {}
66 
get_parentboost::heap::detail::parent_holder67     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 
skew_heap_nodeboost::heap::detail::skew_heap_node84     skew_heap_node(value_type const & v):
85         value(v)
86     {
87         children.assign(0);
88     }
89 
90 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
skew_heap_nodeboost::heap::detail::skew_heap_node91     skew_heap_node(value_type && v):
92         value(v)
93     {
94         children.assign(0);
95     }
96 #endif
97 
98     template <typename Alloc>
skew_heap_nodeboost::heap::detail::skew_heap_node99     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>
clone_childboost::heap::detail::skew_heap_node109     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>
clear_subtreeboost::heap::detail::skew_heap_node118     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>
dispose_childboost::heap::detail::skew_heap_node126     void dispose_child(skew_heap_node * node, Disposer & disposer)
127     {
128         if (node)
129             disposer(node);
130     }
131 
count_childrenboost::heap::detail::skew_heap_node132     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>
is_heapboost::heap::detail::skew_heap_node144     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     {
typeboost::heap::detail::make_skew_heap_base::type201         type(compare_argument const & arg):
202             base_type(arg)
203         {}
204 
205 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
typeboost::heap::detail::make_skew_heap_base::type206         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 
typeboost::heap::detail::make_skew_heap_base::type211         type(type const & rhs):
212             base_type(rhs),
213             allocator_type(rhs)
214         {}
215 
operator =boost::heap::detail::make_skew_heap_base::type216         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 
operator =boost::heap::detail::make_skew_heap_base::type223         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 &)
skew_heap(value_compare const & cmp=value_compare ())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 &)
skew_heap(skew_heap const & rhs)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)
operator =(skew_heap 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 &&)
skew_heap(skew_heap && rhs)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 &&)
operator =(skew_heap && rhs)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 
~skew_heap(void)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      * */
push(value_type const & v)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>
emplace(Args &&...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
empty(void) const445     bool empty(void) const
446     {
447         return root == NULL;
448     }
449 
450     /// \copydoc boost::heap::binomial_heap::size
size(void) const451     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
max_size(void) const463     size_type max_size(void) const
464     {
465         return allocator_type::max_size();
466     }
467 
468     /// \copydoc boost::heap::priority_queue::clear
clear(void)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
get_allocator(void) const483     allocator_type get_allocator(void) const
484     {
485         return *this;
486     }
487 
488     /// \copydoc boost::heap::priority_queue::swap
swap(skew_heap & rhs)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
top(void) const496     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      * */
pop(void)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
begin(void) const529     iterator begin(void) const
530     {
531         return iterator(root, super_t::value_comp());
532     }
533 
534     /// \copydoc boost::heap::priority_queue::end
end(void) const535     iterator end(void) const
536     {
537         return iterator();
538     }
539 
540     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
ordered_begin(void) const541     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
ordered_end(void) const547     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      * */
merge(skew_heap & rhs)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
value_comp(void) const576     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>
operator <(HeapType const & rhs) const583     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>
operator >(HeapType const & rhs) const590     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>
operator >=(HeapType const & rhs) const597     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>
operator <=(HeapType const & rhs) const604     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>
operator ==(HeapType const & rhs) const611     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>
operator !=(HeapType const & rhs) const618     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
s_handle_from_iterator(iterator const & it)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      * */
erase(handle_type object)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      * */
update(handle_type handle,const_reference v)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      * */
update(handle_type handle)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      * */
increase(handle_type handle,const_reference v)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      * */
increase(handle_type handle)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      * */
decrease(handle_type handle,const_reference v)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      * */
decrease(handle_type handle)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     {
pushboost::heap::skew_heap::push_void763         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>
emplaceboost::heap::skew_heap::push_void770         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     {
pushboost::heap::skew_heap::push_handle779         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>
emplaceboost::heap::skew_heap::push_handle786         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 
push_internal(const_reference v)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>
emplace_internal(Args &&...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 
unlink_node(node_pointer node)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 
clone_tree(skew_heap const & rhs)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 
merge_node(node_pointer other)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 
merge_nodes(node_pointer node1,node_pointer node2,node_pointer new_parent)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 
merge_children(node_pointer node)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 
merge_nodes_recursive(node_pointer node1,node_pointer node2,node_pointer new_parent)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 
sanity_check(void)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 */
929