1 // boost heap: skew heap
3 // Copyright (C) 2010 Tim Blechmann
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)
9 #ifndef BOOST_HEAP_SKEW_HEAP_HPP
10 #define BOOST_HEAP_SKEW_HEAP_HPP
16 #include <boost/assert.hpp>
17 #include <boost/array.hpp>
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>
24 #ifdef BOOST_HAS_PRAGMA_ONCE
28 #ifndef BOOST_DOXYGEN_INVOKED
29 #ifdef BOOST_HEAP_SANITYCHECKS
30 #define BOOST_HEAP_ASSERT BOOST_ASSERT
32 #define BOOST_HEAP_ASSERT(expression)
40 template <typename node_pointer, bool store_parent_pointer>
47 void set_parent(node_pointer parent)
49 BOOST_HEAP_ASSERT(static_cast<node_pointer>(this) != parent);
53 node_pointer get_parent(void) const
61 template <typename node_pointer>
62 struct parent_holder<node_pointer, false>
64 void set_parent(node_pointer parent)
67 node_pointer get_parent(void) const
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>
78 typedef parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer> super_t;
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;
84 skew_heap_node(value_type const & v):
90 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
91 skew_heap_node(value_type && v):
98 template <typename Alloc>
99 skew_heap_node (skew_heap_node const & rhs, Alloc & allocator, skew_heap_node * parent):
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);
108 template <typename Cloner>
109 void clone_child(int index, skew_heap_node const & rhs, Cloner & cloner)
111 if (rhs.children[index])
112 children[index] = cloner(*rhs.children[index], this);
114 children[index] = NULL;
117 template <typename Alloc>
118 void clear_subtree(Alloc & alloc)
120 node_disposer<skew_heap_node, skew_heap_node, Alloc> disposer(alloc);
121 dispose_child(children[0], disposer);
122 dispose_child(children[1], disposer);
125 template <typename Disposer>
126 void dispose_child(skew_heap_node * node, Disposer & disposer)
132 std::size_t count_children(void) const
136 ret += children[0]->count_children();
138 ret += children[1]->count_children();
143 template <typename HeapBase>
144 bool is_heap(typename HeapBase::value_compare const & cmp) const
146 for (const_child_iterator it = children.begin(); it != children.end(); ++it) {
147 const skew_heap_node * child = *it;
152 if (store_parent_pointer)
153 BOOST_HEAP_ASSERT(child->get_parent() == this);
155 if (cmp(HeapBase::get_value(value), HeapBase::get_value(child->value)) ||
156 !child->is_heap<HeapBase>(cmp))
163 boost::array<skew_heap_node*, 2> children;
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;
176 template <typename T, typename BoundArgs>
177 struct make_skew_heap_base
179 static const bool constant_time_size = parameter::binding<BoundArgs,
180 tag::constant_time_size,
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;
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;
193 typedef skew_heap_node<typename base_type::internal_type, store_parent_pointer> node_type;
195 typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
201 type(compare_argument const & arg):
205 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
207 base_type(std::move(static_cast<base_type&>(rhs))),
208 allocator_type(std::move(static_cast<allocator_type&>(rhs)))
211 type(type const & rhs):
216 type & operator=(type && rhs)
218 base_type::operator=(std::move(static_cast<base_type&>(rhs)));
219 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
223 type & operator=(type const & rhs)
225 base_type::operator=(static_cast<base_type const &>(rhs));
226 allocator_type::operator=(static_cast<allocator_type const &>(rhs));
233 } /* namespace detail */
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.
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>.
254 #ifdef BOOST_DOXYGEN_INVOKED
255 template<class T, class ...Options>
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_
268 private detail::make_skew_heap_base<T,
269 typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type
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;
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;
280 static const bool store_parent_pointer = base_maker::store_parent_pointer;
281 template <typename Heap1, typename Heap2>
282 friend struct heap_merge_emulate;
284 struct implementation_defined:
285 detail::extract_allocator_types<typename base_maker::allocator_argument>
287 typedef T value_type;
289 typedef typename base_maker::compare_argument value_compare;
290 typedef typename base_maker::allocator_type allocator_type;
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;
296 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
298 typedef boost::array<node_pointer, 2> child_list_type;
299 typedef typename child_list_type::iterator child_list_iterator;
301 typedef typename boost::mpl::if_c<false,
302 detail::recursive_tree_iterator<node,
306 detail::list_iterator_converter<node,
310 detail::tree_iterator<node,
314 detail::dereferencer<node>,
321 typedef iterator const_iterator;
323 typedef detail::tree_iterator<node,
327 detail::dereferencer<node>,
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;
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;
342 typedef T value_type;
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;
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;
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;
365 typedef typename mpl::if_c<is_mutable, typename implementation_defined::handle_type, void*>::type handle_type;
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)
372 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
373 skew_heap(skew_heap const & rhs):
374 super_t(rhs), root(0)
380 size_holder::set_size(rhs.get_size());
383 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs)
384 skew_heap & operator=(skew_heap const & rhs)
387 size_holder::set_size(rhs.get_size());
388 static_cast<super_t&>(*this) = rhs;
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)
402 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
403 skew_heap & operator=(skew_heap && rhs)
405 super_t::operator=(std::move(rhs));
418 * \b Effects: Adds a new element to the priority queue.
420 * \b Complexity: Logarithmic (amortized).
423 typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v)
425 typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper;
426 return push_helper::push(this, v);
429 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
431 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
433 * \b Complexity: Logarithmic (amortized).
436 template <typename... Args>
437 typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args)
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)...);
444 /// \copydoc boost::heap::priority_queue::empty
445 bool empty(void) const
450 /// \copydoc boost::heap::binomial_heap::size
451 size_type size(void) const
453 if (constant_time_size)
454 return size_holder::get_size();
459 return root->count_children();
462 /// \copydoc boost::heap::priority_queue::max_size
463 size_type max_size(void) const
465 return allocator_type::max_size();
468 /// \copydoc boost::heap::priority_queue::clear
474 root->template clear_subtree<allocator_type>(*this);
476 allocator_type::deallocate(root, 1);
479 size_holder::set_size(0);
482 /// \copydoc boost::heap::priority_queue::get_allocator
483 allocator_type get_allocator(void) const
488 /// \copydoc boost::heap::priority_queue::swap
489 void swap(skew_heap & rhs)
492 std::swap(root, rhs.root);
495 /// \copydoc boost::heap::priority_queue::top
496 const_reference top(void) const
498 BOOST_ASSERT(!empty());
500 return super_t::get_value(root->value);
504 * \b Effects: Removes the top element from the priority queue.
506 * \b Complexity: Logarithmic (amortized).
511 BOOST_ASSERT(!empty());
513 node_pointer top = root;
515 root = merge_children(root);
516 size_holder::decrement();
519 BOOST_HEAP_ASSERT(root->get_parent() == NULL);
521 BOOST_HEAP_ASSERT(size_holder::get_size() == 0);
524 allocator_type::deallocate(top, 1);
528 /// \copydoc boost::heap::priority_queue::begin
529 iterator begin(void) const
531 return iterator(root, super_t::value_comp());
534 /// \copydoc boost::heap::priority_queue::end
535 iterator end(void) const
540 /// \copydoc boost::heap::fibonacci_heap::ordered_begin
541 ordered_iterator ordered_begin(void) const
543 return ordered_iterator(root, super_t::value_comp());
546 /// \copydoc boost::heap::fibonacci_heap::ordered_begin
547 ordered_iterator ordered_end(void) const
549 return ordered_iterator(0, super_t::value_comp());
553 * \b Effects: Merge all elements from rhs into this
555 * \b Complexity: Logarithmic (amortized).
558 void merge(skew_heap & rhs)
563 merge_node(rhs.root);
565 size_holder::add(rhs.get_size());
570 super_t::set_stability_count((std::max)(super_t::get_stability_count(),
571 rhs.get_stability_count()));
572 rhs.set_stability_count(0);
575 /// \copydoc boost::heap::priority_queue::value_comp
576 value_compare const & value_comp(void) const
578 return super_t::value_comp();
581 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
582 template <typename HeapType>
583 bool operator<(HeapType const & rhs) const
585 return detail::heap_compare(*this, rhs);
588 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
589 template <typename HeapType>
590 bool operator>(HeapType const & rhs) const
592 return detail::heap_compare(rhs, *this);
595 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
596 template <typename HeapType>
597 bool operator>=(HeapType const & rhs) const
599 return !operator<(rhs);
602 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
603 template <typename HeapType>
604 bool operator<=(HeapType const & rhs) const
606 return !operator>(rhs);
609 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
610 template <typename HeapType>
611 bool operator==(HeapType const & rhs) const
613 return detail::heap_equality(*this, rhs);
616 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
617 template <typename HeapType>
618 bool operator!=(HeapType const & rhs) const
620 return !(*this == rhs);
624 /// \copydoc boost::heap::d_ary_heap::s_handle_from_iterator
625 static handle_type s_handle_from_iterator(iterator const & it)
627 node * ptr = const_cast<node *>(it.get_node());
628 return handle_type(ptr);
632 * \b Effects: Removes the element handled by \c handle from the priority_queue.
634 * \b Complexity: Logarithmic (amortized).
636 void erase (handle_type object)
638 BOOST_STATIC_ASSERT(is_mutable);
639 node_pointer this_node = object.node_;
641 unlink_node(this_node);
642 size_holder::decrement();
646 allocator_type::deallocate(this_node, 1);
650 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
652 * \b Complexity: Logarithmic (amortized).
655 void update (handle_type handle, const_reference v)
657 BOOST_STATIC_ASSERT(is_mutable);
658 if (super_t::operator()(super_t::get_value(handle.node_->value), v))
665 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
667 * \b Complexity: Logarithmic (amortized).
669 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
671 void update (handle_type handle)
673 BOOST_STATIC_ASSERT(is_mutable);
674 node_pointer this_node = handle.node_;
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)))
688 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
690 * \b Complexity: Logarithmic (amortized).
692 * \b Note: The new value is expected to be greater than the current one
694 void increase (handle_type handle, const_reference v)
696 BOOST_STATIC_ASSERT(is_mutable);
697 handle.node_->value = super_t::make_node(v);
702 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
704 * \b Complexity: Logarithmic (amortized).
706 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
708 void increase (handle_type handle)
710 BOOST_STATIC_ASSERT(is_mutable);
711 node_pointer this_node = handle.node_;
713 if (this_node == root)
716 node_pointer parent = this_node->get_parent();
718 if (this_node == parent->children[0])
719 parent->children[0] = NULL;
721 parent->children[1] = NULL;
723 this_node->set_parent(NULL);
724 merge_node(this_node);
728 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
730 * \b Complexity: Logarithmic (amortized).
732 * \b Note: The new value is expected to be less than the current one
734 void decrease (handle_type handle, const_reference v)
736 BOOST_STATIC_ASSERT(is_mutable);
737 handle.node_->value = super_t::make_node(v);
742 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
744 * \b Complexity: Logarithmic (amortized).
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!
748 void decrease (handle_type handle)
750 BOOST_STATIC_ASSERT(is_mutable);
751 node_pointer this_node = handle.node_;
753 unlink_node(this_node);
754 this_node->children.assign(0);
755 this_node->set_parent(NULL);
756 merge_node(this_node);
760 #if !defined(BOOST_DOXYGEN_INVOKED)
763 static void push(skew_heap * self, const_reference v)
765 self->push_internal(v);
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)
772 self->emplace_internal(std::forward<Args>(args)...);
779 static handle_type push(skew_heap * self, const_reference v)
781 return handle_type(self->push_internal(v));
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)
788 return handle_type(self->emplace_internal(std::forward<Args>(args)...));
793 node_pointer push_internal(const_reference v)
795 size_holder::increment();
797 node_pointer n = super_t::allocate(1);
798 new(n) node(super_t::make_node(v));
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)
808 size_holder::increment();
810 node_pointer n = super_t::allocate(1);
811 new(n) node(super_t::make_node(std::forward<Args>(args)...));
818 void unlink_node(node_pointer node)
820 node_pointer parent = node->get_parent();
821 node_pointer merged_children = merge_children(node);
824 if (node == parent->children[0])
825 parent->children[0] = merged_children;
827 parent->children[1] = merged_children;
830 root = merged_children;
833 void clone_tree(skew_heap const & rhs)
835 BOOST_HEAP_ASSERT(root == NULL);
839 root = allocator_type::allocate(1);
841 new(root) node(*rhs.root, static_cast<allocator_type&>(*this), NULL);
844 void merge_node(node_pointer other)
846 BOOST_HEAP_ASSERT(other);
848 root = merge_nodes(root, other, NULL);
853 node_pointer merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent)
857 node2->set_parent(new_parent);
861 node1->set_parent(new_parent);
865 node_pointer merged = merge_nodes_recursive(node1, node2, new_parent);
869 node_pointer merge_children(node_pointer node)
871 node_pointer parent = node->get_parent();
872 node_pointer merged_children = merge_nodes(node->children[0], node->children[1], parent);
874 return merged_children;
877 node_pointer merge_nodes_recursive(node_pointer node1, node_pointer node2, node_pointer new_parent)
879 if (super_t::operator()(node1->value, node2->value))
880 std::swap(node1, node2);
882 node * parent = node1;
883 node * child = node2;
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);
890 parent->children[1] = child;
891 child->set_parent(parent);
895 std::swap(parent->children[0], parent->children[1]);
896 parent->set_parent(new_parent);
900 void sanity_check(void)
902 #ifdef BOOST_HEAP_SANITYCHECKS
904 BOOST_HEAP_ASSERT( root->template is_heap<super_t>(super_t::value_comp()) );
906 if (constant_time_size) {
907 size_type stored_size = size_holder::get_size();
909 size_type counted_size;
913 counted_size = root->count_children();
915 BOOST_HEAP_ASSERT(counted_size == stored_size);
924 } /* namespace heap */
925 } /* namespace boost */
927 #undef BOOST_HEAP_ASSERT
928 #endif /* BOOST_HEAP_SKEW_HEAP_HPP */