Chris@16: // boost heap: skew 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_SKEW_HEAP_HPP
Chris@16: #define BOOST_HEAP_SKEW_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: #include <boost/array.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@16: 
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: template <typename node_pointer, bool store_parent_pointer>
Chris@16: struct parent_holder
Chris@16: {
Chris@16:     parent_holder(void):
Chris@16:         parent_(NULL)
Chris@16:     {}
Chris@16: 
Chris@16:     void set_parent(node_pointer parent)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(static_cast<node_pointer>(this) != parent);
Chris@16:         parent_ = parent;
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer get_parent(void) const
Chris@16:     {
Chris@16:         return parent_;
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer parent_;
Chris@16: };
Chris@16: 
Chris@16: template <typename node_pointer>
Chris@16: struct parent_holder<node_pointer, false>
Chris@16: {
Chris@16:     void set_parent(node_pointer parent)
Chris@16:     {}
Chris@16: 
Chris@16:     node_pointer get_parent(void) const
Chris@16:     {
Chris@16:         return NULL;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename value_type, bool store_parent_pointer>
Chris@16: struct skew_heap_node:
Chris@16:     parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer>
Chris@16: {
Chris@16:     typedef parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer> super_t;
Chris@16: 
Chris@16:     typedef boost::array<skew_heap_node*, 2> child_list_type;
Chris@16:     typedef typename child_list_type::iterator child_iterator;
Chris@16:     typedef typename child_list_type::const_iterator const_child_iterator;
Chris@16: 
Chris@16:     skew_heap_node(value_type const & v):
Chris@16:         value(v)
Chris@16:     {
Chris@16:         children.assign(0);
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     skew_heap_node(value_type && v):
Chris@16:         value(v)
Chris@16:     {
Chris@16:         children.assign(0);
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     skew_heap_node (skew_heap_node const & rhs, Alloc & allocator, skew_heap_node * parent):
Chris@16:         value(rhs.value)
Chris@16:     {
Chris@16:         super_t::set_parent(parent);
Chris@16:         node_cloner<skew_heap_node, skew_heap_node, Alloc> cloner(allocator);
Chris@16:         clone_child(0, rhs, cloner);
Chris@16:         clone_child(1, rhs, cloner);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Cloner>
Chris@16:     void clone_child(int index, skew_heap_node const & rhs, Cloner & cloner)
Chris@16:     {
Chris@16:         if (rhs.children[index])
Chris@16:             children[index] = cloner(*rhs.children[index], this);
Chris@16:         else
Chris@16:             children[index] = NULL;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     void clear_subtree(Alloc & alloc)
Chris@16:     {
Chris@16:         node_disposer<skew_heap_node, skew_heap_node, Alloc> disposer(alloc);
Chris@16:         dispose_child(children[0], disposer);
Chris@16:         dispose_child(children[1], disposer);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Disposer>
Chris@16:     void dispose_child(skew_heap_node * node, Disposer & disposer)
Chris@16:     {
Chris@16:         if (node)
Chris@16:             disposer(node);
Chris@16:     }
Chris@16: 
Chris@16:     std::size_t count_children(void) const
Chris@16:     {
Chris@16:         size_t ret = 1;
Chris@16:         if (children[0])
Chris@16:             ret += children[0]->count_children();
Chris@16:         if (children[1])
Chris@16:             ret += children[1]->count_children();
Chris@16: 
Chris@16:         return ret;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename HeapBase>
Chris@16:     bool is_heap(typename HeapBase::value_compare const & cmp) const
Chris@16:     {
Chris@16:         for (const_child_iterator it = children.begin(); it != children.end(); ++it) {
Chris@16:             const skew_heap_node * child = *it;
Chris@16: 
Chris@16:             if (child == NULL)
Chris@16:                 continue;
Chris@16: 
Chris@16:             if (store_parent_pointer)
Chris@16:                 BOOST_HEAP_ASSERT(child->get_parent() == this);
Chris@16: 
Chris@16:             if (cmp(HeapBase::get_value(value), HeapBase::get_value(child->value)) ||
Chris@16:                 !child->is_heap<HeapBase>(cmp))
Chris@16:                 return false;
Chris@16:         }
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:     value_type value;
Chris@16:     boost::array<skew_heap_node*, 2> children;
Chris@16: };
Chris@16: 
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::store_parent_pointer>,
Chris@16:                               boost::parameter::optional<tag::stability_counter_type>,
Chris@16:                               boost::parameter::optional<tag::constant_time_size>,
Chris@16:                               boost::parameter::optional<tag::mutable_>
Chris@16:                              > skew_heap_signature;
Chris@16: 
Chris@16: template <typename T, typename BoundArgs>
Chris@16: struct make_skew_heap_base
Chris@16: {
Chris@16:     static const bool constant_time_size = parameter::binding<BoundArgs,
Chris@16:                                                               tag::constant_time_size,
Chris@16:                                                               boost::mpl::true_
Chris@16:                                                              >::type::value;
Chris@16: 
Chris@16:     typedef typename make_heap_base<T, BoundArgs, constant_time_size>::type base_type;
Chris@16:     typedef typename make_heap_base<T, BoundArgs, constant_time_size>::allocator_argument allocator_argument;
Chris@16:     typedef typename make_heap_base<T, BoundArgs, constant_time_size>::compare_argument compare_argument;
Chris@16: 
Chris@16:     static const bool is_mutable = extract_mutable<BoundArgs>::value;
Chris@16:     static const bool store_parent_pointer = parameter::binding<BoundArgs,
Chris@16:                                                               tag::store_parent_pointer,
Chris@16:                                                               boost::mpl::false_>::type::value || is_mutable;
Chris@16: 
Chris@16:     typedef skew_heap_node<typename base_type::internal_type, store_parent_pointer> 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 && 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(type const & rhs):
Chris@16:             base_type(rhs),
Chris@16:             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: } /* namespace detail */
Chris@16: 
Chris@16: /**
Chris@16:  * \class skew_heap
Chris@16:  * \brief skew heap
Chris@16:  *
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::compare<>, defaults to \c compare<std::less<T> >
Chris@16:  * - \c boost::heap::stable<>, defaults to \c stable<false>
Chris@16:  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_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::store_parent_pointer<>, defaults to \c store_parent_pointer<true>. Maintaining a parent pointer adds some
Chris@16:  *   maintenance and size overhead, but iterating a heap is more efficient.
Chris@16:  * - \c boost::heap::mutable<>, defaults to \c mutable<false>.
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:           class A4 = boost::parameter::void_,
Chris@16:           class A5 = boost::parameter::void_,
Chris@16:           class A6 = boost::parameter::void_
Chris@16:          >
Chris@16: #endif
Chris@16: class skew_heap:
Chris@16:     private detail::make_skew_heap_base<T,
Chris@16:                                           typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type
Chris@16:                                          >::type
Chris@16: {
Chris@16:     typedef typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type bound_args;
Chris@16:     typedef detail::make_skew_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@16:     typedef typename base_maker::allocator_argument allocator_argument;
Chris@16: 
Chris@16:     static const bool store_parent_pointer = base_maker::store_parent_pointer;
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     friend struct heap_merge_emulate;
Chris@16: 
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: 
Chris@16:         typedef typename base_maker::compare_argument value_compare;
Chris@16:         typedef typename base_maker::allocator_type allocator_type;
Chris@16: 
Chris@16:         typedef typename base_maker::node_type node;
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::value_extractor<value_type, internal_type, super_t> value_extractor;
Chris@16: 
Chris@16:         typedef boost::array<node_pointer, 2> child_list_type;
Chris@16:         typedef typename child_list_type::iterator child_list_iterator;
Chris@16: 
Chris@16:         typedef typename boost::mpl::if_c<false,
Chris@16:                                         detail::recursive_tree_iterator<node,
Chris@16:                                                                         child_list_iterator,
Chris@16:                                                                         const value_type,
Chris@16:                                                                         value_extractor,
Chris@16:                                                                         detail::list_iterator_converter<node,
Chris@16:                                                                                                         child_list_type
Chris@16:                                                                                                        >
Chris@16:                                                                        >,
Chris@16:                                         detail::tree_iterator<node,
Chris@16:                                                               const value_type,
Chris@16:                                                               allocator_type,
Chris@16:                                                               value_extractor,
Chris@16:                                                               detail::dereferencer<node>,
Chris@16:                                                               true,
Chris@16:                                                               false,
Chris@16:                                                               value_compare
Chris@16:                                                     >
Chris@16:                                         >::type iterator;
Chris@16: 
Chris@16:         typedef iterator const_iterator;
Chris@16: 
Chris@16:         typedef detail::tree_iterator<node,
Chris@16:                                       const value_type,
Chris@16:                                       allocator_type,
Chris@16:                                       value_extractor,
Chris@16:                                       detail::dereferencer<node>,
Chris@16:                                       true,
Chris@16:                                       true,
Chris@16:                                       value_compare
Chris@16:                                      > ordered_iterator;
Chris@16: 
Chris@16:         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
Chris@16:         typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
Chris@16:     };
Chris@16: 
Chris@16:     typedef typename implementation_defined::value_extractor value_extractor;
Chris@16:     typedef typename implementation_defined::node node;
Chris@16:     typedef typename implementation_defined::node_pointer node_pointer;
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: 
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:     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:     static const bool is_mutable = detail::extract_mutable<bound_args>::value;
Chris@16: 
Chris@16:     typedef typename mpl::if_c<is_mutable, typename implementation_defined::handle_type, void*>::type handle_type;
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
Chris@16:     explicit skew_heap(value_compare const & cmp = value_compare()):
Chris@16:         super_t(cmp), root(NULL)
Chris@16:     {}
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
Chris@16:     skew_heap(skew_heap const & rhs):
Chris@16:         super_t(rhs), root(0)
Chris@16:     {
Chris@16:         if (rhs.empty())
Chris@16:             return;
Chris@16: 
Chris@16:         clone_tree(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 & rhs)
Chris@16:     skew_heap & operator=(skew_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:         clone_tree(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:     skew_heap(skew_heap && rhs):
Chris@16:         super_t(std::move(rhs)), root(rhs.root)
Chris@16:     {
Chris@16:         rhs.root = NULL;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
Chris@16:     skew_heap & operator=(skew_heap && rhs)
Chris@16:     {
Chris@16:         super_t::operator=(std::move(rhs));
Chris@16:         root = rhs.root;
Chris@16:         rhs.root = NULL;
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     ~skew_heap(void)
Chris@16:     {
Chris@16:         clear();
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Adds a new element to the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic (amortized).
Chris@16:      *
Chris@16:      * */
Chris@16:     typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v)
Chris@16:     {
Chris@16:         typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper;
Chris@16:         return push_helper::push(this, v);
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.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic (amortized).
Chris@16:      *
Chris@16:      * */
Chris@16:     template <typename... Args>
Chris@16:     typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args)
Chris@16:     {
Chris@16:         typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper;
Chris@16:         return push_helper::emplace(this, std::forward<Args>(args)...);
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::empty
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return root == NULL;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::binomial_heap::size
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 (root == NULL)
Chris@16:             return 0;
Chris@16:         else
Chris@16:             return root->count_children();
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:         if (empty())
Chris@16:             return;
Chris@16: 
Chris@16:         root->template clear_subtree<allocator_type>(*this);
Chris@16:         root->~node();
Chris@16:         allocator_type::deallocate(root, 1);
Chris@16: 
Chris@16:         root = NULL;
Chris@16:         size_holder::set_size(0);
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(skew_heap & rhs)
Chris@16:     {
Chris@16:         super_t::swap(rhs);
Chris@16:         std::swap(root, rhs.root);
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(root->value);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Removes the top element from the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic (amortized).
Chris@16:      *
Chris@16:      * */
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16: 
Chris@16:         node_pointer top = root;
Chris@16: 
Chris@16:         root = merge_children(root);
Chris@16:         size_holder::decrement();
Chris@16: 
Chris@16:         if (root)
Chris@16:             BOOST_HEAP_ASSERT(root->get_parent() == NULL);
Chris@16:         else
Chris@16:             BOOST_HEAP_ASSERT(size_holder::get_size() == 0);
Chris@16: 
Chris@16:         top->~node();
Chris@16:         allocator_type::deallocate(top, 1);
Chris@16:         sanity_check();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::begin
Chris@16:     iterator begin(void) const
Chris@16:     {
Chris@16:         return iterator(root, super_t::value_comp());
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::end
Chris@16:     iterator end(void) const
Chris@16:     {
Chris@16:         return iterator();
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(root, super_t::value_comp());
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
Chris@16:     ordered_iterator ordered_end(void) const
Chris@16:     {
Chris@16:         return ordered_iterator(0, super_t::value_comp());
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Merge all elements from rhs into this
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic (amortized).
Chris@16:      *
Chris@16:      * */
Chris@16:     void merge(skew_heap & rhs)
Chris@16:     {
Chris@16:         if (rhs.empty())
Chris@16:             return;
Chris@16: 
Chris@16:         merge_node(rhs.root);
Chris@16: 
Chris@16:         size_holder::add(rhs.get_size());
Chris@16:         rhs.set_size(0);
Chris@16:         rhs.root = NULL;
Chris@16:         sanity_check();
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:     /// \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: 
Chris@16:     /// \copydoc boost::heap::d_ary_heap::s_handle_from_iterator
Chris@16:     static handle_type s_handle_from_iterator(iterator const & it)
Chris@16:     {
Chris@16:         node * ptr = const_cast<node *>(it.get_node());
Chris@16:         return handle_type(ptr);
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 (amortized).
Chris@16:      * */
Chris@16:     void erase (handle_type object)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         node_pointer this_node = object.node_;
Chris@16: 
Chris@16:         unlink_node(this_node);
Chris@16:         size_holder::decrement();
Chris@16: 
Chris@16:         sanity_check();
Chris@16:         this_node->~node();
Chris@16:         allocator_type::deallocate(this_node, 1);
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 (amortized).
Chris@16:      *
Chris@16:      * */
Chris@16:     void update (handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
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 (amortized).
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:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         node_pointer this_node = handle.node_;
Chris@16: 
Chris@16:         if (this_node->get_parent()) {
Chris@16:             if (super_t::operator()(super_t::get_value(this_node->get_parent()->value),
Chris@16:                                     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 (amortized).
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:         BOOST_STATIC_ASSERT(is_mutable);
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 (amortized).
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:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         node_pointer this_node = handle.node_;
Chris@16: 
Chris@16:         if (this_node == root)
Chris@16:             return;
Chris@16: 
Chris@16:         node_pointer parent = this_node->get_parent();
Chris@16: 
Chris@16:         if (this_node == parent->children[0])
Chris@16:             parent->children[0] = NULL;
Chris@16:         else
Chris@16:             parent->children[1] = NULL;
Chris@16: 
Chris@16:         this_node->set_parent(NULL);
Chris@16:         merge_node(this_node);
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 (amortized).
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:         BOOST_STATIC_ASSERT(is_mutable);
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 (amortized).
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:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         node_pointer this_node = handle.node_;
Chris@16: 
Chris@16:         unlink_node(this_node);
Chris@16:         this_node->children.assign(0);
Chris@16:         this_node->set_parent(NULL);
Chris@16:         merge_node(this_node);
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: #if !defined(BOOST_DOXYGEN_INVOKED)
Chris@16:     struct push_void
Chris@16:     {
Chris@16:         static void push(skew_heap * self, const_reference v)
Chris@16:         {
Chris@16:             self->push_internal(v);
Chris@16:         }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:         template <class... Args>
Chris@16:         static void emplace(skew_heap * self, Args&&... args)
Chris@16:         {
Chris@16:             self->emplace_internal(std::forward<Args>(args)...);
Chris@16:         }
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     struct push_handle
Chris@16:     {
Chris@16:         static handle_type push(skew_heap * self, const_reference v)
Chris@16:         {
Chris@16:             return handle_type(self->push_internal(v));
Chris@16:         }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:         template <class... Args>
Chris@16:         static handle_type emplace(skew_heap * self, Args&&... args)
Chris@16:         {
Chris@16:             return handle_type(self->emplace_internal(std::forward<Args>(args)...));
Chris@16:         }
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     node_pointer push_internal(const_reference v)
Chris@16:     {
Chris@16:         size_holder::increment();
Chris@16: 
Chris@16:         node_pointer n = super_t::allocate(1);
Chris@16:         new(n) node(super_t::make_node(v));
Chris@16: 
Chris@16:         merge_node(n);
Chris@16:         return n;
Chris@16:     }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     template <class... Args>
Chris@16:     node_pointer emplace_internal(Args&&... args)
Chris@16:     {
Chris@16:         size_holder::increment();
Chris@16: 
Chris@16:         node_pointer n = super_t::allocate(1);
Chris@16:         new(n) node(super_t::make_node(std::forward<Args>(args)...));
Chris@16: 
Chris@16:         merge_node(n);
Chris@16:         return n;
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     void unlink_node(node_pointer node)
Chris@16:     {
Chris@16:         node_pointer parent = node->get_parent();
Chris@16:         node_pointer merged_children = merge_children(node);
Chris@16: 
Chris@16:         if (parent) {
Chris@16:             if (node == parent->children[0])
Chris@16:                 parent->children[0] = merged_children;
Chris@16:             else
Chris@16:                 parent->children[1] = merged_children;
Chris@16:         }
Chris@16:         else
Chris@16:             root = merged_children;
Chris@16:     }
Chris@16: 
Chris@16:     void clone_tree(skew_heap const & rhs)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(root == NULL);
Chris@16:         if (rhs.empty())
Chris@16:             return;
Chris@16: 
Chris@16:         root = allocator_type::allocate(1);
Chris@16: 
Chris@16:         new(root) node(*rhs.root, static_cast<allocator_type&>(*this), NULL);
Chris@16:     }
Chris@16: 
Chris@16:     void merge_node(node_pointer other)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(other);
Chris@16:         if (root != NULL)
Chris@16:             root = merge_nodes(root, other, NULL);
Chris@16:         else
Chris@16:             root = other;
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent)
Chris@16:     {
Chris@16:         if (node1 == NULL) {
Chris@16:             if (node2)
Chris@16:                 node2->set_parent(new_parent);
Chris@16:             return node2;
Chris@16:         }
Chris@16:         if (node2 == NULL) {
Chris@16:             node1->set_parent(new_parent);
Chris@16:             return node1;
Chris@16:         }
Chris@16: 
Chris@16:         node_pointer merged = merge_nodes_recursive(node1, node2, new_parent);
Chris@16:         return merged;
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer merge_children(node_pointer node)
Chris@16:     {
Chris@16:         node_pointer parent = node->get_parent();
Chris@16:         node_pointer merged_children = merge_nodes(node->children[0], node->children[1], parent);
Chris@16: 
Chris@16:         return merged_children;
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer merge_nodes_recursive(node_pointer node1, node_pointer node2, node_pointer new_parent)
Chris@16:     {
Chris@16:         if (super_t::operator()(node1->value, node2->value))
Chris@16:             std::swap(node1, node2);
Chris@16: 
Chris@16:         node * parent = node1;
Chris@16:         node * child = node2;
Chris@16: 
Chris@16:         if (parent->children[1]) {
Chris@16:             node * merged = merge_nodes(parent->children[1], child, parent);
Chris@16:             parent->children[1] = merged;
Chris@16:             merged->set_parent(parent);
Chris@16:         } else {
Chris@16:             parent->children[1] = child;
Chris@16:             child->set_parent(parent);
Chris@16:         }
Chris@16: 
Chris@16: 
Chris@16:         std::swap(parent->children[0], parent->children[1]);
Chris@16:         parent->set_parent(new_parent);
Chris@16:         return parent;
Chris@16:     }
Chris@16: 
Chris@16:     void sanity_check(void)
Chris@16:     {
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16:         if (root)
Chris@16:             BOOST_HEAP_ASSERT( root->template is_heap<super_t>(super_t::value_comp()) );
Chris@16: 
Chris@16:         if (constant_time_size) {
Chris@16:             size_type stored_size = size_holder::get_size();
Chris@16: 
Chris@16:             size_type counted_size;
Chris@16:             if (root == NULL)
Chris@16:                 counted_size = 0;
Chris@16:             else
Chris@16:                 counted_size = root->count_children();
Chris@16: 
Chris@16:             BOOST_HEAP_ASSERT(counted_size == stored_size);
Chris@16:         }
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     node_pointer root;
Chris@16: #endif
Chris@16: };
Chris@16: 
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #undef BOOST_HEAP_ASSERT
Chris@16: #endif /* BOOST_HEAP_SKEW_HEAP_HPP */