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