Subject: [Boost-commit] svn:boost r76232 - in branches/release: boost/heap boost/heap/detail libs/heap libs/heap/test
From: tim_at_[hidden]
Date: 2011-12-30 08:16:33
Author: timblechmann
Date: 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
New Revision: 76232
URL: http://svn.boost.org/trac/boost/changeset/76232
Log:
heap: merge fixes 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 | 2 +-
branches/release/boost/heap/d_ary_heap.hpp | 3 ++-
branches/release/boost/heap/detail/heap_comparison.hpp | 8 ++++----
branches/release/boost/heap/detail/heap_node.hpp | 2 +-
branches/release/boost/heap/detail/mutable_heap.hpp | 17 ++++++++++++-----
branches/release/boost/heap/detail/ordered_adaptor_iterator.hpp | 5 ++++-
branches/release/boost/heap/detail/tree_iterator.hpp | 8 +++++---
branches/release/boost/heap/priority_queue.hpp | 3 ++-
branches/release/boost/heap/skew_heap.hpp | 8 ++++----
branches/release/libs/heap/test/common_heap_tests.hpp | 2 +-
branches/release/libs/heap/test/stable_heap_tests.hpp | 33 ++++++++++++++-------------------
11 files changed, 50 insertions(+), 41 deletions(-)
Modified: branches/release/boost/heap/binomial_heap.hpp
==============================================================================
--- branches/release/boost/heap/binomial_heap.hpp (original)
+++ branches/release/boost/heap/binomial_heap.hpp 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -807,7 +807,7 @@
if (it != trees.end())
BOOST_HEAP_ASSERT(static_cast<node_pointer>(&*it)->child_count() >= n->child_count());
- for (;;) {
+ while(true) {
BOOST_HEAP_ASSERT(!n->is_linked());
if (it == trees.end())
break;
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 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -65,7 +65,8 @@
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 heap_base_maker::allocator_argument::template rebind<internal_type>::other internal_type_allocator;
+ 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;
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 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -70,7 +70,7 @@
Heap1 lhs_copy(lhs);
Heap2 rhs_copy(rhs);
- for (;;) {
+ while (true) {
if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
return false;
@@ -112,7 +112,7 @@
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(;;) {
+ while (true) {
if (!value_equality(lhs, rhs, *it1, *it2))
return false;
@@ -165,7 +165,7 @@
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(;;) {
+ while (true) {
if (value_compare(lhs, rhs, *it1, *it2))
return true;
@@ -202,7 +202,7 @@
Heap1 lhs_copy(lhs);
Heap2 rhs_copy(rhs);
- for (;;) {
+ while (true) {
if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
return true;
Modified: branches/release/boost/heap/detail/heap_node.hpp
==============================================================================
--- branches/release/boost/heap/detail/heap_node.hpp (original)
+++ branches/release/boost/heap/detail/heap_node.hpp 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -178,7 +178,7 @@
{}
#endif
-protected:
+/* protected: */
heap_node(heap_node const & rhs):
value(rhs.value)
{
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 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -48,7 +48,7 @@
private:
typedef std::pair<value_type, size_type> node_type;
- typedef std::list<node_type, allocator_type> object_list;
+ typedef std::list<node_type, typename allocator_type::template rebind<node_type>::other> object_list;
typedef typename object_list::iterator list_iterator;
typedef typename object_list::const_iterator const_list_iterator;
@@ -149,13 +149,17 @@
#ifdef BOOST_HAS_RVALUE_REFS
priority_queue_mutable_wrapper (priority_queue_mutable_wrapper && rhs):
- q_(std::move(rhs.q_)), objects(std::move(rhs.objects))
- {}
+ q_(std::move(rhs.q_))
+ {
+ /// FIXME: msvc seems to invalidate iterators when moving std::list
+ std::swap(objects, rhs.objects);
+ }
priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper && rhs)
{
q_ = std::move(rhs.q_);
- objects = std::move(rhs.objects);
+ objects.clear();
+ std::swap(objects, rhs.objects);
return *this;
}
#endif
@@ -274,7 +278,10 @@
}
}
- std::priority_queue<iterator, std::vector<iterator, allocator_type>, indirect_cmp> unvisited_nodes;
+ std::priority_queue<iterator,
+ std::vector<iterator, typename allocator_type::template rebind<iterator>::other >,
+ indirect_cmp
+ > unvisited_nodes;
const priority_queue_mutable_wrapper * q_;
};
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 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -132,7 +132,10 @@
unvisited_nodes.push(i);
}
- std::priority_queue<size_t, std::vector<size_t, Alloc>, compare_by_heap_value> unvisited_nodes;
+ std::priority_queue<size_t,
+ std::vector<size_t, typename Alloc::template rebind<size_t>::other >,
+ compare_by_heap_value
+ > unvisited_nodes;
};
Modified: branches/release/boost/heap/detail/tree_iterator.hpp
==============================================================================
--- branches/release/boost/heap/detail/tree_iterator.hpp (original)
+++ branches/release/boost/heap/detail/tree_iterator.hpp 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -96,7 +96,7 @@
return data_.empty();
}
- std::vector<HandleType, Alloc> data_;
+ std::vector<HandleType, typename Alloc::template rebind<HandleType>::other > data_;
};
template <typename ValueType,
@@ -148,7 +148,9 @@
return data_.empty();
}
- std::priority_queue<HandleType, std::vector<HandleType, Alloc>, compare_values_by_handle> data_;
+ std::priority_queue<HandleType,
+ std::vector<HandleType, typename Alloc::template rebind<HandleType>::other>,
+ compare_values_by_handle> data_;
};
@@ -347,7 +349,7 @@
++next;
- for (;;) {
+ while (true) {
if (parent == NULL || next != parent->children.end())
break;
Modified: branches/release/boost/heap/priority_queue.hpp
==============================================================================
--- branches/release/boost/heap/priority_queue.hpp (original)
+++ branches/release/boost/heap/priority_queue.hpp 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -61,7 +61,8 @@
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 heap_base_maker::allocator_argument::template rebind<internal_type>::other internal_type_allocator;
+ typedef std::vector<internal_type, internal_type_allocator> container_type;
template <typename Heap1, typename Heap2>
friend struct detail::heap_merge_emulate;
Modified: branches/release/boost/heap/skew_heap.hpp
==============================================================================
--- branches/release/boost/heap/skew_heap.hpp (original)
+++ branches/release/boost/heap/skew_heap.hpp 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -418,14 +418,14 @@
return push_helper::push(this, v);
}
-#ifdef BOOST_HAS_RVALUE_REFS
+#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).
*
* */
- template <class... Args>
+ template <typename... 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;
@@ -756,7 +756,7 @@
self->push_internal(v);
}
-#ifdef BOOST_HAS_RVALUE_REFS
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
template <class... Args>
static void emplace(skew_heap * self, Args&&... args)
{
@@ -772,7 +772,7 @@
return handle_type(self->push_internal(v));
}
-#ifdef BOOST_HAS_RVALUE_REFS
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
template <class... Args>
static handle_type emplace(skew_heap * self, Args&&... args)
{
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 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -18,7 +18,7 @@
typedef std::vector<int> test_data;
-const int test_size = 128;
+const int test_size = 64;//128;
struct dummy_run
{
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 2011-12-30 08:16:31 EST (Fri, 30 Dec 2011)
@@ -1,3 +1,4 @@
+#include <boost/foreach.hpp>
#include "common_heap_tests.hpp"
struct q_tester
@@ -11,9 +12,9 @@
return value < rhs.value;
}
- bool operator>= (q_tester const & rhs) const
+ bool operator> (q_tester const & rhs) const
{
- return value >= rhs.value;
+ return value > rhs.value;
}
bool operator== (q_tester const & rhs) const
@@ -27,7 +28,7 @@
std::ostream& operator<< (std::ostream& out, q_tester const & t)
{
- out << "[" << t.value << " " << t.id << "";
+ out << "[" << t.value << " " << t.id << "]";
return out;
}
@@ -44,7 +45,7 @@
return ret;
}
-struct cmp1
+struct compare_by_id
{
bool operator()(q_tester const & lhs, q_tester const & rhs)
{
@@ -52,19 +53,6 @@
}
};
-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)
{
@@ -72,7 +60,8 @@
pri_queue q;
fill_q(q, data);
- fixup_test_data(data);
+ std::stable_sort(data.begin(), data.end(), compare_by_id());
+ std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
check_q(q, data);
}
@@ -82,8 +71,14 @@
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>());
+
+ std::stable_sort(push_data.begin(), push_data.end(), std::greater<q_tester>());
+
fill_q(q, push_data);
+
+ std::stable_sort(data.begin(), data.end(), compare_by_id());
+ std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
+
check_q(q, data);
}