1 // boost heap: fibonacci 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_FIBONACCI_HEAP_HPP
10 #define BOOST_HEAP_FIBONACCI_HEAP_HPP
16 #include <boost/array.hpp>
17 #include <boost/assert.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
29 #ifndef BOOST_DOXYGEN_INVOKED
30 #ifdef BOOST_HEAP_SANITYCHECKS
31 #define BOOST_HEAP_ASSERT BOOST_ASSERT
33 #define BOOST_HEAP_ASSERT(expression)
41 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
42 boost::parameter::optional<tag::compare>,
43 boost::parameter::optional<tag::stable>,
44 boost::parameter::optional<tag::constant_time_size>,
45 boost::parameter::optional<tag::stability_counter_type>
46 > fibonacci_heap_signature;
48 template <typename T, typename Parspec>
49 struct make_fibonacci_heap_base
51 static const bool constant_time_size = parameter::binding<Parspec,
52 tag::constant_time_size,
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 typedef marked_heap_node<typename base_type::internal_type> node_type;
61 typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
67 type(compare_argument const & arg):
71 type(type const & rhs):
72 base_type(static_cast<base_type const &>(rhs)),
73 allocator_type(static_cast<allocator_type const &>(rhs))
76 type & operator=(type const & rhs)
78 base_type::operator=(static_cast<base_type const &>(rhs));
79 allocator_type::operator=(static_cast<allocator_type const &>(rhs));
83 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
85 base_type(std::move(static_cast<base_type&>(rhs))),
86 allocator_type(std::move(static_cast<allocator_type&>(rhs)))
89 type & operator=(type && rhs)
91 base_type::operator=(std::move(static_cast<base_type&>(rhs)));
92 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
104 * \class fibonacci_heap
105 * \brief fibonacci heap
107 * The template parameter T is the type to be managed by the container.
108 * The user can specify additional options and if no options are provided default options are used.
110 * The container supports the following options:
111 * - \c boost::heap::stable<>, defaults to \c stable<false>
112 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
113 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
114 * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
115 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
118 #ifdef BOOST_DOXYGEN_INVOKED
119 template<class T, class ...Options>
121 template <typename T,
122 class A0 = boost::parameter::void_,
123 class A1 = boost::parameter::void_,
124 class A2 = boost::parameter::void_,
125 class A3 = boost::parameter::void_,
126 class A4 = boost::parameter::void_
129 class fibonacci_heap:
130 private detail::make_fibonacci_heap_base<T,
131 typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type
134 typedef typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args;
135 typedef detail::make_fibonacci_heap_base<T, bound_args> base_maker;
136 typedef typename base_maker::type super_t;
138 typedef typename super_t::size_holder_type size_holder;
139 typedef typename super_t::internal_type internal_type;
140 typedef typename base_maker::allocator_argument allocator_argument;
142 template <typename Heap1, typename Heap2>
143 friend struct heap_merge_emulate;
146 #ifndef BOOST_DOXYGEN_INVOKED
147 struct implementation_defined:
148 detail::extract_allocator_types<typename base_maker::allocator_argument>
150 typedef T value_type;
151 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
152 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
154 typedef typename base_maker::compare_argument value_compare;
155 typedef typename base_maker::allocator_type allocator_type;
157 typedef typename allocator_type::pointer node_pointer;
158 typedef typename allocator_type::const_pointer const_node_pointer;
160 typedef detail::heap_node_list node_list_type;
161 typedef typename node_list_type::iterator node_list_iterator;
162 typedef typename node_list_type::const_iterator node_list_const_iterator;
164 typedef typename base_maker::node_type node;
166 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
167 typedef typename super_t::internal_compare internal_compare;
168 typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
170 typedef detail::recursive_tree_iterator<node,
171 node_list_const_iterator,
174 detail::list_iterator_converter<node, node_list_type>
176 typedef iterator const_iterator;
178 typedef detail::tree_iterator<node,
182 detail::list_iterator_converter<node, node_list_type>,
189 typedef typename implementation_defined::node node;
190 typedef typename implementation_defined::node_pointer node_pointer;
191 typedef typename implementation_defined::node_list_type node_list_type;
192 typedef typename implementation_defined::node_list_iterator node_list_iterator;
193 typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
194 typedef typename implementation_defined::internal_compare internal_compare;
198 typedef T value_type;
200 typedef typename implementation_defined::size_type size_type;
201 typedef typename implementation_defined::difference_type difference_type;
202 typedef typename implementation_defined::value_compare value_compare;
203 typedef typename implementation_defined::allocator_type allocator_type;
204 typedef typename implementation_defined::reference reference;
205 typedef typename implementation_defined::const_reference const_reference;
206 typedef typename implementation_defined::pointer pointer;
207 typedef typename implementation_defined::const_pointer const_pointer;
208 /// \copydoc boost::heap::priority_queue::iterator
209 typedef typename implementation_defined::iterator iterator;
210 typedef typename implementation_defined::const_iterator const_iterator;
211 typedef typename implementation_defined::ordered_iterator ordered_iterator;
213 typedef typename implementation_defined::handle_type handle_type;
215 static const bool constant_time_size = base_maker::constant_time_size;
216 static const bool has_ordered_iterators = true;
217 static const bool is_mergable = true;
218 static const bool is_stable = detail::extract_stable<bound_args>::value;
219 static const bool has_reserve = false;
221 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
222 explicit fibonacci_heap(value_compare const & cmp = value_compare()):
223 super_t(cmp), top_element(0)
226 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
227 fibonacci_heap(fibonacci_heap const & rhs):
228 super_t(rhs), top_element(0)
234 size_holder::set_size(rhs.size());
237 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
238 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
239 fibonacci_heap(fibonacci_heap && rhs):
240 super_t(std::move(rhs)), top_element(rhs.top_element)
242 roots.splice(roots.begin(), rhs.roots);
243 rhs.top_element = NULL;
246 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
247 fibonacci_heap & operator=(fibonacci_heap && rhs)
251 super_t::operator=(std::move(rhs));
252 roots.splice(roots.begin(), rhs.roots);
253 top_element = rhs.top_element;
254 rhs.top_element = NULL;
259 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
260 fibonacci_heap & operator=(fibonacci_heap const & rhs)
263 size_holder::set_size(rhs.size());
264 static_cast<super_t&>(*this) = rhs;
273 ~fibonacci_heap(void)
278 /// \copydoc boost::heap::priority_queue::empty
279 bool empty(void) const
281 if (constant_time_size)
284 return roots.empty();
287 /// \copydoc boost::heap::priority_queue::size
288 size_type size(void) const
290 if (constant_time_size)
291 return size_holder::get_size();
296 return detail::count_list_nodes<node, node_list_type>(roots);
299 /// \copydoc boost::heap::priority_queue::max_size
300 size_type max_size(void) const
302 return allocator_type::max_size();
305 /// \copydoc boost::heap::priority_queue::clear
308 typedef detail::node_disposer<node, typename node_list_type::value_type, allocator_type> disposer;
309 roots.clear_and_dispose(disposer(*this));
311 size_holder::set_size(0);
315 /// \copydoc boost::heap::priority_queue::get_allocator
316 allocator_type get_allocator(void) const
321 /// \copydoc boost::heap::priority_queue::swap
322 void swap(fibonacci_heap & rhs)
325 std::swap(top_element, rhs.top_element);
326 roots.swap(rhs.roots);
330 /// \copydoc boost::heap::priority_queue::top
331 value_type const & top(void) const
333 BOOST_ASSERT(!empty());
335 return super_t::get_value(top_element->value);
339 * \b Effects: Adds a new element to the priority queue. Returns handle to element
341 * \b Complexity: Constant.
343 * \b Note: Does not invalidate iterators.
346 handle_type push(value_type const & v)
348 size_holder::increment();
350 node_pointer n = allocator_type::allocate(1);
352 new(n) node(super_t::make_node(v));
353 roots.push_front(*n);
355 if (!top_element || super_t::operator()(top_element->value, n->value))
357 return handle_type(n);
360 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
362 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
364 * \b Complexity: Constant.
366 * \b Note: Does not invalidate iterators.
369 template <class... Args>
370 handle_type emplace(Args&&... args)
372 size_holder::increment();
374 node_pointer n = allocator_type::allocate(1);
376 new(n) node(super_t::make_node(std::forward<Args>(args)...));
377 roots.push_front(*n);
379 if (!top_element || super_t::operator()(top_element->value, n->value))
381 return handle_type(n);
386 * \b Effects: Removes the top element from the priority queue.
388 * \b Complexity: Logarithmic (amortized). Linear (worst case).
393 BOOST_ASSERT(!empty());
395 node_pointer element = top_element;
396 roots.erase(node_list_type::s_iterator_to(*element));
398 finish_erase_or_pop(element);
402 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
404 * \b Complexity: Logarithmic if current value < v, Constant otherwise.
407 void update (handle_type handle, const_reference v)
409 if (super_t::operator()(super_t::get_value(handle.node_->value), v))
415 /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference)
417 * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
418 * the iterator to the object referred to by the handle.
420 void update_lazy(handle_type handle, const_reference v)
422 handle.node_->value = super_t::make_node(v);
427 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
429 * \b Complexity: Logarithmic.
431 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
433 void update (handle_type handle)
439 /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle)
441 * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
442 * the iterator to the object referred to by the handle.
444 void update_lazy (handle_type handle)
446 node_pointer n = handle.node_;
447 node_pointer parent = n->get_parent();
451 roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
453 add_children_to_root(n);
455 if (super_t::operator()(top_element->value, n->value))
461 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
463 * \b Complexity: Constant.
465 * \b Note: The new value is expected to be greater than the current one
467 void increase (handle_type handle, const_reference v)
469 handle.node_->value = super_t::make_node(v);
474 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
476 * \b Complexity: Constant.
478 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
480 void increase (handle_type handle)
482 node_pointer n = handle.node_;
485 if (super_t::operator()(n->get_parent()->value, n->value)) {
486 node_pointer parent = n->get_parent();
488 cascading_cut(parent);
492 if (super_t::operator()(top_element->value, n->value)) {
499 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
501 * \b Complexity: Logarithmic.
503 * \b Note: The new value is expected to be less than the current one
505 void decrease (handle_type handle, const_reference v)
507 handle.node_->value = super_t::make_node(v);
512 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
514 * \b Complexity: Logarithmic.
516 * \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!
518 void decrease (handle_type handle)
524 * \b Effects: Removes the element handled by \c handle from the priority_queue.
526 * \b Complexity: Logarithmic.
528 void erase(handle_type const & handle)
530 node_pointer element = handle.node_;
531 node_pointer parent = element->get_parent();
534 parent->children.erase(node_list_type::s_iterator_to(*element));
536 roots.erase(node_list_type::s_iterator_to(*element));
538 finish_erase_or_pop(element);
541 /// \copydoc boost::heap::priority_queue::begin
542 iterator begin(void) const
544 return iterator(roots.begin());
547 /// \copydoc boost::heap::priority_queue::end
548 iterator end(void) const
550 return iterator(roots.end());
555 * \b Effects: Returns an ordered iterator to the first element contained in the priority queue.
557 * \b Note: Ordered iterators traverse the priority queue in heap order.
559 ordered_iterator ordered_begin(void) const
561 return ordered_iterator(roots.begin(), roots.end(), top_element, super_t::value_comp());
565 * \b Effects: Returns an ordered iterator to the end of the priority queue.
567 * \b Note: Ordered iterators traverse the priority queue in heap order.
569 ordered_iterator ordered_end(void) const
571 return ordered_iterator(NULL, super_t::value_comp());
575 * \b Effects: Merge with priority queue rhs.
577 * \b Complexity: Constant.
580 void merge(fibonacci_heap & rhs)
582 size_holder::add(rhs.get_size());
585 (rhs.top_element && super_t::operator()(top_element->value, rhs.top_element->value)))
586 top_element = rhs.top_element;
588 roots.splice(roots.end(), rhs.roots);
590 rhs.top_element = NULL;
593 super_t::set_stability_count((std::max)(super_t::get_stability_count(),
594 rhs.get_stability_count()));
595 rhs.set_stability_count(0);
598 /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
599 static handle_type s_handle_from_iterator(iterator const & it)
601 node * ptr = const_cast<node *>(it.get_node());
602 return handle_type(ptr);
605 /// \copydoc boost::heap::priority_queue::value_comp
606 value_compare const & value_comp(void) const
608 return super_t::value_comp();
611 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
612 template <typename HeapType>
613 bool operator<(HeapType const & rhs) const
615 return detail::heap_compare(*this, rhs);
618 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
619 template <typename HeapType>
620 bool operator>(HeapType const & rhs) const
622 return detail::heap_compare(rhs, *this);
625 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
626 template <typename HeapType>
627 bool operator>=(HeapType const & rhs) const
629 return !operator<(rhs);
632 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
633 template <typename HeapType>
634 bool operator<=(HeapType const & rhs) const
636 return !operator>(rhs);
639 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
640 template <typename HeapType>
641 bool operator==(HeapType const & rhs) const
643 return detail::heap_equality(*this, rhs);
646 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
647 template <typename HeapType>
648 bool operator!=(HeapType const & rhs) const
650 return !(*this == rhs);
654 #if !defined(BOOST_DOXYGEN_INVOKED)
655 void clone_forest(fibonacci_heap const & rhs)
657 BOOST_HEAP_ASSERT(roots.empty());
658 typedef typename node::template node_cloner<allocator_type> node_cloner;
659 roots.clone_from(rhs.roots, node_cloner(*this, NULL), detail::nop_disposer());
661 top_element = detail::find_max_child<node_list_type, node, internal_compare>(roots, super_t::get_internal_cmp());
664 void cut(node_pointer n)
666 node_pointer parent = n->get_parent();
667 roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
672 void cascading_cut(node_pointer n)
674 node_pointer parent = n->get_parent();
681 cascading_cut(parent);
686 void add_children_to_root(node_pointer n)
688 for (node_list_iterator it = n->children.begin(); it != n->children.end(); ++it) {
689 node_pointer child = static_cast<node_pointer>(&*it);
693 roots.splice(roots.end(), n->children);
696 void consolidate(void)
701 static const size_type max_log2 = sizeof(size_type) * 8;
702 boost::array<node_pointer, max_log2> aux;
705 node_list_iterator it = roots.begin();
706 top_element = static_cast<node_pointer>(&*it);
709 node_pointer n = static_cast<node_pointer>(&*it);
711 size_type node_rank = n->child_count();
713 if (aux[node_rank] == NULL)
717 node_pointer other = aux[node_rank];
718 if (super_t::operator()(n->value, other->value))
722 n->children.splice(n->children.end(), other->parent->children, node_list_type::s_iterator_to(*other));
724 n->children.splice(n->children.end(), roots, node_list_type::s_iterator_to(*other));
728 aux[node_rank] = NULL;
729 node_rank = n->child_count();
730 } while (aux[node_rank] != NULL);
734 if (!super_t::operator()(n->value, top_element->value))
737 while (it != roots.end());
740 void finish_erase_or_pop(node_pointer erased_node)
742 add_children_to_root(erased_node);
744 erased_node->~node();
745 allocator_type::deallocate(erased_node, 1);
747 size_holder::decrement();
754 mutable node_pointer top_element;
755 node_list_type roots;
759 } /* namespace heap */
760 } /* namespace boost */
762 #undef BOOST_HEAP_ASSERT
764 #endif /* BOOST_HEAP_FIBONACCI_HEAP_HPP */