]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // boost heap: pairing 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_PAIRING_HEAP_HPP | |
10 | #define BOOST_HEAP_PAIRING_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/policies.hpp> | |
21 | #include <boost/heap/detail/stable_heap.hpp> | |
22 | #include <boost/heap/detail/tree_iterator.hpp> | |
92f5a8d4 | 23 | #include <boost/type_traits/integral_constant.hpp> |
7c673cae FG |
24 | |
25 | #ifdef BOOST_HAS_PRAGMA_ONCE | |
26 | #pragma once | |
27 | #endif | |
28 | ||
29 | ||
30 | #ifndef BOOST_DOXYGEN_INVOKED | |
31 | #ifdef BOOST_HEAP_SANITYCHECKS | |
32 | #define BOOST_HEAP_ASSERT BOOST_ASSERT | |
33 | #else | |
34 | #define BOOST_HEAP_ASSERT(expression) | |
35 | #endif | |
36 | #endif | |
37 | ||
38 | namespace boost { | |
39 | namespace heap { | |
40 | namespace detail { | |
41 | ||
42 | typedef parameter::parameters<boost::parameter::optional<tag::allocator>, | |
43 | boost::parameter::optional<tag::compare>, | |
44 | boost::parameter::optional<tag::stable>, | |
45 | boost::parameter::optional<tag::constant_time_size>, | |
46 | boost::parameter::optional<tag::stability_counter_type> | |
47 | > pairing_heap_signature; | |
48 | ||
49 | template <typename T, typename Parspec> | |
50 | struct make_pairing_heap_base | |
51 | { | |
52 | static const bool constant_time_size = parameter::binding<Parspec, | |
53 | tag::constant_time_size, | |
92f5a8d4 | 54 | boost::true_type |
7c673cae FG |
55 | >::type::value; |
56 | typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type; | |
57 | typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument; | |
58 | typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument; | |
59 | ||
60 | typedef heap_node<typename base_type::internal_type, false> node_type; | |
61 | ||
92f5a8d4 | 62 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae | 63 | typedef typename allocator_argument::template rebind<node_type>::other allocator_type; |
92f5a8d4 TL |
64 | #else |
65 | typedef typename std::allocator_traits<allocator_argument>::template rebind_alloc<node_type> allocator_type; | |
66 | #endif | |
7c673cae FG |
67 | |
68 | struct type: | |
69 | base_type, | |
70 | allocator_type | |
71 | { | |
72 | type(compare_argument const & arg): | |
73 | base_type(arg) | |
74 | {} | |
75 | ||
76 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
77 | type(type const & rhs): | |
78 | base_type(rhs), allocator_type(rhs) | |
79 | {} | |
80 | ||
81 | type(type && rhs): | |
82 | base_type(std::move(static_cast<base_type&>(rhs))), | |
83 | allocator_type(std::move(static_cast<allocator_type&>(rhs))) | |
84 | {} | |
85 | ||
86 | type & operator=(type && rhs) | |
87 | { | |
88 | base_type::operator=(std::move(static_cast<base_type&>(rhs))); | |
89 | allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs))); | |
90 | return *this; | |
91 | } | |
92 | ||
93 | type & operator=(type const & rhs) | |
94 | { | |
95 | base_type::operator=(static_cast<base_type const &>(rhs)); | |
96 | allocator_type::operator=(static_cast<const allocator_type&>(rhs)); | |
97 | return *this; | |
98 | } | |
99 | #endif | |
100 | }; | |
101 | }; | |
102 | ||
103 | } | |
104 | ||
105 | /** | |
106 | * \class pairing_heap | |
107 | * \brief pairing heap | |
108 | * | |
109 | * Pairing heaps are self-adjusting binary heaps. Although design and implementation are rather simple, | |
110 | * the complexity analysis is yet unsolved. For details, consult: | |
111 | * | |
112 | * Pettie, Seth (2005), "Towards a final analysis of pairing heaps", | |
113 | * Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174-183 | |
114 | * | |
115 | * The template parameter T is the type to be managed by the container. | |
116 | * The user can specify additional options and if no options are provided default options are used. | |
117 | * | |
118 | * The container supports the following options: | |
119 | * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > | |
120 | * - \c boost::heap::stable<>, defaults to \c stable<false> | |
121 | * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> | |
122 | * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > | |
123 | * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true> | |
124 | * | |
125 | * | |
126 | */ | |
127 | #ifdef BOOST_DOXYGEN_INVOKED | |
128 | template<class T, class ...Options> | |
129 | #else | |
130 | template <typename T, | |
131 | class A0 = boost::parameter::void_, | |
132 | class A1 = boost::parameter::void_, | |
133 | class A2 = boost::parameter::void_, | |
134 | class A3 = boost::parameter::void_, | |
135 | class A4 = boost::parameter::void_ | |
136 | > | |
137 | #endif | |
138 | class pairing_heap: | |
139 | private detail::make_pairing_heap_base<T, | |
140 | typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type | |
141 | >::type | |
142 | { | |
143 | typedef typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args; | |
144 | typedef detail::make_pairing_heap_base<T, bound_args> base_maker; | |
145 | typedef typename base_maker::type super_t; | |
146 | ||
147 | typedef typename super_t::internal_type internal_type; | |
148 | typedef typename super_t::size_holder_type size_holder; | |
149 | typedef typename base_maker::allocator_argument allocator_argument; | |
150 | ||
151 | private: | |
152 | template <typename Heap1, typename Heap2> | |
153 | friend struct heap_merge_emulate; | |
154 | ||
155 | #ifndef BOOST_DOXYGEN_INVOKED | |
156 | struct implementation_defined: | |
157 | detail::extract_allocator_types<typename base_maker::allocator_argument> | |
158 | { | |
159 | typedef T value_type; | |
160 | typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type; | |
161 | typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference; | |
162 | ||
163 | typedef typename base_maker::compare_argument value_compare; | |
164 | typedef typename base_maker::allocator_type allocator_type; | |
165 | ||
92f5a8d4 | 166 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae FG |
167 | typedef typename allocator_type::pointer node_pointer; |
168 | typedef typename allocator_type::const_pointer const_node_pointer; | |
92f5a8d4 TL |
169 | #else |
170 | typedef std::allocator_traits<allocator_type> allocator_traits; | |
171 | typedef typename allocator_traits::pointer node_pointer; | |
172 | typedef typename allocator_traits::const_pointer const_node_pointer; | |
173 | #endif | |
7c673cae FG |
174 | |
175 | typedef detail::heap_node_list node_list_type; | |
176 | typedef typename node_list_type::iterator node_list_iterator; | |
177 | typedef typename node_list_type::const_iterator node_list_const_iterator; | |
178 | ||
179 | typedef typename base_maker::node_type node; | |
180 | ||
181 | typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor; | |
182 | typedef typename super_t::internal_compare internal_compare; | |
183 | typedef detail::node_handle<node_pointer, super_t, reference> handle_type; | |
184 | ||
185 | typedef detail::tree_iterator<node, | |
186 | const value_type, | |
187 | allocator_type, | |
188 | value_extractor, | |
189 | detail::pointer_to_reference<node>, | |
190 | false, | |
191 | false, | |
192 | value_compare | |
193 | > iterator; | |
194 | ||
195 | typedef iterator const_iterator; | |
196 | ||
197 | typedef detail::tree_iterator<node, | |
198 | const value_type, | |
199 | allocator_type, | |
200 | value_extractor, | |
201 | detail::pointer_to_reference<node>, | |
202 | false, | |
203 | true, | |
204 | value_compare | |
205 | > ordered_iterator; | |
206 | }; | |
207 | ||
208 | typedef typename implementation_defined::node node; | |
209 | typedef typename implementation_defined::node_pointer node_pointer; | |
210 | typedef typename implementation_defined::node_list_type node_list_type; | |
211 | typedef typename implementation_defined::node_list_iterator node_list_iterator; | |
212 | typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator; | |
213 | typedef typename implementation_defined::internal_compare internal_compare; | |
214 | ||
215 | typedef boost::intrusive::list<detail::heap_node_base<true>, | |
216 | boost::intrusive::constant_time_size<false> | |
217 | > node_child_list; | |
218 | #endif | |
219 | ||
220 | public: | |
221 | typedef T value_type; | |
222 | ||
223 | typedef typename implementation_defined::size_type size_type; | |
224 | typedef typename implementation_defined::difference_type difference_type; | |
225 | typedef typename implementation_defined::value_compare value_compare; | |
226 | typedef typename implementation_defined::allocator_type allocator_type; | |
92f5a8d4 TL |
227 | #ifndef BOOST_NO_CXX11_ALLOCATOR |
228 | typedef typename implementation_defined::allocator_traits allocator_traits; | |
229 | #endif | |
7c673cae FG |
230 | typedef typename implementation_defined::reference reference; |
231 | typedef typename implementation_defined::const_reference const_reference; | |
232 | typedef typename implementation_defined::pointer pointer; | |
233 | typedef typename implementation_defined::const_pointer const_pointer; | |
234 | /// \copydoc boost::heap::priority_queue::iterator | |
235 | typedef typename implementation_defined::iterator iterator; | |
236 | typedef typename implementation_defined::const_iterator const_iterator; | |
237 | typedef typename implementation_defined::ordered_iterator ordered_iterator; | |
238 | ||
239 | typedef typename implementation_defined::handle_type handle_type; | |
240 | ||
241 | static const bool constant_time_size = super_t::constant_time_size; | |
242 | static const bool has_ordered_iterators = true; | |
243 | static const bool is_mergable = true; | |
244 | static const bool is_stable = detail::extract_stable<bound_args>::value; | |
245 | static const bool has_reserve = false; | |
246 | ||
247 | /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) | |
248 | explicit pairing_heap(value_compare const & cmp = value_compare()): | |
249 | super_t(cmp), root(NULL) | |
250 | {} | |
251 | ||
252 | /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) | |
253 | pairing_heap(pairing_heap const & rhs): | |
254 | super_t(rhs), root(NULL) | |
255 | { | |
256 | if (rhs.empty()) | |
257 | return; | |
258 | ||
259 | clone_tree(rhs); | |
260 | size_holder::set_size(rhs.get_size()); | |
261 | } | |
262 | ||
263 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
264 | /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) | |
265 | pairing_heap(pairing_heap && rhs): | |
266 | super_t(std::move(rhs)), root(rhs.root) | |
267 | { | |
268 | rhs.root = NULL; | |
269 | } | |
270 | ||
271 | /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) | |
272 | pairing_heap & operator=(pairing_heap && rhs) | |
273 | { | |
274 | super_t::operator=(std::move(rhs)); | |
275 | root = rhs.root; | |
276 | rhs.root = NULL; | |
277 | return *this; | |
278 | } | |
279 | #endif | |
280 | ||
281 | /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs) | |
282 | pairing_heap & operator=(pairing_heap const & rhs) | |
283 | { | |
284 | clear(); | |
285 | size_holder::set_size(rhs.get_size()); | |
286 | static_cast<super_t&>(*this) = rhs; | |
287 | ||
288 | clone_tree(rhs); | |
289 | return *this; | |
290 | } | |
291 | ||
292 | ~pairing_heap(void) | |
293 | { | |
294 | while (!empty()) | |
295 | pop(); | |
296 | } | |
297 | ||
298 | /// \copydoc boost::heap::priority_queue::empty | |
299 | bool empty(void) const | |
300 | { | |
301 | return root == NULL; | |
302 | } | |
303 | ||
304 | /// \copydoc boost::heap::binomial_heap::size | |
305 | size_type size(void) const | |
306 | { | |
307 | if (constant_time_size) | |
308 | return size_holder::get_size(); | |
309 | ||
310 | if (root == NULL) | |
311 | return 0; | |
312 | else | |
313 | return detail::count_nodes(root); | |
314 | } | |
315 | ||
316 | /// \copydoc boost::heap::priority_queue::max_size | |
317 | size_type max_size(void) const | |
318 | { | |
92f5a8d4 | 319 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae | 320 | return allocator_type::max_size(); |
92f5a8d4 TL |
321 | #else |
322 | const allocator_type& alloc = *this; | |
323 | return allocator_traits::max_size(alloc); | |
324 | #endif | |
7c673cae FG |
325 | } |
326 | ||
327 | /// \copydoc boost::heap::priority_queue::clear | |
328 | void clear(void) | |
329 | { | |
330 | if (empty()) | |
331 | return; | |
332 | ||
333 | root->template clear_subtree<allocator_type>(*this); | |
92f5a8d4 | 334 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae FG |
335 | root->~node(); |
336 | allocator_type::deallocate(root, 1); | |
92f5a8d4 TL |
337 | #else |
338 | allocator_type& alloc = *this; | |
339 | allocator_traits::destroy(alloc, root); | |
340 | allocator_traits::deallocate(alloc, root, 1); | |
341 | #endif | |
7c673cae FG |
342 | root = NULL; |
343 | size_holder::set_size(0); | |
344 | } | |
345 | ||
346 | /// \copydoc boost::heap::priority_queue::get_allocator | |
347 | allocator_type get_allocator(void) const | |
348 | { | |
349 | return *this; | |
350 | } | |
351 | ||
352 | /// \copydoc boost::heap::priority_queue::swap | |
353 | void swap(pairing_heap & rhs) | |
354 | { | |
355 | super_t::swap(rhs); | |
356 | std::swap(root, rhs.root); | |
357 | } | |
358 | ||
359 | ||
360 | /// \copydoc boost::heap::priority_queue::top | |
361 | const_reference top(void) const | |
362 | { | |
363 | BOOST_ASSERT(!empty()); | |
364 | ||
365 | return super_t::get_value(root->value); | |
366 | } | |
367 | ||
368 | /** | |
369 | * \b Effects: Adds a new element to the priority queue. Returns handle to element | |
370 | * | |
371 | * \cond | |
372 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
373 | * \endcond | |
374 | * | |
375 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
376 | * | |
377 | * */ | |
378 | handle_type push(value_type const & v) | |
379 | { | |
380 | size_holder::increment(); | |
381 | ||
92f5a8d4 | 382 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae | 383 | node_pointer n = allocator_type::allocate(1); |
7c673cae | 384 | new(n) node(super_t::make_node(v)); |
92f5a8d4 TL |
385 | #else |
386 | allocator_type& alloc = *this; | |
387 | node_pointer n = allocator_traits::allocate(alloc, 1); | |
388 | allocator_traits::construct(alloc, n, super_t::make_node(v)); | |
389 | #endif | |
7c673cae FG |
390 | merge_node(n); |
391 | return handle_type(n); | |
392 | } | |
393 | ||
394 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
395 | /** | |
396 | * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element. | |
397 | * | |
398 | * \cond | |
399 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
400 | * \endcond | |
401 | * | |
402 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
403 | * | |
404 | * */ | |
405 | template <class... Args> | |
406 | handle_type emplace(Args&&... args) | |
407 | { | |
408 | size_holder::increment(); | |
409 | ||
92f5a8d4 | 410 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae | 411 | node_pointer n = allocator_type::allocate(1); |
7c673cae | 412 | new(n) node(super_t::make_node(std::forward<Args>(args)...)); |
92f5a8d4 TL |
413 | #else |
414 | allocator_type& alloc = *this; | |
415 | node_pointer n = allocator_traits::allocate(alloc, 1); | |
416 | allocator_traits::construct(alloc, n, super_t::make_node(std::forward<Args>(args)...)); | |
417 | #endif | |
7c673cae FG |
418 | merge_node(n); |
419 | return handle_type(n); | |
420 | } | |
421 | #endif | |
422 | ||
423 | /** | |
424 | * \b Effects: Removes the top element from the priority queue. | |
425 | * | |
426 | * \b Complexity: Logarithmic (amortized). | |
427 | * | |
428 | * */ | |
429 | void pop(void) | |
430 | { | |
431 | BOOST_ASSERT(!empty()); | |
432 | ||
433 | erase(handle_type(root)); | |
434 | } | |
435 | ||
436 | /** | |
437 | * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. | |
438 | * | |
439 | * \cond | |
440 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
441 | * \endcond | |
442 | * | |
443 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
444 | * | |
445 | * */ | |
446 | void update (handle_type handle, const_reference v) | |
447 | { | |
448 | handle.node_->value = super_t::make_node(v); | |
449 | update(handle); | |
450 | } | |
451 | ||
452 | /** | |
453 | * \b Effects: Updates the heap after the element handled by \c handle has been changed. | |
454 | * | |
455 | * \cond | |
456 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
457 | * \endcond | |
458 | * | |
459 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
460 | * | |
461 | * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! | |
462 | * */ | |
463 | void update (handle_type handle) | |
464 | { | |
465 | node_pointer n = handle.node_; | |
466 | ||
467 | n->unlink(); | |
468 | if (!n->children.empty()) | |
469 | n = merge_nodes(n, merge_node_list(n->children)); | |
470 | ||
471 | if (n != root) | |
472 | merge_node(n); | |
473 | } | |
474 | ||
475 | /** | |
476 | * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. | |
477 | * | |
478 | * \cond | |
479 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
480 | * \endcond | |
481 | * | |
482 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
483 | * | |
484 | * \b Note: The new value is expected to be greater than the current one | |
485 | * */ | |
486 | void increase (handle_type handle, const_reference v) | |
487 | { | |
488 | update(handle, v); | |
489 | } | |
490 | ||
491 | /** | |
492 | * \b Effects: Updates the heap after the element handled by \c handle has been changed. | |
493 | * | |
494 | * \cond | |
495 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
496 | * \endcond | |
497 | * | |
498 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
499 | * | |
500 | * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! | |
501 | * */ | |
502 | void increase (handle_type handle) | |
503 | { | |
504 | update(handle); | |
505 | } | |
506 | ||
507 | /** | |
508 | * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. | |
509 | * | |
510 | * \cond | |
511 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
512 | * \endcond | |
513 | * | |
514 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
515 | * | |
516 | * \b Note: The new value is expected to be less than the current one | |
517 | * */ | |
518 | void decrease (handle_type handle, const_reference v) | |
519 | { | |
520 | update(handle, v); | |
521 | } | |
522 | ||
523 | /** | |
524 | * \b Effects: Updates the heap after the element handled by \c handle has been changed. | |
525 | * | |
526 | * \cond | |
527 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
528 | * \endcond | |
529 | * | |
530 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
531 | * | |
532 | * \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! | |
533 | * */ | |
534 | void decrease (handle_type handle) | |
535 | { | |
536 | update(handle); | |
537 | } | |
538 | ||
539 | /** | |
540 | * \b Effects: Removes the element handled by \c handle from the priority_queue. | |
541 | * | |
542 | * \cond | |
543 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
544 | * \endcond | |
545 | * | |
546 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
547 | * */ | |
548 | void erase(handle_type handle) | |
549 | { | |
550 | node_pointer n = handle.node_; | |
551 | if (n != root) { | |
552 | n->unlink(); | |
553 | if (!n->children.empty()) | |
554 | merge_node(merge_node_list(n->children)); | |
555 | } else { | |
556 | if (!n->children.empty()) | |
557 | root = merge_node_list(n->children); | |
558 | else | |
559 | root = NULL; | |
560 | } | |
561 | ||
562 | size_holder::decrement(); | |
92f5a8d4 | 563 | #ifdef BOOST_NO_CXX11_ALLOCATOR |
7c673cae FG |
564 | n->~node(); |
565 | allocator_type::deallocate(n, 1); | |
92f5a8d4 TL |
566 | #else |
567 | allocator_type& alloc = *this; | |
568 | allocator_traits::destroy(alloc, n); | |
569 | allocator_traits::deallocate(alloc, n, 1); | |
570 | #endif | |
7c673cae FG |
571 | } |
572 | ||
573 | /// \copydoc boost::heap::priority_queue::begin | |
574 | iterator begin(void) const | |
575 | { | |
576 | return iterator(root, super_t::value_comp()); | |
577 | } | |
578 | ||
579 | /// \copydoc boost::heap::priority_queue::end | |
580 | iterator end(void) const | |
581 | { | |
582 | return iterator(super_t::value_comp()); | |
583 | } | |
584 | ||
585 | /// \copydoc boost::heap::fibonacci_heap::ordered_begin | |
586 | ordered_iterator ordered_begin(void) const | |
587 | { | |
588 | return ordered_iterator(root, super_t::value_comp()); | |
589 | } | |
590 | ||
591 | /// \copydoc boost::heap::fibonacci_heap::ordered_begin | |
592 | ordered_iterator ordered_end(void) const | |
593 | { | |
594 | return ordered_iterator(NULL, super_t::value_comp()); | |
595 | } | |
596 | ||
597 | ||
598 | /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator | |
599 | static handle_type s_handle_from_iterator(iterator const & it) | |
600 | { | |
601 | node * ptr = const_cast<node *>(it.get_node()); | |
602 | return handle_type(ptr); | |
603 | } | |
604 | ||
605 | /** | |
606 | * \b Effects: Merge all elements from rhs into this | |
607 | * | |
608 | * \cond | |
609 | * \b Complexity: \f$2^2log(log(N))\f$ (amortized). | |
610 | * \endcond | |
611 | * | |
612 | * \b Complexity: 2**2*log(log(N)) (amortized). | |
613 | * | |
614 | * */ | |
615 | void merge(pairing_heap & rhs) | |
616 | { | |
617 | if (rhs.empty()) | |
618 | return; | |
619 | ||
620 | merge_node(rhs.root); | |
621 | ||
622 | size_holder::add(rhs.get_size()); | |
623 | rhs.set_size(0); | |
624 | rhs.root = NULL; | |
625 | ||
626 | super_t::set_stability_count((std::max)(super_t::get_stability_count(), | |
627 | rhs.get_stability_count())); | |
628 | rhs.set_stability_count(0); | |
629 | } | |
630 | ||
631 | /// \copydoc boost::heap::priority_queue::value_comp | |
632 | value_compare const & value_comp(void) const | |
633 | { | |
634 | return super_t::value_comp(); | |
635 | } | |
636 | ||
637 | /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const | |
638 | template <typename HeapType> | |
639 | bool operator<(HeapType const & rhs) const | |
640 | { | |
641 | return detail::heap_compare(*this, rhs); | |
642 | } | |
643 | ||
644 | /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const | |
645 | template <typename HeapType> | |
646 | bool operator>(HeapType const & rhs) const | |
647 | { | |
648 | return detail::heap_compare(rhs, *this); | |
649 | } | |
650 | ||
651 | /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const | |
652 | template <typename HeapType> | |
653 | bool operator>=(HeapType const & rhs) const | |
654 | { | |
655 | return !operator<(rhs); | |
656 | } | |
657 | ||
658 | /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const | |
659 | template <typename HeapType> | |
660 | bool operator<=(HeapType const & rhs) const | |
661 | { | |
662 | return !operator>(rhs); | |
663 | } | |
664 | ||
665 | /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const | |
666 | template <typename HeapType> | |
667 | bool operator==(HeapType const & rhs) const | |
668 | { | |
669 | return detail::heap_equality(*this, rhs); | |
670 | } | |
671 | ||
672 | /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const | |
673 | template <typename HeapType> | |
674 | bool operator!=(HeapType const & rhs) const | |
675 | { | |
676 | return !(*this == rhs); | |
677 | } | |
678 | ||
679 | private: | |
680 | #if !defined(BOOST_DOXYGEN_INVOKED) | |
681 | void clone_tree(pairing_heap const & rhs) | |
682 | { | |
683 | BOOST_HEAP_ASSERT(root == NULL); | |
684 | if (rhs.empty()) | |
685 | return; | |
686 | ||
687 | root = allocator_type::allocate(1); | |
688 | ||
689 | new(root) node(static_cast<node const &>(*rhs.root), static_cast<allocator_type&>(*this)); | |
690 | } | |
691 | ||
692 | void merge_node(node_pointer other) | |
693 | { | |
694 | BOOST_HEAP_ASSERT(other); | |
695 | if (root != NULL) | |
696 | root = merge_nodes(root, other); | |
697 | else | |
698 | root = other; | |
699 | } | |
700 | ||
701 | node_pointer merge_node_list(node_child_list & children) | |
702 | { | |
703 | BOOST_HEAP_ASSERT(!children.empty()); | |
704 | node_pointer merged = merge_first_pair(children); | |
705 | if (children.empty()) | |
706 | return merged; | |
707 | ||
708 | node_child_list node_list; | |
709 | node_list.push_back(*merged); | |
710 | ||
711 | do { | |
712 | node_pointer next_merged = merge_first_pair(children); | |
713 | node_list.push_back(*next_merged); | |
714 | } while (!children.empty()); | |
715 | ||
716 | return merge_node_list(node_list); | |
717 | } | |
718 | ||
719 | node_pointer merge_first_pair(node_child_list & children) | |
720 | { | |
721 | BOOST_HEAP_ASSERT(!children.empty()); | |
722 | node_pointer first_child = static_cast<node_pointer>(&children.front()); | |
723 | children.pop_front(); | |
724 | if (children.empty()) | |
725 | return first_child; | |
726 | ||
727 | node_pointer second_child = static_cast<node_pointer>(&children.front()); | |
728 | children.pop_front(); | |
729 | ||
730 | return merge_nodes(first_child, second_child); | |
731 | } | |
732 | ||
733 | node_pointer merge_nodes(node_pointer node1, node_pointer node2) | |
734 | { | |
735 | if (super_t::operator()(node1->value, node2->value)) | |
736 | std::swap(node1, node2); | |
737 | ||
738 | node2->unlink(); | |
739 | node1->children.push_front(*node2); | |
740 | return node1; | |
741 | } | |
742 | ||
743 | node_pointer root; | |
744 | #endif | |
745 | }; | |
746 | ||
747 | ||
748 | } /* namespace heap */ | |
749 | } /* namespace boost */ | |
750 | ||
751 | #undef BOOST_HEAP_ASSERT | |
752 | #endif /* BOOST_HEAP_PAIRING_HEAP_HPP */ |