[Boost-commit] svn:boost r67445 - in trunk: boost/range/adaptor libs/range/test/adaptor_test

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;
 }