Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r75821 - in trunk: boost/heap boost/heap/detail doc doc/src libs/heap libs/heap/doc libs/heap/examples libs/heap/test libs/heap/tools
From: tim_at_[hidden]
Date: 2011-12-06 05:17:39

Next message: tim_at_[hidden]: "[Boost-commit] svn:boost r75822 - trunk/status"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r75820 - in trunk: boost/math/special_functions boost/math/special_functions/detail boost/math/tools libs/math/test"

Author: timblechmann
Date: 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
New Revision: 75821
URL: http://svn.boost.org/trac/boost/changeset/75821

Log:
heap: import boost.heap

Added:
   trunk/boost/heap/
   trunk/boost/heap/binomial_heap.hpp (contents, props changed)
   trunk/boost/heap/d_ary_heap.hpp (contents, props changed)
   trunk/boost/heap/detail/
   trunk/boost/heap/detail/heap_comparison.hpp (contents, props changed)
   trunk/boost/heap/detail/heap_node.hpp (contents, props changed)
   trunk/boost/heap/detail/ilog2.hpp (contents, props changed)
   trunk/boost/heap/detail/mutable_heap.hpp (contents, props changed)
   trunk/boost/heap/detail/ordered_adaptor_iterator.hpp (contents, props changed)
   trunk/boost/heap/detail/stable_heap.hpp (contents, props changed)
   trunk/boost/heap/detail/tree_iterator.hpp (contents, props changed)
   trunk/boost/heap/fibonacci_heap.hpp (contents, props changed)
   trunk/boost/heap/heap_concepts.hpp (contents, props changed)
   trunk/boost/heap/heap_merge.hpp (contents, props changed)
   trunk/boost/heap/pairing_heap.hpp (contents, props changed)
   trunk/boost/heap/policies.hpp (contents, props changed)
   trunk/boost/heap/priority_queue.hpp (contents, props changed)
   trunk/boost/heap/skew_heap.hpp (contents, props changed)
   trunk/libs/heap/
   trunk/libs/heap/doc/
   trunk/libs/heap/doc/Jamfile.v2 (contents, props changed)
   trunk/libs/heap/doc/heap.qbk (contents, props changed)
   trunk/libs/heap/examples/
   trunk/libs/heap/examples/interface.cpp (contents, props changed)
   trunk/libs/heap/test/
   trunk/libs/heap/test/Jamfile.v2 (contents, props changed)
   trunk/libs/heap/test/binomial_heap_test.cpp (contents, props changed)
   trunk/libs/heap/test/common_heap_tests.hpp (contents, props changed)
   trunk/libs/heap/test/d_ary_heap_test.cpp (contents, props changed)
   trunk/libs/heap/test/fibonacci_heap_test.cpp (contents, props changed)
   trunk/libs/heap/test/merge_heap_tests.hpp (contents, props changed)
   trunk/libs/heap/test/mutable_heap_test.cpp (contents, props changed)
   trunk/libs/heap/test/mutable_heap_tests.hpp (contents, props changed)
   trunk/libs/heap/test/pairing_heap_tests.cpp (contents, props changed)
   trunk/libs/heap/test/priority_queue_test.cpp (contents, props changed)
   trunk/libs/heap/test/skew_heap_test.cpp (contents, props changed)
   trunk/libs/heap/test/stable_heap_tests.hpp (contents, props changed)
   trunk/libs/heap/tools/
   trunk/libs/heap/tools/heap_benchmarks.hpp (contents, props changed)
   trunk/libs/heap/tools/high_resolution_timer.hpp (contents, props changed)
   trunk/libs/heap/tools/throughput_benchmarks.cpp (contents, props changed)
Text files modified:
   trunk/doc/Jamfile.v2 | 3 +++
   trunk/doc/src/boost.xml | 2 ++
   2 files changed, 5 insertions(+), 0 deletions(-)

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

