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