Subject: [Boost-commit] svn:boost r81319 - in branches/release: boost/heap boost/heap/detail libs/heap libs/heap/examples libs/heap/test libs/heap/tools
From: tim_at_[hidden]
Date: 2012-11-13 06:16:55
Author: timblechmann
Date: 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
New Revision: 81319
URL: http://svn.boost.org/trac/boost/changeset/81319
Log:
heap: merge changes from trunk
Properties modified:
branches/release/boost/heap/ (props changed)
branches/release/libs/heap/ (props changed)
Text files modified:
branches/release/boost/heap/binomial_heap.hpp | 1 +
branches/release/boost/heap/d_ary_heap.hpp | 18 +++++++-----------
branches/release/boost/heap/detail/heap_comparison.hpp | 4 ++--
branches/release/boost/heap/detail/ilog2.hpp | 2 +-
branches/release/boost/heap/detail/mutable_heap.hpp | 13 ++++---------
branches/release/boost/heap/detail/ordered_adaptor_iterator.hpp | 4 ++--
branches/release/boost/heap/fibonacci_heap.hpp | 1 +
branches/release/boost/heap/pairing_heap.hpp | 5 +++--
branches/release/boost/heap/priority_queue.hpp | 1 +
branches/release/libs/heap/examples/interface.cpp | 2 +-
branches/release/libs/heap/test/binomial_heap_test.cpp | 20 ++++++++++++++++++++
branches/release/libs/heap/test/common_heap_tests.hpp | 19 ++++++++++++++++++-
branches/release/libs/heap/test/d_ary_heap_test.cpp | 20 ++++++++++++++++++++
branches/release/libs/heap/test/fibonacci_heap_test.cpp | 21 +++++++++++++++++++++
branches/release/libs/heap/test/merge_heap_tests.hpp | 8 ++++++++
branches/release/libs/heap/test/mutable_heap_test.cpp | 8 ++++++++
branches/release/libs/heap/test/mutable_heap_tests.hpp | 8 ++++++++
branches/release/libs/heap/test/pairing_heap_tests.cpp | 21 +++++++++++++++++++++
branches/release/libs/heap/test/priority_queue_test.cpp | 8 ++++++++
branches/release/libs/heap/test/skew_heap_test.cpp | 21 +++++++++++++++++++++
branches/release/libs/heap/test/stable_heap_tests.hpp | 8 ++++++++
branches/release/libs/heap/tools/heap_benchmarks.hpp | 8 ++++++++
branches/release/libs/heap/tools/throughput_benchmarks.cpp | 8 ++++++++
23 files changed, 200 insertions(+), 29 deletions(-)
Modified: branches/release/boost/heap/binomial_heap.hpp
==============================================================================
--- branches/release/boost/heap/binomial_heap.hpp (original)
+++ branches/release/boost/heap/binomial_heap.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -10,6 +10,7 @@
#define BOOST_HEAP_BINOMIAL_HEAP_HPP
#include <algorithm>
+#include <utility>
#include <vector>
#include <boost/assert.hpp>
Modified: branches/release/boost/heap/d_ary_heap.hpp
==============================================================================
--- branches/release/boost/heap/d_ary_heap.hpp (original)
+++ branches/release/boost/heap/d_ary_heap.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -10,6 +10,7 @@
#define BOOST_HEAP_D_ARY_HEAP_HPP
#include <algorithm>
+#include <utility>
#include <vector>
#include <boost/assert.hpp>
@@ -32,16 +33,11 @@
namespace heap {
namespace detail {
-template <typename T>
struct nop_index_updater
{
- void operator()(T &, std::size_t) const
+ template <typename T>
+ static void run(T &, std::size_t)
{}
-
- template <typename U>
- struct rebind {
- typedef nop_index_updater<U> other;
- };
};
typedef parameter::parameters<boost::parameter::required<tag::arity>,
@@ -69,7 +65,7 @@
typedef std::vector<internal_type, internal_type_allocator> container_type;
typedef typename container_type::const_iterator container_iterator;
- typedef typename IndexUpdater::template rebind<internal_type>::other index_updater;
+ typedef IndexUpdater index_updater;
container_type q_;
@@ -279,7 +275,7 @@
void reset_index(size_type index, size_type new_index)
{
BOOST_HEAP_ASSERT(index < q_.size());
- index_updater()(q_[index], new_index);
+ index_updater::run(q_[index], new_index);
}
void siftdown(size_type index)
@@ -423,8 +419,8 @@
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> >
+ priority_queue_mutable_wrapper<d_ary_heap<T, BoundArgs, nop_index_updater > >,
+ d_ary_heap<T, BoundArgs, nop_index_updater >
>::type type;
};
Modified: branches/release/boost/heap/detail/heap_comparison.hpp
==============================================================================
--- branches/release/boost/heap/detail/heap_comparison.hpp (original)
+++ branches/release/boost/heap/detail/heap_comparison.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -141,8 +141,8 @@
heap_equivalence_copy
>::type equivalence_check;
- equivalence_check check;
- return check(lhs, rhs);
+ equivalence_check eq_check;
+ return eq_check(lhs, rhs);
}
Modified: branches/release/boost/heap/detail/ilog2.hpp
==============================================================================
--- branches/release/boost/heap/detail/ilog2.hpp (original)
+++ branches/release/boost/heap/detail/ilog2.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -61,4 +61,4 @@
} /* namespace heap */
} /* namespace boost */
-#endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */
\ No newline at end of file
+#endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */
Modified: branches/release/boost/heap/detail/mutable_heap.hpp
==============================================================================
--- branches/release/boost/heap/detail/mutable_heap.hpp (original)
+++ branches/release/boost/heap/detail/mutable_heap.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -68,19 +68,13 @@
q_.set_stability_count(new_count);
}
- template <typename value_type>
struct index_updater
{
template <typename It>
- void operator()(It & it, size_type new_index)
+ static void run(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:
@@ -124,7 +118,7 @@
typedef typename PriorityQueueType::template rebind<list_iterator,
indirect_cmp,
- allocator_type, index_updater<list_iterator> >::other q_type;
+ allocator_type, index_updater >::other q_type;
protected:
q_type q_;
@@ -136,7 +130,7 @@
{}
priority_queue_mutable_wrapper(priority_queue_mutable_wrapper const & rhs):
- objects(rhs.objects)
+ q_(rhs.q_), objects(rhs.objects)
{
for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
q_.push(it);
@@ -144,6 +138,7 @@
priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper const & rhs)
{
+ q_ = rhs.q_;
objects = rhs.objects;
q_.clear();
for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
Modified: branches/release/boost/heap/detail/ordered_adaptor_iterator.hpp
==============================================================================
--- branches/release/boost/heap/detail/ordered_adaptor_iterator.hpp (original)
+++ branches/release/boost/heap/detail/ordered_adaptor_iterator.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -64,8 +64,8 @@
bool operator()(size_t lhs, size_t rhs)
{
- assert(lhs <= Dispatcher::max_index(container));
- assert(rhs <= Dispatcher::max_index(container));
+ BOOST_ASSERT(lhs <= Dispatcher::max_index(container));
+ BOOST_ASSERT(rhs <= Dispatcher::max_index(container));
return ValueCompare::operator()(Dispatcher::get_internal_value(container, lhs),
Dispatcher::get_internal_value(container, rhs));
}
Modified: branches/release/boost/heap/fibonacci_heap.hpp
==============================================================================
--- branches/release/boost/heap/fibonacci_heap.hpp (original)
+++ branches/release/boost/heap/fibonacci_heap.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -10,6 +10,7 @@
#define BOOST_HEAP_FIBONACCI_HEAP_HPP
#include <algorithm>
+#include <utility>
#include <vector>
#include <boost/array.hpp>
Modified: branches/release/boost/heap/pairing_heap.hpp
==============================================================================
--- branches/release/boost/heap/pairing_heap.hpp (original)
+++ branches/release/boost/heap/pairing_heap.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -10,6 +10,7 @@
#define BOOST_HEAP_PAIRING_HEAP_HPP
#include <algorithm>
+#include <utility>
#include <vector>
#include <boost/assert.hpp>
@@ -99,7 +100,7 @@
* 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
+ * 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.
@@ -655,7 +656,7 @@
node_pointer merge_node_list(node_child_list & children)
{
- assert(!children.empty());
+ BOOST_HEAP_ASSERT(!children.empty());
node_pointer merged = merge_first_pair(children);
if (children.empty())
return merged;
Modified: branches/release/boost/heap/priority_queue.hpp
==============================================================================
--- branches/release/boost/heap/priority_queue.hpp (original)
+++ branches/release/boost/heap/priority_queue.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -11,6 +11,7 @@
#include <algorithm>
#include <queue>
+#include <utility>
#include <vector>
#include <boost/assert.hpp>
Modified: branches/release/libs/heap/examples/interface.cpp
==============================================================================
--- branches/release/libs/heap/examples/interface.cpp (original)
+++ branches/release/libs/heap/examples/interface.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -258,4 +258,4 @@
mutable_fixup_interface<fibonacci_heap<int> >();
mutable_interface_handle_in_value();
-}
\ No newline at end of file
+}
Modified: branches/release/libs/heap/test/binomial_heap_test.cpp
==============================================================================
--- branches/release/libs/heap/test/binomial_heap_test.cpp (original)
+++ branches/release/libs/heap/test/binomial_heap_test.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,5 +1,17 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
+#ifdef BOOST_HEAP_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
#include <boost/test/unit_test.hpp>
+#endif
#include <algorithm>
@@ -46,3 +58,11 @@
run_binomial_heap_test<true, false>();
run_binomial_heap_test<true, true>();
}
+
+BOOST_AUTO_TEST_CASE( binomial_heap_compare_lookup_test )
+{
+ typedef boost::heap::binomial_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
Modified: branches/release/libs/heap/test/common_heap_tests.hpp
==============================================================================
--- branches/release/libs/heap/test/common_heap_tests.hpp (original)
+++ branches/release/libs/heap/test/common_heap_tests.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#ifndef COMMON_HEAP_TESTS_HPP_INCLUDED
#define COMMON_HEAP_TESTS_HPP_INCLUDED
@@ -18,7 +26,7 @@
typedef std::vector<int> test_data;
-const int test_size = 64;//128;
+const int test_size = 32;
struct dummy_run
{
@@ -432,4 +440,13 @@
check_q(q, data);
}
+struct less_with_T
+{
+ typedef int T;
+ bool operator()(const int& a, const int& b) const
+ {
+ return a < b;
+ }
+};
+
#endif // COMMON_HEAP_TESTS_HPP_INCLUDED
Modified: branches/release/libs/heap/test/d_ary_heap_test.cpp
==============================================================================
--- branches/release/libs/heap/test/d_ary_heap_test.cpp (original)
+++ branches/release/libs/heap/test/d_ary_heap_test.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,5 +1,17 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
+#ifdef BOOST_HEAP_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
#include <boost/test/unit_test.hpp>
+#endif
#include <algorithm>
@@ -100,3 +112,11 @@
run_d_ary_heap_mutable_test<4, true>();
run_d_ary_heap_mutable_test<5, true>();
}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_compare_lookup_test )
+{
+ typedef boost::heap::d_ary_heap<int, boost::heap::arity<2>,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
Modified: branches/release/libs/heap/test/fibonacci_heap_test.cpp
==============================================================================
--- branches/release/libs/heap/test/fibonacci_heap_test.cpp (original)
+++ branches/release/libs/heap/test/fibonacci_heap_test.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,5 +1,18 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
+#ifdef BOOST_HEAP_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
#include <boost/test/unit_test.hpp>
+#endif
+
#include <algorithm>
@@ -49,3 +62,11 @@
run_fibonacci_heap_test<false, false>();
run_fibonacci_heap_test<false, true>();
}
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_compare_lookup_test )
+{
+ typedef boost::heap::fibonacci_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
Modified: branches/release/libs/heap/test/merge_heap_tests.hpp
==============================================================================
--- branches/release/libs/heap/test/merge_heap_tests.hpp (original)
+++ branches/release/libs/heap/test/merge_heap_tests.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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 "common_heap_tests.hpp"
#include <boost/heap/heap_merge.hpp>
Modified: branches/release/libs/heap/test/mutable_heap_test.cpp
==============================================================================
--- branches/release/libs/heap/test/mutable_heap_test.cpp (original)
+++ branches/release/libs/heap/test/mutable_heap_test.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
#include <boost/test/unit_test.hpp>
Modified: branches/release/libs/heap/test/mutable_heap_tests.hpp
==============================================================================
--- branches/release/libs/heap/test/mutable_heap_tests.hpp (original)
+++ branches/release/libs/heap/test/mutable_heap_tests.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
// random uses boost.fusion, which clashes with boost.test
//#define USE_BOOST_RANDOM
Modified: branches/release/libs/heap/test/pairing_heap_tests.cpp
==============================================================================
--- branches/release/libs/heap/test/pairing_heap_tests.cpp (original)
+++ branches/release/libs/heap/test/pairing_heap_tests.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,5 +1,18 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
+#ifdef BOOST_HEAP_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
#include <boost/test/unit_test.hpp>
+#endif
+
#include <algorithm>
@@ -47,3 +60,11 @@
run_pairing_heap_test<true, false>();
run_pairing_heap_test<true, true>();
}
+
+BOOST_AUTO_TEST_CASE( pairing_heap_compare_lookup_test )
+{
+ typedef boost::heap::pairing_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
Modified: branches/release/libs/heap/test/priority_queue_test.cpp
==============================================================================
--- branches/release/libs/heap/test/priority_queue_test.cpp (original)
+++ branches/release/libs/heap/test/priority_queue_test.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
#include <boost/test/unit_test.hpp>
Modified: branches/release/libs/heap/test/skew_heap_test.cpp
==============================================================================
--- branches/release/libs/heap/test/skew_heap_test.cpp (original)
+++ branches/release/libs/heap/test/skew_heap_test.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,5 +1,18 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
#define BOOST_TEST_MAIN
+#ifdef BOOST_HEAP_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
#include <boost/test/unit_test.hpp>
+#endif
+
#include <algorithm>
@@ -93,3 +106,11 @@
run_skew_heap_mutable_test<true, false>();
run_skew_heap_mutable_test<true, true>();
}
+
+BOOST_AUTO_TEST_CASE( skew_heap_compare_lookup_test )
+{
+ typedef boost::heap::skew_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
Modified: branches/release/libs/heap/test/stable_heap_tests.hpp
==============================================================================
--- branches/release/libs/heap/test/stable_heap_tests.hpp (original)
+++ branches/release/libs/heap/test/stable_heap_tests.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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 <boost/foreach.hpp>
#include "common_heap_tests.hpp"
Modified: branches/release/libs/heap/tools/heap_benchmarks.hpp
==============================================================================
--- branches/release/libs/heap/tools/heap_benchmarks.hpp (original)
+++ branches/release/libs/heap/tools/heap_benchmarks.hpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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 <algorithm>
#include <vector>
Modified: branches/release/libs/heap/tools/throughput_benchmarks.cpp
==============================================================================
--- branches/release/libs/heap/tools/throughput_benchmarks.cpp (original)
+++ branches/release/libs/heap/tools/throughput_benchmarks.cpp 2012-11-13 06:16:53 EST (Tue, 13 Nov 2012)
@@ -1,3 +1,11 @@
+/*=============================================================================
+ 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>