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
37namespace boost {
38namespace heap {
39namespace detail {
40
41template <typename node_pointer, bool store_parent_pointer>
42struct parent_holder
43{
44 parent_holder(void):
45 parent_(NULL)
46 {}
47
48 void set_parent(node_pointer parent)
49 {
50 BOOST_HEAP_ASSERT(static_cast<node_pointer>(this) != parent);
51 parent_ = parent;
52 }
53
54 node_pointer get_parent(void) const
55 {
56 return parent_;
57 }
58
59 node_pointer parent_;
60};
61
62template <typename node_pointer>
63struct parent_holder<node_pointer, false>
64{
65 void set_parent(node_pointer parent)
66 {}
67
68 node_pointer get_parent(void) const
69 {
70 return NULL;
71 }
72};
73
74
75template <typename value_type, bool store_parent_pointer>
76struct 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
85 skew_heap_node(value_type const & v):
86 value(v)
87 {
88 children.assign(0);
89 }
90
91#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
92 skew_heap_node(value_type && v):
93 value(v)
94 {
95 children.assign(0);
96 }
97#endif
98
99 template <typename Alloc>
100 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>
110 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>
119 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>
127 void dispose_child(skew_heap_node * node, Disposer & disposer)
128 {
129 if (node)
130 disposer(node);
131 }
132
133 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>
145 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
168typedef 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
177template <typename T, typename BoundArgs>
178struct 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 {
202 type(compare_argument const & arg):
203 base_type(arg)
204 {}
205
206#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
207 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
212 type(type const & rhs):
213 base_type(rhs),
214 allocator_type(rhs)
215 {}
216
217 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
224 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
256template<class T, class ...Options>
257#else
258template <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
268class 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
342public:
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 &)
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 &)
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)
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 &&)
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 &&)
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
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 * */
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>
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
446 bool empty(void) const
447 {
448 return root == NULL;
449 }
450
451 /// \copydoc boost::heap::binomial_heap::size
452 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
464 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
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
485 allocator_type get_allocator(void) const
486 {
487 return *this;
488 }
489
490 /// \copydoc boost::heap::priority_queue::swap
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
498 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 * */
511 void pop(void)
512 {
513 BOOST_ASSERT(!empty());
514
515 node_pointer top = root;
516
517 root = merge_children(node: 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
532 iterator begin(void) const
533 {
534 return iterator(root, super_t::value_comp());
535 }
536
537 /// \copydoc boost::heap::priority_queue::end
538 iterator end(void) const
539 {
540 return iterator();
541 }
542
543 /// \copydoc boost::heap::fibonacci_heap::ordered_begin
544 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
550 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 * */
561 void merge(skew_heap & rhs)
562 {
563 if (rhs.empty())
564 return;
565
566 merge_node(other: 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
579 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>
586 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>
593 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>
600 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>
607 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>
614 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>
621 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
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 * */
639 void erase (handle_type object)
640 {
641 BOOST_STATIC_ASSERT(is_mutable);
642 node_pointer this_node = object.node_;
643
644 unlink_node(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 * */
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 * */
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 * */
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 * */
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(other: 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 * */
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 * */
752 void decrease (handle_type handle)
753 {
754 BOOST_STATIC_ASSERT(is_mutable);
755 node_pointer this_node = handle.node_;
756
757 unlink_node(node: this_node);
758 this_node->children.assign(0);
759 this_node->set_parent(NULL);
760 merge_node(other: this_node);
761 }
762
763private:
764#if !defined(BOOST_DOXYGEN_INVOKED)
765 struct push_void
766 {
767 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>
774 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 {
783 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>
790 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
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(other: n);
805 return n;
806 }
807
808#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
809 template <class... 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(other: n);
818 return n;
819 }
820#endif
821
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
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
848 void merge_node(node_pointer other)
849 {
850 BOOST_HEAP_ASSERT(other);
851 if (root != NULL)
852 root = merge_nodes(node1: root, node2: other, NULL);
853 else
854 root = other;
855 }
856
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
873 node_pointer merge_children(node_pointer node)
874 {
875 node_pointer parent = node->get_parent();
876 node_pointer merged_children = merge_nodes(node1: node->children[0], node2: node->children[1], new_parent: parent);
877
878 return merged_children;
879 }
880
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(node1: parent->children[1], node2: child, new_parent: 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
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

source code of boost/libs/heap/include/boost/heap/skew_heap.hpp