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