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

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