Added: trunk/boost/heap/d_ary_heap.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/d_ary_heap.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,812 @@
+// // boost heap: d-ary heap as containter adaptor
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_D_ARY_HEAP_HPP
+#define BOOST_HEAP_D_ARY_HEAP_HPP
+
+#include <algorithm>
+#include <vector>
+
+#include <boost/assert.hpp>
+
+#include <boost/mem_fn.hpp>
+#include <boost/heap/detail/heap_comparison.hpp>
+#include <boost/heap/detail/ordered_adaptor_iterator.hpp>
+#include <boost/heap/detail/stable_heap.hpp>
+#include <boost/heap/detail/mutable_heap.hpp>
+
+#ifndef BOOST_DOXYGEN_INVOKED
+#ifdef BOOST_HEAP_SANITYCHECKS
+#define BOOST_HEAP_ASSERT BOOST_ASSERT
+#else
+#define BOOST_HEAP_ASSERT(expression)
+#endif
+#endif
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+template <typename T>
+struct nop_index_updater
+{
+ void operator()(T &, std::size_t) const
+ {}
+
+ template <typename U>
+ struct rebind {
+ typedef nop_index_updater<U> other;
+ };
+};
+
+typedef parameter::parameters<boost::parameter::required<tag::arity>,
+ boost::parameter::optional<tag::allocator>,
+ boost::parameter::optional<tag::compare>,
+ boost::parameter::optional<tag::stable>,
+ boost::parameter::optional<tag::stability_counter_type>,
+ boost::parameter::optional<tag::constant_time_size>
+ > d_ary_heap_signature;
+
+
+/* base class for d-ary heap */
+template <typename T,
+ class BoundArgs,
+ class IndexUpdater>
+class d_ary_heap:
+ private make_heap_base<T, BoundArgs, false>::type
+{
+ typedef make_heap_base<T, BoundArgs, false> heap_base_maker;
+
+ typedef typename heap_base_maker::type super_t;
+ typedef typename super_t::internal_type internal_type;
+
+ typedef std::vector<internal_type, typename heap_base_maker::allocator_argument> container_type;
+ typedef typename container_type::const_iterator container_iterator;
+
+ typedef typename IndexUpdater::template rebind<internal_type>::other index_updater;
+
+ container_type q_;
+
+ static const unsigned int D = parameter::binding<BoundArgs, tag::arity>::type::value;
+
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+ struct implementation_defined:
+ extract_allocator_types<typename heap_base_maker::allocator_argument>
+ {
+ typedef T value_type;
+ typedef typename detail::extract_allocator_types<typename heap_base_maker::allocator_argument>::size_type size_type;
+
+ typedef typename heap_base_maker::compare_argument value_compare;
+ typedef typename heap_base_maker::allocator_argument allocator_type;
+
+ struct ordered_iterator_dispatcher
+ {
+ static size_type max_index(const d_ary_heap * heap)
+ {
+ return heap->q_.size() - 1;
+ }
+
+ static bool is_leaf(const d_ary_heap * heap, size_type index)
+ {
+ return !heap->not_leaf(index);
+ }
+
+ static std::pair<size_type, size_type> get_child_nodes(const d_ary_heap * heap, size_type index)
+ {
+ BOOST_HEAP_ASSERT(!is_leaf(heap, index));
+ return std::make_pair(d_ary_heap::first_child_index(index),
+ heap->last_child_index(index));
+ }
+
+ static internal_type const & get_internal_value(const d_ary_heap * heap, size_type index)
+ {
+ return heap->q_[index];
+ }
+
+ static value_type const & get_value(internal_type const & arg)
+ {
+ return super_t::get_value(arg);
+ }
+ };
+
+ typedef detail::ordered_adaptor_iterator<const value_type,
+ internal_type,
+ d_ary_heap,
+ allocator_type,
+ typename super_t::internal_compare,
+ ordered_iterator_dispatcher
+ > ordered_iterator;
+
+ typedef detail::stable_heap_iterator<const value_type, container_iterator, super_t> iterator;
+ typedef iterator const_iterator;
+ typedef void * handle_type;
+
+ };
+
+ typedef typename implementation_defined::ordered_iterator_dispatcher ordered_iterator_dispatcher;
+
+public:
+ typedef T value_type;
+
+ typedef typename implementation_defined::size_type size_type;
+ typedef typename implementation_defined::difference_type difference_type;
+ typedef typename implementation_defined::value_compare value_compare;
+ typedef typename implementation_defined::allocator_type allocator_type;
+ typedef typename implementation_defined::reference reference;
+ typedef typename implementation_defined::const_reference const_reference;
+ typedef typename implementation_defined::pointer pointer;
+ typedef typename implementation_defined::const_pointer const_pointer;
+ typedef typename implementation_defined::iterator iterator;
+ typedef typename implementation_defined::const_iterator const_iterator;
+ typedef typename implementation_defined::ordered_iterator ordered_iterator;
+ typedef typename implementation_defined::handle_type handle_type;
+
+ static const bool is_stable = extract_stable<BoundArgs>::value;
+
+ explicit d_ary_heap(value_compare const & cmp = value_compare()):
+ super_t(cmp)
+ {}
+
+ d_ary_heap(d_ary_heap const & rhs):
+ super_t(rhs), q_(rhs.q_)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ d_ary_heap(d_ary_heap && rhs):
+ super_t(std::move(rhs)), q_(std::move(rhs.q_))
+ {}
+
+ d_ary_heap & operator=(d_ary_heap && rhs)
+ {
+ super_t::operator=(std::move(rhs));
+ q_ = std::move(rhs.q_);
+ return *this;
+ }
+#endif
+
+ d_ary_heap & operator=(d_ary_heap const & rhs)
+ {
+ static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs);
+ q_ = rhs.q_;
+ return *this;
+ }
+
+ bool empty(void) const
+ {
+ return q_.empty();
+ }
+
+ size_type size(void) const
+ {
+ return q_.size();
+ }
+
+ size_type max_size(void) const
+ {
+ return q_.max_size();
+ }
+
+ void clear(void)
+ {
+ q_.clear();
+ }
+
+ allocator_type get_allocator(void) const
+ {
+ return q_.get_allocator();
+ }
+
+ value_type const & top(void) const
+ {
+ BOOST_ASSERT(!empty());
+ return super_t::get_value(q_.front());
+ }
+
+ void push(value_type const & v)
+ {
+ q_.push_back(super_t::make_node(v));
+ reset_index(size() - 1, size() - 1);
+ siftup(q_.size() - 1);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ void emplace(Args&&... args)
+ {
+ q_.emplace_back(super_t::make_node(std::forward<Args>(args)...));
+ reset_index(size() - 1, size() - 1);
+ siftup(q_.size() - 1);
+ }
+#endif
+ void pop(void)
+ {
+ BOOST_ASSERT(!empty());
+ std::swap(q_.front(), q_.back());
+ q_.pop_back();
+
+ if (q_.empty())
+ return;
+
+ reset_index(0, 0);
+ siftdown(0);
+ }
+
+ void swap(d_ary_heap & rhs)
+ {
+ super_t::swap(rhs);
+ q_.swap(rhs.q_);
+ }
+
+ iterator begin(void) const
+ {
+ return iterator(q_.begin());
+ }
+
+ iterator end(void) const
+ {
+ return iterator(q_.end());
+ }
+
+ ordered_iterator ordered_begin(void) const
+ {
+ return ordered_iterator(0, this, super_t::get_internal_cmp());
+ }
+
+ ordered_iterator ordered_end(void) const
+ {
+ return ordered_iterator(size(), this, super_t::get_internal_cmp());
+ }
+
+ void reserve (size_type element_count)
+ {
+ q_.reserve(element_count);
+ }
+
+ value_compare const & value_comp(void) const
+ {
+ return super_t::value_comp();
+ }
+
+private:
+ void reset_index(size_type index, size_type new_index)
+ {
+ BOOST_HEAP_ASSERT(index < q_.size());
+ index_updater()(q_[index], new_index);
+ }
+
+ void siftdown(size_type index)
+ {
+ while (not_leaf(index)) {
+ size_type max_child_index = top_child_index(index);
+ if (!super_t::operator()(q_[max_child_index], q_[index])) {
+ reset_index(index, max_child_index);
+ reset_index(max_child_index, index);
+ std::swap(q_[max_child_index], q_[index]);
+ index = max_child_index;
+ }
+ else
+ return;
+ }
+ }
+
+ /* returns new index */
+ void siftup(size_type index)
+ {
+ while (index != 0) {
+ size_type parent = parent_index(index);
+
+ if (super_t::operator()(q_[parent], q_[index])) {
+ reset_index(index, parent);
+ reset_index(parent, index);
+ std::swap(q_[parent], q_[index]);
+ index = parent;
+ }
+ else
+ return;
+ }
+ }
+
+ bool not_leaf(size_type index) const
+ {
+ const size_t first_child = first_child_index(index);
+ return first_child < q_.size();
+ }
+
+ size_type top_child_index(size_type index) const
+ {
+ // invariant: index is not a leaf, so the iterator range is not empty
+
+ const size_t first_index = first_child_index(index);
+ typedef typename container_type::const_iterator container_iterator;
+
+ const container_iterator first_child = q_.begin() + first_index;
+ const container_iterator end = q_.end();
+
+ const size_type max_elements = std::distance(first_child, end);
+
+ const container_iterator last_child = (max_elements > D) ? first_child + D
+ : end;
+
+ const container_iterator min_element = std::max_element(first_child, last_child, static_cast<super_t const &>(*this));
+
+ return min_element - q_.begin();
+ }
+
+ static size_type parent_index(size_type index)
+ {
+ return (index - 1) / D;
+ }
+
+ static size_type first_child_index(size_type index)
+ {
+ return index * D + 1;
+ }
+
+ size_type last_child_index(size_type index) const
+ {
+ typedef typename container_type::const_iterator container_iterator;
+ const size_t first_index = first_child_index(index);
+
+ const size_type last_index = std::min(first_index + D - 1, size() - 1);
+
+ return last_index;
+ }
+
+ template<typename U,
+ typename V,
+ typename W,
+ typename X>
+ struct rebind {
+ typedef d_ary_heap<U, typename d_ary_heap_signature::bind<boost::heap::stable<heap_base_maker::is_stable>,
+ boost::heap::stability_counter_type<typename heap_base_maker::stability_counter_type>,
+ boost::heap::arity<D>,
+ boost::heap::compare<V>,
+ boost::heap::allocator<W>
+ >::type,
+ X
+ > other;
+ };
+
+ template <class U> friend class priority_queue_mutable_wrapper;
+
+ void update(size_type index)
+ {
+ if (index == 0) {
+ siftdown(index);
+ return;
+ }
+ size_type parent = parent_index(index);
+
+ if (super_t::operator()(q_[parent], q_[index]))
+ siftup(index);
+ else
+ siftdown(index);
+ }
+
+ void erase(size_type index)
+ {
+ while (index != 0)
+ {
+ size_type parent = parent_index(index);
+
+ reset_index(index, parent);
+ reset_index(parent, index);
+ std::swap(q_[parent], q_[index]);
+ index = parent;
+ }
+ pop();
+ }
+
+ void increase(size_type index)
+ {
+ siftup(index);
+ }
+
+ void decrease(size_type index)
+ {
+ siftdown(index);
+ }
+};
+
+
+template <typename T, typename BoundArgs>
+struct select_dary_heap
+{
+ static const bool is_mutable = extract_mutable<BoundArgs>::value;
+
+ typedef typename mpl::if_c< is_mutable,
+ priority_queue_mutable_wrapper<d_ary_heap<T, BoundArgs, nop_index_updater<T> > >,
+ d_ary_heap<T, BoundArgs, nop_index_updater<T> >
+ >::type type;
+};
+
+} /* namespace detail */
+
+
+
+/**
+ * \class d_ary_heap
+ * \brief d-ary heap class
+ *
+ * This class implements an immutable priority queue. Internally, the d-ary heap is represented
+ * as dynamically sized array (std::vector), that directly stores the values.
+ *
+ * The template parameter T is the type to be managed by the container.
+ * The user can specify additional options and if no options are provided default options are used.
+ *
+ * The container supports the following options:
+ * - \c boost::heap::arity<>, required
+ * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
+ * - \c boost::heap::stable<>, defaults to \c stable<false>
+ * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
+ * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
+ * - \c boost::heap::mutable<>, defaults to \c mutable<false>
+ *
+ */
+#ifdef BOOST_DOXYGEN_INVOKED
+template<class T, class ...Options>
+#else
+template <typename T,
+ class A0 = boost::parameter::void_,
+ class A1 = boost::parameter::void_,
+ class A2 = boost::parameter::void_,
+ class A3 = boost::parameter::void_,
+ class A4 = boost::parameter::void_,
+ class A5 = boost::parameter::void_
+ >
+#endif
+class d_ary_heap:
+ public detail::select_dary_heap<T, typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type>::type
+{
+ typedef typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type bound_args;
+ typedef typename detail::select_dary_heap<T, bound_args>::type super_t;
+
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+#ifndef BOOST_DOXYGEN_INVOKED
+ static const bool is_mutable = detail::extract_mutable<bound_args>::value;
+
+#define BOOST_HEAP_TYPEDEF_FROM_SUPER_T(NAME) \
+ typedef typename super_t::NAME NAME;
+
+ struct implementation_defined
+ {
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(size_type)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(difference_type)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(value_compare)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(allocator_type)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(reference)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_reference)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(pointer)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_pointer)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(iterator)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_iterator)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(ordered_iterator)
+ BOOST_HEAP_TYPEDEF_FROM_SUPER_T(handle_type)
+ };
+#undef BOOST_HEAP_TYPEDEF_FROM_SUPER_T
+
+#endif
+public:
+ static const bool constant_time_size = true;
+ static const bool has_ordered_iterators = true;
+ static const bool is_mergable = false;
+ static const bool has_reserve = true;
+ static const bool is_stable = super_t::is_stable;
+
+ typedef T value_type;
+ typedef typename implementation_defined::size_type size_type;
+ typedef typename implementation_defined::difference_type difference_type;
+ typedef typename implementation_defined::value_compare value_compare;
+ typedef typename implementation_defined::allocator_type allocator_type;
+ typedef typename implementation_defined::reference reference;
+ typedef typename implementation_defined::const_reference const_reference;
+ typedef typename implementation_defined::pointer pointer;
+ typedef typename implementation_defined::const_pointer const_pointer;
+ /// \copydoc boost::heap::priority_queue::iterator
+ typedef typename implementation_defined::iterator iterator;
+ typedef typename implementation_defined::const_iterator const_iterator;
+ typedef typename implementation_defined::ordered_iterator ordered_iterator;
+ typedef typename implementation_defined::handle_type handle_type;
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
+ explicit d_ary_heap(value_compare const & cmp = value_compare()):
+ super_t(cmp)
+ {}
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
+ d_ary_heap(d_ary_heap const & rhs):
+ super_t(rhs)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
+ d_ary_heap(d_ary_heap && rhs):
+ super_t(std::move(rhs))
+ {}
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
+ d_ary_heap & operator=(d_ary_heap && rhs)
+ {
+ super_t::operator=(std::move(rhs));
+ return *this;
+ }
+#endif
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
+ d_ary_heap & operator=(d_ary_heap const & rhs)
+ {
+ super_t::operator=(rhs);
+ return *this;
+ }
+
+ /// \copydoc boost::heap::priority_queue::empty
+ bool empty(void) const
+ {
+ return super_t::empty();
+ }
+
+ /// \copydoc boost::heap::priority_queue::size
+ size_type size(void) const
+ {
+ return super_t::size();
+ }
+
+ /// \copydoc boost::heap::priority_queue::max_size
+ size_type max_size(void) const
+ {
+ return super_t::max_size();
+ }
+
+ /// \copydoc boost::heap::priority_queue::clear
+ void clear(void)
+ {
+ super_t::clear();
+ }
+
+ /// \copydoc boost::heap::priority_queue::get_allocator
+ allocator_type get_allocator(void) const
+ {
+ return super_t::get_allocator();
+ }
+
+ /// \copydoc boost::heap::priority_queue::top
+ value_type const & top(void) const
+ {
+ return super_t::top();
+ }
+
+ /// \copydoc boost::heap::priority_queue::push
+ typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v)
+ {
+ return super_t::push(v);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ /// \copydoc boost::heap::priority_queue::emplace
+ template <class... Args>
+ typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args)
+ {
+ return super_t::emplace(std::forward<Args>(args)...);
+ }
+#endif
+
+ /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<(HeapType const & rhs) const
+ {
+ return detail::heap_compare(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>(HeapType const & rhs) const
+ {
+ return detail::heap_compare(rhs, *this);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>=(HeapType const & rhs) const
+ {
+ return !operator<(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<=(HeapType const & rhs) const
+ {
+ return !operator>(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator==(HeapType const & rhs) const
+ {
+ return detail::heap_equality(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator!=(HeapType const & rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void update(handle_type handle, const_reference v)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::update(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void update(handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::update(handle);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be greater than the current one
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void increase(handle_type handle, const_reference v)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::increase(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void increase(handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::increase(handle);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be less than the current one
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void decrease(handle_type handle, const_reference v)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::decrease(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \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!
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void decrease(handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::decrease(handle);
+ }
+
+ /**
+ * \b Effects: Removes the element handled by \c handle from the priority_queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ void erase(handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ super_t::erase(handle);
+ }
+
+ /**
+ * \b Effects: Casts an iterator to a node handle.
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Requirement: data structure must be configured as mutable
+ * */
+ static handle_type s_handle_from_iterator(iterator const & it)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ return super_t::handle_type(it);
+ }
+
+ /// \copydoc boost::heap::priority_queue::pop
+ void pop(void)
+ {
+ super_t::pop();
+ }
+
+ /// \copydoc boost::heap::priority_queue::swap
+ void swap(d_ary_heap & rhs)
+ {
+ super_t::swap(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::begin
+ iterator begin(void) const
+ {
+ return super_t::begin();
+ }
+
+ /// \copydoc boost::heap::priority_queue::end
+ iterator end(void) const
+ {
+ return super_t::end();
+ }
+
+ /// \copydoc boost::heap::fibonacci_heap::ordered_begin
+ ordered_iterator ordered_begin(void) const
+ {
+ return super_t::ordered_begin();
+ }
+
+ /// \copydoc boost::heap::fibonacci_heap::ordered_end
+ ordered_iterator ordered_end(void) const
+ {
+ return super_t::ordered_end();
+ }
+
+ /// \copydoc boost::heap::priority_queue::reserve
+ void reserve (size_type element_count)
+ {
+ super_t::reserve(element_count);
+ }
+
+ /// \copydoc boost::heap::priority_queue::value_comp
+ value_compare const & value_comp(void) const
+ {
+ return super_t::value_comp();
+ }
+};
+
+} /* namespace heap */
+} /* namespace boost */
+
+#undef BOOST_HEAP_ASSERT
+
+#endif /* BOOST_HEAP_D_ARY_HEAP_HPP */

Added: trunk/boost/heap/detail/heap_comparison.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/heap_comparison.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,245 @@
+// boost heap: heap node helper classes
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
+#define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
+
+#include <boost/assert.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/concept/assert.hpp>
+#include <boost/heap/heap_concepts.hpp>
+
+#ifdef BOOST_HEAP_SANITYCHECKS
+#define BOOST_HEAP_ASSERT BOOST_ASSERT
+#else
+#define BOOST_HEAP_ASSERT(expression)
+#endif
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+template <typename Heap1, typename Heap2>
+bool value_equality(Heap1 const & lhs, Heap2 const & rhs,
+ typename Heap1::value_type lval, typename Heap2::value_type rval)
+{
+ typename Heap1::value_compare const & cmp = lhs.value_comp();
+ bool ret = !(cmp(lval, rval)) && !(cmp(rval, lval));
+
+ // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
+ BOOST_ASSERT((ret == (!(rhs.value_comp()(lval, rval)) && !(rhs.value_comp()(rval, lval)))));
+
+ return ret;
+}
+
+template <typename Heap1, typename Heap2>
+bool value_compare(Heap1 const & lhs, Heap2 const & rhs,
+ typename Heap1::value_type lval, typename Heap2::value_type rval)
+{
+ typename Heap1::value_compare const & cmp = lhs.value_comp();
+ bool ret = cmp(lval, rval);
+
+ // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
+ BOOST_ASSERT((ret == rhs.value_comp()(lval, rval)));
+ return ret;
+}
+
+struct heap_equivalence_copy
+{
+ template <typename Heap1, typename Heap2>
+ bool operator()(Heap1 const & lhs, Heap2 const & rhs)
+ {
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
+
+ // if this assertion is triggered, the value_compare types are incompatible
+ BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
+
+ if (Heap1::constant_time_size && Heap2::constant_time_size)
+ if (lhs.size() != rhs.size())
+ return false;
+
+ if (lhs.empty() && rhs.empty())
+ return true;
+
+ Heap1 lhs_copy(lhs);
+ Heap2 rhs_copy(rhs);
+
+ for (;;) {
+ if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
+ return false;
+
+ lhs_copy.pop();
+ rhs_copy.pop();
+
+ if (lhs_copy.empty() && rhs_copy.empty())
+ return true;
+
+ if (lhs_copy.empty())
+ return false;
+
+ if (rhs_copy.empty())
+ return false;
+ }
+ }
+};
+
+
+struct heap_equivalence_iteration
+{
+ template <typename Heap1, typename Heap2>
+ bool operator()(Heap1 const & lhs, Heap2 const & rhs)
+ {
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
+
+ // if this assertion is triggered, the value_compare types are incompatible
+ BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
+
+ if (Heap1::constant_time_size && Heap2::constant_time_size)
+ if (lhs.size() != rhs.size())
+ return false;
+
+ if (lhs.empty() && rhs.empty())
+ return true;
+
+ typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
+ typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
+ typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
+ typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
+ for(;;) {
+ if (!value_equality(lhs, rhs, *it1, *it2))
+ return false;
+
+ ++it1;
+ ++it2;
+
+ if (it1 == it1_end && it2 == it2_end)
+ return true;
+
+ if (it1 == it1_end || it2 == it2_end)
+ return false;
+ }
+ }
+};
+
+
+template <typename Heap1,
+ typename Heap2
+ >
+bool heap_equality(Heap1 const & lhs, Heap2 const & rhs)
+{
+ const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
+
+ typedef typename boost::mpl::if_c<use_ordered_iterators,
+ heap_equivalence_iteration,
+ heap_equivalence_copy
+ >::type equivalence_check;
+
+ equivalence_check check;
+ return check(lhs, rhs);
+}
+
+
+struct heap_compare_iteration
+{
+ template <typename Heap1,
+ typename Heap2
+ >
+ bool operator()(Heap1 const & lhs, Heap2 const & rhs)
+ {
+ typename Heap1::size_type left_size = lhs.size();
+ typename Heap2::size_type right_size = rhs.size();
+ if (left_size < right_size)
+ return true;
+
+ if (left_size > right_size)
+ return false;
+
+ typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
+ typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
+ typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
+ typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
+ for(;;) {
+ if (value_compare(lhs, rhs, *it1, *it2))
+ return true;
+
+ if (value_compare(lhs, rhs, *it2, *it1))
+ return false;
+
+ ++it1;
+ ++it2;
+
+ if (it1 == it1_end && it2 == it2_end)
+ return true;
+
+ if (it1 == it1_end || it2 == it2_end)
+ return false;
+ }
+ }
+};
+
+struct heap_compare_copy
+{
+ template <typename Heap1,
+ typename Heap2
+ >
+ bool operator()(Heap1 const & lhs, Heap2 const & rhs)
+ {
+ typename Heap1::size_type left_size = lhs.size();
+ typename Heap2::size_type right_size = rhs.size();
+ if (left_size < right_size)
+ return true;
+
+ if (left_size > right_size)
+ return false;
+
+ Heap1 lhs_copy(lhs);
+ Heap2 rhs_copy(rhs);
+
+ for (;;) {
+ if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
+ return true;
+
+ if (value_compare(lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top()))
+ return false;
+
+ lhs_copy.pop();
+ rhs_copy.pop();
+
+ if (lhs_copy.empty() && rhs_copy.empty())
+ return false;
+ }
+ }
+};
+
+template <typename Heap1,
+ typename Heap2
+ >
+bool heap_compare(Heap1 const & lhs, Heap2 const & rhs)
+{
+ const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
+
+ typedef typename boost::mpl::if_c<use_ordered_iterators,
+ heap_compare_iteration,
+ heap_compare_copy
+ >::type compare_check;
+
+ compare_check check;
+ return check(lhs, rhs);
+}
+
+
+} /* namespace detail */
+} /* namespace heap */
+} /* namespace boost */
+
+
+#undef BOOST_HEAP_ASSERT
+
+#endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP

Added: trunk/boost/heap/detail/heap_node.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/heap_node.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,366 @@
+// boost heap: heap node helper classes
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_DETAIL_HEAP_NODE_HPP
+#define BOOST_HEAP_DETAIL_HEAP_NODE_HPP
+
+#include <boost/assert.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/intrusive/list.hpp>
+#include <boost/mpl/if.hpp>
+
+#ifdef BOOST_HEAP_SANITYCHECKS
+#define BOOST_HEAP_ASSERT BOOST_ASSERT
+#else
+#define BOOST_HEAP_ASSERT(expression)
+#endif
+
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+namespace bi = boost::intrusive;
+namespace mpl = boost::mpl;
+
+template <bool auto_unlink = false>
+struct heap_node_base:
+ bi::list_base_hook<typename mpl::if_c<auto_unlink,
+ bi::link_mode<bi::auto_unlink>,
+ bi::link_mode<bi::safe_link>
+ >::type
+ >
+{};
+
+typedef bi::list<heap_node_base<false> > heap_node_list;
+
+struct nop_disposer
+{
+ template <typename T>
+ void operator()(T * n)
+ {
+ BOOST_HEAP_ASSERT(false);
+ }
+};
+
+template <typename Node, typename HeapBase>
+bool is_heap(const Node * n, typename HeapBase::value_compare const & cmp)
+{
+ for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
+ Node const & this_node = static_cast<Node const &>(*it);
+ const Node * child = static_cast<const Node*>(&this_node);
+
+ if (cmp(HeapBase::get_value(n->value), HeapBase::get_value(child->value)) ||
+ !is_heap<Node, HeapBase>(child, cmp))
+ return false;
+ }
+ return true;
+}
+
+template <typename Node>
+std::size_t count_nodes(const Node * n);
+
+template <typename Node, typename List>
+std::size_t count_list_nodes(List const & node_list)
+{
+ std::size_t ret = 0;
+
+ for (typename List::const_iterator it = node_list.begin(); it != node_list.end(); ++it) {
+ const Node * child = static_cast<const Node*>(&*it);
+ ret += count_nodes<Node>(child);
+ }
+ return ret;
+}
+
+template <typename Node>
+std::size_t count_nodes(const Node * n)
+{
+ return 1 + count_list_nodes<Node, typename Node::child_list>(n->children);
+}
+
+
+/* node cloner
+ *
+ * Requires `Clone Constructor':
+ * template <typename Alloc>
+ * Node::Node(Node const &, Alloc &)
+ *
+ * template <typename Alloc>
+ * Node::Node(Node const &, Alloc &, Node * parent)
+ *
+ * */
+template <typename Node,
+ typename NodeBase,
+ typename Alloc>
+struct node_cloner
+{
+ node_cloner(Alloc & allocator):
+ allocator(allocator)
+ {}
+
+ Node * operator() (NodeBase const & node)
+ {
+ Node * ret = allocator.allocate(1);
+ new (ret) Node(static_cast<Node const &>(node), allocator);
+ return ret;
+ }
+
+ Node * operator() (NodeBase const & node, Node * parent)
+ {
+ Node * ret = allocator.allocate(1);
+ new (ret) Node(static_cast<Node const &>(node), allocator, parent);
+ return ret;
+ }
+
+private:
+ Alloc & allocator;
+};
+
+/* node disposer
+ *
+ * Requirements:
+ * Node::clear_subtree(Alloc &) clears the subtree via allocator
+ *
+ * */
+template <typename Node,
+ typename NodeBase,
+ typename Alloc>
+struct node_disposer
+{
+ typedef typename Alloc::pointer node_pointer;
+
+ node_disposer(Alloc & alloc):
+ alloc_(alloc)
+ {}
+
+ void operator()(NodeBase * base)
+ {
+ node_pointer n = static_cast<node_pointer>(base);
+ n->clear_subtree(alloc_);
+ alloc_.deallocate(n, 1);
+ }
+
+ Alloc & alloc_;
+};
+
+
+template <typename ValueType,
+ bool constant_time_child_size = true
+ >
+struct heap_node:
+ heap_node_base<!constant_time_child_size>
+{
+ typedef heap_node_base<!constant_time_child_size> node_base;
+
+public:
+ typedef ValueType value_type;
+
+ typedef bi::list<node_base,
+ bi::constant_time_size<constant_time_child_size> > child_list;
+
+ typedef typename child_list::iterator child_iterator;
+ typedef typename child_list::const_iterator const_child_iterator;
+ typedef typename child_list::size_type size_type;
+
+ heap_node(ValueType const & v):
+ value(v)
+ {}
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ heap_node(Args&&... args):
+ value(std::forward<Args>(args)...)
+ {}
+#endif
+
+protected:
+ heap_node(heap_node const & rhs):
+ value(rhs.value)
+ {
+ /* we don't copy the child list, but clone it later */
+ }
+
+public:
+
+ template <typename Alloc>
+ heap_node (heap_node const & rhs, Alloc & allocator):
+ value(rhs.value)
+ {
+ children.clone_from(rhs.children, node_cloner<heap_node, node_base, Alloc>(allocator), nop_disposer());
+ }
+
+ size_type child_count(void) const
+ {
+ BOOST_STATIC_ASSERT(constant_time_child_size);
+ return children.size();
+ }
+
+ void add_child(heap_node * n)
+ {
+ children.push_back(*n);
+ }
+
+ template <typename Alloc>
+ void clear_subtree(Alloc & alloc)
+ {
+ children.clear_and_dispose(node_disposer<heap_node, node_base, Alloc>(alloc));
+ }
+
+ void swap_children(heap_node * rhs)
+ {
+ children.swap(rhs->children);
+ }
+
+ ValueType value;
+ child_list children;
+};
+
+template <typename value_type>
+struct parent_pointing_heap_node:
+ heap_node<value_type>
+{
+ typedef heap_node<value_type> super_t;
+
+ parent_pointing_heap_node(value_type const & v):
+ super_t(v), parent(NULL)
+ {}
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ parent_pointing_heap_node(Args&&... args):
+ super_t(std::forward<Args>(args)...), parent(NULL)
+ {}
+#endif
+
+ template <typename Alloc>
+ struct node_cloner
+ {
+ node_cloner(Alloc & allocator, parent_pointing_heap_node * parent):
+ allocator(allocator), parent_(parent)
+ {}
+
+ parent_pointing_heap_node * operator() (typename super_t::node_base const & node)
+ {
+ parent_pointing_heap_node * ret = allocator.allocate(1);
+ new (ret) parent_pointing_heap_node(static_cast<parent_pointing_heap_node const &>(node), allocator, parent_);
+ return ret;
+ }
+
+ private:
+ Alloc & allocator;
+ parent_pointing_heap_node * parent_;
+ };
+
+ template <typename Alloc>
+ parent_pointing_heap_node (parent_pointing_heap_node const & rhs, Alloc & allocator, parent_pointing_heap_node * parent):
+ super_t(static_cast<super_t const &>(rhs)), parent(parent)
+ {
+ super_t::children.clone_from(rhs.children, node_cloner<Alloc>(allocator, this), nop_disposer());
+ }
+
+ void update_children(void)
+ {
+ typedef heap_node_list::iterator node_list_iterator;
+ for (node_list_iterator it = super_t::children.begin(); it != super_t::children.end(); ++it) {
+ parent_pointing_heap_node * child = static_cast<parent_pointing_heap_node*>(&*it);
+ child->parent = this;
+ }
+ }
+
+ void remove_from_parent(void)
+ {
+ BOOST_HEAP_ASSERT(parent);
+ parent->children.erase(heap_node_list::s_iterator_to(*this));
+ parent = NULL;
+ }
+
+ void add_child(parent_pointing_heap_node * n)
+ {
+ BOOST_HEAP_ASSERT(n->parent == NULL);
+ n->parent = this;
+ super_t::add_child(n);
+ }
+
+ parent_pointing_heap_node * get_parent(void)
+ {
+ return parent;
+ }
+
+ const parent_pointing_heap_node * get_parent(void) const
+ {
+ return parent;
+ }
+
+ parent_pointing_heap_node * parent;
+};
+
+
+template <typename value_type>
+struct marked_heap_node:
+ parent_pointing_heap_node<value_type>
+{
+ typedef parent_pointing_heap_node<value_type> super_t;
+
+ marked_heap_node(value_type const & v):
+ super_t(v), mark(false)
+ {}
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ marked_heap_node(Args&&... args):
+ super_t(std::forward<Args>(args)...), mark(false)
+ {}
+#endif
+
+ marked_heap_node * get_parent(void)
+ {
+ return static_cast<marked_heap_node*>(super_t::parent);
+ }
+
+ const marked_heap_node * get_parent(void) const
+ {
+ return static_cast<marked_heap_node*>(super_t::parent);
+ }
+
+ bool mark;
+};
+
+
+template <typename Node>
+struct cmp_by_degree
+{
+ template <typename NodeBase>
+ bool operator()(NodeBase const & left,
+ NodeBase const & right)
+ {
+ return static_cast<const Node*>(&left)->child_count() < static_cast<const Node*>(&right)->child_count();
+ }
+};
+
+template <typename List, typename Node, typename Cmp>
+Node * find_max_child(List const & list, Cmp const & cmp)
+{
+ BOOST_HEAP_ASSERT(!list.empty());
+
+ const Node * ret = static_cast<const Node *> (&list.front());
+ for (typename List::const_iterator it = list.begin(); it != list.end(); ++it) {
+ const Node * current = static_cast<const Node *> (&*it);
+
+ if (cmp(ret->value, current->value))
+ ret = current;
+ }
+
+ return const_cast<Node*>(ret);
+}
+
+} /* namespace detail */
+} /* namespace heap */
+} /* namespace boost */
+
+#undef BOOST_HEAP_ASSERT
+#endif /* BOOST_HEAP_DETAIL_HEAP_NODE_HPP */
\ No newline at end of file

Added: trunk/boost/heap/detail/ilog2.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/ilog2.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,64 @@
+// boost heap: integer log2
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_DETAIL_ILOG2_HPP
+#define BOOST_HEAP_DETAIL_ILOG2_HPP
+
+#include <string> // std::size_t
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+template <typename IntType>
+struct log2
+{
+ IntType operator()(IntType value)
+ {
+ IntType l = 0;
+ while( (value >> l) > 1 )
+ ++l;
+ return l;
+ }
+};
+
+#ifdef __GNUC__
+template<>
+struct log2<unsigned int>
+{
+ unsigned int operator()(unsigned int value)
+ {
+ return sizeof(unsigned int)*8 - __builtin_clz(value - 1);
+ }
+};
+
+template<>
+struct log2<unsigned long>
+{
+ unsigned long operator()(unsigned long value)
+ {
+ return sizeof(unsigned long)*8 - __builtin_clzl(value - 1);
+ }
+};
+
+#endif
+
+} /* namespace detail */
+
+
+template <typename IntType>
+IntType log2(IntType value)
+{
+ detail::log2<IntType> fn;
+ return fn(value);
+}
+
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */
\ No newline at end of file

Added: trunk/boost/heap/detail/mutable_heap.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/mutable_heap.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,504 @@
+// boost heap
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
+#define BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
+
+/*! \file
+ * INTERNAL ONLY
+ */
+
+#include <list>
+#include <utility>
+
+#include <boost/noncopyable.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/heap/detail/ordered_adaptor_iterator.hpp>
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+/* wrapper for a mutable heap container adaptors
+ *
+ * this wrapper introduces an additional indirection. the heap is not constructed from objects,
+ * but instead from std::list iterators. this way, the mutability is achieved
+ *
+ */
+template <typename PriorityQueueType>
+class priority_queue_mutable_wrapper
+{
+public:
+ typedef typename PriorityQueueType::value_type value_type;
+ typedef typename PriorityQueueType::size_type size_type;
+ typedef typename PriorityQueueType::value_compare value_compare;
+ typedef typename PriorityQueueType::allocator_type allocator_type;
+
+ typedef typename PriorityQueueType::reference reference;
+ typedef typename PriorityQueueType::const_reference const_reference;
+ typedef typename PriorityQueueType::pointer pointer;
+ typedef typename PriorityQueueType::const_pointer const_pointer;
+ static const bool is_stable = PriorityQueueType::is_stable;
+
+private:
+ typedef std::pair<value_type, size_type> node_type;
+
+ typedef std::list<node_type, allocator_type> object_list;
+
+ typedef typename object_list::iterator list_iterator;
+ typedef typename object_list::const_iterator const_list_iterator;
+
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+ typedef typename PriorityQueueType::super_t::stability_counter_type stability_counter_type;
+
+ stability_counter_type get_stability_count(void) const
+ {
+ return q_.get_stability_count();
+ }
+
+ void set_stability_count(stability_counter_type new_count)
+ {
+ q_.set_stability_count(new_count);
+ }
+
+ template <typename value_type>
+ struct index_updater
+ {
+ template <typename It>
+ void operator()(It & it, size_type new_index)
+ {
+ q_type::get_value(it)->second = new_index;
+ }
+
+ template <typename U>
+ struct rebind {
+ typedef index_updater<U> other;
+ };
+ };
+
+public:
+ struct handle_type
+ {
+ value_type & operator*() const
+ {
+ return iterator->first;
+ }
+
+ handle_type (void)
+ {}
+
+ private:
+ explicit handle_type(list_iterator const & it):
+ iterator(it)
+ {}
+
+ list_iterator iterator;
+
+ friend class priority_queue_mutable_wrapper;
+ };
+
+private:
+ struct indirect_cmp:
+ public value_compare
+ {
+ indirect_cmp(value_compare const & cmp = value_compare()):
+ value_compare(cmp)
+ {}
+
+ bool operator()(const_list_iterator const & lhs, const_list_iterator const & rhs) const
+ {
+ return value_compare::operator()(lhs->first, rhs->first);
+ }
+ };
+
+ typedef typename PriorityQueueType::template rebind<list_iterator,
+ indirect_cmp,
+ allocator_type, index_updater<list_iterator> >::other q_type;
+
+protected:
+ q_type q_;
+ object_list objects;
+
+protected:
+ priority_queue_mutable_wrapper(value_compare const & cmp = value_compare()):
+ q_(cmp)
+ {}
+
+ priority_queue_mutable_wrapper(priority_queue_mutable_wrapper const & rhs):
+ objects(rhs.objects)
+ {
+ for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
+ q_.push(it);
+ }
+
+ priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper const & rhs)
+ {
+ objects = rhs.objects;
+ q_.clear();
+ for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
+ q_.push(it);
+ return *this;
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ priority_queue_mutable_wrapper (priority_queue_mutable_wrapper && rhs):
+ q_(std::move(rhs.q_)), objects(std::move(rhs.objects))
+ {}
+
+ priority_queue_mutable_wrapper & operator=(priority_queue_mutabe_wrapper && rhs)
+ {
+ q_ = std::move(rhs.q_);
+ objects = std::move(rhs.objects);
+ return *this;
+ }
+#endif
+
+
+public:
+ class iterator:
+ public boost::iterator_adaptor<iterator,
+ const_list_iterator,
+ value_type const,
+ boost::bidirectional_traversal_tag>
+ {
+ typedef boost::iterator_adaptor<iterator,
+ const_list_iterator,
+ value_type const,
+ boost::bidirectional_traversal_tag> super_t;
+
+ friend class boost::iterator_core_access;
+ friend class priority_queue_mutable_wrapper;
+
+ iterator(void):
+ super_t(0)
+ {}
+
+ explicit iterator(const_list_iterator const & it):
+ super_t(it)
+ {}
+
+ value_type const & dereference() const
+ {
+ return super_t::base()->first;
+ }
+ };
+
+ typedef iterator const_iterator;
+ typedef typename object_list::difference_type difference_type;
+
+ class ordered_iterator:
+ public boost::iterator_adaptor<ordered_iterator,
+ const_list_iterator,
+ value_type const,
+ boost::forward_traversal_tag
+ >,
+ q_type::ordered_iterator_dispatcher
+ {
+ typedef boost::iterator_adaptor<ordered_iterator,
+ const_list_iterator,
+ value_type const,
+ boost::forward_traversal_tag
+ > adaptor_type;
+
+ typedef const_list_iterator iterator;
+ typedef typename q_type::ordered_iterator_dispatcher ordered_iterator_dispatcher;
+
+ friend class boost::iterator_core_access;
+
+ public:
+ ordered_iterator(void):
+ adaptor_type(0), q_(NULL), unvisited_nodes(indirect_cmp())
+ {}
+
+ ordered_iterator(const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
+ adaptor_type(0), q_(q), unvisited_nodes(cmp)
+ {}
+
+ ordered_iterator(const_list_iterator it, const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
+ adaptor_type(it), q_(q), unvisited_nodes(cmp)
+ {
+ if (it != q->objects.end())
+ discover_nodes(it);
+ }
+
+ bool operator!=(ordered_iterator const & rhs) const
+ {
+ return adaptor_type::base() != rhs.base();
+ }
+
+ bool operator==(ordered_iterator const & rhs) const
+ {
+ return !operator!=(rhs);
+ }
+
+ private:
+ void increment(void)
+ {
+ if (unvisited_nodes.empty())
+ adaptor_type::base_reference() = q_->objects.end();
+ else {
+ iterator next = unvisited_nodes.top();
+ unvisited_nodes.pop();
+ discover_nodes(next);
+ adaptor_type::base_reference() = next;
+ }
+ }
+
+ value_type const & dereference() const
+ {
+ return adaptor_type::base()->first;
+ }
+
+ void discover_nodes(iterator current)
+ {
+ size_type current_index = current->second;
+ const q_type * q = &(q_->q_);
+
+ if (ordered_iterator_dispatcher::is_leaf(q, current_index))
+ return;
+
+ std::pair<size_type, size_type> child_range = ordered_iterator_dispatcher::get_child_nodes(q, current_index);
+
+ for (size_type i = child_range.first; i <= child_range.second; ++i) {
+ typename q_type::internal_type const & internal_value_at_index = ordered_iterator_dispatcher::get_internal_value(q, i);
+ typename q_type::value_type const & value_at_index = q_->q_.get_value(internal_value_at_index);
+
+ unvisited_nodes.push(value_at_index);
+ }
+ }
+
+ std::priority_queue<iterator, std::vector<iterator, allocator_type>, indirect_cmp> unvisited_nodes;
+ const priority_queue_mutable_wrapper * q_;
+ };
+
+ bool empty(void) const
+ {
+ return q_.empty();
+ }
+
+ size_type size(void) const
+ {
+ return q_.size();
+ }
+
+ size_type max_size(void) const
+ {
+ return objects.max_size();
+ }
+
+ void clear(void)
+ {
+ q_.clear();
+ objects.clear();
+ }
+
+ allocator_type get_allocator(void) const
+ {
+ return q_.get_allocator();
+ }
+
+ void swap(priority_queue_mutable_wrapper & rhs)
+ {
+ objects.swap(rhs.objects);
+ q_.swap(rhs.q_);
+ }
+
+ const_reference top(void) const
+ {
+ BOOST_ASSERT(!empty());
+ return q_.top()->first;
+ }
+
+ handle_type push(value_type const & v)
+ {
+ objects.push_front(std::make_pair(v, 0));
+ list_iterator ret = objects.begin();
+ q_.push(ret);
+ return handle_type(ret);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ handle_type emplace(Args&&... args)
+ {
+ objects.push_front(std::make_pair(std::forward<Args>(args)..., 0));
+ list_iterator ret = objects.begin();
+ q_.push(ret);
+ return handle_type(ret);
+ }
+#endif
+
+ void pop(void)
+ {
+ BOOST_ASSERT(!empty());
+ list_iterator q_top = q_.top();
+ q_.pop();
+ objects.erase(q_top);
+ }
+
+ /**
+ * \b Effects: Merge with priority queue rhs.
+ *
+ * \b Complexity: N log(N)
+ *
+ * */
+ void merge(priority_queue_mutable_wrapper const & rhs)
+ {
+ q_.reserve(q_.size() + rhs.q_.size());
+
+ for (typename object_list::const_iterator it = rhs.objects.begin(); it != rhs.objects.end(); ++it)
+ push(it->first);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * */
+ void update(handle_type handle, const_reference v)
+ {
+ list_iterator it = handle.iterator;
+ value_type const & current_value = it->first;
+ value_compare const & cmp = q_;
+ if (cmp(v, current_value))
+ decrease(handle, v);
+ else
+ increase(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void update(handle_type handle)
+ {
+ list_iterator it = handle.iterator;
+ size_type index = it->second;
+ q_.update(index);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be greater than the current one
+ * */
+ void increase(handle_type handle, const_reference v)
+ {
+ BOOST_ASSERT(!value_compare()(v, handle.iterator->first));
+ handle.iterator->first = v;
+ increase(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void increase(handle_type handle)
+ {
+ list_iterator it = handle.iterator;
+ size_type index = it->second;
+ q_.increase(index);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be less than the current one
+ * */
+ void decrease(handle_type handle, const_reference v)
+ {
+ BOOST_ASSERT(!value_compare()(handle.iterator->first, v));
+ handle.iterator->first = v;
+ decrease(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \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!
+ * */
+ void decrease(handle_type handle)
+ {
+ list_iterator it = handle.iterator;
+ size_type index = it->second;
+ q_.decrease(index);
+ }
+
+ /**
+ * \b Effects: Removes the element handled by \c handle from the priority_queue.
+ *
+ * \b Complexity: Logarithmic.
+ * */
+ void erase(handle_type handle)
+ {
+ list_iterator it = handle.iterator;
+ size_type index = it->second;
+ q_.erase(index);
+ objects.erase(it);
+ }
+
+ iterator begin(void) const
+ {
+ return iterator(objects.begin());
+ }
+
+ iterator end(void) const
+ {
+ return iterator(objects.end());
+ }
+
+ ordered_iterator ordered_begin(void) const
+ {
+ if (!empty())
+ return ordered_iterator(q_.top(), this, indirect_cmp(q_.value_comp()));
+ else
+ return ordered_end();
+ }
+
+ ordered_iterator ordered_end(void) const
+ {
+ return ordered_iterator(objects.end(), this, indirect_cmp(q_.value_comp()));
+ }
+
+ static handle_type s_handle_from_iterator(iterator const & it)
+ {
+ return handle_type(it);
+ }
+
+ value_compare const & value_comp(void) const
+ {
+ return q_.value_comp();
+ }
+
+ void reserve (size_type element_count)
+ {
+ q_.reserve(element_count);
+ }
+};
+
+
+} /* namespace detail */
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP */

Added: trunk/boost/heap/detail/ordered_adaptor_iterator.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/ordered_adaptor_iterator.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,143 @@
+// boost heap: ordered iterator helper classes for container adaptors
+//
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP
+#define BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP
+
+#include <cassert>
+#include <limits>
+
+#include <boost/assert.hpp>
+#include <boost/heap/detail/tree_iterator.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/concept_check.hpp>
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+/* ordered iterator helper classes for container adaptors
+ *
+ * Requirements for Dispatcher:
+ *
+ * * static size_type max_index(const ContainerType * heap); // return maximum index
+ * * static bool is_leaf(const ContainerType * heap, size_type index); // return if index denotes a leaf
+ * * static std::pair<size_type, size_type> get_child_nodes(const ContainerType * heap, size_type index); // get index range of child nodes
+ * * static internal_type const & get_internal_value(const ContainerType * heap, size_type index); // get internal value at index
+ * * static value_type const & get_value(internal_type const & arg) const; // get value_type from internal_type
+ *
+ * */
+template <typename ValueType,
+ typename InternalType,
+ typename ContainerType,
+ typename Alloc,
+ typename ValueCompare,
+ typename Dispatcher
+ >
+class ordered_adaptor_iterator:
+ public boost::iterator_facade<ordered_adaptor_iterator<ValueType,
+ InternalType,
+ ContainerType,
+ Alloc,
+ ValueCompare,
+ Dispatcher>,
+ ValueType,
+ boost::forward_traversal_tag
+ >,
+ Dispatcher
+{
+ friend class boost::iterator_core_access;
+
+ struct compare_by_heap_value:
+ ValueCompare
+ {
+ const ContainerType * container;
+
+ compare_by_heap_value (const ContainerType * container, ValueCompare const & cmp):
+ ValueCompare(cmp), container(container)
+ {}
+
+ bool operator()(size_t lhs, size_t rhs)
+ {
+ assert(lhs <= Dispatcher::max_index(container));
+ assert(rhs <= Dispatcher::max_index(container));
+ return ValueCompare::operator()(Dispatcher::get_internal_value(container, lhs),
+ Dispatcher::get_internal_value(container, rhs));
+ }
+ };
+
+ const ContainerType * container;
+ size_t current_index; // current index: special value -1 denotes `end' iterator
+
+public:
+ ordered_adaptor_iterator(void):
+ container(NULL), current_index(std::numeric_limits<size_t>::max()),
+ unvisited_nodes(compare_by_heap_value(NULL, ValueCompare()))
+ {}
+
+ ordered_adaptor_iterator(const ContainerType * container, ValueCompare const & cmp):
+ container(container), current_index(container->size()),
+ unvisited_nodes(compare_by_heap_value(container, ValueCompare()))
+ {}
+
+ ordered_adaptor_iterator(size_t initial_index, const ContainerType * container, ValueCompare const & cmp):
+ container(container), current_index(initial_index),
+ unvisited_nodes(compare_by_heap_value(container, cmp))
+ {
+ discover_nodes(initial_index);
+ }
+
+private:
+ bool equal (ordered_adaptor_iterator const & rhs) const
+ {
+ if (current_index != rhs.current_index)
+ return false;
+
+ if (container != rhs.container) // less likely than first check
+ return false;
+
+ return true;
+ }
+
+ void increment(void)
+ {
+ if (unvisited_nodes.empty())
+ current_index = Dispatcher::max_index(container) + 1;
+ else {
+ current_index = unvisited_nodes.top();
+ unvisited_nodes.pop();
+ discover_nodes(current_index);
+ }
+ }
+
+ ValueType const & dereference() const
+ {
+ BOOST_ASSERT(current_index <= Dispatcher::max_index(container));
+ return Dispatcher::get_value(Dispatcher::get_internal_value(container, current_index));
+ }
+
+ void discover_nodes(size_t index)
+ {
+ if (Dispatcher::is_leaf(container, index))
+ return;
+
+ std::pair<size_t, size_t> child_range = Dispatcher::get_child_nodes(container, index);
+
+ for (size_t i = child_range.first; i <= child_range.second; ++i)
+ unvisited_nodes.push(i);
+ }
+
+ std::priority_queue<size_t, std::vector<size_t, Alloc>, compare_by_heap_value> unvisited_nodes;
+};
+
+
+} /* namespace detail */
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */

Added: trunk/boost/heap/detail/stable_heap.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/stable_heap.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,426 @@
+// boost heap: helper classes for stable priority queues
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
+#define BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
+
+#include <limits>
+#include <stdexcept>
+#include <utility>
+
+#include <boost/cstdint.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+
+#include <boost/heap/policies.hpp>
+#include <boost/heap/heap_merge.hpp>
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+
+template<bool ConstantSize, class SizeType>
+struct size_holder
+{
+ static const bool constant_time_size = ConstantSize;
+ typedef SizeType size_type;
+
+ size_holder(void):
+ size_(0)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ size_holder(size_holder && rhs):
+ size_(rhs.size_)
+ {
+ rhs.size_ = 0;
+ }
+
+ size_holder & operator=(size_holder && rhs)
+ {
+ size_ = rhs.size_;
+ rhs.size_ = 0;
+ }
+#endif
+
+ SizeType get_size() const
+ { return size_; }
+
+ void set_size(SizeType size)
+ { size_ = size; }
+
+ void decrement()
+ { --size_; }
+
+ void increment()
+ { ++size_; }
+
+ void add(SizeType value)
+ { size_ += value; }
+
+ void sub(SizeType value)
+ { size_ -= value; }
+
+ void swap(size_holder & rhs)
+ { std::swap(size_, rhs.size_); }
+
+ SizeType size_;
+};
+
+template<class SizeType>
+struct size_holder<false, SizeType>
+{
+ static const bool constant_time_size = false;
+ typedef SizeType size_type;
+
+ size_holder(void)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ size_holder(size_holder && rhs)
+ {}
+
+ size_holder & operator=(size_holder && rhs)
+ {}
+#endif
+
+ size_type get_size() const
+ { return 0; }
+
+ void set_size(size_type)
+ {}
+
+ void decrement()
+ {}
+
+ void increment()
+ {}
+
+ void add(SizeType value)
+ {}
+
+ void sub(SizeType value)
+ {}
+
+ void swap(size_holder & rhs)
+ {}
+};
+
+template <typename T,
+ typename Cmp,
+ bool constant_time_size,
+ typename StabilityCounterType = boost::uintmax_t,
+ bool stable = false
+ >
+struct heap_base:
+ Cmp,
+ size_holder<constant_time_size, size_t>
+{
+ typedef StabilityCounterType stability_counter_type;
+ typedef T value_type;
+ typedef T internal_type;
+ typedef size_holder<constant_time_size, size_t> size_holder_type;
+ typedef Cmp value_compare;
+ typedef Cmp internal_compare;
+ static const bool is_stable = stable;
+
+ heap_base (Cmp const & cmp = Cmp()):
+ Cmp(cmp)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ heap_base(heap_base && rhs):
+ Cmp(std::move(static_cast<Cmp&>(rhs))),
+ size_holder_type(std::move(static_cast<size_holder_type&>(rhs)))
+ {}
+
+ heap_base & operator=(heap_base && rhs)
+ {
+ Cmp::operator=(std::move(static_cast<Cmp&>(rhs)));
+ size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs)));
+ }
+#endif
+
+ bool operator()(internal_type const & lhs, internal_type const & rhs) const
+ {
+ return Cmp::operator()(lhs, rhs);
+ }
+
+ internal_type make_node(T const & val)
+ {
+ return val;
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ T && make_node(T && val)
+ {
+ return std::forward<T>(val);
+ }
+#endif
+
+ static T & get_value(internal_type & val)
+ {
+ return val;
+ }
+
+ static T const & get_value(internal_type const & val)
+ {
+ return val;
+ }
+
+ Cmp const & value_comp(void) const
+ {
+ return *this;
+ }
+
+ Cmp const & get_internal_cmp(void) const
+ {
+ return *this;
+ }
+
+ void swap(heap_base & rhs)
+ {
+ std::swap(static_cast<Cmp&>(*this), static_cast<Cmp&>(rhs));
+ size_holder<constant_time_size, size_t>::swap(rhs);
+ }
+
+ stability_counter_type get_stability_count(void) const
+ {
+ return 0;
+ }
+
+ void set_stability_count(stability_counter_type)
+ {}
+
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+};
+
+template <typename T,
+ typename Cmp,
+ bool constant_time_size,
+ typename StabilityCounterType
+ >
+struct heap_base<T, Cmp, constant_time_size, StabilityCounterType, true>:
+ Cmp,
+ size_holder<constant_time_size, size_t>
+{
+ typedef StabilityCounterType stability_counter_type;
+ typedef T value_type;
+ typedef std::pair<T, stability_counter_type> internal_type;
+ typedef size_holder<constant_time_size, size_t> size_holder_type;
+ typedef Cmp value_compare;
+
+ heap_base (Cmp const & cmp = Cmp()):
+ Cmp(cmp), counter_(0)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ heap_base(heap_base && rhs):
+ Cmp(std::move(static_cast<Cmp&>(rhs))),
+ size_holder_type(std::move(static_cast<size_holder_type&>(rhs))), counter_(rhs.counter_)
+ {
+ rhs.counter_ = 0;
+ }
+
+ heap_base & operator=(heap_base && rhs)
+ {
+ Cmp::operator=(std::move(static_cast<Cmp&>(rhs)));
+ size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs)));
+
+ counter_ = rhs.counter_;
+ rhs.counter_ = 0;
+ }
+#endif
+
+ bool operator()(internal_type const & lhs, internal_type const & rhs) const
+ {
+ internal_compare cmp(get_internal_cmp());
+ return cmp(lhs, rhs);
+ }
+
+ bool operator()(T const & lhs, T const & rhs) const
+ {
+ return Cmp::operator()(lhs, rhs);
+ }
+
+ internal_type make_node(T const & val)
+ {
+ std::size_t count = ++counter_;
+ if (counter_ == std::numeric_limits<stability_counter_type>::max())
+ BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow"));
+ return std::make_pair(val, count);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ internal_type make_node(Args&&... args)
+ {
+ std::size_t count = ++counter_;
+ if (counter_ == std::numeric_limits<stability_counter_type>::max())
+ BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow"));
+ return std::make_pair(std::forward<T>(args)..., count);
+ }
+#endif
+
+ static T & get_value(internal_type & val)
+ {
+ return val.first;
+ }
+
+ static T const & get_value(internal_type const & val)
+ {
+ return val.first;
+ }
+
+ Cmp const & value_comp(void) const
+ {
+ return *this;
+ }
+
+ struct internal_compare:
+ Cmp
+ {
+ internal_compare(Cmp const & cmp = Cmp()):
+ Cmp(cmp)
+ {}
+
+ bool operator()(internal_type const & lhs, internal_type const & rhs) const
+ {
+ if (Cmp::operator()(lhs.first, rhs.first))
+ return true;
+
+ if (Cmp::operator()(rhs.first, lhs.first))
+ return false;
+
+ return lhs.second > rhs.second;
+ }
+ };
+
+ internal_compare get_internal_cmp(void) const
+ {
+ return internal_compare(*this);
+ }
+
+ void swap(heap_base & rhs)
+ {
+ std::swap(static_cast<Cmp&>(*this), static_cast<Cmp&>(rhs));
+ std::swap(counter_, rhs.counter_);
+ size_holder<constant_time_size, size_t>::swap(rhs);
+ }
+
+ stability_counter_type get_stability_count(void) const
+ {
+ return counter_;
+ }
+
+ void set_stability_count(stability_counter_type new_count)
+ {
+ counter_ = new_count;
+ }
+
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+private:
+ stability_counter_type counter_;
+};
+
+template <typename node_pointer,
+ typename extractor,
+ typename reference
+ >
+struct node_handle
+{
+ explicit node_handle(node_pointer n = 0):
+ node_(n)
+ {}
+
+ reference operator*() const
+ {
+ return extractor::get_value(node_->value);
+ }
+
+ node_pointer node_;
+};
+
+template <typename value_type,
+ typename internal_type,
+ typename extractor
+ >
+struct value_extractor
+{
+ value_type const & operator()(internal_type const & data) const
+ {
+ return extractor::get_value(data);
+ }
+};
+
+template <typename T,
+ typename ContainerIterator,
+ typename Extractor>
+class stable_heap_iterator:
+ public boost::iterator_adaptor<stable_heap_iterator<T, ContainerIterator, Extractor>,
+ ContainerIterator,
+ T const,
+ boost::random_access_traversal_tag>
+{
+ typedef boost::iterator_adaptor<stable_heap_iterator,
+ ContainerIterator,
+ T const,
+ boost::random_access_traversal_tag> super_t;
+
+public:
+ stable_heap_iterator(void):
+ super_t(0)
+ {}
+
+ explicit stable_heap_iterator(ContainerIterator const & it):
+ super_t(it)
+ {}
+
+private:
+ friend class boost::iterator_core_access;
+
+ T const & dereference() const
+ {
+ return Extractor::get_value(*super_t::base());
+ }
+};
+
+template <typename T, typename Parspec, bool constant_time_size>
+struct make_heap_base
+{
+ typedef typename parameter::binding<Parspec, tag::compare, std::less<T> >::type compare_argument;
+ typedef typename parameter::binding<Parspec, tag::allocator, std::allocator<T> >::type allocator_argument;
+ typedef typename parameter::binding<Parspec, tag::stability_counter_type, boost::uintmax_t >::type stability_counter_type;
+
+ static const bool is_stable = extract_stable<Parspec>::value;
+
+ typedef heap_base<T, compare_argument, constant_time_size, stability_counter_type, is_stable> type;
+};
+
+
+template <typename Alloc>
+struct extract_allocator_types
+{
+ typedef typename Alloc::size_type size_type;
+ typedef typename Alloc::difference_type difference_type;
+ typedef typename Alloc::reference reference;
+ typedef typename Alloc::const_reference const_reference;
+ typedef typename Alloc::pointer pointer;
+ typedef typename Alloc::const_pointer const_pointer;
+};
+
+
+} /* namespace detail */
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_DETAIL_STABLE_HEAP_HPP */

Added: trunk/boost/heap/detail/tree_iterator.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/detail/tree_iterator.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,381 @@
+// boost heap: node tree iterator helper classes
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// Disclaimer: Not a Boost library.
+
+#ifndef BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
+#define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
+
+#include <functional>
+#include <vector>
+
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <queue>
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+
+template<typename type>
+struct identity:
+ public std::unary_function<type,type>
+{
+ type& operator()(type& x) const
+ { return x; }
+
+ const type& operator()(const type& x) const
+ { return x; }
+};
+
+template<typename type>
+struct caster:
+ public std::unary_function<type,type>
+{
+ template <typename U>
+ type& operator()(U& x) const
+ { return static_cast<type&>(x); }
+
+ template <typename U>
+ const type& operator()(const U& x) const
+ { return static_cast<const type&>(x); }
+};
+
+template<typename Node>
+struct dereferencer
+{
+ template <typename Iterator>
+ Node * operator()(Iterator const & it)
+ {
+ return static_cast<Node *>(*it);
+ }
+};
+
+template<typename Node>
+struct pointer_to_reference
+{
+ template <typename Iterator>
+ const Node * operator()(Iterator const & it)
+ {
+ return static_cast<const Node *>(&*it);
+ }
+};
+
+
+template <typename HandleType,
+ typename Alloc,
+ typename ValueCompare
+ >
+struct unordered_tree_iterator_storage
+{
+ unordered_tree_iterator_storage(ValueCompare const & cmp)
+ {}
+
+ void push(HandleType h)
+ {
+ data_.push_back(h);
+ }
+
+ HandleType const & top(void)
+ {
+ return data_.back();
+ }
+
+ void pop(void)
+ {
+ data_.pop_back();
+ }
+
+ bool empty(void) const
+ {
+ return data_.empty();
+ }
+
+ std::vector<HandleType, Alloc> data_;
+};
+
+template <typename ValueType,
+ typename HandleType,
+ typename Alloc,
+ typename ValueCompare,
+ typename ValueExtractor
+ >
+struct ordered_tree_iterator_storage:
+ ValueExtractor
+{
+ struct compare_values_by_handle:
+ ValueExtractor,
+ ValueCompare
+ {
+ compare_values_by_handle(ValueCompare const & cmp):
+ ValueCompare(cmp)
+ {}
+
+ bool operator()(HandleType const & lhs, HandleType const & rhs) const
+ {
+ ValueType const & lhs_value = ValueExtractor::operator()(lhs->value);
+ ValueType const & rhs_value = ValueExtractor::operator()(rhs->value);
+ return ValueCompare::operator()(lhs_value, rhs_value);
+ }
+ };
+
+ ordered_tree_iterator_storage(ValueCompare const & cmp):
+ data_(compare_values_by_handle(cmp))
+ {}
+
+ void push(HandleType h)
+ {
+ data_.push(h);
+ }
+
+ void pop(void)
+ {
+ data_.pop();
+ }
+
+ HandleType const & top(void)
+ {
+ return data_.top();
+ }
+
+ bool empty(void) const
+ {
+ return data_.empty();
+ }
+
+ std::priority_queue<HandleType, std::vector<HandleType, Alloc>, compare_values_by_handle> data_;
+};
+
+
+/* tree iterator helper class
+ *
+ * Requirements:
+ * Node provides child_iterator
+ * ValueExtractor can convert Node->value to ValueType
+ *
+ * */
+template <typename Node,
+ typename ValueType,
+ typename Alloc = std::allocator<Node>,
+ typename ValueExtractor = identity<typename Node::value_type>,
+ typename PointerExtractor = dereferencer<Node>,
+ bool check_null_pointer = false,
+ bool ordered_iterator = false,
+ typename ValueCompare = std::less<ValueType>
+ >
+class tree_iterator:
+ public boost::iterator_adaptor<tree_iterator<Node,
+ ValueType,
+ Alloc,
+ ValueExtractor,
+ PointerExtractor,
+ check_null_pointer,
+ ordered_iterator,
+ ValueCompare
+ >,
+ const Node *,
+ ValueType,
+ boost::forward_traversal_tag
+ >,
+ ValueExtractor,
+ PointerExtractor
+{
+ typedef boost::iterator_adaptor<tree_iterator<Node,
+ ValueType,
+ Alloc,
+ ValueExtractor,
+ PointerExtractor,
+ check_null_pointer,
+ ordered_iterator,
+ ValueCompare
+ >,
+ const Node *,
+ ValueType,
+ boost::forward_traversal_tag
+ > adaptor_type;
+
+ friend class boost::iterator_core_access;
+
+ typedef typename boost::mpl::if_c< ordered_iterator,
+ ordered_tree_iterator_storage<ValueType, const Node*, Alloc, ValueCompare, ValueExtractor>,
+ unordered_tree_iterator_storage<const Node*, Alloc, ValueCompare>
+ >::type
+ unvisited_node_container;
+
+public:
+ tree_iterator(void):
+ adaptor_type(0), unvisited_nodes(ValueCompare())
+ {}
+
+ tree_iterator(ValueCompare const & cmp):
+ adaptor_type(0), unvisited_nodes(cmp)
+ {}
+
+ tree_iterator(const Node * it, ValueCompare const & cmp):
+ adaptor_type(it), unvisited_nodes(cmp)
+ {
+ if (it)
+ discover_nodes(it);
+ }
+
+ /* fills the iterator from a list of possible top nodes */
+ template <typename NodePointerIterator>
+ tree_iterator(NodePointerIterator begin, NodePointerIterator end, const Node * top_node, ValueCompare const & cmp):
+ adaptor_type(0), unvisited_nodes(cmp)
+ {
+ BOOST_STATIC_ASSERT(ordered_iterator);
+ if (begin == end)
+ return;
+
+ adaptor_type::base_reference() = top_node;
+ discover_nodes(top_node);
+
+ for (NodePointerIterator it = begin; it != end; ++it) {
+ const Node * current_node = static_cast<const Node*>(&*it);
+ if (current_node != top_node)
+ unvisited_nodes.push(current_node);
+ }
+ }
+
+ bool operator!=(tree_iterator const & rhs) const
+ {
+ return adaptor_type::base() != rhs.base();
+ }
+
+ bool operator==(tree_iterator const & rhs) const
+ {
+ return !operator!=(rhs);
+ }
+
+private:
+ void increment(void)
+ {
+ if (unvisited_nodes.empty())
+ adaptor_type::base_reference() = 0;
+ else {
+ const Node * next = unvisited_nodes.top();
+ unvisited_nodes.pop();
+ discover_nodes(next);
+ adaptor_type::base_reference() = next;
+ }
+ }
+
+ ValueType const & dereference() const
+ {
+ return ValueExtractor::operator()(adaptor_type::base_reference()->value);
+ }
+
+ void discover_nodes(const Node * n)
+ {
+ for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
+ const Node * n = PointerExtractor::operator()(it);
+ if (check_null_pointer && n == NULL)
+ continue;
+ unvisited_nodes.push(n);
+ }
+ }
+
+ unvisited_node_container unvisited_nodes;
+};
+
+template <typename Node, typename NodeList>
+struct list_iterator_converter
+{
+ typename NodeList::const_iterator operator()(const Node * node)
+ {
+ return NodeList::s_iterator_to(*node);
+ }
+
+ Node * operator()(typename NodeList::const_iterator it)
+ {
+ return const_cast<Node*>(static_cast<const Node*>(&*it));
+ }
+};
+
+template <typename Node,
+ typename NodeIterator,
+ typename ValueType,
+ typename ValueExtractor = identity<typename Node::value_type>,
+ typename IteratorCoverter = identity<NodeIterator>
+ >
+class recursive_tree_iterator:
+ public boost::iterator_adaptor<recursive_tree_iterator<Node,
+ NodeIterator,
+ ValueType,
+ ValueExtractor,
+ IteratorCoverter
+ >,
+ NodeIterator,
+ ValueType const,
+ boost::bidirectional_traversal_tag>,
+ ValueExtractor, IteratorCoverter
+{
+ typedef boost::iterator_adaptor<recursive_tree_iterator<Node,
+ NodeIterator,
+ ValueType,
+ ValueExtractor,
+ IteratorCoverter
+ >,
+ NodeIterator,
+ ValueType const,
+ boost::bidirectional_traversal_tag> adaptor_type;
+
+ friend class boost::iterator_core_access;
+
+
+public:
+ recursive_tree_iterator(void):
+ adaptor_type(0)
+ {}
+
+ explicit recursive_tree_iterator(NodeIterator const & it):
+ adaptor_type(it)
+ {}
+
+ void increment(void)
+ {
+ NodeIterator next = adaptor_type::base_reference();
+
+ const Node * n = get_node(next);
+ if (n->children.empty()) {
+ const Node * parent = get_node(next)->get_parent();
+
+ ++next;
+
+ for (;;) {
+ if (parent == NULL || next != parent->children.end())
+ break;
+
+ next = IteratorCoverter::operator()(parent);
+ parent = get_node(next)->get_parent();
+ ++next;
+ }
+ } else
+ next = n->children.begin();
+
+ adaptor_type::base_reference() = next;
+ return;
+ }
+
+ ValueType const & dereference() const
+ {
+ return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
+ }
+
+ static const Node * get_node(NodeIterator const & it)
+ {
+ return static_cast<const Node *>(&*it);
+ }
+};
+
+
+} /* namespace detail */
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */

Added: trunk/boost/heap/fibonacci_heap.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/fibonacci_heap.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,744 @@
+// boost heap: fibonacci heap
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_FIBONACCI_HEAP_HPP
+#define BOOST_HEAP_FIBONACCI_HEAP_HPP
+
+#include <algorithm>
+#include <vector>
+
+#include <boost/array.hpp>
+#include <boost/assert.hpp>
+
+#include <boost/heap/detail/heap_comparison.hpp>
+#include <boost/heap/detail/heap_node.hpp>
+#include <boost/heap/detail/stable_heap.hpp>
+#include <boost/heap/detail/tree_iterator.hpp>
+
+#ifndef BOOST_DOXYGEN_INVOKED
+#ifdef BOOST_HEAP_SANITYCHECKS
+#define BOOST_HEAP_ASSERT BOOST_ASSERT
+#else
+#define BOOST_HEAP_ASSERT(expression)
+#endif
+#endif
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
+ boost::parameter::optional<tag::compare>,
+ boost::parameter::optional<tag::stable>,
+ boost::parameter::optional<tag::constant_time_size>,
+ boost::parameter::optional<tag::stability_counter_type>
+ > fibonacci_heap_signature;
+
+template <typename T, typename Parspec>
+struct make_fibonacci_heap_base
+{
+ static const bool constant_time_size = parameter::binding<Parspec,
+ tag::constant_time_size,
+ boost::mpl::true_
+ >::type::value;
+
+ typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type;
+ typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument;
+ typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument;
+ typedef marked_heap_node<typename base_type::internal_type> node_type;
+
+ typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
+
+ struct type:
+ base_type,
+ allocator_type
+ {
+ type(compare_argument const & arg):
+ base_type(arg)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ type(type && rhs):
+ base_type(std::move(static_cast<base_type&>(rhs))),
+ allocator_type(std::move(static_cast<allocator_type&>(rhs)))
+ {}
+
+ type & operator=(type && rhs)
+ {
+ base_type::operator=(std::move(static_cast<base_type&>(rhs)));
+ allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
+ }
+#endif
+ };
+};
+
+}
+
+
+
+/**
+ * \class fibonacci_heap
+ * \brief fibonacci heap
+ *
+ * The template parameter T is the type to be managed by the container.
+ * The user can specify additional options and if no options are provided default options are used.
+ *
+ * The container supports the following options:
+ * - \c boost::heap::stable<>, defaults to \c stable<false>
+ * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
+ * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
+ * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
+ * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
+ *
+ */
+#ifdef BOOST_DOXYGEN_INVOKED
+template<class T, class ...Options>
+#else
+template <typename T,
+ class A0 = boost::parameter::void_,
+ class A1 = boost::parameter::void_,
+ class A2 = boost::parameter::void_,
+ class A3 = boost::parameter::void_,
+ class A4 = boost::parameter::void_
+ >
+#endif
+class fibonacci_heap:
+ private detail::make_fibonacci_heap_base<T,
+ typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type
+ >::type
+{
+ typedef typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args;
+ typedef detail::make_fibonacci_heap_base<T, bound_args> base_maker;
+ typedef typename base_maker::type super_t;
+
+ typedef typename super_t::size_holder_type size_holder;
+ typedef typename super_t::internal_type internal_type;
+ typedef typename base_maker::allocator_argument allocator_argument;
+
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+private:
+#ifndef BOOST_DOXYGEN_INVOKED
+ struct implementation_defined:
+ detail::extract_allocator_types<typename base_maker::allocator_argument>
+ {
+ typedef T value_type;
+ typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
+ typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
+
+ typedef typename base_maker::compare_argument value_compare;
+ typedef typename base_maker::allocator_type allocator_type;
+
+ typedef typename allocator_type::pointer node_pointer;
+ typedef typename allocator_type::const_pointer const_node_pointer;
+
+ typedef detail::heap_node_list node_list_type;
+ typedef typename node_list_type::iterator node_list_iterator;
+ typedef typename node_list_type::const_iterator node_list_const_iterator;
+
+ typedef typename base_maker::node_type node;
+
+ typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
+ typedef typename super_t::internal_compare internal_compare;
+ typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
+
+ typedef detail::recursive_tree_iterator<node,
+ node_list_const_iterator,
+ const value_type,
+ value_extractor,
+ detail::list_iterator_converter<node, node_list_type>
+ > iterator;
+ typedef iterator const_iterator;
+
+ typedef detail::tree_iterator<node,
+ const value_type,
+ allocator_type,
+ value_extractor,
+ detail::list_iterator_converter<node, node_list_type>,
+ true,
+ true,
+ value_compare
+ > ordered_iterator;
+ };
+
+ typedef typename implementation_defined::node node;
+ typedef typename implementation_defined::node_pointer node_pointer;
+ typedef typename implementation_defined::node_list_type node_list_type;
+ typedef typename implementation_defined::node_list_iterator node_list_iterator;
+ typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
+ typedef typename implementation_defined::internal_compare internal_compare;
+#endif
+
+public:
+ typedef T value_type;
+
+ typedef typename implementation_defined::size_type size_type;
+ typedef typename implementation_defined::difference_type difference_type;
+ typedef typename implementation_defined::value_compare value_compare;
+ typedef typename implementation_defined::allocator_type allocator_type;
+ typedef typename implementation_defined::reference reference;
+ typedef typename implementation_defined::const_reference const_reference;
+ typedef typename implementation_defined::pointer pointer;
+ typedef typename implementation_defined::const_pointer const_pointer;
+ /// \copydoc boost::heap::priority_queue::iterator
+ typedef typename implementation_defined::iterator iterator;
+ typedef typename implementation_defined::const_iterator const_iterator;
+ typedef typename implementation_defined::ordered_iterator ordered_iterator;
+
+ typedef typename implementation_defined::handle_type handle_type;
+
+ static const bool constant_time_size = base_maker::constant_time_size;
+ static const bool has_ordered_iterators = true;
+ static const bool is_mergable = true;
+ static const bool is_stable = detail::extract_stable<bound_args>::value;
+ static const bool has_reserve = false;
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
+ explicit fibonacci_heap(value_compare const & cmp = value_compare()):
+ super_t(cmp), top_element(0)
+ {}
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
+ fibonacci_heap(fibonacci_heap const & rhs):
+ super_t(rhs), top_element(0)
+ {
+ if (rhs.empty())
+ return;
+
+ clone_forest(rhs);
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
+ fibonacci_heap(fibonacci_heap && rhs):
+ super_t(std::move(rhs)), top_element(rhs.top_element)
+ {
+ roots.splice(roots.begin(), rhs.roots);
+ rhs.top_element = NULL;
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
+ fibonacci_heap & operator=(fibonacci_heap && rhs)
+ {
+ clear();
+
+ super_t::operator=(std::move(rhs));
+ roots.splice(roots.begin(), rhs.roots);
+ top_element = rhs.top_element;
+ rhs.top_element = NULL;
+ return *this;
+ }
+#endif
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
+ fibonacci_heap & operator=(fibonacci_heap const & rhs)
+ {
+ clear();
+ size_holder::set_size(rhs.size());
+ static_cast<super_t&>(*this) = rhs;
+
+ if (rhs.empty())
+ top_element = NULL;
+ else
+ clone_forest(rhs);
+ return *this;
+ }
+
+ ~fibonacci_heap(void)
+ {
+ clear();
+ }
+
+ /// \copydoc boost::heap::priority_queue::empty
+ bool empty(void) const
+ {
+ if (constant_time_size)
+ return size() == 0;
+ else
+ return roots.empty();
+ }
+
+ /// \copydoc boost::heap::priority_queue::size
+ size_type size(void) const
+ {
+ if (constant_time_size)
+ return size_holder::get_size();
+
+ if (empty())
+ return 0;
+ else
+ return detail::count_list_nodes<node, node_list_type>(roots);
+ }
+
+ /// \copydoc boost::heap::priority_queue::max_size
+ size_type max_size(void) const
+ {
+ return allocator_type::max_size();
+ }
+
+ /// \copydoc boost::heap::priority_queue::clear
+ void clear(void)
+ {
+ typedef detail::node_disposer<node, typename node_list_type::value_type, allocator_type> disposer;
+ roots.clear_and_dispose(disposer(*this));
+
+ size_holder::set_size(0);
+ top_element = NULL;
+ }
+
+ /// \copydoc boost::heap::priority_queue::get_allocator
+ allocator_type get_allocator(void) const
+ {
+ return *this;
+ }
+
+ /// \copydoc boost::heap::priority_queue::swap
+ void swap(fibonacci_heap & rhs)
+ {
+ super_t::swap(rhs);
+ std::swap(top_element, rhs.top_element);
+ roots.swap(rhs.roots);
+ }
+
+
+ /// \copydoc boost::heap::priority_queue::top
+ value_type const & top(void) const
+ {
+ BOOST_ASSERT(!empty());
+
+ return super_t::get_value(top_element->value);
+ }
+
+ /**
+ * \b Effects: Adds a new element to the priority queue. Returns handle to element
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Note: Does not invalidate iterators.
+ *
+ * */
+ handle_type push(value_type const & v)
+ {
+ size_holder::increment();
+
+ node_pointer n = allocator_type::allocate(1);
+
+ new(n) node(super_t::make_node(v));
+ roots.push_front(*n);
+
+ if (!top_element || super_t::operator()(top_element->value, n->value))
+ top_element = n;
+ return handle_type(n);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ /**
+ * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Note: Does not invalidate iterators.
+ *
+ * */
+ template <class... Args>
+ handle_type emplace(Args&&... args)
+ {
+ size_holder::increment();
+
+ node_pointer n = allocator_type::allocate(1);
+
+ new(n) node(super_t::make_node(std::forward<Args>(args)...));
+ roots.push_front(*n);
+
+ if (!top_element || super_t::operator()(top_element->value, n->value))
+ top_element = n;
+ return handle_type(n);
+ }
+#endif
+
+ /**
+ * \b Effects: Removes the top element from the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized). Linear (worst case).
+ *
+ * */
+ void pop(void)
+ {
+ BOOST_ASSERT(!empty());
+
+ node_pointer element = top_element;
+ roots.erase(node_list_type::s_iterator_to(*element));
+
+ add_children_to_root(element);
+
+ element->~node();
+ allocator_type::deallocate(element, 1);
+
+ size_holder::decrement();
+ if (!empty())
+ consolidate();
+ else
+ top_element = NULL;
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic if current value < v, Constant otherwise.
+ *
+ * */
+ void update (handle_type handle, const_reference v)
+ {
+ if (super_t::operator()(super_t::get_value(handle.node_->value), v))
+ increase(handle, v);
+ else
+ decrease(handle, v);
+ }
+
+ /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference)
+ *
+ * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
+ * the iterator the the object referred to by the handle.
+ * */
+ void update_lazy(handle_type handle, const_reference v)
+ {
+ handle.node_->value = super_t::make_node(v);
+ update_lazy(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void update (handle_type handle)
+ {
+ node_pointer n = handle.node_;
+ node_pointer parent = n->get_parent();
+
+ if (parent) {
+ n->parent = NULL;
+ roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
+ }
+ add_children_to_root(n);
+ consolidate();
+ }
+
+ /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle)
+ *
+ * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
+ * the iterator the the object referred to by the handle.
+ * */
+ void update_lazy (handle_type handle)
+ {
+ node_pointer n = handle.node_;
+ node_pointer parent = n->get_parent();
+
+ if (parent) {
+ n->parent = NULL;
+ roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
+ }
+ add_children_to_root(n);
+ }
+
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Note: The new value is expected to be greater than the current one
+ * */
+ void increase (handle_type handle, const_reference v)
+ {
+ handle.node_->value = super_t::make_node(v);
+ increase(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void increase (handle_type handle)
+ {
+ node_pointer n = handle.node_;
+
+ if (n->parent) {
+ if (super_t::operator()(n->get_parent()->value, n->value)) {
+ node_pointer parent = n->get_parent();
+ cut(n);
+ cascading_cut(parent);
+ }
+ }
+
+ if (super_t::operator()(top_element->value, n->value)) {
+ top_element = n;
+ return;
+ }
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \b Note: The new value is expected to be less than the current one
+ * */
+ void decrease (handle_type handle, const_reference v)
+ {
+ handle.node_->value = super_t::make_node(v);
+ decrease(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic.
+ *
+ * \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!
+ * */
+ void decrease (handle_type handle)
+ {
+ update(handle);
+ }
+
+ /**
+ * \b Effects: Removes the element handled by \c handle from the priority_queue.
+ *
+ * \b Complexity: Logarithmic.
+ * */
+ void erase(handle_type const & handle)
+ {
+ node_pointer n = handle.node_;
+ node_pointer parent = n->get_parent();
+
+ if (parent)
+ parent->children.erase(node_list_type::s_iterator_to(*n));
+ else
+ roots.erase(node_list_type::s_iterator_to(*n));
+
+ add_children_to_root(n);
+ consolidate();
+
+ n->~node();
+ allocator_type::deallocate(n, 1);
+
+ size_holder::decrement();
+ }
+
+ /// \copydoc boost::heap::priority_queue::begin
+ iterator begin(void) const
+ {
+ return iterator(roots.begin());
+ }
+
+ /// \copydoc boost::heap::priority_queue::end
+ iterator end(void) const
+ {
+ return iterator(roots.end());
+ }
+
+
+ /**
+ * \b Effects: Returns an ordered iterator to the first element contained in the priority queue.
+ *
+ * \b Note: Ordered iterators traverse the priority queue in heap order.
+ * */
+ ordered_iterator ordered_begin(void) const
+ {
+ return ordered_iterator(roots.begin(), roots.end(), top_element, super_t::value_comp());
+ }
+
+ /**
+ * \b Effects: Returns an ordered iterator to the first element contained in the priority queue.
+ *
+ * \b Note: Ordered iterators traverse the priority queue in heap order.
+ * */
+ ordered_iterator ordered_end(void) const
+ {
+ return ordered_iterator(NULL, super_t::value_comp());
+ }
+
+ /**
+ * \b Effects: Merge with priority queue rhs.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ void merge(fibonacci_heap & rhs)
+ {
+ size_holder::add(rhs.get_size());
+
+ if (!top_element ||
+ (rhs.top_element && super_t::operator()(top_element->value, rhs.top_element->value)))
+ top_element = rhs.top_element;
+
+ roots.splice(roots.end(), rhs.roots);
+
+ rhs.set_size(0);
+
+ super_t::set_stability_count(std::max(super_t::get_stability_count(),
+ rhs.get_stability_count()));
+ rhs.set_stability_count(0);
+ }
+
+ /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
+ static handle_type s_handle_from_iterator(iterator const & it)
+ {
+ return super_t::s_handle_from_iterator(&*it);
+ }
+
+ /// \copydoc boost::heap::priority_queue::value_comp
+ value_compare const & value_comp(void) const
+ {
+ return super_t::value_comp();
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<(HeapType const & rhs) const
+ {
+ return detail::heap_compare(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>(HeapType const & rhs) const
+ {
+ return detail::heap_compare(rhs, *this);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>=(HeapType const & rhs) const
+ {
+ return !operator<(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<=(HeapType const & rhs) const
+ {
+ return !operator>(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator==(HeapType const & rhs) const
+ {
+ return detail::heap_equality(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator!=(HeapType const & rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+private:
+#if !defined(BOOST_DOXYGEN_INVOKED)
+ void clone_forest(fibonacci_heap const & rhs)
+ {
+ BOOST_HEAP_ASSERT(roots.empty());
+ typedef typename node::template node_cloner<allocator_type> node_cloner;
+ roots.clone_from(rhs.roots, node_cloner(*this, NULL), detail::nop_disposer());
+
+ top_element = detail::find_max_child<node_list_type, node, internal_compare>(roots, super_t::get_internal_cmp());
+ }
+
+ void cut(node_pointer n)
+ {
+ node_pointer parent = n->get_parent();
+ roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
+ n->parent = 0;
+ n->mark = false;
+ }
+
+ void cascading_cut(node_pointer n)
+ {
+ node_pointer parent = n->get_parent();
+
+ if (parent) {
+ if (!parent->mark)
+ parent->mark = true;
+ else {
+ cut(n);
+ cascading_cut(parent);
+ }
+ }
+ }
+
+ void add_children_to_root(node_pointer n)
+ {
+ for (node_list_iterator it = n->children.begin(); it != n->children.end(); ++it) {
+ node_pointer child = static_cast<node_pointer>(&*it);
+ child->parent = 0;
+ }
+
+ roots.splice(roots.end(), n->children);
+ }
+
+ void consolidate(void)
+ {
+ static const size_type max_log2 = sizeof(size_type) * 8;
+ boost::array<node_pointer, max_log2> aux;
+ aux.assign(NULL);
+
+ node_list_iterator it = roots.begin();
+ top_element = static_cast<node_pointer>(&*it);
+
+ do {
+ node_pointer n = static_cast<node_pointer>(&*it);
+ ++it;
+ size_type node_rank = n->child_count();
+
+ if (aux[node_rank] == NULL)
+ aux[node_rank] = n;
+ else {
+ do {
+ node_pointer other = aux[node_rank];
+ if (super_t::operator()(n->value, other->value))
+ std::swap(n, other);
+
+ if (other->parent)
+ n->children.splice(n->children.end(), other->parent->children, node_list_type::s_iterator_to(*other));
+ else
+ n->children.splice(n->children.end(), roots, node_list_type::s_iterator_to(*other));
+
+ other->parent = n;
+
+ aux[node_rank] = NULL;
+ node_rank = n->child_count();
+ } while (aux[node_rank] != NULL);
+ aux[node_rank] = n;
+ }
+
+ if (super_t::operator()(top_element->value, n->value))
+ top_element = n;
+ }
+ while (it != roots.end());
+ }
+
+ mutable node_pointer top_element;
+ node_list_type roots;
+#endif
+};
+
+} /* namespace heap */
+} /* namespace boost */
+
+#undef BOOST_HEAP_ASSERT
+
+#endif /* BOOST_HEAP_FIBONACCI_HEAP_HPP */

Added: trunk/boost/heap/heap_concepts.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/heap_concepts.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,101 @@
+// boost heap: concepts
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_CONCEPTS_HPP
+#define BOOST_HEAP_CONCEPTS_HPP
+
+#include <boost/concept_check.hpp>
+
+namespace boost {
+namespace heap {
+
+
+template <class C>
+struct PriorityQueue:
+ boost::ForwardContainer<C>
+{
+ typedef typename C::iterator iterator;
+ typedef typename C::const_iterator const_iterator;
+ typedef typename C::allocator_type allocator_type;
+ typedef typename C::value_compare value_compare;
+ typedef typename C::value_type value_type;
+ typedef typename C::const_reference const_reference;
+
+
+ BOOST_CONCEPT_USAGE(PriorityQueue)
+ {
+ BOOST_CONCEPT_ASSERT((boost::Assignable<value_type>));
+ BOOST_CONCEPT_ASSERT((boost::Container<C>));
+ BOOST_CONCEPT_ASSERT((boost::EqualityComparable<C>));
+ BOOST_CONCEPT_ASSERT((boost::Comparable<C>));
+
+ BOOST_CONCEPT_ASSERT((boost::Const_BinaryPredicate<value_compare, value_type, value_type>));
+
+ c.swap(c2);
+ c.clear();
+ a = c.get_allocator();
+
+ typename PriorityQueue::value_type v;
+ c.push(v);
+
+ v = c.top();
+ c.pop();
+
+ value_compare cmp = c.value_comp();
+
+ // verify tags
+ bool has_ordered_iterators = C::has_ordered_iterators;
+ bool is_mergable = C::is_mergable;
+ bool is_stable = C::is_stable;
+ }
+
+private:
+ C c, c2;
+ allocator_type a;
+ typename C::value_type v;
+};
+
+template <class C>
+struct MergablePriorityQueue:
+ PriorityQueue<C>
+{
+ BOOST_CONCEPT_USAGE(MergablePriorityQueue)
+ {
+ C c, c2;
+ c.merge(c2);
+ }
+};
+
+
+template <class C>
+struct MutablePriorityQueue:
+ PriorityQueue<C>
+{
+ typedef typename C::handle_type handle_type;
+
+ BOOST_CONCEPT_USAGE(MutablePriorityQueue)
+ {
+ BOOST_CONCEPT_ASSERT((boost::Assignable<typename MutablePriorityQueue::handle_type>));
+
+ typename MutablePriorityQueue::value_type v;
+ typename MutablePriorityQueue::handle_type h = c.push(v);
+ c.update(h, v);
+ c.increase(h, v);
+ c.decrease(h, v);
+
+ c.update(h);
+ c.increase(h);
+ c.decrease(h);
+ }
+
+ C c;
+};
+
+}}
+
+#endif /* BOOST_HEAP_CONCEPTS_HPP */

Added: trunk/boost/heap/heap_merge.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/heap_merge.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,125 @@
+// boost heap: heap merge algorithms
+//
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_MERGE_HPP
+#define BOOST_HEAP_MERGE_HPP
+
+#include <boost/concept/assert.hpp>
+#include <boost/heap/heap_concepts.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+template <typename Heap1, typename Heap2>
+struct heap_merge_emulate
+{
+ struct dummy_reserver
+ {
+ static void reserve (Heap1 & lhs, std::size_t required_size)
+ {}
+ };
+
+ struct reserver
+ {
+ static void reserve (Heap1 & lhs, std::size_t required_size)
+ {
+ lhs.reserve(required_size);
+ }
+ };
+
+ typedef typename boost::mpl::if_c<Heap1::has_reserve,
+ reserver,
+ dummy_reserver>::type space_reserver;
+
+ static void merge(Heap1 & lhs, Heap2 & rhs)
+ {
+ if (Heap1::constant_time_size && Heap2::constant_time_size) {
+ if (Heap1::has_reserve) {
+ std::size_t required_size = lhs.size() + rhs.size();
+ space_reserver::reserve(lhs, required_size);
+ }
+ }
+
+ // FIXME: container adaptors could benefit from first appending all elements and then restoring the heap order
+ // FIXME: optimize: if we have ordered iterators and we can efficiently insert keys with a below the lowest key in the heap
+ // d-ary, b and fibonacci heaps fall into this category
+
+ while (!rhs.empty()) {
+ lhs.push(rhs.top());
+ rhs.pop();
+ }
+
+ lhs.set_stability_count(std::max(lhs.get_stability_count(),
+ rhs.get_stability_count()));
+ rhs.set_stability_count(0);
+ }
+
+};
+
+
+template <typename Heap>
+struct heap_merge_same_mergable
+{
+ static void merge(Heap & lhs, Heap & rhs)
+ {
+ lhs.merge(rhs);
+ }
+};
+
+
+template <typename Heap>
+struct heap_merge_same
+{
+ static const bool is_mergable = Heap::is_mergable;
+ typedef typename boost::mpl::if_c<is_mergable,
+ heap_merge_same_mergable<Heap>,
+ heap_merge_emulate<Heap, Heap>
+ >::type heap_merger;
+
+ static void merge(Heap & lhs, Heap & rhs)
+ {
+ heap_merger::merge(lhs, rhs);
+ }
+};
+
+} /* namespace detail */
+
+
+/** merge rhs into lhs
+ *
+ * \b Effect: lhs contains all elements that have been part of rhs, lhs is empty.
+ *
+ * */
+template <typename Heap1,
+ typename Heap2
+ >
+void heap_merge(Heap1 & lhs, Heap2 & rhs)
+{
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
+
+ // if this assertion is triggered, the value_compare types are incompatible
+ BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
+
+ const bool same_heaps = boost::is_same<Heap1, Heap2>::value;
+
+ typedef typename boost::mpl::if_c<same_heaps,
+ detail::heap_merge_same<Heap1>,
+ detail::heap_merge_emulate<Heap1, Heap2>
+ >::type heap_merger;
+
+ heap_merger::merge(lhs, rhs);
+}
+
+
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_MERGE_HPP */
\ No newline at end of file

Added: trunk/boost/heap/pairing_heap.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/pairing_heap.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,693 @@
+// boost heap: pairing heap
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_PAIRING_HEAP_HPP
+#define BOOST_HEAP_PAIRING_HEAP_HPP
+
+#include <algorithm>
+#include <vector>
+
+#include <boost/assert.hpp>
+
+#include <boost/heap/detail/heap_comparison.hpp>
+#include <boost/heap/detail/heap_node.hpp>
+#include <boost/heap/policies.hpp>
+#include <boost/heap/detail/stable_heap.hpp>
+#include <boost/heap/detail/tree_iterator.hpp>
+
+#ifndef BOOST_DOXYGEN_INVOKED
+#ifdef BOOST_HEAP_SANITYCHECKS
+#define BOOST_HEAP_ASSERT BOOST_ASSERT
+#else
+#define BOOST_HEAP_ASSERT(expression)
+#endif
+#endif
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
+ boost::parameter::optional<tag::compare>,
+ boost::parameter::optional<tag::stable>,
+ boost::parameter::optional<tag::constant_time_size>,
+ boost::parameter::optional<tag::stability_counter_type>
+ > pairing_heap_signature;
+
+template <typename T, typename Parspec>
+struct make_pairing_heap_base
+{
+ static const bool constant_time_size = parameter::binding<Parspec,
+ tag::constant_time_size,
+ boost::mpl::true_
+ >::type::value;
+ typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type;
+ typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument;
+ typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument;
+
+ typedef heap_node<typename base_type::internal_type, false> node_type;
+
+ typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
+
+ struct type:
+ base_type,
+ allocator_type
+ {
+ type(compare_argument const & arg):
+ base_type(arg)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ type(type && rhs):
+ base_type(std::move(static_cast<base_type&>(rhs))),
+ allocator_type(std::move(static_cast<allocator_type&>(rhs)))
+ {}
+
+ type & operator=(type && rhs)
+ {
+ base_type::operator=(std::move(static_cast<base_type&>(rhs)));
+ allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
+ }
+#endif
+ };
+};
+
+}
+
+/**
+ * \class pairing_heap
+ * \brief pairing heap
+ *
+ * Pairing heaps are self-adjusting binary heaps. Although design and implementation are rather simple,
+ * the complexity analysis is yet unsolved. For details, consult:
+ *
+ * Pettie, Seth (2005), "Towards a final analysis of pairing heaps",
+ * Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174â€“183
+ *
+ * The template parameter T is the type to be managed by the container.
+ * The user can specify additional options and if no options are provided default options are used.
+ *
+ * The container supports the following options:
+ * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
+ * - \c boost::heap::stable<>, defaults to \c stable<false>
+ * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
+ * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
+ * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
+ *
+ *
+ */
+#ifdef BOOST_DOXYGEN_INVOKED
+template<class T, class ...Options>
+#else
+template <typename T,
+ class A0 = boost::parameter::void_,
+ class A1 = boost::parameter::void_,
+ class A2 = boost::parameter::void_,
+ class A3 = boost::parameter::void_,
+ class A4 = boost::parameter::void_
+ >
+#endif
+class pairing_heap:
+ private detail::make_pairing_heap_base<T,
+ typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type
+ >::type
+{
+ typedef typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args;
+ typedef detail::make_pairing_heap_base<T, bound_args> base_maker;
+ typedef typename base_maker::type super_t;
+
+ typedef typename super_t::internal_type internal_type;
+ typedef typename super_t::size_holder_type size_holder;
+ typedef typename base_maker::allocator_argument allocator_argument;
+
+private:
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+#ifndef BOOST_DOXYGEN_INVOKED
+ struct implementation_defined:
+ detail::extract_allocator_types<typename base_maker::allocator_argument>
+ {
+ typedef T value_type;
+ typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
+ typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
+
+ typedef typename base_maker::compare_argument value_compare;
+ typedef typename base_maker::allocator_type allocator_type;
+
+ typedef typename allocator_type::pointer node_pointer;
+ typedef typename allocator_type::const_pointer const_node_pointer;
+
+ typedef detail::heap_node_list node_list_type;
+ typedef typename node_list_type::iterator node_list_iterator;
+ typedef typename node_list_type::const_iterator node_list_const_iterator;
+
+ typedef typename base_maker::node_type node;
+
+ typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
+ typedef typename super_t::internal_compare internal_compare;
+ typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
+
+ typedef detail::tree_iterator<node,
+ const value_type,
+ allocator_type,
+ value_extractor,
+ detail::pointer_to_reference<node>,
+ false,
+ false,
+ value_compare
+ > iterator;
+
+ typedef iterator const_iterator;
+
+ typedef detail::tree_iterator<node,
+ const value_type,
+ allocator_type,
+ value_extractor,
+ detail::pointer_to_reference<node>,
+ false,
+ true,
+ value_compare
+ > ordered_iterator;
+ };
+
+ typedef typename implementation_defined::node node;
+ typedef typename implementation_defined::node_pointer node_pointer;
+ typedef typename implementation_defined::node_list_type node_list_type;
+ typedef typename implementation_defined::node_list_iterator node_list_iterator;
+ typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
+ typedef typename implementation_defined::internal_compare internal_compare;
+
+ typedef boost::intrusive::list<detail::heap_node_base<true>,
+ boost::intrusive::constant_time_size<false>
+ > node_child_list;
+#endif
+
+public:
+ typedef T value_type;
+
+ typedef typename implementation_defined::size_type size_type;
+ typedef typename implementation_defined::difference_type difference_type;
+ typedef typename implementation_defined::value_compare value_compare;
+ typedef typename implementation_defined::allocator_type allocator_type;
+ typedef typename implementation_defined::reference reference;
+ typedef typename implementation_defined::const_reference const_reference;
+ typedef typename implementation_defined::pointer pointer;
+ typedef typename implementation_defined::const_pointer const_pointer;
+ /// \copydoc boost::heap::priority_queue::iterator
+ typedef typename implementation_defined::iterator iterator;
+ typedef typename implementation_defined::const_iterator const_iterator;
+ typedef typename implementation_defined::ordered_iterator ordered_iterator;
+
+ typedef typename implementation_defined::handle_type handle_type;
+
+ static const bool constant_time_size = super_t::constant_time_size;
+ static const bool has_ordered_iterators = true;
+ static const bool is_mergable = true;
+ static const bool is_stable = detail::extract_stable<bound_args>::value;
+ static const bool has_reserve = false;
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
+ explicit pairing_heap(value_compare const & cmp = value_compare()):
+ super_t(cmp), root(NULL)
+ {}
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
+ pairing_heap(pairing_heap const & rhs):
+ super_t(rhs), root(NULL)
+ {
+ if (rhs.empty())
+ return;
+
+ clone_tree(rhs);
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
+ pairing_heap(pairing_heap && rhs):
+ super_t(std::move(rhs)), root(rhs.root)
+ {
+ rhs.root = NULL;
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
+ pairing_heap & operator=(pairing_heap && rhs)
+ {
+ super_t::operator=(std::move(rhs));
+ root = rhs.root;
+ rhs.root = NULL;
+ return *this;
+ }
+#endif
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs)
+ pairing_heap & operator=(pairing_heap const & rhs)
+ {
+ clear();
+ size_holder::set_size(rhs.get_size());
+ static_cast<super_t&>(*this) = rhs;
+
+ clone_tree(rhs);
+ return *this;
+ }
+
+ ~pairing_heap(void)
+ {
+ while (!empty())
+ pop();
+ }
+
+ /// \copydoc boost::heap::priority_queue::empty
+ bool empty(void) const
+ {
+ return root == NULL;
+ }
+
+ /// \copydoc boost::heap::binomial_heap::size
+ size_type size(void) const
+ {
+ if (constant_time_size)
+ return size_holder::get_size();
+
+ if (root == NULL)
+ return 0;
+ else
+ return detail::count_nodes(root);
+ }
+
+ /// \copydoc boost::heap::priority_queue::max_size
+ size_type max_size(void) const
+ {
+ return allocator_type::max_size();
+ }
+
+ /// \copydoc boost::heap::priority_queue::clear
+ void clear(void)
+ {
+ if (empty())
+ return;
+
+ root->template clear_subtree<allocator_type>(*this);
+ root->~node();
+ allocator_type::deallocate(root, 1);
+ root = NULL;
+ size_holder::set_size(0);
+ }
+
+ /// \copydoc boost::heap::priority_queue::get_allocator
+ allocator_type get_allocator(void) const
+ {
+ return *this;
+ }
+
+ /// \copydoc boost::heap::priority_queue::swap
+ void swap(pairing_heap & rhs)
+ {
+ super_t::swap(rhs);
+ std::swap(root, rhs.root);
+ }
+
+
+ /// \copydoc boost::heap::priority_queue::top
+ const_reference top(void) const
+ {
+ BOOST_ASSERT(!empty());
+
+ return super_t::get_value(root->value);
+ }
+
+ /**
+ * \b Effects: Adds a new element to the priority queue. Returns handle to element
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * */
+ handle_type push(value_type const & v)
+ {
+ size_holder::increment();
+
+ node_pointer n = allocator_type::allocate(1);
+
+ new(n) node(super_t::make_node(v));
+
+ merge_node(n);
+ return handle_type(n);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ /**
+ * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * */
+ template <class... Args>
+ handle_type emplace(Args&&... args)
+ {
+ size_holder::increment();
+
+ node_pointer n = allocator_type::allocate(1);
+
+ new(n) node(super_t::make_node(std::forward<T>(args)...));
+
+ merge_node(n);
+ return handle_type(n);
+ }
+#endif
+
+ /**
+ * \b Effects: Removes the top element from the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * */
+ void pop(void)
+ {
+ BOOST_ASSERT(!empty());
+
+ erase(handle_type(root));
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * */
+ void update (handle_type handle, const_reference v)
+ {
+ handle.node_->value = super_t::make_node(v);
+ update(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void update (handle_type handle)
+ {
+ node_pointer n = handle.node_;
+
+ n->unlink();
+ if (!n->children.empty())
+ n = merge_nodes(n, merge_node_list(n->children));
+
+ if (n != root)
+ merge_node(n);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * \b Note: The new value is expected to be greater than the current one
+ * */
+ void increase (handle_type handle, const_reference v)
+ {
+ update(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void increase (handle_type handle)
+ {
+ update(handle);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * \b Note: The new value is expected to be less than the current one
+ * */
+ void decrease (handle_type handle, const_reference v)
+ {
+ update(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * \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!
+ * */
+ void decrease (handle_type handle)
+ {
+ update(handle);
+ }
+
+ /**
+ * \b Effects: Removes the element handled by \c handle from the priority_queue.
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ * */
+ void erase(handle_type handle)
+ {
+ node_pointer n = handle.node_;
+ if (n != root) {
+ n->unlink();
+ if (!n->children.empty())
+ merge_node(merge_node_list(n->children));
+ } else {
+ if (!n->children.empty())
+ root = merge_node_list(n->children);
+ else
+ root = NULL;
+ }
+
+ size_holder::decrement();
+ n->~node();
+ allocator_type::deallocate(n, 1);
+ }
+
+ /// \copydoc boost::heap::priority_queue::begin
+ iterator begin(void) const
+ {
+ return iterator(root, super_t::value_comp());
+ }
+
+ /// \copydoc boost::heap::priority_queue::end
+ iterator end(void) const
+ {
+ return iterator();
+ }
+
+ /// \copydoc boost::heap::fibonacci_heap::ordered_begin
+ ordered_iterator ordered_begin(void) const
+ {
+ return ordered_iterator(root, super_t::value_comp());
+ }
+
+ /// \copydoc boost::heap::fibonacci_heap::ordered_begin
+ ordered_iterator ordered_end(void) const
+ {
+ return ordered_iterator(NULL, super_t::value_comp());
+ }
+
+
+ /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
+ static handle_type s_handle_from_iterator(iterator const & it)
+ {
+ return super_t::s_handle_from_iterator(&*it);
+ }
+
+ /**
+ * \b Effects: Merge all elements from rhs into this
+ *
+ * \cond
+ * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
+ * \endcond
+ *
+ * \b Complexity: 2**2*log(log(N)) (amortized).
+ *
+ * */
+ void merge(pairing_heap & rhs)
+ {
+ if (rhs.empty())
+ return;
+
+ merge_node(rhs.root);
+
+ size_holder::add(rhs.get_size());
+ rhs.set_size(0);
+ rhs.root = NULL;
+
+ super_t::set_stability_count(std::max(super_t::get_stability_count(),
+ rhs.get_stability_count()));
+ rhs.set_stability_count(0);
+ }
+
+ /// \copydoc boost::heap::priority_queue::value_comp
+ value_compare const & value_comp(void) const
+ {
+ return super_t::value_comp();
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<(HeapType const & rhs) const
+ {
+ return detail::heap_compare(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>(HeapType const & rhs) const
+ {
+ return detail::heap_compare(rhs, *this);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>=(HeapType const & rhs) const
+ {
+ return !operator<(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<=(HeapType const & rhs) const
+ {
+ return !operator>(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator==(HeapType const & rhs) const
+ {
+ return detail::heap_equality(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator!=(HeapType const & rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+private:
+#if !defined(BOOST_DOXYGEN_INVOKED)
+ void clone_tree(pairing_heap const & rhs)
+ {
+ BOOST_HEAP_ASSERT(root == NULL);
+ if (rhs.empty())
+ return;
+
+ root = allocator_type::allocate(1);
+
+ new(root) node(static_cast<node const &>(*rhs.root), static_cast<allocator_type&>(*this));
+ }
+
+ void merge_node(node_pointer other)
+ {
+ BOOST_HEAP_ASSERT(other);
+ if (root != NULL)
+ root = merge_nodes(root, other);
+ else
+ root = other;
+ }
+
+ node_pointer merge_node_list(node_child_list & children)
+ {
+ assert(!children.empty());
+ node_pointer merged = merge_first_pair(children);
+ if (children.empty())
+ return merged;
+
+ node_child_list node_list;
+ node_list.push_back(*merged);
+
+ do {
+ node_pointer next_merged = merge_first_pair(children);
+ node_list.push_back(*next_merged);
+ } while (!children.empty());
+
+ return merge_node_list(node_list);
+ }
+
+ node_pointer merge_first_pair(node_child_list & children)
+ {
+ assert(!children.empty());
+ node_pointer first_child = static_cast<node_pointer>(&children.front());
+ children.pop_front();
+ if (children.empty())
+ return first_child;
+
+ node_pointer second_child = static_cast<node_pointer>(&children.front());
+ children.pop_front();
+
+ return merge_nodes(first_child, second_child);
+ }
+
+ node_pointer merge_nodes(node_pointer node1, node_pointer node2)
+ {
+ if (super_t::operator()(node1->value, node2->value))
+ std::swap(node1, node2);
+
+ node2->unlink();
+ node1->children.push_front(*node2);
+ return node1;
+ }
+
+ node_pointer root;
+#endif
+};
+
+
+} /* namespace heap */
+} /* namespace boost */
+
+#undef BOOST_HEAP_ASSERT
+#endif /* BOOST_HEAP_PAIRING_HEAP_HPP */

Added: trunk/boost/heap/policies.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/policies.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,169 @@
+// boost heap
+//
+// Copyright (C) 2010-2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_POLICIES_HPP
+#define BOOST_HEAP_POLICIES_HPP
+
+#include <boost/parameter.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/mpl/int.hpp>
+#include <boost/mpl/void.hpp>
+#include <../boost-trunk/boost/concept_check.hpp>
+
+
+namespace boost {
+namespace heap {
+
+#ifndef BOOST_DOXYGEN_INVOKED
+BOOST_PARAMETER_TEMPLATE_KEYWORD(allocator)
+BOOST_PARAMETER_TEMPLATE_KEYWORD(compare)
+
+namespace tag { struct stable; }
+
+template <bool T>
+struct stable:
+ boost::parameter::template_keyword<tag::stable, boost::mpl::bool_<T> >
+{};
+
+namespace tag { struct mutable_; }
+
+template <bool T>
+struct mutable_:
+ boost::parameter::template_keyword<tag::mutable_, boost::mpl::bool_<T> >
+{};
+
+
+namespace tag { struct constant_time_size; }
+
+template <bool T>
+struct constant_time_size:
+ boost::parameter::template_keyword<tag::constant_time_size, boost::mpl::bool_<T> >
+{};
+
+namespace tag { struct store_parent_pointer; }
+
+template <bool T>
+struct store_parent_pointer:
+ boost::parameter::template_keyword<tag::store_parent_pointer, boost::mpl::bool_<T> >
+{};
+
+namespace tag { struct arity; }
+
+template <unsigned int T>
+struct arity:
+ boost::parameter::template_keyword<tag::arity, boost::mpl::int_<T> >
+{};
+
+namespace tag { struct objects_per_page; }
+
+template <unsigned int T>
+struct objects_per_page:
+ boost::parameter::template_keyword<tag::objects_per_page, boost::mpl::int_<T> >
+{};
+
+BOOST_PARAMETER_TEMPLATE_KEYWORD(stability_counter_type)
+
+namespace detail {
+
+namespace mpl = boost::mpl;
+
+template <typename bound_args, typename tag_type>
+struct has_arg
+{
+ typedef typename boost::parameter::binding<bound_args, tag_type, mpl::void_>::type type;
+ static const bool value = mpl::is_not_void_<type>::type::value;
+};
+
+template <typename bound_args>
+struct extract_stable
+{
+ static const bool has_stable = has_arg<bound_args, tag::stable>::value;
+
+ typedef typename mpl::if_c<has_stable,
+ typename has_arg<bound_args, tag::stable>::type,
+ mpl::bool_<false>
+ >::type stable_t;
+
+ static const bool value = stable_t::value;
+};
+
+template <typename bound_args>
+struct extract_mutable
+{
+ static const bool has_mutable = has_arg<bound_args, tag::mutable_>::value;
+
+ typedef typename mpl::if_c<has_mutable,
+ typename has_arg<bound_args, tag::mutable_>::type,
+ mpl::bool_<false>
+ >::type mutable_t;
+
+ static const bool value = mutable_t::value;
+};
+
+}
+
+#else
+
+/** \brief Specifies the predicate for the heap order
+ */
+template <typename T>
+struct compare{};
+
+/** \brief Configure heap as mutable
+ *
+ * Certain heaps need to be configured specifically do be mutable.
+ *
+ * */
+template <bool T>
+struct mutable_{};
+
+/** \brief Specifies allocator for the internal memory management
+ */
+template <typename T>
+struct allocator{};
+
+/** \brief Configure a heap as \b stable
+ *
+ * A priority queue is stable, if elements with the same priority are popped from the heap, in the same order as
+ * they are inserted.
+ * */
+template <bool T>
+struct stable{};
+
+/** \brief Specifies the type for stability counter
+ *
+ * */
+template <typename IntType>
+struct stability_counter_type{};
+
+/** \brief Configures complexity of <tt> size() </tt>
+ *
+ * Specifies, whether size() should have linear or constant complexity.
+ * */
+template <bool T>
+struct constant_time_size{};
+
+/** \brief Store parent pointer in heap node.
+ *
+ * Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.
+ * */
+template <bool T>
+struct store_parent_pointer{};
+
+/** \brief Specify arity.
+ *
+ * Specifies the arity of a D-ary heap
+ * */
+template <unsigned int T>
+struct arity{};
+#endif
+
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_POLICIES_HPP */

Added: trunk/boost/heap/priority_queue.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/priority_queue.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,403 @@
+// boost heap: wrapper for stl heap
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_PRIORITY_QUEUE_HPP
+#define BOOST_HEAP_PRIORITY_QUEUE_HPP
+
+#include <algorithm>
+#include <queue>
+#include <vector>
+
+#include <boost/assert.hpp>
+
+#include <boost/heap/detail/heap_comparison.hpp>
+#include <boost/heap/detail/stable_heap.hpp>
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
+ boost::parameter::optional<tag::compare>,
+ boost::parameter::optional<tag::stable>,
+ boost::parameter::optional<tag::stability_counter_type>
+ > priority_queue_signature;
+}
+
+/**
+ * \class priority_queue
+ * \brief priority queue, based on stl heap functions
+ *
+ * The priority_queue class is a wrapper for the stl heap functions.<br>
+ * The template parameter T is the type to be managed by the container.
+ * The user can specify additional options and if no options are provided default options are used.
+ *
+ * The container supports the following options:
+ * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
+ * - \c boost::heap::stable<>, defaults to \c stable<false>
+ * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
+ * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
+ *
+ */
+#ifdef BOOST_DOXYGEN_INVOKED
+template<class T, class ...Options>
+#else
+template <typename T,
+ class A0 = boost::parameter::void_,
+ class A1 = boost::parameter::void_,
+ class A2 = boost::parameter::void_,
+ class A3 = boost::parameter::void_
+ >
+#endif
+class priority_queue:
+ private detail::make_heap_base<T, typename detail::priority_queue_signature::bind<A0, A1, A2, A3>::type, false>::type
+{
+ typedef detail::make_heap_base<T, typename detail::priority_queue_signature::bind<A0, A1, A2, A3>::type, false> heap_base_maker;
+
+ typedef typename heap_base_maker::type super_t;
+ typedef typename super_t::internal_type internal_type;
+ typedef std::vector<internal_type, typename heap_base_maker::allocator_argument> container_type;
+
+ template <typename Heap1, typename Heap2>
+ friend struct detail::heap_merge_emulate;
+
+ container_type q_;
+
+#ifndef BOOST_DOXYGEN_INVOKED
+ struct implementation_defined:
+ detail::extract_allocator_types<typename heap_base_maker::allocator_argument>
+ {
+ typedef typename heap_base_maker::compare_argument value_compare;
+ typedef detail::stable_heap_iterator<T, typename container_type::const_iterator, super_t> iterator;
+ typedef iterator const_iterator;
+ typedef typename container_type::allocator_type allocator_type;
+ };
+#endif
+
+public:
+ typedef T value_type;
+ typedef typename implementation_defined::size_type size_type;
+ typedef typename implementation_defined::difference_type difference_type;
+ typedef typename implementation_defined::value_compare value_compare;
+ typedef typename implementation_defined::allocator_type allocator_type;
+ typedef typename implementation_defined::reference reference;
+ typedef typename implementation_defined::const_reference const_reference;
+ typedef typename implementation_defined::pointer pointer;
+ typedef typename implementation_defined::const_pointer const_pointer;
+ /**
+ * \b Note: The iterator does not traverse the priority queue in order of the priorities.
+ * */
+ typedef typename implementation_defined::iterator iterator;
+ typedef typename implementation_defined::const_iterator const_iterator;
+
+ static const bool constant_time_size = true;
+ static const bool has_ordered_iterators = false;
+ static const bool is_mergable = false;
+ static const bool is_stable = heap_base_maker::is_stable;
+ static const bool has_reserve = true;
+
+ /**
+ * \b Effects: constructs an empty priority queue.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ explicit priority_queue(value_compare const & cmp = value_compare()):
+ super_t(cmp)
+ {}
+
+ /**
+ * \b Effects: copy-constructs priority queue from rhs.
+ *
+ * \b Complexity: Linear.
+ *
+ * */
+ priority_queue (priority_queue const & rhs):
+ super_t(rhs), q_(rhs.q_)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ /**
+ * \b Effects: C++11-style move constructor.
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Note: Only available, if BOOST_HAS_RVALUE_REFS is defined
+ * */
+ priority_queue(priority_queue && rhs):
+ super_t(std::move(rhs)), q_(std::move(rhs.q_))
+ {}
+
+ /**
+ * \b Effects: C++11-style move assignment.
+ *
+ * \b Complexity: Constant.
+ *
+ * \b Note: Only available, if BOOST_HAS_RVALUE_REFS is defined
+ * */
+ priority_queue & operator=(priority_queue && rhs)
+ {
+ super_t::operator=(std::move(rhs));
+ q_ = std::move(rhs.q_);
+ return *this;
+ }
+#endif
+
+ /**
+ * \b Effects: Assigns priority queue from rhs.
+ *
+ * \b Complexity: Linear.
+ *
+ * */
+ priority_queue & operator=(priority_queue const & rhs)
+ {
+ static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs);
+ q_ = rhs.q_;
+ return *this;
+ }
+
+ /**
+ * \b Effects: Returns true, if the priority queue contains no elements.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ bool empty(void) const
+ {
+ return q_.empty();
+ }
+
+ /**
+ * \b Effects: Returns the number of elements contained in the priority queue.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ size_type size(void) const
+ {
+ return q_.size();
+ }
+
+ /**
+ * \b Effects: Returns the maximum number of elements the priority queue can contain.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ size_type max_size(void) const
+ {
+ return q_.max_size();
+ }
+
+ /**
+ * \b Effects: Removes all elements from the priority queue.
+ *
+ * \b Complexity: Linear.
+ *
+ * */
+ void clear(void)
+ {
+ q_.clear();
+ }
+
+ /**
+ * \b Effects: Returns allocator.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ allocator_type get_allocator(void) const
+ {
+ return q_.get_allocator();
+ }
+
+ /**
+ * \b Effects: Returns a const_reference to the maximum element.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ const_reference top(void) const
+ {
+ BOOST_ASSERT(!empty());
+ return super_t::get_value(q_.front());
+ }
+
+ /**
+ * \b Effects: Adds a new element to the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized). Linear (worst case).
+ *
+ * */
+ void push(value_type const & v)
+ {
+ q_.push_back(super_t::make_node(v));
+ std::push_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ /**
+ * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
+ *
+ * \b Complexity: Logarithmic (amortized). Linear (worst case).
+ *
+ * */
+ template <class... Args>
+ void emplace(Args&&... args)
+ {
+ q_.emplace_back(super_t::make_node(std::forward<Args>(args)...));
+ std::push_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
+ }
+#endif
+
+ /**
+ * \b Effects: Removes the top element from the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized). Linear (worst case).
+ *
+ * */
+ void pop(void)
+ {
+ BOOST_ASSERT(!empty());
+ std::pop_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
+ q_.pop_back();
+ }
+
+ /**
+ * \b Effects: Swaps two priority queues.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ void swap(priority_queue & rhs)
+ {
+ super_t::swap(rhs);
+ q_.swap(rhs.q_);
+ }
+
+ /**
+ * \b Effects: Returns an iterator to the first element contained in the priority queue.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ iterator begin(void) const
+ {
+ return iterator(q_.begin());
+ }
+
+ /**
+ * \b Effects: Returns an iterator to the end of the priority queue.
+ *
+ * \b Complexity: Constant.
+ *
+ * */
+ iterator end(void) const
+ {
+ return iterator(q_.end());
+ }
+
+ /**
+ * \b Effects: Reserves memory for element_count elements
+ *
+ * \b Complexity: Linear.
+ *
+ * \b Node: Invalidates iterators
+ *
+ * */
+ void reserve(size_type element_count)
+ {
+ q_.reserve(element_count);
+ }
+
+ /**
+ * \b Effect: Returns the value_compare object used by the priority queue
+ *
+ * */
+ value_compare const & value_comp(void) const
+ {
+ return super_t::value_comp();
+ }
+
+ /**
+ * \b Returns: Element-wise comparison of heap data structures
+ *
+ * \b Requirement: the \c value_compare object of both heaps must match.
+ *
+ * */
+ template <typename HeapType>
+ bool operator<(HeapType const & rhs) const
+ {
+ return detail::heap_compare(*this, rhs);
+ }
+
+ /**
+ * \b Returns: Element-wise comparison of heap data structures
+ *
+ * \b Requirement: the \c value_compare object of both heaps must match.
+ *
+ * */
+ template <typename HeapType>
+ bool operator>(HeapType const & rhs) const
+ {
+ return detail::heap_compare(rhs, *this);
+ }
+
+ /**
+ * \b Returns: Element-wise comparison of heap data structures
+ *
+ * \b Requirement: the \c value_compare object of both heaps must match.
+ *
+ * */
+ template <typename HeapType>
+ bool operator>=(HeapType const & rhs) const
+ {
+ return !operator<(rhs);
+ }
+
+ /**
+ * \b Returns: Element-wise comparison of heap data structures
+ *
+ * \b Requirement: the \c value_compare object of both heaps must match.
+ *
+ * */
+ template <typename HeapType>
+ bool operator<=(HeapType const & rhs) const
+ {
+ return !operator>(rhs);
+ }
+
+ /** \brief Equivalent comparison
+ * \b Returns: True, if both heap data structures are equivalent.
+ *
+ * \b Requirement: the \c value_compare object of both heaps must match.
+ *
+ * */
+ template <typename HeapType>
+ bool operator==(HeapType const & rhs) const
+ {
+ return detail::heap_equality(*this, rhs);
+ }
+
+ /** \brief Equivalent comparison
+ * \b Returns: True, if both heap data structures are not equivalent.
+ *
+ * \b Requirement: the \c value_compare object of both heaps must match.
+ *
+ * */
+ template <typename HeapType>
+ bool operator!=(HeapType const & rhs) const
+ {
+ return !(*this == rhs);
+ }
+};
+
+} /* namespace heap */
+} /* namespace boost */
+
+#endif /* BOOST_HEAP_PRIORITY_QUEUE_HPP */

Added: trunk/boost/heap/skew_heap.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/heap/skew_heap.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,910 @@
+// boost heap: skew heap
+//
+// Copyright (C) 2010 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_HEAP_SKEW_HEAP_HPP
+#define BOOST_HEAP_SKEW_HEAP_HPP
+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include <boost/assert.hpp>
+#include <boost/array.hpp>
+
+#include <boost/heap/detail/heap_comparison.hpp>
+#include <boost/heap/detail/heap_node.hpp>
+#include <boost/heap/detail/stable_heap.hpp>
+#include <boost/heap/detail/tree_iterator.hpp>
+
+
+#ifndef BOOST_DOXYGEN_INVOKED
+#ifdef BOOST_HEAP_SANITYCHECKS
+#define BOOST_HEAP_ASSERT BOOST_ASSERT
+#else
+#define BOOST_HEAP_ASSERT(expression)
+#endif
+#endif
+
+namespace boost {
+namespace heap {
+namespace detail {
+
+template <typename node_pointer, bool store_parent_pointer>
+struct parent_holder
+{
+ parent_holder(void):
+ parent_(NULL)
+ {}
+
+ void set_parent(node_pointer parent)
+ {
+ BOOST_HEAP_ASSERT(static_cast<node_pointer>(this) != parent);
+ parent_ = parent;
+ }
+
+ node_pointer get_parent(void) const
+ {
+ return parent_;
+ }
+
+ node_pointer parent_;
+};
+
+template <typename node_pointer>
+struct parent_holder<node_pointer, false>
+{
+ void set_parent(node_pointer parent)
+ {}
+
+ node_pointer get_parent(void) const
+ {
+ return NULL;
+ }
+};
+
+
+template <typename value_type, bool store_parent_pointer>
+struct skew_heap_node:
+ parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer>
+{
+ typedef parent_holder<skew_heap_node<value_type, store_parent_pointer>*, store_parent_pointer> super_t;
+
+ typedef boost::array<skew_heap_node*, 2> child_list_type;
+ typedef typename child_list_type::iterator child_iterator;
+ typedef typename child_list_type::const_iterator const_child_iterator;
+
+ skew_heap_node(value_type const & v):
+ value(v)
+ {
+ children.assign(0);
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ skew_heap_node(value_type && v):
+ value(v)
+ {
+ children.assign(0);
+ }
+#endif
+
+ template <typename Alloc>
+ skew_heap_node (skew_heap_node const & rhs, Alloc & allocator, skew_heap_node * parent):
+ value(rhs.value)
+ {
+ super_t::set_parent(parent);
+ node_cloner<skew_heap_node, skew_heap_node, Alloc> cloner(allocator);
+ clone_child(0, rhs, cloner);
+ clone_child(1, rhs, cloner);
+ }
+
+ template <typename Cloner>
+ void clone_child(int index, skew_heap_node const & rhs, Cloner & cloner)
+ {
+ if (rhs.children[index])
+ children[index] = cloner(*rhs.children[index], this);
+ else
+ children[index] = NULL;
+ }
+
+ template <typename Alloc>
+ void clear_subtree(Alloc & alloc)
+ {
+ node_disposer<skew_heap_node, skew_heap_node, Alloc> disposer(alloc);
+ dispose_child(children[0], disposer);
+ dispose_child(children[1], disposer);
+ }
+
+ template <typename Disposer>
+ void dispose_child(skew_heap_node * node, Disposer & disposer)
+ {
+ if (node)
+ disposer(node);
+ }
+
+ std::size_t count_children(void) const
+ {
+ size_t ret = 1;
+ if (children[0])
+ ret += children[0]->count_children();
+ if (children[1])
+ ret += children[1]->count_children();
+
+ return ret;
+ }
+
+ template <typename HeapBase>
+ bool is_heap(typename HeapBase::value_compare const & cmp) const
+ {
+ for (const_child_iterator it = children.begin(); it != children.end(); ++it) {
+ const skew_heap_node * child = *it;
+
+ if (child == NULL)
+ continue;
+
+ if (store_parent_pointer)
+ BOOST_HEAP_ASSERT(child->get_parent() == this);
+
+ if (cmp(HeapBase::get_value(value), HeapBase::get_value(child->value)) ||
+ !child->is_heap<HeapBase>(cmp))
+ return false;
+ }
+ return true;
+ }
+
+ value_type value;
+ boost::array<skew_heap_node*, 2> children;
+};
+
+
+typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
+ boost::parameter::optional<tag::compare>,
+ boost::parameter::optional<tag::stable>,
+ boost::parameter::optional<tag::store_parent_pointer>,
+ boost::parameter::optional<tag::stability_counter_type>,
+ boost::parameter::optional<tag::constant_time_size>,
+ boost::parameter::optional<tag::mutable_>
+ > skew_heap_signature;
+
+template <typename T, typename BoundArgs>
+struct make_skew_heap_base
+{
+ static const bool constant_time_size = parameter::binding<BoundArgs,
+ tag::constant_time_size,
+ boost::mpl::true_
+ >::type::value;
+
+ typedef typename make_heap_base<T, BoundArgs, constant_time_size>::type base_type;
+ typedef typename make_heap_base<T, BoundArgs, constant_time_size>::allocator_argument allocator_argument;
+ typedef typename make_heap_base<T, BoundArgs, constant_time_size>::compare_argument compare_argument;
+
+ static const bool is_mutable = extract_mutable<BoundArgs>::value;
+ static const bool store_parent_pointer = parameter::binding<BoundArgs,
+ tag::store_parent_pointer,
+ boost::mpl::false_>::type::value || is_mutable;
+
+ typedef skew_heap_node<typename base_type::internal_type, store_parent_pointer> node_type;
+
+ typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
+
+ struct type:
+ base_type,
+ allocator_type
+ {
+ type(compare_argument const & arg):
+ base_type(arg)
+ {}
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ type(type && rhs):
+ base_type(std::move(static_cast<base_type&>(rhs))),
+ allocator_type(std::move(static_cast<allocator_type&>(rhs)))
+ {}
+
+ type & operator=(type && rhs)
+ {
+ base_type::operator=(std::move(static_cast<base_type&>(rhs)));
+ allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
+ }
+#endif
+ };
+};
+
+} /* namespace detail */
+
+/**
+ * \class skew_heap
+ * \brief skew heap
+ *
+ *
+ * The template parameter T is the type to be managed by the container.
+ * The user can specify additional options and if no options are provided default options are used.
+ *
+ * The container supports the following options:
+ * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
+ * - \c boost::heap::stable<>, defaults to \c stable<false>
+ * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
+ * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
+ * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
+ * - \c boost::heap::store_parent_pointer<>, defaults to \c store_parent_pointer<true>. Maintaining a parent pointer adds some
+ * maintenance and size overhead, but iterating a heap is more efficient.
+ * - \c boost::heap::mutable<>, defaults to \c mutable<false>.
+ *
+ */
+#ifdef BOOST_DOXYGEN_INVOKED
+template<class T, class ...Options>
+#else
+template <typename T,
+ class A0 = boost::parameter::void_,
+ class A1 = boost::parameter::void_,
+ class A2 = boost::parameter::void_,
+ class A3 = boost::parameter::void_,
+ class A4 = boost::parameter::void_,
+ class A5 = boost::parameter::void_,
+ class A6 = boost::parameter::void_
+ >
+#endif
+class skew_heap:
+ private detail::make_skew_heap_base<T,
+ typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type
+ >::type
+{
+ typedef typename detail::skew_heap_signature::bind<A0, A1, A2, A3, A4, A5, A6>::type bound_args;
+ typedef detail::make_skew_heap_base<T, bound_args> base_maker;
+ typedef typename base_maker::type super_t;
+
+ typedef typename super_t::internal_type internal_type;
+ typedef typename super_t::size_holder_type size_holder;
+ typedef typename base_maker::allocator_argument allocator_argument;
+
+ static const bool store_parent_pointer = base_maker::store_parent_pointer;
+ template <typename Heap1, typename Heap2>
+ friend struct heap_merge_emulate;
+
+ struct implementation_defined:
+ detail::extract_allocator_types<typename base_maker::allocator_argument>
+ {
+ typedef T value_type;
+
+ typedef typename base_maker::compare_argument value_compare;
+ typedef typename base_maker::allocator_type allocator_type;
+
+ typedef typename base_maker::node_type node;
+ typedef typename allocator_type::pointer node_pointer;
+ typedef typename allocator_type::const_pointer const_node_pointer;
+
+ typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
+
+ typedef boost::array<node_pointer, 2> child_list_type;
+ typedef typename child_list_type::iterator child_list_iterator;
+
+ typedef typename boost::mpl::if_c<false,
+ detail::recursive_tree_iterator<node,
+ child_list_iterator,
+ const value_type,
+ value_extractor,
+ detail::list_iterator_converter<node,
+ child_list_type
+ >
+ >,
+ detail::tree_iterator<node,
+ const value_type,
+ allocator_type,
+ value_extractor,
+ detail::dereferencer<node>,
+ true,
+ false,
+ value_compare
+ >
+ >::type iterator;
+
+ typedef iterator const_iterator;
+
+ typedef detail::tree_iterator<node,
+ const value_type,
+ allocator_type,
+ value_extractor,
+ detail::dereferencer<node>,
+ true,
+ true,
+ value_compare
+ > ordered_iterator;
+
+ typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
+ typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
+ };
+
+ typedef typename implementation_defined::value_extractor value_extractor;
+ typedef typename implementation_defined::node node;
+ typedef typename implementation_defined::node_pointer node_pointer;
+
+public:
+ typedef T value_type;
+
+ typedef typename implementation_defined::size_type size_type;
+ typedef typename implementation_defined::difference_type difference_type;
+ typedef typename implementation_defined::value_compare value_compare;
+ typedef typename implementation_defined::allocator_type allocator_type;
+ typedef typename implementation_defined::reference reference;
+ typedef typename implementation_defined::const_reference const_reference;
+ typedef typename implementation_defined::pointer pointer;
+ typedef typename implementation_defined::const_pointer const_pointer;
+
+ /// \copydoc boost::heap::priority_queue::iterator
+ typedef typename implementation_defined::iterator iterator;
+ typedef typename implementation_defined::const_iterator const_iterator;
+ typedef typename implementation_defined::ordered_iterator ordered_iterator;
+
+ static const bool constant_time_size = super_t::constant_time_size;
+ static const bool has_ordered_iterators = true;
+ static const bool is_mergable = true;
+ static const bool is_stable = detail::extract_stable<bound_args>::value;
+ static const bool has_reserve = false;
+ static const bool is_mutable = detail::extract_mutable<bound_args>::value;
+
+ typedef typename mpl::if_c<is_mutable, typename implementation_defined::handle_type, void*>::type handle_type;
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
+ explicit skew_heap(value_compare const & cmp = value_compare()):
+ super_t(cmp), root(NULL)
+ {}
+
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
+ skew_heap(skew_heap const & rhs):
+ super_t(rhs), root(0)
+ {
+ if (rhs.empty())
+ return;
+
+ clone_tree(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs)
+ skew_heap & operator=(skew_heap const & rhs)
+ {
+ clear();
+ size_holder::set_size(rhs.get_size());
+ static_cast<super_t&>(*this) = rhs;
+
+ clone_tree(rhs);
+ return *this;
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
+ skew_heap(skew_heap && rhs):
+ super_t(std::move(rhs)), root(rhs.root)
+ {
+ rhs.root = NULL;
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
+ skew_heap & operator=(skew_heap && rhs)
+ {
+ super_t::operator=(std::move(rhs));
+ root = rhs.root;
+ rhs.root = NULL;
+ return *this;
+ }
+#endif
+
+ ~skew_heap(void)
+ {
+ clear();
+ }
+
+ /**
+ * \b Effects: Adds a new element to the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * */
+ typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v)
+ {
+ typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper;
+ return push_helper::push(this, v);
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ /**
+ * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * */
+ template <class... Args>
+ typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args)
+ {
+ typedef typename mpl::if_c<is_mutable, push_handle, push_void>::type push_helper;
+ return push_helper::emplace(this, std::forward<Args>(args)...);
+ }
+#endif
+
+ /// \copydoc boost::heap::priority_queue::empty
+ bool empty(void) const
+ {
+ return root == NULL;
+ }
+
+ /// \copydoc boost::heap::binomial_heap::size
+ size_type size(void) const
+ {
+ if (constant_time_size)
+ return size_holder::get_size();
+
+ if (root == NULL)
+ return 0;
+ else
+ return root->count_children();
+ }
+
+ /// \copydoc boost::heap::priority_queue::max_size
+ size_type max_size(void) const
+ {
+ return allocator_type::max_size();
+ }
+
+ /// \copydoc boost::heap::priority_queue::clear
+ void clear(void)
+ {
+ if (empty())
+ return;
+
+ root->template clear_subtree<allocator_type>(*this);
+ root->~node();
+ allocator_type::deallocate(root, 1);
+
+ root = NULL;
+ size_holder::set_size(0);
+ }
+
+ /// \copydoc boost::heap::priority_queue::get_allocator
+ allocator_type get_allocator(void) const
+ {
+ return *this;
+ }
+
+ /// \copydoc boost::heap::priority_queue::swap
+ void swap(skew_heap & rhs)
+ {
+ super_t::swap(rhs);
+ std::swap(root, rhs.root);
+ }
+
+ /// \copydoc boost::heap::priority_queue::top
+ const_reference top(void) const
+ {
+ BOOST_ASSERT(!empty());
+
+ return super_t::get_value(root->value);
+ }
+
+ /**
+ * \b Effects: Removes the top element from the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * */
+ void pop(void)
+ {
+ BOOST_ASSERT(!empty());
+
+ node_pointer top = root;
+
+ root = merge_children(root);
+ size_holder::decrement();
+
+ if (root)
+ BOOST_HEAP_ASSERT(root->get_parent() == NULL);
+ else
+ BOOST_HEAP_ASSERT(size_holder::get_size() == 0);
+
+ top->~node();
+ allocator_type::deallocate(top, 1);
+ sanity_check();
+ }
+
+ /// \copydoc boost::heap::priority_queue::begin
+ iterator begin(void) const
+ {
+ return iterator(root, super_t::value_comp());
+ }
+
+ /// \copydoc boost::heap::priority_queue::end
+ iterator end(void) const
+ {
+ return iterator();
+ }
+
+ /// \copydoc boost::heap::fibonacci_heap::ordered_begin
+ ordered_iterator ordered_begin(void) const
+ {
+ return ordered_iterator(root, super_t::value_comp());
+ }
+
+ /// \copydoc boost::heap::fibonacci_heap::ordered_begin
+ ordered_iterator ordered_end(void) const
+ {
+ return ordered_iterator(0, super_t::value_comp());
+ }
+
+ /**
+ * \b Effects: Merge all elements from rhs into this
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * */
+ void merge(skew_heap & rhs)
+ {
+ if (rhs.empty())
+ return;
+
+ merge_node(rhs.root);
+
+ size_holder::add(rhs.get_size());
+ rhs.set_size(0);
+ rhs.root = NULL;
+ sanity_check();
+
+ super_t::set_stability_count(std::max(super_t::get_stability_count(),
+ rhs.get_stability_count()));
+ rhs.set_stability_count(0);
+ }
+
+ /// \copydoc boost::heap::priority_queue::value_comp
+ value_compare const & value_comp(void) const
+ {
+ return super_t::value_comp();
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<(HeapType const & rhs) const
+ {
+ return detail::heap_compare(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>(HeapType const & rhs) const
+ {
+ return detail::heap_compare(rhs, *this);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator>=(HeapType const & rhs) const
+ {
+ return !operator<(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator<=(HeapType const & rhs) const
+ {
+ return !operator>(rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator==(HeapType const & rhs) const
+ {
+ return detail::heap_equality(*this, rhs);
+ }
+
+ /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
+ template <typename HeapType>
+ bool operator!=(HeapType const & rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+
+ /// \copydoc boost::heap::d_ary_heap::s_handle_from_iterator
+ static handle_type s_handle_from_iterator(iterator const & it)
+ {
+ return handle_type(&*it);
+ }
+
+ /**
+ * \b Effects: Removes the element handled by \c handle from the priority_queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ * */
+ void erase (handle_type object)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ node_pointer this_node = object.node_;
+
+ unlink_node(this_node);
+ size_holder::decrement();
+
+ sanity_check();
+ this_node->~node();
+ allocator_type::deallocate(this_node, 1);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * */
+ void update (handle_type handle, const_reference v)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ if (super_t::operator()(super_t::get_value(handle.node_->value), v))
+ increase(handle, v);
+ else
+ decrease(handle, v);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void update (handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ node_pointer this_node = handle.node_;
+
+ if (this_node->get_parent()) {
+ if (super_t::operator()(super_t::get_value(this_node->get_parent()->value),
+ super_t::get_value(this_node->value)))
+ increase(handle);
+ else
+ decrease(handle);
+ }
+ else
+ decrease(handle);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * \b Note: The new value is expected to be greater than the current one
+ * */
+ void increase (handle_type handle, const_reference v)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ handle.node_->value = super_t::make_node(v);
+ increase(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
+ * */
+ void increase (handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ node_pointer this_node = handle.node_;
+
+ if (this_node == root)
+ return;
+
+ node_pointer parent = this_node->get_parent();
+
+ if (this_node == parent->children[0])
+ parent->children[0] = NULL;
+ else
+ parent->children[1] = NULL;
+
+ this_node->set_parent(NULL);
+ merge_node(this_node);
+ }
+
+ /**
+ * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * \b Note: The new value is expected to be less than the current one
+ * */
+ void decrease (handle_type handle, const_reference v)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ handle.node_->value = super_t::make_node(v);
+ decrease(handle);
+ }
+
+ /**
+ * \b Effects: Updates the heap after the element handled by \c handle has been changed.
+ *
+ * \b Complexity: Logarithmic (amortized).
+ *
+ * \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!
+ * */
+ void decrease (handle_type handle)
+ {
+ BOOST_STATIC_ASSERT(is_mutable);
+ node_pointer this_node = handle.node_;
+
+ unlink_node(this_node);
+ this_node->children.assign(0);
+ this_node->set_parent(NULL);
+ merge_node(this_node);
+ }
+
+private:
+#if !defined(BOOST_DOXYGEN_INVOKED)
+ struct push_void
+ {
+ static void push(skew_heap * self, const_reference v)
+ {
+ self->push_internal(v);
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ template <class... Args>
+ static void emplace(skew_heap * self, Args&&... args)
+ {
+ self->emplace_internal(std::forward<Args>(args)...);
+ }
+#endif
+ };
+
+ struct push_handle
+ {
+ static handle_type push(skew_heap * self, const_reference v)
+ {
+ return handle_type(self->push_internal(v));
+ }
+
+#ifdef BOOST_HAS_RVALUE_REFS
+ template <class... Args>
+ static handle_type emplace(skew_heap * self, Args&&... args)
+ {
+ return handle_type(self->emplace_internal(std::forward<Args>(args)...));
+ }
+#endif
+ };
+
+ node_pointer push_internal(const_reference v)
+ {
+ size_holder::increment();
+
+ node_pointer n = super_t::allocate(1);
+ new(n) node(super_t::make_node(v));
+
+ merge_node(n);
+ return n;
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ template <class... Args>
+ node_pointer emplace_internal(Args&&... args)
+ {
+ size_holder::increment();
+
+ node_pointer n = super_t::allocate(1);
+ new(n) node(super_t::make_node(std::forward<Args>(args)...));
+
+ merge_node(n);
+ return n;
+ }
+#endif
+
+ void unlink_node(node_pointer node)
+ {
+ node_pointer parent = node->get_parent();
+ node_pointer merged_children = merge_children(node);
+
+ if (parent) {
+ if (node == parent->children[0])
+ parent->children[0] = merged_children;
+ else
+ parent->children[1] = merged_children;
+ }
+ else
+ root = merged_children;
+ }
+
+ void clone_tree(skew_heap const & rhs)
+ {
+ BOOST_HEAP_ASSERT(root == NULL);
+ if (rhs.empty())
+ return;
+
+ root = allocator_type::allocate(1);
+
+ new(root) node(*rhs.root, static_cast<allocator_type&>(*this), NULL);
+ }
+
+ void merge_node(node_pointer other)
+ {
+ BOOST_HEAP_ASSERT(other);
+ if (root != NULL)
+ root = merge_nodes(root, other, NULL);
+ else
+ root = other;
+ }
+
+ node_pointer merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent)
+ {
+ if (node1 == NULL) {
+ if (node2)
+ node2->set_parent(new_parent);
+ return node2;
+ }
+ if (node2 == NULL) {
+ node1->set_parent(new_parent);
+ return node1;
+ }
+
+ node_pointer merged = merge_nodes_recursive(node1, node2, new_parent);
+ return merged;
+ }
+
+ node_pointer merge_children(node_pointer node)
+ {
+ node_pointer parent = node->get_parent();
+ node_pointer merged_children = merge_nodes(node->children[0], node->children[1], parent);
+
+ return merged_children;
+ }
+
+ node_pointer merge_nodes_recursive(node_pointer node1, node_pointer node2, node_pointer new_parent)
+ {
+ if (super_t::operator()(node1->value, node2->value))
+ std::swap(node1, node2);
+
+ node * parent = node1;
+ node * child = node2;
+
+ if (parent->children[1]) {
+ node * merged = merge_nodes(parent->children[1], child, parent);
+ parent->children[1] = merged;
+ merged->set_parent(parent);
+ } else {
+ parent->children[1] = child;
+ child->set_parent(parent);
+ }
+
+
+ std::swap(parent->children[0], parent->children[1]);
+ parent->set_parent(new_parent);
+ return parent;
+ }
+
+ void sanity_check(void)
+ {
+#ifdef BOOST_HEAP_SANITYCHECKS
+ if (root)
+ BOOST_HEAP_ASSERT( root->template is_heap<super_t>(super_t::value_comp()) );
+
+ if (constant_time_size) {
+ size_type stored_size = size_holder::get_size();
+
+ size_type counted_size;
+ if (root == NULL)
+ counted_size = 0;
+ else
+ counted_size = root->count_children();
+
+ BOOST_HEAP_ASSERT(counted_size == stored_size);
+ }
+#endif
+ }
+
+ node_pointer root;
+#endif
+};
+
+} /* namespace heap */
+} /* namespace boost */
+
+#undef BOOST_HEAP_ASSERT
+#endif /* BOOST_HEAP_SKEW_HEAP_HPP */

Modified: trunk/doc/Jamfile.v2
==============================================================================
--- trunk/doc/Jamfile.v2 (original)
+++ trunk/doc/Jamfile.v2 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -58,6 +58,8 @@
     <dependency>../libs/signals2/doc//hello_world_def_code_snippet.xml
     <dependency>../libs/random/doc//random
     #<dependency>../libs/spirit/doc//spirit
+ <dependency>../libs/heap/doc//autodoc.xml
+ <dependency>../libs/heap/doc//heap

     ## Add path references to the QuickBook generated docs...

@@ -87,6 +89,7 @@
     <implicit-dependency>../libs/signals2/doc//hello_world_def_code_snippet.xml
     <implicit-dependency>../libs/random/doc//random
     #<implicit-dependency>../libs/spirit/doc//spirit
+ <implicit-dependency>../libs/heap/doc//heap

     <xsl:param>boost.libraries=../../libs/libraries.htm

Modified: trunk/doc/src/boost.xml
==============================================================================
--- trunk/doc/src/boost.xml (original)
+++ trunk/doc/src/boost.xml 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -295,6 +295,8 @@
      </libraryinfo>
    </library>

+ <xi:include href="heap.xml"/>
+
    <library name="Integer" dirname="integer" html-only="1"
             url="../../libs/integer/index.html">
      <libraryinfo>

Added: trunk/libs/heap/doc/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/heap/doc/Jamfile.v2 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,52 @@
+# Copyright 2010 Tim Blechmann
+# Distributed under the Boost Software License, Version 1.0. (See accompanying
+# file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+import doxygen ;
+import quickbook ;
+
+doxygen autodoc
+ :
+ [ glob ../../../boost/heap/*.hpp ] ../../../boost/heap/detail/mutable_heap.hpp
+ :
+ #<doxygen:param>EXTRACT_ALL=YES
+ <doxygen:param>"PREDEFINED=\"BOOST_DOXYGEN_INVOKED\" \\
+ \"BOOST_DEDUCED_TYPENAME=typename\" \\
+ \"BOOST_HAS_RVALUE_REFS\" \\
+ "
+ <doxygen:param>HIDE_UNDOC_MEMBERS=YES
+ <doxygen:param>HIDE_UNDOC_CLASSES=YES
+ <doxygen:param>INLINE_INHERITED_MEMB=YES
+ <doxygen:param>EXTRACT_PRIVATE=NO
+ <doxygen:param>ENABLE_PREPROCESSING=YES
+ <doxygen:param>MACRO_EXPANSION=YES
+ <doxygen:param>EXPAND_ONLY_PREDEF=YES
+ <doxygen:param>SEARCH_INCLUDES=YES
+ <doxygen:param>INCLUDE_PATH=$(BOOST_ROOT)
+ <doxygen:param>EXAMPLE_PATH=$(BOOST_ROOT)/libs/heap/examples
+ <doxygen:param>BRIEF_MEMBER_DESC=YES
+ <doxygen:param>REPEAT_BRIEF=YES
+ <doxygen:param>ALWAYS_DETAILED_SEC=YES
+ <doxygen:param>MULTILINE_CPP_IS_BRIEF=YES
+ ;
+
+xml heap : heap.qbk : ;
+
+boostbook standalone
+ : heap
+ : <xsl:param>html.stylesheet=boostbook.css
+ <xsl:param>boost.root=../../../..
+ <xsl:param>boost.libraries=../../../libraries.htm
+ <xsl:param>toc.max.depth=3
+ <xsl:param>toc.section.depth=1
+ <xsl:param>chunk.section.depth=1
+ <dependency>autodoc
+ <format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/libs/heap/doc/html
+ ;
+
+install css : [ glob $(BOOST_ROOT)/doc/src/*.css ]
+ : <location>html ;
+install images : [ glob $(BOOST_ROOT)/doc/src/images/*.png ]
+ : <location>html/images ;
+explicit css ;
+explicit images ;

Added: trunk/libs/heap/doc/heap.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/heap/doc/heap.qbk 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,422 @@
+[library Boost.Heap
+ [quickbook 1.4]
+ [authors [Blechmann, Tim]]
+ [copyright 2010-2011 Tim Blechmann]
+ [category algorithms]
+ [purpose
+ heap data structures
+ ]
+ [id heap]
+ [dirname heap]
+ [license
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ [@http://www.boost.org/LICENSE_1_0.txt])
+ ]
+]
+
+[c++]
+
+
+[/ Links ]
+
+[def _heap_ [^boost.heap]]
+
+[/ unspecified stuff ]
+[def __unspecified_int__ /unspecified-int-type/]
+[def __unspecified__ /unspecified/]
+[def __unspecified_bool__ /unspecified-bool-type/]
+
+[section Introduction & Motivation]
+
+_heap_ is an implementation of priority queues. Priority queues are queue data structures, that order their elements by
+a priority. The STL provides a single template class =std::priority_queue=, which only provides a limited functionality.
+To overcome these limitations, _heap_ implements [link heap.data_structures data structures] with more functionality and
+different performance characteristics. Especially, it deals with additional aspects:
+
+* *Mutability*: The priority of heap elements can be modified.
+* *Iterators*: Heaps provide iterators to iterate all elements.
+* *Mergable*: While all heaps can be merged, some can be merged efficiently.
+* *Stability*: Heaps can be configured to be stable sorted.
+* *Comparison*: Heaps can be compared for equivalence.
+
+[endsect]
+
+[section:concepts Concepts & Interface]
+
+[section:basic Basic Priority Queue Interface]
+
+Priority queues are queues of objects, that are ordered by their priority. They support the operations of adding nodes to
+the data structure, accessing the top element (the element with the highest priority), and removing the top element.
+
+[note _heap_ implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to
+the typical textbook design, which uses min-heaps.]
+
+[h5 Synopsis]
+
+ template <typename T, class ...Options>
+ class priority_queue
+ {
+ // types
+ typedef T value_type;
+ typedef ``/unspecified/`` size_type;
+ typedef ``/unspecified/`` difference_type;
+
+ typedef ``/unspecified/`` allocator_type;
+ typedef ``/unspecified/`` value_compare;
+
+ typedef ``/unspecified/`` reference;
+ typedef ``/unspecified/`` const_reference;
+ typedef ``/unspecified/`` pointer;
+ typedef ``/unspecified/`` const_pointer;
+
+ // construct/copy/destruct
+ explicit priority_queue(value_compare const & = value_compare());
+ priority_queue(priority_queue const &);
+ priority_queue& operator=(priority_queue const &);
+ priority_queue(priority_queue &&); // move semantics (C++11 only)
+ priority_queue& operator=(priority_queue &&); // move semantics (C++11 only)
+
+ // public member functions
+ ``/unspecified/`` push(const_reference); // push new element to heap
+ template<class... Args> void emplace(Args &&...); // push new element to heap, C++11 only
+ const_reference top() const; // return top element
+ void pop(); // remove top element
+ void clear(); // clear heap
+ size_type size() const; // number of elements
+ bool empty() const; // priority queue is empty
+ allocator_type get_allocator(void) const; // return allocator
+ size_type max_size(void) const; // maximal possible size
+ void reserve(size_type); // reserve space, only available if (has_reserve == true)
+
+ // heap equivalence
+ template<typename HeapType> bool operator==(HeapType const &) const;
+ template<typename HeapType> bool operator!=(HeapType const &) const;
+
+ // heap comparison
+ template<typename HeapType> bool operator<(HeapType const &) const;
+ template<typename HeapType> bool operator>(HeapType const &) const;
+ template<typename HeapType> bool operator>=(HeapType const &) const;
+ template<typename HeapType> bool operator<=(HeapType const &) const;
+
+ // public data members
+ static const bool constant_time_size; // size() has constant complexity
+ static const bool has_ordered_iterators; // priority queue has ``[link heap.concepts.iterators ordered iterators]``
+ static const bool is_mergable; // priority queue is efficiently ``[link heap.concepts.merge mergable]``
+ static const bool is_stable; // priority queue has a ``[link heap.concepts.stability stable heap order]``
+ static const bool has_reserve; // priority queue has a reserve() member
+ };
+
+[h5 Example]
+
+[import ../examples/interface.cpp]
+[basic_interface]
+
+[endsect]
+
+
+[section:iterators Priority Queue Iterators]
+
+[h5 Synopsis]
+ class iteratable_heap_interface
+ {
+ public:
+ // types
+ typedef ``/unspecified/`` iterator;
+ typedef ``/unspecified/`` const_iterator;
+ typedef ``/unspecified/`` ordered_iterator;
+
+ // public member functions
+ iterator begin(void) const;
+ iterator end(void) const;
+ ordered_iterator ordered_begin(void) const;
+ ordered_iterator ordered_end(void) const;
+ };
+
+Priority queues provide iterators, that can be used to traverse their elements. All heap iterators are const_iterators, that means
+they cannot be used to modify the values, because changing the value of a heap node may corrupt the heap order. Details about
+modifying heap nodes are described in the section about the [link heap.concepts.mutability mutability interface].
+
+Iterators do not visit heap elements in any specific order. Unless otherwise noted, all non-const heap member functions invalidate
+iterators, while all const member functions preserve the iterator validity.
+
+[note Some implementations require iterators, that contain a set of elements, that are *discovered*, but not *visited*. Therefore
+copying iterators can be inefficient and should be avoided.]
+
+[h5 Example]
+[iterator_interface]
+
+[section:ordered_iterators Ordered Iterators]
+
+Except for [classref boost::heap::priority_queue] all _heap_ data structures support ordered iterators, which visit all elements
+of the heap in heap-order. The implementation of these [^ordered_iterator]s requires some internal bookkeeping, so iterating the a
+heap in heap order has an amortized complexity of O(N*log(N)).
+
+[h5 Example]
+[ordered_iterator_interface]
+
+[endsect]
+
+[endsect]
+
+[section:comparing Comparing Priority Queues & Equivalence]
+
+The data structures of _heap_ can be compared with standard comparison operators. The comparison is performed by comparing two
+heaps element by element using =value_compare=.
+
+[note Depending on the heap type, this operation can be rather expensive, because both data structures need to be traversed in
+heap order. On heaps without ordered iterators, the heap needs to be copied internally. The typical complexity is O(n log(n)).]
+
+[endsect]
+
+
+[section:merge Merging Priority Queues]
+
+
+[h3 Mergable Priority Queues]
+
+[h5 Synopsis]
+ class mergable_heap_interface
+ {
+ public:
+ // public member functions
+ void merge(mergable_heap_interface &);
+ };
+
+_heap_ has a concept of a Mergable Priority Queue. A mergable priority queue can efficiently be merged with a different instance
+of the same type.
+
+[h5 Example]
+[merge_interface]
+
+
+[h3 Heap Merge Algorithms]
+
+_heap_ provides a =heap_merge()= algorithm that is can be used to merge different kinds of heaps. Using this algorithm, all _heap_
+data structures can be merged, although some cannot be merged efficiently.
+
+[h5 Example]
+[heap_merge_algorithm]
+
+[endsect]
+
+[section:mutability Mutability]
+
+Some priority queues of _heap_ are mutable, that means the priority of their elements can be changed. To achieve mutability,
+_heap_ introduces the concept of *handles*, which can be used to access the internal nodes of the priority queue in order to
+change its value and to restore the heap order.
+
+[h5 Synopsis]
+ class mutable_heap_interface
+ {
+ public:
+ typedef ``/unspecified/`` iterator;
+ struct handle_type
+ {
+ value_type & operator*() const;
+ };
+
+ static handle_type s_iterator_to_handle(iterator const &);
+
+ // priority queue interface
+ handle_type push(T const & v);
+
+ // update element via assignment and fix heap
+ void update(handle_type const & handle, value_type const & v);
+ void increase(handle_type const & handle, value_type const & v);
+ void decrease(handle_type const & handle, value_type const & v);
+
+ // fix heap after element has been changed via the handle
+ void update(handle_type const & handle);
+ void increase(handle_type const & handle);
+ void decrease(handle_type const & handle);
+ };
+
+[warning Incorrect use of =increase= or =decrease= may corrupt the priority queue data structure. If unsure use =update= can be
+used at the cost of efficiency.]
+
+[h5 Example]
+[mutable_interface]
+
+Note that handles can be stored inside the =value_type=:
+
+[mutable_interface_handle_in_value]
+
+[h3 The Fixup Interface]
+
+There are two different APIs to support mutability. The first family of functions provides update functionality by changing
+the current element by assigning a new value. The second family of functions can be used to fix the heap data structure after
+an element has been changed directly via a handle. While this provides the user with a means to modify the priority of queue
+elements without the need to change their non-priority part, this needs to be handled with care. The heap needs to be fixed up
+immediately after the priority of the element has been changed.
+
+
+Beside an =update= function, two additional functions =increase= and =decrease= are provided, that are generally more efficient
+than the generic =update= function. However the user has do ensure, that the priority of an element is changed to the right
+direction.
+
+[h5 Example]
+
+[mutable_fixup_interface]
+
+Iterators can be coverted to handles using the static member function =s_handle_from_iterator=. However most implementations of
+=update= invalidate all iterators. The most notable exception is the [classref boost::heap::fibonacci_heap fibonacci heap],
+providing a lazy update function, that just invalidates the iterators, that are related to this handle.
+
+[warning After changing the priority via a handle, the heap needs to be fixed by calling one of the update functions. Otherwise the
+priority queue structure may be corrupted!]
+
+[endsect]
+
+[section:stability Stability]
+
+A priority queue is `stable', if elements with the same priority are popped from the heap, in the same order as
+they are inserted. The data structures provided by _heap_, can be configured to be stable at compile time using the
+[classref boost::heap::stable] policy. Two notions of stability are supported. If a heap is configured with *no stability*,
+the order of nodes of the same priority is undefined, if it is configured as *stable*, nodes of the same priority are ordered by
+their insertion time.
+
+Stability is achieved by associating an integer version count with each value in order to distinguish values with the same node.
+The type of this version count defaults to =boost::uintmax_t=, which is at least 64bit on most systems. However it can be
+configured to use a different type using the [classref boost::heap::stability_counter_type] template argument.
+
+[warning The stability counter is prone to integer overflows. If an overflow occurs during a =push()= call, the operation
+ will fail and an exception is thrown. Later =push()= call will succeed, but the stable heap order will be compromised. However an
+ integer overflow at 64bit is very unlikely: if an application would issue one =push()= operation per microsecond, the value will
+ overflow in more than 500000 years.]
+
+[endsect]
+
+
+[endsect]
+
+[section:data_structures Data Structures]
+_heap_ provides the following data structures:
+
+[variablelist
+ [[[classref boost::heap::priority_queue]]
+ [
+ The [classref boost::heap::priority_queue priority_queue] class is a wrapper to the stl heap functions. It implements
+ a heap as container adaptor ontop of a =std::vector= and is immutable.
+ ]
+ ]
+
+ [[[classref boost::heap::d_ary_heap]]
+ [
+ [@http://en.wikipedia.org/wiki/D-ary_heap D-ary heaps] are a generalization of binary heap with each non-leaf node
+ having N children. For a low arity, the height of the heap is larger, but the number of comparisons to find the largest
+ child node is bigger. D-ary heaps are implemented as container adaptors based on a =std::vector=.
+
+ The data structure can be configured as mutable. This is achieved by storing the values inside a std::list.
+ ]
+ ]
+
+ [[[classref boost::heap::binomial_heap]]
+ [
+ [@http://en.wikipedia.org/wiki/Binomial_heap Binomial heaps] are node-base heaps, that are implemented as a set of
+ binomial trees of piecewise different order. The most important heap operations have a worst-case complexity of O(log n).
+ In contrast to d-ary heaps, binomial heaps can also be merged in O(log n).
+ ]
+ ]
+
+ [[[classref boost::heap::fibonacci_heap]]
+ [
+ [@http://en.wikipedia.org/wiki/Fibonacci_heap Fibonacci heaps] are node-base heaps, that are implemented as a forest of
+ heap-ordered trees. They provide better amortized performance than binomial heaps. Except =pop()= and =erase()=, the most
+ important heap operations have constant amortized complexity.
+ ]
+ ]
+
+ [[[classref boost::heap::pairing_heap]]
+ [
+ [@http://en.wikipedia.org/wiki/Pairing_heap Pairing heaps] are self-adjusting node-based heaps. Although design and
+ implementation are rather simple, the complexity analysis is yet unsolved. For details, consult:
+
+ Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174â€“183
+ ]
+ ]
+
+ [[[classref boost::heap::skew_heap]]
+ [
+ [@http://en.wikipedia.org/wiki/Skew_heap Skew heaps] are self-adjusting node-based heaps. Although there are no
+ constraints for the tree structure, all heap operations can be performed in O(log n).
+ ]
+ ]
+]
+
+[table Comparison of amortized complexity
+ [[] [[^top()]] [[^push()]] [[^pop()]] [[^update()]] [[^increase()]] [[^decrease()]] [[^erase()]] [[^merge_and_clear()]]]
+ [[[classref boost::heap::priority_queue]] [[^O(1)]] [O(log(N))] [O(log(N))] [n/a] [n/a] [n/a] [n/a] [O((N+M)*log(N+M))]]
+ [[[classref boost::heap::d_ary_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O((N+M)*log(N+M))]]
+ [[[classref boost::heap::binomial_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]]
+ [[[classref boost::heap::fibonacci_heap]] [[^O(1)]] [O(1)] [O(log(N))] [O(log(N))
+ [footnote The fibonacci a [^update_lazy()] method, which has O(log(N)) amortized complexity as well, but does not try to consolidate the internal forest]
+ ] [O(1)] [O(log(N))] [O(log(N))] [O(1)]]
+
+ [[[classref boost::heap::pairing_heap]] [[^O(1)]] [O(2**2*log(log(N)))] [O(log(N))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))]]
+ [[[classref boost::heap::skew_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]]
+]
+
+
+
+[section Data Structure Configuration]
+
+The data structures can be configured with [@boost:/libs/parameter/doc/html/index.html Boost.Parameter]-style templates.
+
+[variablelist
+ [[[classref boost::heap::compare]]
+ [Predicate for defining the heap order, optional
+ (defaults to =boost::heap::compare<std::less<T> >=)]
+ ]
+ [[[classref boost::heap::allocator]]
+ [Allocator for internal memory management, optional
+ (defaults to =boost::heap::allocator<std::allocator<T> >=)]
+ ]
+ [[[classref boost::heap::stable]]
+ [Configures the heap to use a [link heap.concepts.stability stable heap order], optional (defaults to =boost::heap::stable<false>=).
+ ]
+ ]
+ [[[classref boost::heap::mutable_]]
+ [Configures the heap to be mutable. [classref boost::heap::d_ary_heap] and [classref boost::heap::skew_heap] have to be configured
+ with this policy to enable the [link heap.concepts.mutability mutability interface].
+ ]
+ ]
+ [[[classref boost::heap::stability_counter_type]]
+ [Configures the integer type used for the stability counter, optional (defaults to =boost::heap::stability_counter_type<boost::uintmax_t>=).
+ For more details, consult the [link heap.concepts.stability Stability] section.
+ ]
+ ]
+ [[[classref boost::heap::constant_time_size]]
+ [Specifies, whether =size()= should have linear or constant complexity. This argument is only available for node-based
+ heap data structures and if available, it is optional (defaults to =boost::heap::constant_time_size<true>=)]
+ ]
+
+ [[[classref boost::heap::arity]]
+ [Specifies the arity of a d-ary heap. For details, please consult the class reference of [classref boost::heap::d_ary_heap]]
+ ]
+
+ [[[classref boost::heap::store_parent_pointer]]
+ [Store the parent pointer in the heap nodes. This policy is only available in the [classref boost::heap::skew_heap].
+ ]
+ ]
+]
+
+[endsect]
+
+[endsect]
+
+
+[xinclude autodoc.xml]
+
+
+[section Acknowledgements]
+
+[variablelist
+ [[Google Inc.]
+ [For sponsoring the development of this library during the Summer of Code 2010]
+ ]
+ [[Hartmut Kaiser]
+ [For mentoring the Summer of Code project]
+ ]
+]
+[endsect]
\ No newline at end of file

Added: trunk/libs/heap/examples/interface.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/examples/interface.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,261 @@
+/*=============================================================================
+ Copyright (c) 2010 Tim Blechmann
+
+ Use, modification and distribution is subject to the Boost Software
+ License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+=============================================================================*/
+
+#include <iostream>
+#include <iomanip>
+
+#include "../../../boost/heap/fibonacci_heap.hpp"
+
+using std::cout;
+using std::endl;
+using namespace boost::heap;
+
+//[ basic_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void basic_interface(void)
+{
+ PriorityQueue pq;
+
+ pq.push(2);
+ pq.push(3);
+ pq.push(1);
+
+ cout << "Priority Queue: popped elements" << endl;
+ cout << pq.top() << " "; // 3
+ pq.pop();
+ cout << pq.top() << " "; // 2
+ pq.pop();
+ cout << pq.top() << " "; // 1
+ pq.pop();
+ cout << endl;
+}
+//]
+
+//[ iterator_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void iterator_interface(void)
+{
+ PriorityQueue pq;
+
+ pq.push(2);
+ pq.push(3);
+ pq.push(1);
+
+ typename PriorityQueue::iterator begin = pq.begin();
+ typename PriorityQueue::iterator end = pq.end();
+
+ cout << "Priority Queue: iteration" << endl;
+ for (typename PriorityQueue::iterator it = begin; it != end; ++it)
+ cout << *it << " "; // 1, 2, 3 in unspecified order
+ cout << endl;
+}
+//]
+
+//[ ordered_iterator_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void ordered_iterator_interface(void)
+{
+ PriorityQueue pq;
+
+ pq.push(2);
+ pq.push(3);
+ pq.push(1);
+
+ typename PriorityQueue::ordered_iterator begin = pq.ordered_begin();
+ typename PriorityQueue::ordered_iterator end = pq.ordered_end();
+
+ cout << "Priority Queue: ordered iteration" << endl;
+ for (typename PriorityQueue::ordered_iterator it = begin; it != end; ++it)
+ cout << *it << " "; // 3, 2, 1 (i.e. 1, 2, 3 in heap order)
+ cout << endl;
+}
+//]
+
+
+//[ merge_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void merge_interface(void)
+{
+ PriorityQueue pq;
+
+ pq.push(3);
+ pq.push(5);
+ pq.push(1);
+
+ PriorityQueue pq2;
+
+ pq2.push(2);
+ pq2.push(4);
+ pq2.push(0);
+
+ pq.merge(pq2);
+
+ cout << "Priority Queue: merge" << endl;
+ cout << "first queue: ";
+ while (!pq.empty()) {
+ cout << pq.top() << " "; // 5 4 3 2 1 0
+ pq.pop();
+ }
+ cout << endl;
+
+ cout << "second queue: ";
+ while (!pq2.empty()) {
+ cout << pq2.top() << " "; // 4 2 0
+ pq2.pop();
+ }
+ cout << endl;
+}
+//]
+
+//[ heap_merge_algorithm
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void heap_merge_algorithm(void)
+{
+ PriorityQueue pq;
+
+ pq.push(3);
+ pq.push(5);
+ pq.push(1);
+
+ PriorityQueue pq2;
+
+ pq2.push(2);
+ pq2.push(4);
+ pq2.push(0);
+
+ boost::heap::heap_merge(pq, pq2);
+
+ cout << "Priority Queue: merge" << endl;
+ cout << "first queue: ";
+ while (!pq.empty()) {
+ cout << pq.top() << " "; // 5 4 3 2 1 0
+ pq.pop();
+ }
+ cout << endl;
+
+ cout << "second queue: ";
+ while (!pq2.empty()) {
+ cout << pq2.top() << " "; // 4 2 0
+ pq2.pop();
+ }
+ cout << endl;
+}
+//]
+
+//[ mutable_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void mutable_interface(void)
+{
+ PriorityQueue pq;
+ typedef typename PriorityQueue::handle_type handle_t;
+
+ handle_t t3 = pq.push(3);
+ handle_t t5 = pq.push(5);
+ handle_t t1 = pq.push(1);
+
+ pq.update(t3, 4);
+ pq.increase(t5, 7);
+ pq.decrease(t1, 0);
+
+ cout << "Priority Queue: update" << endl;
+ while (!pq.empty()) {
+ cout << pq.top() << " "; // 7, 4, 0
+ pq.pop();
+ }
+ cout << endl;
+}
+//]
+
+//[ mutable_fixup_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void mutable_fixup_interface(void)
+{
+ PriorityQueue pq;
+ typedef typename PriorityQueue::handle_type handle_t;
+
+ handle_t t3 = pq.push(3);
+ handle_t t5 = pq.push(5);
+ handle_t t1 = pq.push(1);
+
+ *t3 = 4;
+ pq.update(t3);
+
+ *t5 = 7;
+ pq.increase(t5, 7);
+
+ *t1 = 0;
+ pq.decrease(t1, 0);
+
+ cout << "Priority Queue: update with fixup" << endl;
+ while (!pq.empty()) {
+ cout << pq.top() << " "; // 7, 4, 0
+ pq.pop();
+ }
+ cout << endl;
+}
+//]
+
+//[ mutable_interface_handle_in_value
+struct heap_data
+{
+ fibonacci_heap<heap_data>::handle_type handle;
+ int payload;
+
+ heap_data(int i):
+ payload(i)
+ {}
+
+ bool operator<(heap_data const & rhs) const
+ {
+ return payload < rhs.payload;
+ }
+};
+
+void mutable_interface_handle_in_value(void)
+{
+ fibonacci_heap<heap_data> heap;
+ heap_data f(2);
+
+ fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
+ (*handle).handle = handle; // store handle in node
+}
+//]
+
+
+int main(void)
+{
+ using boost::heap::fibonacci_heap;
+
+ cout << std::setw(2);
+
+ basic_interface<fibonacci_heap<int> >();
+ cout << endl;
+
+ iterator_interface<fibonacci_heap<int> >();
+ cout << endl;
+
+ ordered_iterator_interface<fibonacci_heap<int> >();
+ cout << endl;
+
+ merge_interface<fibonacci_heap<int> >();
+ cout << endl;
+
+ mutable_interface<fibonacci_heap<int> >();
+ cout << endl;
+
+ mutable_fixup_interface<fibonacci_heap<int> >();
+
+ mutable_interface_handle_in_value();
+}
\ No newline at end of file

Added: trunk/libs/heap/test/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/Jamfile.v2 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,25 @@
+# (C) Copyright 2010: Tim Blechmann
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+import testing ;
+
+lib boost_unit_test_framework ;
+
+rule test_all
+{
+ local all_rules = ;
+
+ for local fileb in [ glob *.cpp ]
+ {
+ all_rules += [ run $(fileb) boost_unit_test_framework
+ : # additional args
+ : # test-files
+ : # requirements
+ ] ;
+ }
+
+ return $(all_rules) ;
+}
+
+test-suite heap : [ test_all r ] : <threading>multi ;

Added: trunk/libs/heap/test/binomial_heap_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/binomial_heap_test.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,50 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <algorithm>
+
+#include "../../../boost/heap/binomial_heap.hpp"
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size>
+void run_binomial_heap_test(void)
+{
+ typedef boost::heap::binomial_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size> > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue >();
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::binomial_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size> > stable_pri_queue;
+
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( binomial_heap_test )
+{
+ run_binomial_heap_test<false, false>();
+ run_binomial_heap_test<false, true>();
+ run_binomial_heap_test<true, false>();
+ run_binomial_heap_test<true, true>();
+}
\ No newline at end of file

Added: trunk/libs/heap/test/common_heap_tests.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/common_heap_tests.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,435 @@
+#ifndef COMMON_HEAP_TESTS_HPP_INCLUDED
+#define COMMON_HEAP_TESTS_HPP_INCLUDED
+
+#include <algorithm>
+#include <vector>
+
+#include <boost/concept/assert.hpp>
+#include <boost/concept_archetype.hpp>
+
+#include "../../../boost/heap/heap_concepts.hpp"
+
+
+typedef boost::default_constructible_archetype<
+ boost::less_than_comparable_archetype<
+ boost::copy_constructible_archetype<
+ boost::assignable_archetype<
+ > > > > test_value_type;
+
+
+typedef std::vector<int> test_data;
+const int test_size = 128;
+
+struct dummy_run
+{
+ static void run(void)
+ {}
+};
+
+
+test_data make_test_data(int size, int offset = 0, int strive = 1)
+{
+ test_data ret;
+
+ for (int i = 0; i != size; ++i)
+ ret.push_back(i * strive + offset);
+ return ret;
+}
+
+
+template <typename pri_queue, typename data_container>
+void check_q(pri_queue & q, data_container const & expected)
+{
+ BOOST_REQUIRE_EQUAL(q.size(), expected.size());
+
+ for (unsigned int i = 0; i != expected.size(); ++i)
+ {
+ BOOST_REQUIRE_EQUAL(q.size(), expected.size() - i);
+ BOOST_REQUIRE_EQUAL(q.top(), expected[expected.size()-1-i]);
+ q.pop();
+ }
+
+ BOOST_REQUIRE(q.empty());
+}
+
+
+template <typename pri_queue, typename data_container>
+void fill_q(pri_queue & q, data_container const & data)
+{
+ for (unsigned int i = 0; i != data.size(); ++i)
+ q.push(data[i]);
+}
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+template <typename pri_queue, typename data_container>
+void fill_emplace_q(pri_queue & q, data_container const & data)
+{
+ for (unsigned int i = 0; i != data.size(); ++i) {
+ auto value = data[i];
+ q.emplace(std::move(value));
+ }
+}
+#endif
+
+template <typename pri_queue>
+void pri_queue_test_sequential_push(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ fill_q(q, data);
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_sequential_reverse_push(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ std::reverse(data.begin(), data.end());
+ fill_q(q, data);
+ std::reverse(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_emplace(void)
+{
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ std::reverse(data.begin(), data.end());
+ fill_emplace_q(q, data);
+ std::reverse(data.begin(), data.end());
+ check_q(q, data);
+ }
+#endif
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_random_push(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+
+ test_data shuffled (data);
+ std::random_shuffle(shuffled.begin(), shuffled.end());
+
+ fill_q(q, shuffled);
+
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_copyconstructor(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ fill_q(q, data);
+
+ pri_queue r(q);
+
+ check_q(r, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_assignment(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ fill_q(q, data);
+
+ pri_queue r;
+ r = q;
+
+ check_q(r, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_moveconstructor(void)
+{
+#ifdef BOOST_HAS_RVALUE_REFS
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ fill_q(q, data);
+
+ pri_queue r(std::move(q));
+
+ check_q(r, data);
+ BOOST_REQUIRE(q.empty());
+#endif
+}
+
+template <typename pri_queue>
+void pri_queue_test_move_assignment(void)
+{
+#ifdef BOOST_HAS_RVALUE_REFS
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ fill_q(q, data);
+
+ pri_queue r;
+ r = std::move(q);
+
+ check_q(r, data);
+ BOOST_REQUIRE(q.empty());
+#endif
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_swap(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ test_data shuffled (data);
+ std::random_shuffle(shuffled.begin(), shuffled.end());
+ fill_q(q, shuffled);
+
+ pri_queue r;
+
+ q.swap(r);
+ check_q(r, data);
+ BOOST_REQUIRE(q.empty());
+ }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_iterators(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ test_data data = make_test_data(test_size);
+ test_data shuffled (data);
+ std::random_shuffle(shuffled.begin(), shuffled.end());
+ pri_queue q;
+ BOOST_REQUIRE(q.begin() == q.end());
+ fill_q(q, shuffled);
+
+ for (unsigned long i = 0; i != data.size(); ++i)
+ BOOST_REQUIRE(std::find(q.begin(), q.end(), data[i]) != q.end());
+
+ for (unsigned long i = 0; i != data.size(); ++i)
+ BOOST_REQUIRE(std::find(q.begin(), q.end(), data[i] + data.size()) == q.end());
+
+ test_data data_from_queue(q.begin(), q.end());
+ std::sort(data_from_queue.begin(), data_from_queue.end());
+
+ BOOST_REQUIRE(data == data_from_queue);
+
+ for (unsigned long i = 0; i != data.size(); ++i) {
+ BOOST_REQUIRE_EQUAL(std::distance(q.begin(), q.end()), data.size() - i);
+ q.pop();
+ }
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_ordered_iterators(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ test_data data = make_test_data(i);
+ test_data shuffled (data);
+ std::random_shuffle(shuffled.begin(), shuffled.end());
+ pri_queue q;
+ BOOST_REQUIRE(q.ordered_begin() == q.ordered_end());
+ fill_q(q, shuffled);
+
+ test_data data_from_queue(q.ordered_begin(), q.ordered_end());
+ std::reverse(data_from_queue.begin(), data_from_queue.end());
+ BOOST_REQUIRE(data == data_from_queue);
+
+ for (unsigned long i = 0; i != data.size(); ++i)
+ BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[i]) != q.ordered_end());
+
+ for (unsigned long i = 0; i != data.size(); ++i)
+ BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[i] + data.size()) == q.ordered_end());
+
+ for (unsigned long i = 0; i != data.size(); ++i) {
+ BOOST_REQUIRE_EQUAL(std::distance(q.begin(), q.end()), data.size() - i);
+ q.pop();
+ }
+ }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_equality(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q, r;
+ test_data data = make_test_data(i);
+ fill_q(q, data);
+ std::reverse(data.begin(), data.end());
+ fill_q(r, data);
+
+ BOOST_REQUIRE(r == q);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_inequality(void)
+{
+ for (int i = 1; i != test_size; ++i)
+ {
+ pri_queue q, r;
+ test_data data = make_test_data(i);
+ fill_q(q, data);
+ data[0] = data.back() + 1;
+ fill_q(r, data);
+
+ BOOST_REQUIRE(r != q);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_less(void)
+{
+ for (int i = 1; i != test_size; ++i)
+ {
+ pri_queue q, r;
+ test_data data = make_test_data(i);
+ test_data r_data(data);
+ r_data.pop_back();
+
+ fill_q(q, data);
+ fill_q(r, r_data);
+
+ BOOST_REQUIRE(r < q);
+ }
+
+ for (int i = 1; i != test_size; ++i)
+ {
+ pri_queue q, r;
+ test_data data = make_test_data(i);
+ test_data r_data(data);
+ data.push_back(data.back() + 1);
+
+ fill_q(q, data);
+ fill_q(r, r_data);
+
+ BOOST_REQUIRE(r < q);
+ }
+
+ for (int i = 1; i != test_size; ++i)
+ {
+ pri_queue q, r;
+ test_data data = make_test_data(i);
+ test_data r_data(data);
+
+ data.back() += 1;
+
+ fill_q(q, data);
+ fill_q(r, r_data);
+
+ BOOST_REQUIRE(r < q);
+ }
+
+ for (int i = 1; i != test_size; ++i)
+ {
+ pri_queue q, r;
+ test_data data = make_test_data(i);
+ test_data r_data(data);
+
+ r_data.front() -= 1;
+
+ fill_q(q, data);
+ fill_q(r, r_data);
+
+ BOOST_REQUIRE(r < q);
+ }
+
+}
+
+template <typename pri_queue>
+void pri_queue_test_clear(void)
+{
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(i);
+ fill_q(q, data);
+
+ q.clear();
+ BOOST_REQUIRE(q.size() == 0);
+ BOOST_REQUIRE(q.empty());
+ }
+}
+
+
+template <typename pri_queue>
+void run_concept_check(void)
+{
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+}
+
+template <typename pri_queue>
+void run_common_heap_tests(void)
+{
+ pri_queue_test_sequential_push<pri_queue>();
+ pri_queue_test_sequential_reverse_push<pri_queue>();
+ pri_queue_test_random_push<pri_queue>();
+ pri_queue_test_equality<pri_queue>();
+ pri_queue_test_inequality<pri_queue>();
+ pri_queue_test_less<pri_queue>();
+ pri_queue_test_clear<pri_queue>();
+
+ pri_queue_test_emplace<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_iterator_heap_tests(void)
+{
+ pri_queue_test_iterators<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_copyable_heap_tests(void)
+{
+ pri_queue_test_copyconstructor <pri_queue>();
+ pri_queue_test_assignment<pri_queue>();
+ pri_queue_test_swap<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_moveable_heap_tests(void)
+{
+ pri_queue_test_moveconstructor <pri_queue>();
+ pri_queue_test_move_assignment <pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_reserve_heap_tests(void)
+{
+ test_data data = make_test_data(test_size);
+ pri_queue q;
+ q.reserve(6);
+ fill_q(q, data);
+
+ check_q(q, data);
+}
+
+#endif // COMMON_HEAP_TESTS_HPP_INCLUDED

Added: trunk/libs/heap/test/d_ary_heap_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/d_ary_heap_test.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,104 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <algorithm>
+
+#include "../../../boost/heap/d_ary_heap.hpp"
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+
+template <int D, bool stable>
+void run_d_ary_heap_test(void)
+{
+ typedef boost::heap::d_ary_heap<int, boost::heap::arity<D>,
+ boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+
+ run_concept_check<pri_queue>();
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+ run_reserve_heap_tests<pri_queue>();
+ run_merge_tests<pri_queue>();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::d_ary_heap<q_tester, boost::heap::arity<D>,
+ boost::heap::stable<stable>
+ > stable_pri_queue;
+
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_test )
+{
+ run_d_ary_heap_test<2, false>();
+ run_d_ary_heap_test<3, false>();
+ run_d_ary_heap_test<4, false>();
+ run_d_ary_heap_test<5, false>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_stable_test )
+{
+ run_d_ary_heap_test<2, true>();
+ run_d_ary_heap_test<3, true>();
+ run_d_ary_heap_test<4, true>();
+ run_d_ary_heap_test<5, true>();
+}
+
+template <int D, bool stable>
+void run_d_ary_heap_mutable_test(void)
+{
+ typedef boost::heap::d_ary_heap<int, boost::heap::mutable_<true>,
+ boost::heap::arity<D>,
+ boost::heap::stable<stable>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+ run_reserve_heap_tests<pri_queue>();
+ run_mutable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::d_ary_heap<q_tester, boost::heap::mutable_<true>,
+ boost::heap::arity<D>,
+ boost::heap::stable<stable>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_mutable_test )
+{
+ run_d_ary_heap_mutable_test<2, false>();
+ run_d_ary_heap_mutable_test<3, false>();
+ run_d_ary_heap_mutable_test<4, false>();
+ run_d_ary_heap_mutable_test<5, false>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_mutable_stable_test )
+{
+ run_d_ary_heap_mutable_test<2, true>();
+ run_d_ary_heap_mutable_test<3, true>();
+ run_d_ary_heap_mutable_test<4, true>();
+ run_d_ary_heap_mutable_test<5, true>();
+}

Added: trunk/libs/heap/test/fibonacci_heap_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/fibonacci_heap_test.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,53 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <algorithm>
+
+#include "../../../boost/heap/fibonacci_heap.hpp"
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+
+template <bool stable, bool constant_time_size>
+void run_fibonacci_heap_test(void)
+{
+ typedef boost::heap::fibonacci_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue>();
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::fibonacci_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_test )
+{
+ run_fibonacci_heap_test<true, false>();
+ run_fibonacci_heap_test<true, true>();
+
+ run_fibonacci_heap_test<false, false>();
+ run_fibonacci_heap_test<false, true>();
+}

Added: trunk/libs/heap/test/merge_heap_tests.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/merge_heap_tests.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,67 @@
+#include "common_heap_tests.hpp"
+#include <boost/heap/heap_merge.hpp>
+
+#define GENERATE_TEST_DATA(INDEX) \
+ test_data data = make_test_data(test_size, 0, 1); \
+ std::random_shuffle(data.begin(), data.end()); \
+ \
+ test_data data_q (data.begin(), data.begin() + INDEX); \
+ test_data data_r (data.begin() + INDEX, data.end()); \
+ \
+ std::stable_sort(data.begin(), data.end());
+
+
+template <typename pri_queue>
+struct pri_queue_test_merge
+{
+ static void run(void)
+ {
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q, r;
+ GENERATE_TEST_DATA(i);
+
+ fill_q(q, data_q);
+ fill_q(r, data_r);
+
+ q.merge(r);
+
+ BOOST_REQUIRE(r.empty());
+ check_q(q, data);
+ }
+ }
+};
+
+
+template <typename pri_queue1, typename pri_queue2>
+struct pri_queue_test_heap_merge
+{
+ static void run (void)
+ {
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue1 q;
+ pri_queue2 r;
+ GENERATE_TEST_DATA(i);
+
+ fill_q(q, data_q);
+ fill_q(r, data_r);
+
+ boost::heap::heap_merge(q, r);
+
+ BOOST_REQUIRE(r.empty());
+ check_q(q, data);
+ }
+ }
+};
+
+
+
+template <typename pri_queue>
+void run_merge_tests(void)
+{
+ boost::mpl::if_c<pri_queue::is_mergable,
+ pri_queue_test_merge<pri_queue>,
+ dummy_run
+ >::type::run();
+
+ pri_queue_test_heap_merge<pri_queue, pri_queue>::run();
+}

Added: trunk/libs/heap/test/mutable_heap_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/mutable_heap_test.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,136 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <boost/heap/d_ary_heap.hpp>
+#include <boost/heap/fibonacci_heap.hpp>
+#include <boost/heap/pairing_heap.hpp>
+#include <boost/heap/binomial_heap.hpp>
+#include <boost/heap/skew_heap.hpp>
+
+using namespace boost::heap;
+
+
+typedef fibonacci_heap<struct fwd_declared_struct_1>::handle_type handle_type_1;
+typedef d_ary_heap<struct fwd_declared_struct_2, arity<4>, mutable_<true> >::handle_type handle_type_2;
+typedef pairing_heap<struct fwd_declared_struct_3>::handle_type handle_type_3;
+typedef binomial_heap<struct fwd_declared_struct_4>::handle_type handle_type_4;
+typedef skew_heap<struct fwd_declared_struct_5, mutable_<true> >::handle_type handle_type_5;
+
+template <typename HeapType>
+void run_handle_as_member_test(void)
+{
+ typedef typename HeapType::value_type value_type;
+ HeapType heap;
+ value_type f(2);
+ typename value_type::handle_type handle = heap.push(f);
+ value_type & fInHeap = *handle;
+ fInHeap.handle = handle;
+}
+
+
+struct fibonacci_heap_data
+{
+ typedef fibonacci_heap<fibonacci_heap_data>::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ fibonacci_heap_data(int i):i(i) {}
+
+ bool operator<(fibonacci_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_handle_as_member )
+{
+ run_handle_as_member_test<fibonacci_heap<fibonacci_heap_data> >();
+}
+
+struct d_heap_data
+{
+ typedef d_ary_heap<d_heap_data, arity<4>, mutable_<true> >::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ d_heap_data(int i):i(i) {}
+
+ bool operator<(d_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( d_heap_handle_as_member )
+{
+ run_handle_as_member_test<d_ary_heap<d_heap_data, arity<4>, mutable_<true> > >();
+}
+
+struct pairing_heap_data
+{
+ typedef pairing_heap<pairing_heap_data>::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ pairing_heap_data(int i):i(i) {}
+
+ bool operator<(pairing_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( pairing_heap_handle_as_member )
+{
+ run_handle_as_member_test<pairing_heap<pairing_heap_data> >();
+}
+
+
+struct binomial_heap_data
+{
+ typedef binomial_heap<binomial_heap_data>::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ binomial_heap_data(int i):i(i) {}
+
+ bool operator<(binomial_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( binomial_heap_handle_as_member )
+{
+ run_handle_as_member_test<binomial_heap<binomial_heap_data> >();
+}
+
+struct skew_heap_data
+{
+ typedef skew_heap<skew_heap_data, mutable_<true> >::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ skew_heap_data(int i):i(i) {}
+
+ bool operator<(skew_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_handle_as_member )
+{
+ run_handle_as_member_test<skew_heap<skew_heap_data, mutable_<true> > >();
+}

Added: trunk/libs/heap/test/mutable_heap_tests.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/mutable_heap_tests.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,290 @@
+#include <boost/random.hpp>
+
+#include "common_heap_tests.hpp"
+
+
+#define PUSH_WITH_HANDLES(HANDLES, Q, DATA) \
+ std::vector<typename pri_queue::handle_type> HANDLES; \
+ \
+ for (unsigned int k = 0; k != data.size(); ++k) \
+ HANDLES.push_back(Q.push(DATA[k]));
+
+
+
+template <typename pri_queue>
+void pri_queue_test_update_decrease(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ *handles[i] = -1;
+ data[i] = -1;
+ q.update(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_decrease_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = -1;
+ q.update(handles[i], -1);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_function_identity(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ q.update(handles[i], data[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_shuffled(void)
+{
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ test_data shuffled (data);
+ std::random_shuffle(shuffled.begin(), shuffled.end());
+
+ for (int i = 0; i != test_size; ++i)
+ q.update(handles[i], shuffled[i]);
+
+ check_q(q, data);
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_update_increase(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ *handles[i] = data[i];
+ q.update(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_increase_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ q.update(handles[i], data[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ *handles[i] = -1;
+ data[i] = -1;
+ q.decrease(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = -1;
+ q.decrease(handles[i], -1);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease_function_identity(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ q.decrease(handles[i], data[i]);
+
+ check_q(q, data);
+ }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_increase(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ *handles[i] = data[i];
+ q.increase(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_increase_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ q.increase(handles[i], data[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_increase_function_identity(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ q.increase(handles[i], data[i]);
+
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_erase(void)
+{
+ boost::mt19937 rng;
+
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ for (int j = 0; j != i; ++j)
+ {
+ boost::uniform_int<> range(0, data.size() - 1);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
+
+ int index = gen();
+ q.erase(handles[index]);
+ handles.erase(handles.begin() + index);
+ data.erase(data.begin() + index);
+ }
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_update_tests(void)
+{
+ pri_queue_test_update_increase<pri_queue>();
+ pri_queue_test_update_decrease<pri_queue>();
+
+ pri_queue_test_update_shuffled<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_update_function_tests(void)
+{
+ pri_queue_test_update_increase_function<pri_queue>();
+ pri_queue_test_update_decrease_function<pri_queue>();
+ pri_queue_test_update_function_identity<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_decrease_tests(void)
+{
+ pri_queue_test_decrease<pri_queue>();
+ pri_queue_test_decrease_function<pri_queue>();
+ pri_queue_test_decrease_function_identity<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_increase_tests(void)
+{
+ pri_queue_test_increase<pri_queue>();
+ pri_queue_test_increase_function<pri_queue>();
+ pri_queue_test_increase_function_identity<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_erase_tests(void)
+{
+ pri_queue_test_erase<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_tests(void)
+{
+ run_mutable_heap_update_function_tests<pri_queue>();
+ run_mutable_heap_update_tests<pri_queue>();
+ run_mutable_heap_decrease_tests<pri_queue>();
+ run_mutable_heap_increase_tests<pri_queue>();
+ run_mutable_heap_erase_tests<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_ordered_iterator_tests()
+{
+ pri_queue_test_ordered_iterators<pri_queue>();
+}

Added: trunk/libs/heap/test/pairing_heap_tests.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/pairing_heap_tests.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,51 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <algorithm>
+
+#include "../../../boost/heap/pairing_heap.hpp"
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size>
+void run_pairing_heap_test(void)
+{
+ typedef boost::heap::pairing_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size> > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue >();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::pairing_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( pairing_heap_test )
+{
+ run_pairing_heap_test<false, false>();
+ run_pairing_heap_test<false, true>();
+ run_pairing_heap_test<true, false>();
+ run_pairing_heap_test<true, true>();
+}

Added: trunk/libs/heap/test/priority_queue_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/priority_queue_test.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,37 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <algorithm>
+
+#include "../../../boost/heap/priority_queue.hpp"
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable>
+void run_common_priority_queue_tests(void)
+{
+ typedef boost::heap::priority_queue<int, boost::heap::stable<stable> > pri_queue;
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+
+ run_concept_check<pri_queue>();
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+ run_merge_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::priority_queue<q_tester, boost::heap::stable<stable> > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( std_pri_queue_test )
+{
+ run_common_priority_queue_tests<false>();
+ run_common_priority_queue_tests<true>();
+}

Added: trunk/libs/heap/test/skew_heap_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/skew_heap_test.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,97 @@
+#include <climits>
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MAIN
+#include "boost/test/included/unit_test.hpp"
+
+#include <algorithm>
+
+#include "../../../boost/heap/skew_heap.hpp"
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size, bool store_parent_pointer>
+void run_skew_heap_test(void)
+{
+ typedef boost::heap::skew_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size>,
+ boost::heap::store_parent_pointer<store_parent_pointer>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ pri_queue_test_ordered_iterators<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::skew_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size>,
+ boost::heap::store_parent_pointer<store_parent_pointer>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+template <bool stable, bool constant_time_size>
+void run_skew_heap_mutable_test(void)
+{
+ typedef boost::heap::skew_heap<int, boost::heap::stable<stable>, boost::heap::mutable_<true>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue >();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::skew_heap<q_tester, boost::heap::stable<stable>, boost::heap::mutable_<true>,
+ boost::heap::constant_time_size<constant_time_size>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_test )
+{
+ run_skew_heap_test<false, false, true>();
+ run_skew_heap_test<false, true, true>();
+ run_skew_heap_test<true, false, true>();
+ run_skew_heap_test<true, true, true>();
+
+ run_skew_heap_test<false, false, false>();
+ run_skew_heap_test<false, true, false>();
+ run_skew_heap_test<true, false, false>();
+ run_skew_heap_test<true, true, false>();
+}
+
+BOOST_AUTO_TEST_CASE( skew_heap_mutable_test )
+{
+ run_skew_heap_mutable_test<false, false>();
+ run_skew_heap_mutable_test<false, true>();
+ run_skew_heap_mutable_test<true, false>();
+ run_skew_heap_mutable_test<true, true>();
+}

Added: trunk/libs/heap/test/stable_heap_tests.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/test/stable_heap_tests.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,96 @@
+#include "common_heap_tests.hpp"
+
+struct q_tester
+{
+ q_tester(int i = 0, int j = 0):
+ value(i), id(j)
+ {}
+
+ bool operator< (q_tester const & rhs) const
+ {
+ return value < rhs.value;
+ }
+
+ bool operator>= (q_tester const & rhs) const
+ {
+ return value >= rhs.value;
+ }
+
+ bool operator== (q_tester const & rhs) const
+ {
+ return (value == rhs.value) && (id == rhs.id);
+ }
+
+ int value;
+ int id;
+};
+
+std::ostream& operator<< (std::ostream& out, q_tester const & t)
+{
+ out << "[" << t.value << " " << t.id << "";
+ return out;
+}
+
+typedef std::vector<q_tester> stable_test_data;
+
+stable_test_data make_stable_test_data(int size, int same_count = 3,
+ int offset = 0, int strive = 1)
+{
+ stable_test_data ret;
+
+ for (int i = 0; i != size; ++i)
+ for (int j = 0; j != same_count; ++j)
+ ret.push_back(q_tester(i * strive + offset, j));
+ return ret;
+}
+
+struct cmp1
+{
+ bool operator()(q_tester const & lhs, q_tester const & rhs)
+ {
+ return lhs.id > rhs.id;
+ }
+};
+
+struct cmp2 {
+ bool operator()(q_tester const & lhs, q_tester const & rhs)
+ {
+ return lhs.value < rhs.value;
+ }
+};
+
+void fixup_test_data(stable_test_data & data)
+{
+ std::stable_sort(data.begin(), data.end(), cmp1());
+ std::stable_sort(data.begin(), data.end(), cmp2());
+}
+
+template <typename pri_queue>
+void pri_queue_stable_test_sequential_push(void)
+{
+ stable_test_data data = make_stable_test_data(test_size);
+
+ pri_queue q;
+ fill_q(q, data);
+ fixup_test_data(data);
+ check_q(q, data);
+}
+
+template <typename pri_queue>
+void pri_queue_stable_test_sequential_reverse_push(void)
+{
+ stable_test_data data = make_stable_test_data(test_size);
+ pri_queue q;
+ stable_test_data push_data(data);
+ std::stable_sort(push_data.begin(), push_data.end(), std::greater_equal<q_tester>());
+ fill_q(q, push_data);
+ check_q(q, data);
+}
+
+
+template <typename pri_queue>
+void run_stable_heap_tests(void)
+{
+ pri_queue_stable_test_sequential_push<pri_queue>();
+ pri_queue_stable_test_sequential_reverse_push<pri_queue>();
+}

Added: trunk/libs/heap/tools/heap_benchmarks.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/tools/heap_benchmarks.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,269 @@
+#include <algorithm>
+#include <vector>
+
+#include <boost/foreach.hpp>
+#include "high_resolution_timer.hpp"
+
+#include <boost/heap/heap_merge.hpp>
+
+#if defined(__GNUC__) && (!defined __INTEL_COMPILER)
+#define no_inline __attribute__ ((noinline))
+#else
+#define no_inline
+#endif
+
+typedef std::vector<int> test_data;
+
+const int num_benchmarks = 1;
+
+inline test_data make_sequential_test_data(int size)
+{
+ test_data v(size);
+ for (int i = 0; i != size; ++i)
+ v[i] = i;
+ return v;
+}
+
+inline test_data make_test_data(int size)
+{
+ test_data v = make_sequential_test_data(size);
+ std::random_shuffle(v.begin(), v.end());
+ return v;
+}
+
+const int max_data = 20;
+
+test_data const & get_data(int index)
+{
+ static std::vector <test_data> data;
+ if (data.empty())
+ for (int i = 0; i != num_benchmarks; ++i)
+ data.push_back(make_test_data((1<<(max_data+1))+1024));
+
+ return data[index];
+}
+
+
+#define DEFINE_BENCHMARKS_SELECTOR(SUFFIX) \
+struct make_##SUFFIX \
+{ \
+ template <typename heap> \
+ struct rebind { \
+ typedef run_##SUFFIX<heap> type; \
+ }; \
+};
+
+
+template <typename pri_queue>
+void fill_heap(pri_queue & q, int index, int size, int offset = 0)
+{
+ test_data const & data = get_data(index);
+
+ for (int i = 0; i != size + 1; ++i) {
+ q.push(data[i]);
+ int top = q.top();
+ q.pop();
+ q.push(top);
+ }
+}
+
+template <typename pri_queue,
+ typename handle_container
+ >
+void fill_heap_with_handles(pri_queue & q, handle_container & handles, int index, int size, int offset = 0)
+{
+ test_data const & data = get_data(index);
+
+ for (int i = 0; i != size + 1; ++i) {
+ handles[i] = q.push(data[i]);
+
+ if (i > 0) {
+ typename pri_queue::handle_type last = handles[i-1];
+ int val = *last;
+ q.erase(last);
+ handles[i-1] = q.push(val);
+ }
+ }
+}
+
+
+template <typename pri_queue>
+struct run_sequential_push
+{
+ run_sequential_push(int size):
+ size(size)
+ {}
+
+ void prepare(int index)
+ {
+ q.clear();
+ fill_heap(q, index, size);
+ }
+
+ no_inline void operator()(int index)
+ {
+ test_data const & data = get_data(index);
+
+ for (int i = 0; i != 16; ++i)
+ q.push(data[(1<<max_data) + i]);
+ }
+
+ pri_queue q;
+ int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_push)
+
+template <typename pri_queue>
+struct run_sequential_pop
+{
+ run_sequential_pop(int size):
+ size(size)
+ {}
+
+ void prepare(int index)
+ {
+ q.clear();
+ fill_heap(q, index, size);
+ }
+
+ no_inline void operator()(int index)
+ {
+ for (int i = 0; i != 16; ++i)
+ q.pop();
+ }
+
+ pri_queue q;
+ int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_pop)
+
+template <typename pri_queue>
+struct run_sequential_increase
+{
+ run_sequential_increase(int size):
+ size(size), handles(size)
+ {}
+
+ void prepare(int index)
+ {
+ q.clear();
+ fill_heap_with_handles(q, handles, index, size);
+ }
+
+ no_inline void operator()(int index)
+ {
+ test_data const & data = get_data(index);
+ for (int i = 0; i != 16; ++i)
+ q.increase(handles[i], data[i] + (1<<max_data));
+ }
+
+ pri_queue q;
+ int size;
+ std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_increase)
+
+template <typename pri_queue>
+struct run_sequential_decrease
+{
+ run_sequential_decrease(int size):
+ size(size), handles(size)
+ {}
+
+ void prepare(int index)
+ {
+ q.clear();
+ fill_heap_with_handles(q, handles, index, size);
+ }
+
+ no_inline void operator()(int index)
+ {
+ test_data const & data = get_data(index);
+ for (int i = 0; i != 16; ++i)
+ q.decrease(handles[i], data[i] + (1<<max_data));
+ }
+
+ pri_queue q;
+ int size;
+ std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_decrease)
+
+template <typename pri_queue>
+struct run_merge_and_clear
+{
+ run_merge_and_clear(int size):
+ size(size)
+ {}
+
+ void prepare(int index)
+ {
+ q.clear();
+ r.clear();
+
+ fill_heap(q, index, size);
+ fill_heap(r, index, size, size);
+ }
+
+ no_inline void operator()(int index)
+ {
+ boost::heap::heap_merge(q, r);
+ }
+
+ pri_queue q, r;
+ int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(merge_and_clear)
+
+template <typename pri_queue>
+struct run_equivalence
+{
+ run_equivalence(int size):
+ size(size)
+ {}
+
+ void prepare(int index)
+ {
+ q.clear();
+ r.clear();
+ s.clear();
+
+ fill_heap(q, index, size);
+ fill_heap(r, index, size, size);
+ fill_heap(s, index, size);
+ }
+
+ no_inline bool operator()(int index)
+ {
+ return (q == r) ^ (q == s);
+ }
+
+ pri_queue q, r, s;
+ int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(equivalence)
+
+
+template <typename benchmark>
+inline double run_benchmark(benchmark & b)
+{
+ boost::high_resolution_timer timer;
+ std::vector<double> results;
+
+ for (int i = 0; i != num_benchmarks; ++i)
+ {
+ b.prepare(i);
+ timer.restart();
+ b(i);
+ double t = timer.elapsed();
+ results.push_back(t);
+ }
+
+ return results.at(results.size()/2); // median
+}

Added: trunk/libs/heap/tools/high_resolution_timer.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/tools/high_resolution_timer.hpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,208 @@
+/*=============================================================================
+ Copyright (c) 2005-2007 Hartmut Kaiser
+ 2007, 2009 Tim Blechmann
+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+=============================================================================*/
+#if !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+#define BOOST_HIGH_RESOLUTION_TIMER_HPP
+
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+
+#if _POSIX_C_SOURCE >= 199309L
+
+#include "time.h"
+
+#include <stdexcept>
+#include <limits>
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+ high_resolution_timer()
+ {
+ restart();
+ }
+
+ void restart()
+ {
+ int status = clock_gettime(CLOCK_REALTIME, &start_time);
+
+ if (status == -1)
+ boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+ }
+
+ double elapsed() const // return elapsed time in seconds
+ {
+ struct timespec now;
+
+ int status = clock_gettime(CLOCK_REALTIME, &now);
+
+ if (status == -1)
+ boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+ struct timespec diff;
+
+ double ret_sec = double(now.tv_sec - start_time.tv_sec);
+ double ret_nsec = double(now.tv_nsec - start_time.tv_nsec);
+
+ while (ret_nsec < 0)
+ {
+ ret_sec -= 1.0;
+ ret_nsec += 1e9;
+ }
+
+ double ret = ret_sec + ret_nsec / 1e9;
+
+ return ret;
+ }
+
+ double elapsed_max() const // return estimated maximum value for elapsed()
+ {
+ return double((std::numeric_limits<double>::max)());
+ }
+
+ double elapsed_min() const // return minimum value for elapsed()
+ {
+ return 0.0;
+ }
+
+private:
+ struct timespec start_time;
+};
+
+} // namespace boost
+
+#elif defined(__APPLE__)
+
+#import <mach/mach_time.h>
+
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+ high_resolution_timer(void)
+ {
+ mach_timebase_info_data_t info;
+
+ kern_return_t err = mach_timebase_info(&info);
+ if (err)
+ throw std::runtime_error("cannot create mach timebase info");
+
+ conversion_factor = (double)info.numer/(double)info.denom;
+ restart();
+ }
+
+ void restart()
+ {
+ start = mach_absolute_time();
+ }
+
+ double elapsed() const // return elapsed time in seconds
+ {
+ uint64_t now = mach_absolute_time();
+ double duration = double(now - start) * conversion_factor;
+
+ return duration
+ }
+
+ double elapsed_max() const // return estimated maximum value for elapsed()
+ {
+ return double((std::numeric_limits<double>::max)());
+ }
+
+ double elapsed_min() const // return minimum value for elapsed()
+ {
+ return 0.0;
+ }
+
+private:
+ uint64_t start;
+ double conversion_factor;
+};
+
+} // namespace boost
+
+#elif defined(BOOST_WINDOWS)
+
+#include <stdexcept>
+#include <limits>
+#include <windows.h>
+
+namespace boost {
+
+///////////////////////////////////////////////////////////////////////////////
+//
+// high_resolution_timer
+// A timer object measures elapsed time.
+// CAUTION: Windows only!
+//
+///////////////////////////////////////////////////////////////////////////////
+class high_resolution_timer
+{
+public:
+ high_resolution_timer()
+ {
+ start_time.QuadPart = 0;
+ frequency.QuadPart = 0;
+
+ if (!QueryPerformanceFrequency(&frequency))
+ boost::throw_exception(std::runtime_error("Couldn't acquire frequency"));
+
+ restart();
+ }
+
+ void restart()
+ {
+ if (!QueryPerformanceCounter(&start_time))
+ boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+ }
+
+ double elapsed() const // return elapsed time in seconds
+ {
+ LARGE_INTEGER now;
+ if (!QueryPerformanceCounter(&now))
+ boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+ return double(now.QuadPart - start_time.QuadPart) / frequency.QuadPart;
+ }
+
+ double elapsed_max() const // return estimated maximum value for elapsed()
+ {
+ return (double((std::numeric_limits<LONGLONG>::max)())
+ - double(start_time.QuadPart)) / double(frequency.QuadPart);
+ }
+
+ double elapsed_min() const // return minimum value for elapsed()
+ {
+ return 1.0 / frequency.QuadPart;
+ }
+
+private:
+ LARGE_INTEGER start_time;
+ LARGE_INTEGER frequency;
+};
+
+} // namespace boost
+
+#else
+
+// For other platforms, simply fall back to boost::timer
+#include <boost/timer.hpp>
+#include <boost/throw_exception.hpp>
+
+namespace boost {
+ typedef boost::timer high_resolution_timer;
+}
+
+#endif
+
+#endif // !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+

Added: trunk/libs/heap/tools/throughput_benchmarks.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/heap/tools/throughput_benchmarks.cpp 2011-12-06 05:17:35 EST (Tue, 06 Dec 2011)
@@ -0,0 +1,240 @@
+#include <iostream>
+#include <iomanip>
+
+
+#include "../../../boost/heap/d_ary_heap.hpp"
+#include "../../../boost/heap/pairing_heap.hpp"
+#include "../../../boost/heap/fibonacci_heap.hpp"
+#include "../../../boost/heap/binomial_heap.hpp"
+#include "../../../boost/heap/skew_heap.hpp"
+
+#include "heap_benchmarks.hpp"
+
+using namespace std;
+
+template <typename benchmark_selector>
+void run_benchmarks_immutable(void)
+{
+ for (int i = 4; i != max_data; ++i) {
+ for (int j = 0; j != 8; ++j) {
+ int size = 1<<i;
+ if (j%4 == 1)
+ size += 1<<(i-3);
+ if (j%4 == 2)
+ size += 1<<(i-2);
+ if (j%4 == 3)
+ size += (1<<(i-3)) + (1<<(i-2));
+ if (j >= 4)
+ size += (1<<(i-1));
+
+ cout << size << "\t";
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::binomial_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::fibonacci_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::pairing_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::skew_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::skew_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+ cout << endl;
+ }
+ }
+}
+
+template <typename benchmark_selector>
+void run_benchmarks_mutable(void)
+{
+ for (int i = 4; i != max_data; ++i)
+ {
+ for (int j = 0; j != 8; ++j)
+ {
+ int size = 1<<i;
+ if (j%4 == 1)
+ size += 1<<(i-3);
+ if (j%4 == 2)
+ size += 1<<(i-2);
+ if (j%4 == 3)
+ size += (1<<(i-3)) + (1<<(i-2));
+ if (j >= 4)
+ size += (1<<(i-1));
+
+ cout << size << "\t";
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::binomial_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::fibonacci_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::pairing_heap<long> >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+
+ {
+ typedef typename benchmark_selector::
+ template rebind<boost::heap::skew_heap<long, boost::heap::mutable_<true> > >
+ ::type benchmark_functor;
+ benchmark_functor benchmark(size);
+ double result = run_benchmark(benchmark);
+ cout << result << '\t';
+ }
+ cout << endl;
+ }
+ }
+}
+
+int main()
+{
+ cout << fixed << setprecision(12);
+
+ cout << "sequential push" << endl;
+ run_benchmarks_immutable<make_sequential_push>();
+
+ cout << endl << "sequential pop" << endl;
+ run_benchmarks_immutable<make_sequential_pop>();
+
+ cout << endl << "sequential increase" << endl;
+ run_benchmarks_mutable<make_sequential_increase>();
+
+ cout << endl << "sequential decrease" << endl;
+ run_benchmarks_mutable<make_sequential_decrease>();
+
+ cout << endl << "merge_and_clear" << endl;
+ run_benchmarks_immutable<make_merge_and_clear>();
+
+ cout << endl << "equivalence" << endl;
+ run_benchmarks_immutable<make_equivalence>();
+}

Next message: tim_at_[hidden]: "[Boost-commit] svn:boost r75822 - trunk/status"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r75820 - in trunk: boost/math/special_functions boost/math/special_functions/detail boost/math/tools libs/math/test"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk