|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r67445 - in trunk: boost/range/adaptor libs/range/test/adaptor_test
From: neil_at_[hidden]
Date: 2010-12-24 10:00:11
Author: neilgroves
Date: 2010-12-24 10:00:08 EST (Fri, 24 Dec 2010)
New Revision: 67445
URL: http://svn.boost.org/trac/boost/changeset/67445
Log:
[boost][range] - Corrected yesterdays erroneous modifications to the strided adaptor.
Text files modified:
trunk/boost/range/adaptor/strided.hpp | 125 ++++++++++++++++++++++++++++-----------
trunk/libs/range/test/adaptor_test/strided.cpp | 118 +++++++++++++++++++++++++++++++++++--
2 files changed, 198 insertions(+), 45 deletions(-)
Modified: trunk/boost/range/adaptor/strided.hpp
==============================================================================
--- trunk/boost/range/adaptor/strided.hpp (original)
+++ trunk/boost/range/adaptor/strided.hpp 2010-12-24 10:00:08 EST (Fri, 24 Dec 2010)
@@ -16,68 +16,119 @@
#include <boost/iterator/iterator_adaptor.hpp>
#include <iterator>
+#include <iostream>
+
namespace boost
{
namespace range_detail
{
- template<typename BaseIterator>
+ template<class BaseIterator>
class strided_iterator
: public iterator_adaptor<
- strided_iterator<BaseIterator>,
- BaseIterator>
+ strided_iterator<BaseIterator>
+ , BaseIterator
+ >
{
friend class iterator_core_access;
typedef iterator_adaptor<strided_iterator<BaseIterator>, BaseIterator> super_t;
public:
- typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<BaseIterator>::difference_type difference_type;
+ typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<BaseIterator>::difference_type difference_type;
- strided_iterator() : m_stride() { }
+ strided_iterator()
+ : m_stride(), m_offset(), m_max_offset()
+ {
+ }
- strided_iterator(const strided_iterator& other)
- : super_t(other), m_stride(other.m_stride) { }
+ explicit strided_iterator(BaseIterator base_it,
+ difference_type stride,
+ difference_type offset,
+ difference_type max_offset)
+ : super_t(base_it)
+ , m_stride(stride)
+ , m_offset(offset)
+ , m_max_offset(max_offset)
+ {
+ }
- explicit strided_iterator(BaseIterator base_it, difference_type stride)
- : super_t(base_it), m_stride(stride) { }
+ template<class OtherIterator>
+ strided_iterator(const strided_iterator<OtherIterator>& other,
+ BOOST_DEDUCED_TYPENAME enable_if_convertible<OtherIterator, BaseIterator>::type* = 0)
+ : super_t(other)
+ , m_stride(other.m_stride)
+ , m_offset(other.m_offset)
+ , m_max_offset(other.m_max_offset)
+ {
+ }
strided_iterator&
operator=(const strided_iterator& other)
{
super_t::operator=(other);
-
- // Is the interoperation of the stride safe?
m_stride = other.m_stride;
+ m_offset = other.m_offset;
+ m_max_offset = other.m_max_offset;
return *this;
}
- void increment() { std::advance(this->base_reference(), m_stride); }
+ void increment()
+ {
+ m_offset += m_stride;
+ if (m_offset <= m_max_offset)
+ std::advance(this->base_reference(), m_stride);
+ }
+
+ void decrement()
+ {
+ m_offset -= m_stride;
+ if (m_offset >= 0)
+ std::advance(this->base_reference(), -m_stride);
+ }
- void decrement() { std::advance(this->base_reference(), -m_stride); }
+ void advance(difference_type n)
+ {
+ n *= m_stride;
+ m_offset += n;
- void advance(difference_type n) { std::advance(this->base_reference(), n * m_stride); }
+ if (m_offset >= 0 && m_offset <= m_max_offset)
+ std::advance(this->base_reference(), n);
+ }
+
+ template<class OtherIterator>
+ bool equal(const strided_iterator<OtherIterator>& other,
+ BOOST_DEDUCED_TYPENAME enable_if_convertible<OtherIterator, BaseIterator>::type* = 0) const
+ {
+ return m_offset == other.m_offset;
+ }
difference_type
distance_to(const strided_iterator& other) const
{
- return std::distance(this->base_reference(), other.base_reference()) / m_stride;
+ return (other.m_offset - m_offset) / m_stride;
}
- // Using the compiler generated copy constructor and
- // and assignment operator
-
private:
difference_type m_stride;
+ difference_type m_offset;
+ difference_type m_max_offset;
};
- template<class BaseIterator> inline
+ template<class BaseIterator, class Difference> inline
strided_iterator<BaseIterator>
make_strided_iterator(
const BaseIterator& first,
- BOOST_DEDUCED_TYPENAME std::iterator_traits<BaseIterator>::difference_type stride)
- {
- return strided_iterator<BaseIterator>(first, stride);
+ Difference stride,
+ typename std::iterator_traits<BaseIterator>::difference_type offset,
+ typename std::iterator_traits<BaseIterator>::difference_type max_offset
+ )
+ {
+ BOOST_ASSERT( stride >= 0 );
+ BOOST_ASSERT( (stride == 0) || (offset % stride == 0) );
+ BOOST_ASSERT( (stride == 0) || (max_offset % stride == 0) );
+ BOOST_ASSERT( offset <= max_offset );
+ return strided_iterator<BaseIterator>(first, stride, offset, max_offset);
}
template< class Rng >
@@ -87,33 +138,33 @@
typedef range_detail::strided_iterator<BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type> iter_type;
typedef iterator_range<iter_type> super_t;
public:
- template< typename Difference >
+ template<class Difference>
strided_range(Difference stride, Rng& rng)
- : super_t(make_first(rng, stride), make_last(rng, stride))
+ : super_t(make_super(stride, rng))
{
BOOST_ASSERT( stride >= 0 );
}
+
private:
- template<typename Difference>
- static iter_type make_first(Rng& rng, Difference stride)
+ template<class Difference>
+ static super_t make_super(const Difference stride, Rng& rng)
{
- return make_strided_iterator(boost::begin(rng), stride);
+ const Difference count = boost::size(rng);
+ const Difference max_count = max_offset(count, stride);
+ return super_t(make_strided_iterator(boost::begin(rng), stride, 0, max_count),
+ make_strided_iterator(boost::end(rng), stride, max_count, max_count));
}
- template<typename Difference>
- static iter_type make_last(Rng& rng, Difference stride)
+ template<class Difference, class Stride>
+ static Difference max_offset(Difference sz, const Stride stride)
{
- typedef BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type raw_iter_t;
- typedef BOOST_DEDUCED_TYPENAME range_difference<Rng>::type diff_t;
-
if (stride > 0)
{
- raw_iter_t it = boost::end(rng);
- const diff_t count = boost::size(rng);
- std::advance(it, -(count % stride));
- return iter_type(it, stride);
+ sz += stride - 1;
+ sz /= stride;
+ sz *= stride;
}
- return make_strided_iterator(boost::end(rng), stride);
+ return sz;
}
};
Modified: trunk/libs/range/test/adaptor_test/strided.cpp
==============================================================================
--- trunk/libs/range/test/adaptor_test/strided.cpp (original)
+++ trunk/libs/range/test/adaptor_test/strided.cpp 2010-12-24 10:00:08 EST (Fri, 24 Dec 2010)
@@ -44,15 +44,13 @@
typedef BOOST_DEDUCED_TYPENAME Container::size_type size_type;
iterator_t it = c.begin();
- size_type count = c.size();
- size_type unreachable_element_count = c.size() - ((count / stride_size) * stride_size);
- diff_t offset = -static_cast<diff_t>(unreachable_element_count);
iterator_t last = c.end();
- std::advance(last, offset);
-
- for (; it != last; std::advance(it, stride_size))
+ for (; it != last; )
{
reference.push_back(*it);
+
+ for (int i = 0; (it != last) && (i < stride_size); ++i)
+ ++it;
}
}
@@ -129,8 +127,8 @@
strided_range_t rng( boost::adaptors::stride(c, 0) );
typedef typename boost::range_iterator<strided_range_t>::type iter_t;
- iter_t first(boost::begin(c), 0);
- iter_t last(boost::end(c), 0);
+ iter_t first(boost::begin(c), 0, 0, boost::size(c));
+ iter_t last(boost::end(c), 0, boost::size(c), boost::size(c));
iter_t it = first;
for (int i = 0; i < 10; ++i, ++it)
@@ -157,6 +155,108 @@
strided_test_impl< std::deque<int> >();
strided_test_impl< std::list<int> >();
}
+
+ void strided_defect_Trac5014()
+ {
+ using namespace boost::assign;
+
+ std::vector<int> v;
+ for (int i = 0; i < 30; ++i)
+ v.push_back(i);
+
+ std::vector<int> reference;
+ reference += 0,4,8,12,16,20,24,28;
+
+ std::vector<int> output;
+ boost::push_back(output, v | boost::adaptors::strided(4));
+
+ BOOST_CHECK_EQUAL_COLLECTIONS( reference.begin(), reference.end(),
+ output.begin(), output.end() );
+
+ BOOST_CHECK_EQUAL( output.back(), 28 );
+ }
+
+ template<typename BaseIterator, typename Category>
+ class strided_mock_iterator
+ : public boost::iterator_adaptor<
+ strided_mock_iterator<BaseIterator,Category>
+ , BaseIterator
+ , boost::use_default
+ , Category
+ >
+ {
+ typedef boost::iterator_adaptor<
+ strided_mock_iterator
+ , BaseIterator
+ , boost::use_default
+ , Category
+ > super_t;
+ public:
+ explicit strided_mock_iterator(BaseIterator it)
+ : super_t(it)
+ {
+ }
+
+ private:
+ void increment()
+ {
+ ++(this->base_reference());
+ }
+
+ bool equal(const strided_mock_iterator& other) const
+ {
+ return this->base() == other.base();
+ }
+
+ BOOST_DEDUCED_TYPENAME super_t::reference dereference() const
+ {
+ return *(this->base());
+ }
+
+ friend class boost::iterator_core_access;
+ };
+
+ template<typename Category, typename Range>
+ boost::iterator_range<strided_mock_iterator<BOOST_DEDUCED_TYPENAME boost::range_iterator<Range>::type, Category> >
+ as_mock_range(Range& rng)
+ {
+ typedef BOOST_DEDUCED_TYPENAME boost::range_iterator<Range>::type range_iter_t;
+ typedef strided_mock_iterator<range_iter_t, Category> mock_iter_t;
+
+ return boost::iterator_range<mock_iter_t>(
+ mock_iter_t(boost::begin(rng)),
+ mock_iter_t(boost::end(rng)));
+ }
+
+ void strided_test_traversal()
+ {
+ using namespace boost::assign;
+
+ std::vector<int> v;
+ for (int i = 0; i < 30; ++i)
+ v.push_back(i);
+
+ std::vector<int> reference;
+ reference += 0,4,8,12,16,20,24,28;
+
+ std::vector<int> output;
+ boost::push_back(output, as_mock_range<boost::forward_traversal_tag>(v) | boost::adaptors::strided(4));
+
+ BOOST_CHECK_EQUAL_COLLECTIONS( reference.begin(), reference.end(),
+ output.begin(), output.end() );
+
+ output.clear();
+ boost::push_back(output, as_mock_range<boost::bidirectional_traversal_tag>(v) | boost::adaptors::strided(4));
+
+ BOOST_CHECK_EQUAL_COLLECTIONS( reference.begin(), reference.end(),
+ output.begin(), output.end() );
+
+ output.clear();
+ boost::push_back(output, as_mock_range<boost::random_access_traversal_tag>(v) | boost::adaptors::strided(4));
+
+ BOOST_CHECK_EQUAL_COLLECTIONS( reference.begin(), reference.end(),
+ output.begin(), output.end() );
+ }
}
}
@@ -167,6 +267,8 @@
= BOOST_TEST_SUITE( "RangeTestSuite.adaptor.strided" );
test->add( BOOST_TEST_CASE( &boost::strided_test ) );
+ test->add( BOOST_TEST_CASE( &boost::strided_defect_Trac5014 ) );
+ test->add( BOOST_TEST_CASE( &boost::strided_test_traversal ) );
return test;
}
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