• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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     typedef typename boost::allocator_rebind<allocator_argument, node_type>::type allocator_type;
197 
198     struct type:
199         base_type,
200         allocator_type
201     {
typeboost::heap::detail::make_skew_heap_base::type202         type(compare_argument const & arg):
203             base_type(arg)
204         {}
205 
206 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
typeboost::heap::detail::make_skew_heap_base::type207         type(type && rhs):
208             base_type(std::move(static_cast<base_type&>(rhs))),
209             allocator_type(std::move(static_cast<allocator_type&>(rhs)))
210         {}
211 
typeboost::heap::detail::make_skew_heap_base::type212         type(type const & rhs):
213             base_type(rhs),
214             allocator_type(rhs)
215         {}
216 
operator =boost::heap::detail::make_skew_heap_base::type217         type & operator=(type && rhs)
218         {
219             base_type::operator=(std::move(static_cast<base_type&>(rhs)));
220             allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
221             return *this;
222         }
223 
operator =boost::heap::detail::make_skew_heap_base::type224         type & operator=(type const & rhs)
225         {
226             base_type::operator=(static_cast<base_type const &>(rhs));
227             allocator_type::operator=(static_cast<allocator_type const &>(rhs));
228             return *this;
229         }
230 #endif
231     };
232 };
233 
234 } /* namespace detail */
235 
236 /**
237  * \class skew_heap
238  * \brief skew heap
239  *
240  *
241  * The template parameter T is the type to be managed by the container.
242  * The user can specify additional options and if no options are provided default options are used.
243  *
244  * The container supports the following options:
245  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
246  * - \c boost::heap::stable<>, defaults to \c stable<false>
247  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
248  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
249  * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
250  * - \c boost::heap::store_parent_pointer<>, defaults to \c store_parent_pointer<true>. Maintaining a parent pointer adds some
251  *   maintenance and size overhead, but iterating a heap is more efficient.
252  * - \c boost::heap::mutable<>, defaults to \c mutable<false>.
253  *
254  */
255 #ifdef BOOST_DOXYGEN_INVOKED
256 template<class T, class ...Options>
257 #else
258 template <typename T,
259           class A0 = boost::parameter::void_,
260           class A1 = boost::parameter::void_,
261           class A2 = boost::parameter::void_,
262           class A3 = boost::parameter::void_,
263           class A4 = boost::parameter::void_,
264           class A5 = boost::parameter::void_,
265           class A6 = boost::parameter::void_
266          >
267 #endif
268 class skew_heap:
269     private detail::make_skew_heap_base<T,
270                                           typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type
271                                          >::type
272 {
273     typedef typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type bound_args;
274     typedef detail::make_skew_heap_base<T, bound_args> base_maker;
275     typedef typename base_maker::type super_t;
276 
277     typedef typename super_t::internal_type internal_type;
278     typedef typename super_t::size_holder_type size_holder;
279     typedef typename base_maker::allocator_argument allocator_argument;
280 
281     static const bool store_parent_pointer = base_maker::store_parent_pointer;
282     template <typename Heap1, typename Heap2>
283     friend struct heap_merge_emulate;
284 
285     struct implementation_defined:
286         detail::extract_allocator_types<typename base_maker::allocator_argument>
287     {
288         typedef T value_type;
289 
290         typedef typename base_maker::compare_argument value_compare;
291         typedef typename base_maker::allocator_type allocator_type;
292 
293         typedef typename base_maker::node_type node;
294         typedef typename boost::allocator_pointer<allocator_type>::type node_pointer;
295         typedef typename boost::allocator_const_pointer<allocator_type>::type const_node_pointer;
296 
297         typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
298 
299         typedef boost::array<node_pointer, 2> child_list_type;
300         typedef typename child_list_type::iterator child_list_iterator;
301 
302         typedef typename boost::conditional<false,
303                                         detail::recursive_tree_iterator<node,
304                                                                         child_list_iterator,
305                                                                         const value_type,
306                                                                         value_extractor,
307                                                                         detail::list_iterator_converter<node,
308                                                                                                         child_list_type
309                                                                                                        >
310                                                                        >,
311                                         detail::tree_iterator<node,
312                                                               const value_type,
313                                                               allocator_type,
314                                                               value_extractor,
315                                                               detail::dereferencer<node>,
316                                                               true,
317                                                               false,
318                                                               value_compare
319                                                     >
320                                         >::type iterator;
321 
322         typedef iterator const_iterator;
323 
324         typedef detail::tree_iterator<node,
325                                       const value_type,
326                                       allocator_type,
327                                       value_extractor,
328                                       detail::dereferencer<node>,
329                                       true,
330                                       true,
331                                       value_compare
332                                      > ordered_iterator;
333 
334         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
335         typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
336     };
337 
338     typedef typename implementation_defined::value_extractor value_extractor;
339     typedef typename implementation_defined::node node;
340     typedef typename implementation_defined::node_pointer node_pointer;
341 
342 public:
343     typedef T value_type;
344 
345     typedef typename implementation_defined::size_type size_type;
346     typedef typename implementation_defined::difference_type difference_type;
347     typedef typename implementation_defined::value_compare value_compare;
348     typedef typename implementation_defined::allocator_type allocator_type;
349     typedef typename implementation_defined::reference reference;
350     typedef typename implementation_defined::const_reference const_reference;
351     typedef typename implementation_defined::pointer pointer;
352     typedef typename implementation_defined::const_pointer const_pointer;
353 
354     /// \copydoc boost::heap::priority_queue::iterator
355     typedef typename implementation_defined::iterator iterator;
356     typedef typename implementation_defined::const_iterator const_iterator;
357     typedef typename implementation_defined::ordered_iterator ordered_iterator;
358 
359     static const bool constant_time_size = super_t::constant_time_size;
360     static const bool has_ordered_iterators = true;
361     static const bool is_mergable = true;
362     static const bool is_stable = detail::extract_stable<bound_args>::value;
363     static const bool has_reserve = false;
364     static const bool is_mutable = detail::extract_mutable<bound_args>::value;
365 
366     typedef typename boost::conditional<is_mutable, typename implementation_defined::handle_type, void*>::type handle_type;
367 
368     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
skew_heap(value_compare const & cmp=value_compare ())369     explicit skew_heap(value_compare const & cmp = value_compare()):
370         super_t(cmp), root(NULL)
371     {}
372 
373     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
skew_heap(skew_heap const & rhs)374     skew_heap(skew_heap const & rhs):
375         super_t(rhs), root(0)
376     {
377         if (rhs.empty())
378             return;
379 
380         clone_tree(rhs);
381         size_holder::set_size(rhs.get_size());
382     }
383 
384     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs)
operator =(skew_heap const & rhs)385     skew_heap & operator=(skew_heap const & rhs)
386     {
387         clear();
388         size_holder::set_size(rhs.get_size());
389         static_cast<super_t&>(*this) = rhs;
390 
391         clone_tree(rhs);
392         return *this;
393     }
394 
395 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
396     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
skew_heap(skew_heap && rhs)397     skew_heap(skew_heap && rhs):
398         super_t(std::move(rhs)), root(rhs.root)
399     {
400         rhs.root = NULL;
401     }
402 
403     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
operator =(skew_heap && rhs)404     skew_heap & operator=(skew_heap && rhs)
405     {
406         super_t::operator=(std::move(rhs));
407         root = rhs.root;
408         rhs.root = NULL;
409         return *this;
410     }
411 #endif
412 
~skew_heap(void)413     ~skew_heap(void)
414     {
415         clear();
416     }
417 
418     /**
419      * \b Effects: Adds a new element to the priority queue.
420      *
421      * \b Complexity: Logarithmic (amortized).
422      *
423      * */
push(value_type const & v)424     typename boost::conditional<is_mutable, handle_type, void>::type push(value_type const & v)
425     {
426         typedef typename boost::conditional<is_mutable, push_handle, push_void>::type push_helper;
427         return push_helper::push(this, v);
428     }
429 
430 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
431     /**
432      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
433      *
434      * \b Complexity: Logarithmic (amortized).
435      *
436      * */
437     template <typename... Args>
emplace(Args &&...args)438     typename boost::conditional<is_mutable, handle_type, void>::type emplace(Args&&... args)
439     {
440         typedef typename boost::conditional<is_mutable, push_handle, push_void>::type push_helper;
441         return push_helper::emplace(this, std::forward<Args>(args)...);
442     }
443 #endif
444 
445     /// \copydoc boost::heap::priority_queue::empty
empty(void) const446     bool empty(void) const
447     {
448         return root == NULL;
449     }
450 
451     /// \copydoc boost::heap::binomial_heap::size
size(void) const452     size_type size(void) const
453     {
454         if (constant_time_size)
455             return size_holder::get_size();
456 
457         if (root == NULL)
458             return 0;
459         else
460             return root->count_children();
461     }
462 
463     /// \copydoc boost::heap::priority_queue::max_size
max_size(void) const464     size_type max_size(void) const
465     {
466         const allocator_type& alloc = *this;
467         return boost::allocator_max_size(alloc);
468     }
469 
470     /// \copydoc boost::heap::priority_queue::clear
clear(void)471     void clear(void)
472     {
473         if (empty())
474             return;
475 
476         root->template clear_subtree<allocator_type>(*this);
477         root->~node();
478         allocator_type& alloc = *this;
479         alloc.deallocate(root, 1);
480         root = NULL;
481         size_holder::set_size(0);
482     }
483 
484     /// \copydoc boost::heap::priority_queue::get_allocator
get_allocator(void) const485     allocator_type get_allocator(void) const
486     {
487         return *this;
488     }
489 
490     /// \copydoc boost::heap::priority_queue::swap
swap(skew_heap & rhs)491     void swap(skew_heap & rhs)
492     {
493         super_t::swap(rhs);
494         std::swap(root, rhs.root);
495     }
496 
497     /// \copydoc boost::heap::priority_queue::top
top(void) const498     const_reference top(void) const
499     {
500         BOOST_ASSERT(!empty());
501 
502         return super_t::get_value(root->value);
503     }
504 
505     /**
506      * \b Effects: Removes the top element from the priority queue.
507      *
508      * \b Complexity: Logarithmic (amortized).
509      *
510      * */
pop(void)511     void pop(void)
512     {
513         BOOST_ASSERT(!empty());
514 
515         node_pointer top = root;
516 
517         root = merge_children(root);
518         size_holder::decrement();
519 
520         if (root)
521             BOOST_HEAP_ASSERT(root->get_parent() == NULL);
522         else
523             BOOST_HEAP_ASSERT(size_holder::get_size() == 0);
524 
525         top->~node();
526         allocator_type& alloc = *this;
527         alloc.deallocate(top, 1);
528         sanity_check();
529     }
530 
531     /// \copydoc boost::heap::priority_queue::begin
begin(void) const532     iterator begin(void) const
533     {
534         return iterator(root, super_t::value_comp());
535     }
536 
537     /// \copydoc boost::heap::priority_queue::end
end(void) const538     iterator end(void) const
539     {
540         return iterator();
541     }
542 
543     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
ordered_begin(void) const544     ordered_iterator ordered_begin(void) const
545     {
546         return ordered_iterator(root, super_t::value_comp());
547     }
548 
549     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
ordered_end(void) const550     ordered_iterator ordered_end(void) const
551     {
552         return ordered_iterator(0, super_t::value_comp());
553     }
554 
555     /**
556      * \b Effects: Merge all elements from rhs into this
557      *
558      * \b Complexity: Logarithmic (amortized).
559      *
560      * */
merge(skew_heap & rhs)561     void merge(skew_heap & rhs)
562     {
563         if (rhs.empty())
564             return;
565 
566         merge_node(rhs.root);
567 
568         size_holder::add(rhs.get_size());
569         rhs.set_size(0);
570         rhs.root = NULL;
571         sanity_check();
572 
573         super_t::set_stability_count((std::max)(super_t::get_stability_count(),
574                                      rhs.get_stability_count()));
575         rhs.set_stability_count(0);
576     }
577 
578     /// \copydoc boost::heap::priority_queue::value_comp
value_comp(void) const579     value_compare const & value_comp(void) const
580     {
581         return super_t::value_comp();
582     }
583 
584     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
585     template <typename HeapType>
operator <(HeapType const & rhs) const586     bool operator<(HeapType const & rhs) const
587     {
588         return detail::heap_compare(*this, rhs);
589     }
590 
591     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
592     template <typename HeapType>
operator >(HeapType const & rhs) const593     bool operator>(HeapType const & rhs) const
594     {
595         return detail::heap_compare(rhs, *this);
596     }
597 
598     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
599     template <typename HeapType>
operator >=(HeapType const & rhs) const600     bool operator>=(HeapType const & rhs) const
601     {
602         return !operator<(rhs);
603     }
604 
605     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
606     template <typename HeapType>
operator <=(HeapType const & rhs) const607     bool operator<=(HeapType const & rhs) const
608     {
609         return !operator>(rhs);
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_equality(*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 !(*this == rhs);
624     }
625 
626 
627     /// \copydoc boost::heap::d_ary_heap::s_handle_from_iterator
s_handle_from_iterator(iterator const & it)628     static handle_type s_handle_from_iterator(iterator const & it)
629     {
630         node * ptr = const_cast<node *>(it.get_node());
631         return handle_type(ptr);
632     }
633 
634     /**
635      * \b Effects: Removes the element handled by \c handle from the priority_queue.
636      *
637      * \b Complexity: Logarithmic (amortized).
638      * */
erase(handle_type object)639     void erase (handle_type object)
640     {
641         BOOST_STATIC_ASSERT(is_mutable);
642         node_pointer this_node = object.node_;
643 
644         unlink_node(this_node);
645         size_holder::decrement();
646 
647         sanity_check();
648         this_node->~node();
649         allocator_type& alloc = *this;
650         alloc.deallocate(this_node, 1);
651     }
652 
653     /**
654      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
655      *
656      * \b Complexity: Logarithmic (amortized).
657      *
658      * */
update(handle_type handle,const_reference v)659     void update (handle_type handle, const_reference v)
660     {
661         BOOST_STATIC_ASSERT(is_mutable);
662         if (super_t::operator()(super_t::get_value(handle.node_->value), v))
663             increase(handle, v);
664         else
665             decrease(handle, v);
666     }
667 
668     /**
669      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
670      *
671      * \b Complexity: Logarithmic (amortized).
672      *
673      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
674      * */
update(handle_type handle)675     void update (handle_type handle)
676     {
677         BOOST_STATIC_ASSERT(is_mutable);
678         node_pointer this_node = handle.node_;
679 
680         if (this_node->get_parent()) {
681             if (super_t::operator()(super_t::get_value(this_node->get_parent()->value),
682                                     super_t::get_value(this_node->value)))
683                 increase(handle);
684             else
685                 decrease(handle);
686         }
687         else
688             decrease(handle);
689     }
690 
691     /**
692      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
693      *
694      * \b Complexity: Logarithmic (amortized).
695      *
696      * \b Note: The new value is expected to be greater than the current one
697      * */
increase(handle_type handle,const_reference v)698     void increase (handle_type handle, const_reference v)
699     {
700         BOOST_STATIC_ASSERT(is_mutable);
701         handle.node_->value = super_t::make_node(v);
702         increase(handle);
703     }
704 
705     /**
706      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
707      *
708      * \b Complexity: Logarithmic (amortized).
709      *
710      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
711      * */
increase(handle_type handle)712     void increase (handle_type handle)
713     {
714         BOOST_STATIC_ASSERT(is_mutable);
715         node_pointer this_node = handle.node_;
716 
717         if (this_node == root)
718             return;
719 
720         node_pointer parent = this_node->get_parent();
721 
722         if (this_node == parent->children[0])
723             parent->children[0] = NULL;
724         else
725             parent->children[1] = NULL;
726 
727         this_node->set_parent(NULL);
728         merge_node(this_node);
729     }
730 
731     /**
732      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
733      *
734      * \b Complexity: Logarithmic (amortized).
735      *
736      * \b Note: The new value is expected to be less than the current one
737      * */
decrease(handle_type handle,const_reference v)738     void decrease (handle_type handle, const_reference v)
739     {
740         BOOST_STATIC_ASSERT(is_mutable);
741         handle.node_->value = super_t::make_node(v);
742         decrease(handle);
743     }
744 
745     /**
746      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
747      *
748      * \b Complexity: Logarithmic (amortized).
749      *
750      * \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!
751      * */
decrease(handle_type handle)752     void decrease (handle_type handle)
753     {
754         BOOST_STATIC_ASSERT(is_mutable);
755         node_pointer this_node = handle.node_;
756 
757         unlink_node(this_node);
758         this_node->children.assign(0);
759         this_node->set_parent(NULL);
760         merge_node(this_node);
761     }
762 
763 private:
764 #if !defined(BOOST_DOXYGEN_INVOKED)
765     struct push_void
766     {
pushboost::heap::skew_heap::push_void767         static void push(skew_heap * self, const_reference v)
768         {
769             self->push_internal(v);
770         }
771 
772 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
773         template <class... Args>
emplaceboost::heap::skew_heap::push_void774         static void emplace(skew_heap * self, Args&&... args)
775         {
776             self->emplace_internal(std::forward<Args>(args)...);
777         }
778 #endif
779     };
780 
781     struct push_handle
782     {
pushboost::heap::skew_heap::push_handle783         static handle_type push(skew_heap * self, const_reference v)
784         {
785             return handle_type(self->push_internal(v));
786         }
787 
788 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
789         template <class... Args>
emplaceboost::heap::skew_heap::push_handle790         static handle_type emplace(skew_heap * self, Args&&... args)
791         {
792             return handle_type(self->emplace_internal(std::forward<Args>(args)...));
793         }
794 #endif
795     };
796 
push_internal(const_reference v)797     node_pointer push_internal(const_reference v)
798     {
799         size_holder::increment();
800 
801         allocator_type& alloc = *this;
802         node_pointer n = alloc.allocate(1);
803         new(n) node(super_t::make_node(v));
804         merge_node(n);
805         return n;
806     }
807 
808 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
809     template <class... Args>
emplace_internal(Args &&...args)810     node_pointer emplace_internal(Args&&... args)
811     {
812         size_holder::increment();
813 
814         allocator_type& alloc = *this;
815         node_pointer n = alloc.allocate(1);
816         new(n) node(super_t::make_node(std::forward<Args>(args)...));
817         merge_node(n);
818         return n;
819     }
820 #endif
821 
unlink_node(node_pointer node)822     void unlink_node(node_pointer node)
823     {
824         node_pointer parent = node->get_parent();
825         node_pointer merged_children = merge_children(node);
826 
827         if (parent) {
828             if (node == parent->children[0])
829                 parent->children[0] = merged_children;
830             else
831                 parent->children[1] = merged_children;
832         }
833         else
834             root = merged_children;
835     }
836 
clone_tree(skew_heap const & rhs)837     void clone_tree(skew_heap const & rhs)
838     {
839         BOOST_HEAP_ASSERT(root == NULL);
840         if (rhs.empty())
841             return;
842 
843         allocator_type& alloc = *this;
844         root = alloc.allocate(1);
845         new(root) node(*rhs.root, alloc, NULL);
846     }
847 
merge_node(node_pointer other)848     void merge_node(node_pointer other)
849     {
850         BOOST_HEAP_ASSERT(other);
851         if (root != NULL)
852             root = merge_nodes(root, other, NULL);
853         else
854             root = other;
855     }
856 
merge_nodes(node_pointer node1,node_pointer node2,node_pointer new_parent)857     node_pointer merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent)
858     {
859         if (node1 == NULL) {
860             if (node2)
861                 node2->set_parent(new_parent);
862             return node2;
863         }
864         if (node2 == NULL) {
865             node1->set_parent(new_parent);
866             return node1;
867         }
868 
869         node_pointer merged = merge_nodes_recursive(node1, node2, new_parent);
870         return merged;
871     }
872 
merge_children(node_pointer node)873     node_pointer merge_children(node_pointer node)
874     {
875         node_pointer parent = node->get_parent();
876         node_pointer merged_children = merge_nodes(node->children[0], node->children[1], parent);
877 
878         return merged_children;
879     }
880 
merge_nodes_recursive(node_pointer node1,node_pointer node2,node_pointer new_parent)881     node_pointer merge_nodes_recursive(node_pointer node1, node_pointer node2, node_pointer new_parent)
882     {
883         if (super_t::operator()(node1->value, node2->value))
884             std::swap(node1, node2);
885 
886         node * parent = node1;
887         node * child = node2;
888 
889         if (parent->children[1]) {
890             node * merged = merge_nodes(parent->children[1], child, parent);
891             parent->children[1] = merged;
892             merged->set_parent(parent);
893         } else {
894             parent->children[1] = child;
895             child->set_parent(parent);
896         }
897 
898 
899         std::swap(parent->children[0], parent->children[1]);
900         parent->set_parent(new_parent);
901         return parent;
902     }
903 
sanity_check(void)904     void sanity_check(void)
905     {
906 #ifdef BOOST_HEAP_SANITYCHECKS
907         if (root)
908             BOOST_HEAP_ASSERT( root->template is_heap<super_t>(super_t::value_comp()) );
909 
910         if (constant_time_size) {
911             size_type stored_size = size_holder::get_size();
912 
913             size_type counted_size;
914             if (root == NULL)
915                 counted_size = 0;
916             else
917                 counted_size = root->count_children();
918 
919             BOOST_HEAP_ASSERT(counted_size == stored_size);
920         }
921 #endif
922     }
923 
924     node_pointer root;
925 #endif
926 };
927 
928 } /* namespace heap */
929 } /* namespace boost */
930 
931 #undef BOOST_HEAP_ASSERT
932 #endif /* BOOST_HEAP_SKEW_HEAP_HPP */
933