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