Chris@16: // boost heap: binomial heap
Chris@16: //
Chris@16: // Copyright (C) 2010 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_BINOMIAL_HEAP_HPP
Chris@16: #define BOOST_HEAP_BINOMIAL_HEAP_HPP
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <utility>
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@16: #include <boost/heap/detail/heap_comparison.hpp>
Chris@16: #include <boost/heap/detail/heap_node.hpp>
Chris@16: #include <boost/heap/detail/stable_heap.hpp>
Chris@16: #include <boost/heap/detail/tree_iterator.hpp>
Chris@16: 
Chris@101: #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@101: #pragma once
Chris@101: #endif
Chris@101: 
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16: #define BOOST_HEAP_ASSERT BOOST_ASSERT
Chris@16: #else
Chris@16: #define BOOST_HEAP_ASSERT(expression)
Chris@16: #endif
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
Chris@16:                               boost::parameter::optional<tag::compare>,
Chris@16:                               boost::parameter::optional<tag::stable>,
Chris@16:                               boost::parameter::optional<tag::constant_time_size>,
Chris@16:                               boost::parameter::optional<tag::stability_counter_type>
Chris@16:                              > binomial_heap_signature;
Chris@16: 
Chris@16: template <typename T, typename Parspec>
Chris@16: struct make_binomial_heap_base
Chris@16: {
Chris@16:     static const bool constant_time_size = parameter::binding<Parspec,
Chris@16:                                                               tag::constant_time_size,
Chris@16:                                                               boost::mpl::true_
Chris@16:                                                              >::type::value;
Chris@16:     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type;
Chris@16:     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument;
Chris@16:     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument;
Chris@16: 
Chris@16:     typedef parent_pointing_heap_node<typename base_type::internal_type> node_type;
Chris@16: 
Chris@16:     typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
Chris@16: 
Chris@16:     struct type:
Chris@16:         base_type,
Chris@16:         allocator_type
Chris@16:     {
Chris@16:         type(compare_argument const & arg):
Chris@16:             base_type(arg)
Chris@16:         {}
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:         type(type const & rhs):
Chris@16:             base_type(rhs), allocator_type(rhs)
Chris@16:         {}
Chris@16: 
Chris@16:         type(type && rhs):
Chris@16:             base_type(std::move(static_cast<base_type&>(rhs))),
Chris@16:             allocator_type(std::move(static_cast<allocator_type&>(rhs)))
Chris@16:         {}
Chris@16: 
Chris@16:         type & operator=(type && rhs)
Chris@16:         {
Chris@16:             base_type::operator=(std::move(static_cast<base_type&>(rhs)));
Chris@16:             allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         type & operator=(type const & rhs)
Chris@16:         {
Chris@16:             base_type::operator=(static_cast<base_type const &>(rhs));
Chris@16:             allocator_type::operator=(static_cast<allocator_type const &>(rhs));
Chris@16:             return *this;
Chris@16:         }
Chris@16: #endif
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: /**
Chris@16:  * \class binomial_heap
Chris@16:  * \brief binomial heap
Chris@16:  *
Chris@16:  * The template parameter T is the type to be managed by the container.
Chris@16:  * The user can specify additional options and if no options are provided default options are used.
Chris@16:  *
Chris@16:  * The container supports the following options:
Chris@16:  * - \c boost::heap::stable<>, defaults to \c stable<false>
Chris@16:  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
Chris@16:  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
Chris@16:  * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
Chris@16:  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
Chris@16:  *
Chris@16:  */
Chris@16: #ifdef BOOST_DOXYGEN_INVOKED
Chris@16: template<class T, class ...Options>
Chris@16: #else
Chris@16: template <typename T,
Chris@16:           class A0 = boost::parameter::void_,
Chris@16:           class A1 = boost::parameter::void_,
Chris@16:           class A2 = boost::parameter::void_,
Chris@16:           class A3 = boost::parameter::void_
Chris@16:          >
Chris@16: #endif
Chris@16: class binomial_heap:
Chris@16:     private detail::make_binomial_heap_base<T,
Chris@16:                                             typename detail::binomial_heap_signature::bind<A0, A1, A2, A3>::type
Chris@16:                                            >::type
Chris@16: {
Chris@16:     typedef typename detail::binomial_heap_signature::bind<A0, A1, A2, A3>::type bound_args;
Chris@16:     typedef detail::make_binomial_heap_base<T, bound_args> base_maker;
Chris@16:     typedef typename base_maker::type super_t;
Chris@16: 
Chris@16:     typedef typename super_t::internal_type internal_type;
Chris@16:     typedef typename super_t::size_holder_type size_holder;
Chris@101:     typedef typename super_t::stability_counter_type stability_counter_type;
Chris@16:     typedef typename base_maker::allocator_argument allocator_argument;
Chris@16: 
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     friend struct heap_merge_emulate;
Chris@16: 
Chris@16: public:
Chris@16:     static const bool constant_time_size = super_t::constant_time_size;
Chris@16:     static const bool has_ordered_iterators = true;
Chris@16:     static const bool is_mergable = true;
Chris@16:     static const bool is_stable = detail::extract_stable<bound_args>::value;
Chris@16:     static const bool has_reserve = false;
Chris@16: 
Chris@16: private:
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16:     struct implementation_defined:
Chris@16:         detail::extract_allocator_types<typename base_maker::allocator_argument>
Chris@16:     {
Chris@16:         typedef T value_type;
Chris@16:         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
Chris@16:         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
Chris@16: 
Chris@16:         typedef typename base_maker::compare_argument value_compare;
Chris@16:         typedef typename base_maker::allocator_type allocator_type;
Chris@16:         typedef typename base_maker::node_type node;
Chris@16: 
Chris@16:         typedef typename allocator_type::pointer node_pointer;
Chris@16:         typedef typename allocator_type::const_pointer const_node_pointer;
Chris@16: 
Chris@16:         typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
Chris@16: 
Chris@16:         typedef typename base_maker::node_type node_type;
Chris@16: 
Chris@16:         typedef boost::intrusive::list<detail::heap_node_base<false>,
Chris@16:                                        boost::intrusive::constant_time_size<true>
Chris@16:                                        > node_list_type;
Chris@16: 
Chris@16:         typedef typename node_list_type::iterator node_list_iterator;
Chris@16:         typedef typename node_list_type::const_iterator node_list_const_iterator;
Chris@16:         typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
Chris@16: 
Chris@16:         typedef detail::recursive_tree_iterator<node_type,
Chris@16:                                         node_list_const_iterator,
Chris@16:                                         const value_type,
Chris@16:                                         value_extractor,
Chris@16:                                         detail::list_iterator_converter<node_type, node_list_type>
Chris@16:                                         > iterator;
Chris@16:         typedef iterator const_iterator;
Chris@16: 
Chris@16:         typedef detail::tree_iterator<node_type,
Chris@16:                                      const value_type,
Chris@16:                                      allocator_type,
Chris@16:                                      value_extractor,
Chris@16:                                      detail::list_iterator_converter<node_type, node_list_type>,
Chris@16:                                      true,
Chris@16:                                      true,
Chris@16:                                      value_compare
Chris@16:                                     > ordered_iterator;
Chris@16:     };
Chris@16: #endif
Chris@16: 
Chris@16: public:
Chris@16:     typedef T value_type;
Chris@16: 
Chris@16:     typedef typename implementation_defined::size_type size_type;
Chris@16:     typedef typename implementation_defined::difference_type difference_type;
Chris@16:     typedef typename implementation_defined::value_compare value_compare;
Chris@16:     typedef typename implementation_defined::allocator_type allocator_type;
Chris@16:     typedef typename implementation_defined::reference reference;
Chris@16:     typedef typename implementation_defined::const_reference const_reference;
Chris@16:     typedef typename implementation_defined::pointer pointer;
Chris@16:     typedef typename implementation_defined::const_pointer const_pointer;
Chris@16:     /// \copydoc boost::heap::priority_queue::iterator
Chris@16:     typedef typename implementation_defined::iterator iterator;
Chris@16:     typedef typename implementation_defined::const_iterator const_iterator;
Chris@16:     typedef typename implementation_defined::ordered_iterator ordered_iterator;
Chris@16: 
Chris@16:     typedef typename implementation_defined::handle_type handle_type;
Chris@16: 
Chris@16: private:
Chris@16:     typedef typename implementation_defined::node_type node_type;
Chris@16:     typedef typename implementation_defined::node_list_type node_list_type;
Chris@16:     typedef typename implementation_defined::node_pointer node_pointer;
Chris@16:     typedef typename implementation_defined::const_node_pointer const_node_pointer;
Chris@16:     typedef typename implementation_defined::node_list_iterator node_list_iterator;
Chris@16:     typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
Chris@16: 
Chris@16:     typedef typename super_t::internal_compare internal_compare;
Chris@16: 
Chris@16: public:
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
Chris@16:     explicit binomial_heap(value_compare const & cmp = value_compare()):
Chris@16:         super_t(cmp), top_element(0)
Chris@16:     {}
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
Chris@16:     binomial_heap(binomial_heap const & rhs):
Chris@16:         super_t(rhs), top_element(0)
Chris@16:     {
Chris@16:         if (rhs.empty())
Chris@16:             return;
Chris@16: 
Chris@16:         clone_forest(rhs);
Chris@16:         size_holder::set_size(rhs.get_size());
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
Chris@16:     binomial_heap & operator=(binomial_heap const & rhs)
Chris@16:     {
Chris@16:         clear();
Chris@16:         size_holder::set_size(rhs.get_size());
Chris@16:         static_cast<super_t&>(*this) = rhs;
Chris@16: 
Chris@16:         if (rhs.empty())
Chris@16:             top_element = NULL;
Chris@16:         else
Chris@16:             clone_forest(rhs);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
Chris@16:     binomial_heap(binomial_heap && rhs):
Chris@16:         super_t(std::move(rhs)), top_element(rhs.top_element)
Chris@16:     {
Chris@16:         trees.splice(trees.begin(), rhs.trees);
Chris@16:         rhs.top_element = NULL;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
Chris@16:     binomial_heap & operator=(binomial_heap && rhs)
Chris@16:     {
Chris@16:         clear();
Chris@16:         super_t::operator=(std::move(rhs));
Chris@16:         trees.splice(trees.begin(), rhs.trees);
Chris@16:         top_element = rhs.top_element;
Chris@16:         rhs.top_element = NULL;
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     ~binomial_heap(void)
Chris@16:     {
Chris@16:         clear();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::empty
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return top_element == NULL;
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Returns the number of elements contained in the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
Chris@16:      *
Chris@16:      * */
Chris@16:     size_type size(void) const
Chris@16:     {
Chris@16:         if (constant_time_size)
Chris@16:             return size_holder::get_size();
Chris@16: 
Chris@16:         if (empty())
Chris@16:             return 0;
Chris@16:         else
Chris@16:             return detail::count_list_nodes<node_type, node_list_type>(trees);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::max_size
Chris@16:     size_type max_size(void) const
Chris@16:     {
Chris@16:         return allocator_type::max_size();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::clear
Chris@16:     void clear(void)
Chris@16:     {
Chris@16:         typedef detail::node_disposer<node_type, typename node_list_type::value_type, allocator_type> disposer;
Chris@16:         trees.clear_and_dispose(disposer(*this));
Chris@16: 
Chris@16:         size_holder::set_size(0);
Chris@16:         top_element = NULL;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::get_allocator
Chris@16:     allocator_type get_allocator(void) const
Chris@16:     {
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::swap
Chris@16:     void swap(binomial_heap & rhs)
Chris@16:     {
Chris@16:         super_t::swap(rhs);
Chris@16:         std::swap(top_element, rhs.top_element);
Chris@16:         trees.swap(rhs.trees);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::top
Chris@16:     const_reference top(void) const
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16: 
Chris@16:         return super_t::get_value(top_element->value);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Adds a new element to the priority queue. Returns handle to element
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * */
Chris@16:     handle_type push(value_type const & v)
Chris@16:     {
Chris@16:         node_pointer n = allocator_type::allocate(1);
Chris@16:         new(n) node_type(super_t::make_node(v));
Chris@16: 
Chris@16:         insert_node(trees.begin(), n);
Chris@16: 
Chris@16:         if (!top_element || super_t::operator()(top_element->value, n->value))
Chris@16:             top_element = n;
Chris@16: 
Chris@16:         size_holder::increment();
Chris@16:         sanity_check();
Chris@16:         return handle_type(n);
Chris@16:     }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     /**
Chris@16:      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * */
Chris@16:     template <class... Args>
Chris@16:     handle_type emplace(Args&&... args)
Chris@16:     {
Chris@16:         node_pointer n = allocator_type::allocate(1);
Chris@16:         new(n) node_type(super_t::make_node(std::forward<Args>(args)...));
Chris@16: 
Chris@16:         insert_node(trees.begin(), n);
Chris@16: 
Chris@16:         if (!top_element || super_t::operator()(top_element->value, n->value))
Chris@16:             top_element = n;
Chris@16: 
Chris@16:         size_holder::increment();
Chris@16:         sanity_check();
Chris@16:         return handle_type(n);
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Removes the top element from the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * */
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16: 
Chris@16:         node_pointer element = top_element;
Chris@16: 
Chris@16:         trees.erase(node_list_type::s_iterator_to(*element));
Chris@16:         size_holder::decrement();
Chris@16: 
Chris@16:         if (element->child_count()) {
Chris@16:             size_type sz = (1 << element->child_count()) - 1;
Chris@101: 
Chris@16:             binomial_heap children(value_comp(), element->children, sz);
Chris@101:             if (trees.empty()) {
Chris@101:                 stability_counter_type stability_count = super_t::get_stability_count();
Chris@16:                 swap(children);
Chris@101:                 super_t::set_stability_count(stability_count);
Chris@101:             } else
Chris@16:                 merge_and_clear_nodes(children);
Chris@101: 
Chris@16:         }
Chris@16: 
Chris@16:         if (trees.empty())
Chris@16:             top_element = NULL;
Chris@16:         else
Chris@16:             update_top_element();
Chris@16: 
Chris@16:         element->~node_type();
Chris@16:         allocator_type::deallocate(element, 1);
Chris@16:         sanity_check();
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * */
Chris@16:     void update (handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         if (super_t::operator()(super_t::get_value(handle.node_->value), v))
Chris@16:             increase(handle, v);
Chris@16:         else
Chris@16:             decrease(handle, v);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Chris@16:      * */
Chris@16:     void update (handle_type handle)
Chris@16:     {
Chris@16:         node_pointer this_node = handle.node_;
Chris@16: 
Chris@16:         if (this_node->parent) {
Chris@16:             if (super_t::operator()(super_t::get_value(this_node->parent->value), super_t::get_value(this_node->value)))
Chris@16:                 increase(handle);
Chris@16:             else
Chris@16:                 decrease(handle);
Chris@16:         }
Chris@16:         else
Chris@16:             decrease(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be greater than the current one
Chris@16:      * */
Chris@16:     void increase (handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         handle.node_->value = super_t::make_node(v);
Chris@16:         increase(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Chris@16:      * */
Chris@16:     void increase (handle_type handle)
Chris@16:     {
Chris@16:         node_pointer n = handle.node_;
Chris@16:         siftup(n, *this);
Chris@16: 
Chris@16:         update_top_element();
Chris@16:         sanity_check();
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be less than the current one
Chris@16:      * */
Chris@16:     void decrease (handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         handle.node_->value = super_t::make_node(v);
Chris@16:         decrease(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \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!
Chris@16:      * */
Chris@16:     void decrease (handle_type handle)
Chris@16:     {
Chris@16:         node_pointer n = handle.node_;
Chris@16: 
Chris@16:         siftdown(n);
Chris@16: 
Chris@16:         if (n == top_element)
Chris@16:             update_top_element();
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Merge with priority queue rhs.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * */
Chris@16:     void merge(binomial_heap & rhs)
Chris@16:     {
Chris@16:         if (rhs.empty())
Chris@16:             return;
Chris@16: 
Chris@16:         if (empty()) {
Chris@16:             swap(rhs);
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         size_type new_size = size_holder::get_size() + rhs.get_size();
Chris@16:         merge_and_clear_nodes(rhs);
Chris@16: 
Chris@16:         size_holder::set_size(new_size);
Chris@16:         rhs.set_size(0);
Chris@16:         rhs.top_element = NULL;
Chris@16: 
Chris@16:         super_t::set_stability_count((std::max)(super_t::get_stability_count(),
Chris@16:                                      rhs.get_stability_count()));
Chris@16:         rhs.set_stability_count(0);
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16:     /// \copydoc boost::heap::priority_queue::begin
Chris@16:     iterator begin(void) const
Chris@16:     {
Chris@16:         return iterator(trees.begin());
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::end
Chris@16:     iterator end(void) const
Chris@16:     {
Chris@16:         return iterator(trees.end());
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
Chris@16:     ordered_iterator ordered_begin(void) const
Chris@16:     {
Chris@16:         return ordered_iterator(trees.begin(), trees.end(), top_element, super_t::value_comp());
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::fibonacci_heap::ordered_end
Chris@16:     ordered_iterator ordered_end(void) const
Chris@16:     {
Chris@16:         return ordered_iterator(NULL, super_t::value_comp());
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Removes the element handled by \c handle from the priority_queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      * */
Chris@16:     void erase(handle_type handle)
Chris@16:     {
Chris@16:         node_pointer n = handle.node_;
Chris@16:         siftup(n, force_inf());
Chris@16:         top_element = n;
Chris@16:         pop();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
Chris@16:     static handle_type s_handle_from_iterator(iterator const & it)
Chris@16:     {
Chris@16:         node_type * ptr = const_cast<node_type *>(it.get_node());
Chris@16:         return handle_type(ptr);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::value_comp
Chris@16:     value_compare const & value_comp(void) const
Chris@16:     {
Chris@16:         return super_t::value_comp();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator<(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return detail::heap_compare(*this, rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator>(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return detail::heap_compare(rhs, *this);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator>=(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return !operator<(rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator<=(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return !operator>(rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator==(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return detail::heap_equality(*this, rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator!=(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return !(*this == rhs);
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: #if !defined(BOOST_DOXYGEN_INVOKED)
Chris@16:     void merge_and_clear_nodes(binomial_heap & rhs)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT (!empty());
Chris@16:         BOOST_HEAP_ASSERT (!rhs.empty());
Chris@16: 
Chris@16:         node_list_iterator this_iterator = trees.begin();
Chris@16:         node_pointer carry_node = NULL;
Chris@16: 
Chris@16:         while (!rhs.trees.empty()) {
Chris@16:             node_pointer rhs_node = static_cast<node_pointer>(&rhs.trees.front());
Chris@16:             size_type rhs_degree = rhs_node->child_count();
Chris@16: 
Chris@16:             if (super_t::operator()(top_element->value, rhs_node->value))
Chris@16:                 top_element = rhs_node;
Chris@16: 
Chris@16:         try_again:
Chris@16:             node_pointer this_node = static_cast<node_pointer>(&*this_iterator);
Chris@16:             size_type this_degree = this_node->child_count();
Chris@16:             sorted_by_degree();
Chris@16:             rhs.sorted_by_degree();
Chris@16: 
Chris@16:             if (this_degree == rhs_degree) {
Chris@16:                 if (carry_node) {
Chris@16:                     if (carry_node->child_count() < this_degree) {
Chris@16:                         trees.insert(this_iterator, *carry_node);
Chris@16:                         carry_node = NULL;
Chris@16:                     } else {
Chris@16:                         rhs.trees.pop_front();
Chris@16:                         carry_node = merge_trees(carry_node, rhs_node);
Chris@16:                     }
Chris@16:                     ++this_iterator;
Chris@16:                 } else {
Chris@16:                     this_iterator = trees.erase(this_iterator);
Chris@16:                     rhs.trees.pop_front();
Chris@16:                     carry_node = merge_trees(this_node, rhs_node);
Chris@16:                 }
Chris@16: 
Chris@16:                 if (this_iterator == trees.end())
Chris@16:                     break;
Chris@16:                 else
Chris@16:                     continue;
Chris@16:             }
Chris@16: 
Chris@16:             if (this_degree < rhs_degree) {
Chris@16:                 if (carry_node) {
Chris@16:                     if (carry_node->child_count() < this_degree) {
Chris@16:                         trees.insert(this_iterator, *carry_node);
Chris@16:                         carry_node = NULL;
Chris@16:                         ++this_iterator;
Chris@16:                     } else if (carry_node->child_count() == rhs_degree) {
Chris@16:                         rhs.trees.pop_front();
Chris@16:                         carry_node = merge_trees(carry_node, rhs_node);
Chris@16:                         continue;
Chris@16:                     } else {
Chris@16:                         this_iterator = trees.erase(this_iterator);
Chris@16:                         carry_node = merge_trees(this_node, carry_node);
Chris@16:                     }
Chris@16:                     goto try_again;
Chris@16:                 } else {
Chris@16:                     ++this_iterator;
Chris@16:                     if (this_iterator == trees.end())
Chris@16:                         break;
Chris@16:                     goto try_again;
Chris@16:                 }
Chris@16: 
Chris@16:                 if (this_iterator == trees.end())
Chris@16:                     break;
Chris@16:                 else
Chris@16:                     continue;
Chris@16:             }
Chris@16: 
Chris@16:             if (this_degree > rhs_degree) {
Chris@16:                 rhs.trees.pop_front();
Chris@16:                 if (carry_node) {
Chris@16:                     if (carry_node->child_count() < rhs_degree) {
Chris@16:                         trees.insert(this_iterator, *carry_node);
Chris@16:                         trees.insert(this_iterator, *rhs_node);
Chris@16:                         carry_node = NULL;
Chris@16:                     } else
Chris@16:                         carry_node = merge_trees(rhs_node, carry_node);
Chris@16:                 } else
Chris@16:                     trees.insert(this_iterator, *rhs_node);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         if (!rhs.trees.empty()) {
Chris@16:             if (carry_node) {
Chris@16:                 node_list_iterator rhs_it = rhs.trees.begin();
Chris@16:                 while (static_cast<node_pointer>(&*rhs_it)->child_count() < carry_node->child_count())
Chris@16:                     ++rhs_it;
Chris@16:                 rhs.insert_node(rhs_it, carry_node);
Chris@16:                 rhs.increment();
Chris@16:                 sorted_by_degree();
Chris@16:                 rhs.sorted_by_degree();
Chris@16:                 if (trees.empty()) {
Chris@16:                     trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end());
Chris@16:                     update_top_element();
Chris@16:                 } else
Chris@16:                     merge_and_clear_nodes(rhs);
Chris@16:             } else
Chris@16:                 trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end());
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         if (carry_node)
Chris@16:             insert_node(this_iterator, carry_node);
Chris@16:     }
Chris@16: 
Chris@16:     void clone_forest(binomial_heap const & rhs)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(trees.empty());
Chris@16:         typedef typename node_type::template node_cloner<allocator_type> node_cloner;
Chris@16:         trees.clone_from(rhs.trees, node_cloner(*this, NULL), detail::nop_disposer());
Chris@16: 
Chris@16:         update_top_element();
Chris@16:     }
Chris@16: 
Chris@16:     struct force_inf
Chris@16:     {
Chris@16:         template <typename X>
Chris@16:         bool operator()(X const &, X const &) const
Chris@16:         {
Chris@16:             return false;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Compare>
Chris@16:     void siftup(node_pointer n, Compare const & cmp)
Chris@16:     {
Chris@16:         while (n->parent) {
Chris@16:             node_pointer parent = n->parent;
Chris@16:             node_pointer grand_parent = parent->parent;
Chris@16:             if (cmp(n->value, parent->value))
Chris@16:                 return;
Chris@16: 
Chris@16:             n->remove_from_parent();
Chris@16: 
Chris@16:             n->swap_children(parent);
Chris@16:             n->update_children();
Chris@16:             parent->update_children();
Chris@16: 
Chris@16:             if (grand_parent) {
Chris@16:                 parent->remove_from_parent();
Chris@16:                 grand_parent->add_child(n);
Chris@16:             } else {
Chris@16:                 node_list_iterator it = trees.erase(node_list_type::s_iterator_to(*parent));
Chris@16:                 trees.insert(it, *n);
Chris@16:             }
Chris@16:             n->add_child(parent);
Chris@16:             BOOST_HEAP_ASSERT(parent->child_count() == n->child_count());
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void siftdown(node_pointer n)
Chris@16:     {
Chris@16:         while (n->child_count()) {
Chris@16:             node_pointer max_child = detail::find_max_child<node_list_type, node_type, internal_compare>(n->children, super_t::get_internal_cmp());
Chris@16: 
Chris@16:             if (super_t::operator()(max_child->value, n->value))
Chris@16:                 return;
Chris@16: 
Chris@16:             max_child->remove_from_parent();
Chris@16: 
Chris@16:             n->swap_children(max_child);
Chris@16:             n->update_children();
Chris@16:             max_child->update_children();
Chris@16: 
Chris@16:             node_pointer parent = n->parent;
Chris@16:             if (parent) {
Chris@16:                 n->remove_from_parent();
Chris@16:                 max_child->add_child(n);
Chris@16:                 parent->add_child(max_child);
Chris@16:             } else {
Chris@16:                 node_list_iterator position = trees.erase(node_list_type::s_iterator_to(*n));
Chris@16:                 max_child->add_child(n);
Chris@16:                 trees.insert(position, *max_child);
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void insert_node(node_list_iterator it, node_pointer n)
Chris@16:     {
Chris@16:         if (it != trees.end())
Chris@16:             BOOST_HEAP_ASSERT(static_cast<node_pointer>(&*it)->child_count() >= n->child_count());
Chris@16: 
Chris@16:         while(true) {
Chris@16:             BOOST_HEAP_ASSERT(!n->is_linked());
Chris@16:             if (it == trees.end())
Chris@16:                 break;
Chris@16: 
Chris@16:             node_pointer this_node = static_cast<node_pointer>(&*it);
Chris@16:             size_type this_degree = this_node->child_count();
Chris@16:             size_type n_degree = n->child_count();
Chris@16:             if (this_degree == n_degree) {
Chris@16:                 BOOST_HEAP_ASSERT(it->is_linked());
Chris@16:                 it = trees.erase(it);
Chris@16: 
Chris@16:                 n = merge_trees(n, this_node);
Chris@16:             } else
Chris@16:                 break;
Chris@16:         }
Chris@16:         trees.insert(it, *n);
Chris@16:     }
Chris@16: 
Chris@16:     // private constructor, just used in pop()
Chris@16:     explicit binomial_heap(value_compare const & cmp, node_list_type & child_list, size_type size):
Chris@16:         super_t(cmp)
Chris@16:     {
Chris@16:         size_holder::set_size(size);
Chris@16:         if (size)
Chris@16:             top_element = static_cast<node_pointer>(&*child_list.begin()); // not correct, but we will reset it later
Chris@16:         else
Chris@16:             top_element = NULL;
Chris@16: 
Chris@16:         for (node_list_iterator it = child_list.begin(); it != child_list.end(); ++it) {
Chris@16:             node_pointer n = static_cast<node_pointer>(&*it);
Chris@16:             n->parent = NULL;
Chris@16:         }
Chris@16: 
Chris@16:         trees.splice(trees.end(), child_list, child_list.begin(), child_list.end());
Chris@16: 
Chris@16:         trees.sort(detail::cmp_by_degree<node_type>());
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer merge_trees (node_pointer node1, node_pointer node2)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(node1->child_count() == node2->child_count());
Chris@16: 
Chris@16:         if (super_t::operator()(node1->value, node2->value))
Chris@16:             std::swap(node1, node2);
Chris@16: 
Chris@16:         if (node2->parent)
Chris@16:             node2->remove_from_parent();
Chris@16: 
Chris@16:         node1->add_child(node2);
Chris@16:         return node1;
Chris@16:     }
Chris@16: 
Chris@16:     void update_top_element(void)
Chris@16:     {
Chris@16:         top_element = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp());
Chris@16:     }
Chris@16: 
Chris@16:     void sorted_by_degree(void) const
Chris@16:     {
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16:         int degree = -1;
Chris@16: 
Chris@16:         for (node_list_const_iterator it = trees.begin(); it != trees.end(); ++it) {
Chris@16:             const_node_pointer n = static_cast<const_node_pointer>(&*it);
Chris@16:             BOOST_HEAP_ASSERT(int(n->child_count()) > degree);
Chris@16:             degree = n->child_count();
Chris@16: 
Chris@16:             BOOST_HEAP_ASSERT((detail::is_heap<node_type, super_t>(n, *this)));
Chris@16: 
Chris@16:             size_type child_nodes = detail::count_nodes<node_type>(n);
Chris@16:             BOOST_HEAP_ASSERT(child_nodes == size_type(1 << static_cast<const_node_pointer>(&*it)->child_count()));
Chris@16:         }
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     void sanity_check(void)
Chris@16:     {
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16:         sorted_by_degree();
Chris@16: 
Chris@16:         if (!empty()) {
Chris@16:             node_pointer found_top = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp());
Chris@16:             BOOST_HEAP_ASSERT(top_element == found_top);
Chris@16:         }
Chris@16: 
Chris@16:         if (constant_time_size) {
Chris@16:             size_t counted = detail::count_list_nodes<node_type, node_list_type>(trees);
Chris@16:             size_t stored = size_holder::get_size();
Chris@16:             BOOST_HEAP_ASSERT(counted == stored);
Chris@16:         }
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer top_element;
Chris@16:     node_list_type trees;
Chris@16: #endif // BOOST_DOXYGEN_INVOKED
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #undef BOOST_HEAP_ASSERT
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */