Subject: [Boost-commit] svn:boost r78549 - in branches/release: boost/heap boost/heap/detail libs/heap libs/heap/test
From: tim_at_[hidden]
Date: 2012-05-23 04:37:47
Author: timblechmann
Date: 2012-05-23 04:37:44 EDT (Wed, 23 May 2012)
New Revision: 78549
URL: http://svn.boost.org/trac/boost/changeset/78549
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 | 8 ++++++
branches/release/boost/heap/d_ary_heap.hpp | 18 +++++++++++++--
branches/release/boost/heap/detail/mutable_heap.hpp | 45 ++++++++++++++++++++++++++++++---------
branches/release/boost/heap/detail/stable_heap.hpp | 5 ++++
branches/release/boost/heap/detail/tree_iterator.hpp | 10 ++++++++
branches/release/boost/heap/fibonacci_heap.hpp | 15 ++++++++++++
branches/release/boost/heap/pairing_heap.hpp | 7 +++++
branches/release/boost/heap/skew_heap.hpp | 8 ++++++
branches/release/libs/heap/test/mutable_heap_tests.hpp | 24 ++++++++++++++++----
9 files changed, 117 insertions(+), 23 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-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -62,6 +62,10 @@
{}
#ifdef BOOST_HAS_RVALUE_REFS
+ type(type const & rhs):
+ base_type(rhs), allocator_type(rhs)
+ {}
+
type(type && rhs):
base_type(std::move(static_cast<base_type&>(rhs))),
allocator_type(std::move(static_cast<allocator_type&>(rhs)))
@@ -145,6 +149,7 @@
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;
@@ -569,7 +574,8 @@
/// \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);
+ node_type * ptr = const_cast<node_type *>(it.get_node());
+ return handle_type(ptr);
}
/// \copydoc boost::heap::priority_queue::value_comp
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-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -753,7 +753,7 @@
static handle_type s_handle_from_iterator(iterator const & it)
{
BOOST_STATIC_ASSERT(is_mutable);
- return super_t::handle_type(it);
+ return super_t::s_handle_from_iterator(it);
}
/// \copydoc boost::heap::priority_queue::pop
@@ -769,13 +769,25 @@
}
/// \copydoc boost::heap::priority_queue::begin
- iterator begin(void) const
+ const_iterator begin(void) const
{
return super_t::begin();
}
+ /// \copydoc boost::heap::priority_queue::begin
+ iterator begin(void)
+ {
+ return super_t::begin();
+ }
+
+ /// \copydoc boost::heap::priority_queue::end
+ iterator end(void)
+ {
+ return super_t::end();
+ }
+
/// \copydoc boost::heap::priority_queue::end
- iterator end(void) const
+ const_iterator end(void) const
{
return super_t::end();
}
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-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -94,6 +94,10 @@
handle_type (void)
{}
+ handle_type(handle_type const & rhs):
+ iterator(rhs.iterator)
+ {}
+
private:
explicit handle_type(list_iterator const & it):
iterator(it)
@@ -166,25 +170,27 @@
public:
- class iterator:
- public boost::iterator_adaptor<iterator,
- const_list_iterator,
+ template <typename iterator_type>
+ class iterator_base:
+ public boost::iterator_adaptor<iterator_base<iterator_type>,
+ iterator_type,
value_type const,
boost::bidirectional_traversal_tag>
{
- typedef boost::iterator_adaptor<iterator,
- const_list_iterator,
+ typedef boost::iterator_adaptor<iterator_base<iterator_type>,
+ iterator_type,
value_type const,
boost::bidirectional_traversal_tag> super_t;
friend class boost::iterator_core_access;
friend class priority_queue_mutable_wrapper;
- iterator(void):
+ iterator_base(void):
super_t(0)
{}
- explicit iterator(const_list_iterator const & it):
+ template <typename T>
+ explicit iterator_base(T const & it):
super_t(it)
{}
@@ -192,9 +198,16 @@
{
return super_t::base()->first;
}
+
+ iterator_type get_list_iterator() const
+ {
+ return super_t::base_reference();
+ }
};
- typedef iterator const_iterator;
+ typedef iterator_base<list_iterator> iterator;
+ typedef iterator_base<const_list_iterator> const_iterator;
+
typedef typename object_list::difference_type difference_type;
class ordered_iterator:
@@ -464,12 +477,22 @@
objects.erase(it);
}
- iterator begin(void) const
+ const_iterator begin(void) const
+ {
+ return const_iterator(objects.begin());
+ }
+
+ const_iterator end(void) const
+ {
+ return const_iterator(objects.end());
+ }
+
+ iterator begin(void)
{
return iterator(objects.begin());
}
- iterator end(void) const
+ iterator end(void)
{
return iterator(objects.end());
}
@@ -489,7 +512,7 @@
static handle_type s_handle_from_iterator(iterator const & it)
{
- return handle_type(it);
+ return handle_type(it.get_list_iterator());
}
value_compare const & value_comp(void) const
Modified: branches/release/boost/heap/detail/stable_heap.hpp
==============================================================================
--- branches/release/boost/heap/detail/stable_heap.hpp (original)
+++ branches/release/boost/heap/detail/stable_heap.hpp 2012-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -263,6 +263,11 @@
rhs.counter_ = 0;
}
+ heap_base(heap_base & rhs):
+ Cmp(static_cast<Cmp&>(rhs)),
+ size_holder_type(static_cast<size_holder_type&>(rhs)), counter_(rhs.counter_)
+ {}
+
heap_base & operator=(heap_base && rhs)
{
Cmp::operator=(std::move(static_cast<Cmp&>(rhs)));
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 2012-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -254,6 +254,11 @@
return !operator!=(rhs);
}
+ const Node * get_node() const
+ {
+ return adaptor_type::base_reference();
+ }
+
private:
void increment(void)
{
@@ -373,6 +378,11 @@
{
return static_cast<const Node *>(&*it);
}
+
+ const Node * get_node() const
+ {
+ return get_node(adaptor_type::base_reference());
+ }
};
Modified: branches/release/boost/heap/fibonacci_heap.hpp
==============================================================================
--- branches/release/boost/heap/fibonacci_heap.hpp (original)
+++ branches/release/boost/heap/fibonacci_heap.hpp 2012-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -68,6 +68,11 @@
allocator_type(std::move(static_cast<allocator_type&>(rhs)))
{}
+ type(type & rhs):
+ base_type(static_cast<base_type&>(rhs)),
+ allocator_type(static_cast<allocator_type&>(rhs))
+ {}
+
type & operator=(type && rhs)
{
base_type::operator=(std::move(static_cast<base_type&>(rhs)));
@@ -232,6 +237,13 @@
rhs.top_element = NULL;
}
+ fibonacci_heap(fibonacci_heap & rhs):
+ super_t(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)
{
@@ -605,7 +617,8 @@
/// \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);
+ node * ptr = const_cast<node *>(it.get_node());
+ return handle_type(ptr);
}
/// \copydoc boost::heap::priority_queue::value_comp
Modified: branches/release/boost/heap/pairing_heap.hpp
==============================================================================
--- branches/release/boost/heap/pairing_heap.hpp (original)
+++ branches/release/boost/heap/pairing_heap.hpp 2012-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -63,6 +63,10 @@
{}
#ifdef BOOST_HAS_RVALUE_REFS
+ type(type const & rhs):
+ base_type(rhs), allocator_type(rhs)
+ {}
+
type(type && rhs):
base_type(std::move(static_cast<base_type&>(rhs))),
allocator_type(std::move(static_cast<allocator_type&>(rhs)))
@@ -549,7 +553,8 @@
/// \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);
+ node * ptr = const_cast<node *>(it.get_node());
+ return handle_type(ptr);
}
/**
Modified: branches/release/boost/heap/skew_heap.hpp
==============================================================================
--- branches/release/boost/heap/skew_heap.hpp (original)
+++ branches/release/boost/heap/skew_heap.hpp 2012-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -205,6 +205,11 @@
allocator_type(std::move(static_cast<allocator_type&>(rhs)))
{}
+ type(type const & rhs):
+ base_type(rhs),
+ allocator_type(rhs)
+ {}
+
type & operator=(type && rhs)
{
base_type::operator=(std::move(static_cast<base_type&>(rhs)));
@@ -616,7 +621,8 @@
/// \copydoc boost::heap::d_ary_heap::s_handle_from_iterator
static handle_type s_handle_from_iterator(iterator const & it)
{
- return handle_type(&*it);
+ node * ptr = const_cast<node *>(it.get_node());
+ return handle_type(ptr);
}
/**
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-05-23 04:37:44 EDT (Wed, 23 May 2012)
@@ -215,7 +215,7 @@
void pri_queue_test_erase(void)
{
#ifdef USE_BOOST_RANDOM
- boost::mt19937 rng;
+ boost::mt19937 rng;
#endif
for (int i = 0; i != test_size; ++i)
@@ -227,12 +227,12 @@
for (int j = 0; j != i; ++j)
{
#ifdef USE_BOOST_RANDOM
- boost::uniform_int<> range(0, data.size() - 1);
- boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
+ boost::uniform_int<> range(0, data.size() - 1);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
- int index = gen();
+ int index = gen();
#else
- int index = rand() % (data.size() - 1);
+ int index = std::rand() % (data.size() - 1);
#endif
q.erase(handles[index]);
handles.erase(handles.begin() + index);
@@ -285,6 +285,19 @@
pri_queue_test_erase<pri_queue>();
}
+template <typename pri_queue>
+void run_mutable_heap_test_handle_from_iterator(void)
+{
+ pri_queue que;
+
+ que.push(3);
+ que.push(1);
+ que.push(4);
+
+ que.update(pri_queue::s_handle_from_iterator(que.begin()),
+ 6);
+}
+
template <typename pri_queue>
void run_mutable_heap_tests(void)
@@ -294,6 +307,7 @@
run_mutable_heap_decrease_tests<pri_queue>();
run_mutable_heap_increase_tests<pri_queue>();
run_mutable_heap_erase_tests<pri_queue>();
+ run_mutable_heap_test_handle_from_iterator<pri_queue>();
}
template <typename pri_queue>