Chris@16: // Boost.Range library
Chris@16: //
Chris@16: //  Copyright Neil Groves 2007. Use, modification and
Chris@16: //  distribution is subject to the Boost Software License, Version
Chris@16: //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: //
Chris@16: // For more information, see http://www.boost.org/libs/range/
Chris@16: //
Chris@16: #ifndef BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
Chris@16: #define BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
Chris@16: 
Chris@16: #include <boost/range/adaptor/argument_fwd.hpp>
Chris@16: #include <boost/range/iterator_range.hpp>
Chris@16: #include <boost/iterator/iterator_adaptor.hpp>
Chris@16: #include <iterator>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:     namespace range_detail
Chris@16:     {
Chris@16:         // strided_iterator for wrapping a forward traversal iterator
Chris@16:         template<class BaseIterator, class Category>
Chris@16:         class strided_iterator
Chris@16:             : public iterator_adaptor<
Chris@16:                 strided_iterator<BaseIterator, Category>
Chris@16:               , BaseIterator
Chris@16:               , use_default
Chris@16:               , boost::forward_traversal_tag
Chris@16:             >
Chris@16:         {
Chris@16:             friend class ::boost::iterator_core_access;
Chris@16: 
Chris@16:             typedef iterator_adaptor<
Chris@16:                         strided_iterator<BaseIterator, Category>
Chris@16:                       , BaseIterator
Chris@16:                       , use_default
Chris@16:                       , boost::forward_traversal_tag
Chris@16:                     > super_t;
Chris@16: 
Chris@16:         public:
Chris@16:             typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<BaseIterator>::difference_type difference_type;
Chris@16:             typedef BaseIterator base_iterator;
Chris@16: 
Chris@16:             strided_iterator()
Chris@16:                 : m_last()
Chris@16:                 , m_stride()
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             strided_iterator(base_iterator first, base_iterator it, base_iterator last, difference_type stride)
Chris@16:                 : super_t(it)
Chris@16:                 , m_last(last)
Chris@16:                 , m_stride(stride)
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             template<class OtherIterator>
Chris@16:             strided_iterator(const strided_iterator<OtherIterator, Category>& other,
Chris@16:                              BOOST_DEDUCED_TYPENAME enable_if_convertible<OtherIterator, base_iterator>::type* = 0)
Chris@16:                 : super_t(other)
Chris@16:                 , m_last(other.base_end())
Chris@16:                 , m_stride(other.get_stride())
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             base_iterator base_end() const { return m_last; }
Chris@16:             difference_type get_stride() const { return m_stride; }
Chris@16: 
Chris@16:         private:
Chris@16:             void increment()
Chris@16:             {
Chris@16:                 base_iterator& it = this->base_reference();
Chris@16:                 for (difference_type i = 0; (it != m_last) && (i < m_stride); ++i)
Chris@16:                     ++it;
Chris@16:             }
Chris@16: 
Chris@16:             base_iterator m_last;
Chris@16:             difference_type m_stride;
Chris@16:         };
Chris@16: 
Chris@16:         // strided_iterator for wrapping a bidirectional iterator
Chris@16:         template<class BaseIterator>
Chris@16:         class strided_iterator<BaseIterator, bidirectional_traversal_tag>
Chris@16:             : public iterator_adaptor<
Chris@16:                 strided_iterator<BaseIterator, bidirectional_traversal_tag>
Chris@16:               , BaseIterator
Chris@16:               , use_default
Chris@16:               , bidirectional_traversal_tag
Chris@16:             >
Chris@16:         {
Chris@16:             friend class ::boost::iterator_core_access;
Chris@16: 
Chris@16:             typedef iterator_adaptor<
Chris@16:                         strided_iterator<BaseIterator, bidirectional_traversal_tag>
Chris@16:                       , BaseIterator
Chris@16:                       , use_default
Chris@16:                       , bidirectional_traversal_tag
Chris@16:                     > super_t;
Chris@16:         public:
Chris@16:             typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<BaseIterator>::difference_type difference_type;
Chris@16:             typedef BaseIterator base_iterator;
Chris@16: 
Chris@16:             strided_iterator()
Chris@16:                 : m_first()
Chris@16:                 , m_last()
Chris@16:                 , m_stride()
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             strided_iterator(base_iterator first, base_iterator it, base_iterator last, difference_type stride)
Chris@16:                 : super_t(it)
Chris@16:                 , m_first(first)
Chris@16:                 , m_last(last)
Chris@16:                 , m_stride(stride)
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             template<class OtherIterator>
Chris@16:             strided_iterator(const strided_iterator<OtherIterator, bidirectional_traversal_tag>& other,
Chris@16:                              BOOST_DEDUCED_TYPENAME enable_if_convertible<OtherIterator, base_iterator>::type* = 0)
Chris@16:                 : super_t(other.base())
Chris@16:                 , m_first(other.base_begin())
Chris@16:                 , m_last(other.base_end())
Chris@16:                 , m_stride(other.get_stride())
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             base_iterator base_begin() const { return m_first; }
Chris@16:             base_iterator base_end() const { return m_last; }
Chris@16:             difference_type get_stride() const { return m_stride; }
Chris@16: 
Chris@16:         private:
Chris@16:             void increment()
Chris@16:             {
Chris@16:                 base_iterator& it = this->base_reference();
Chris@16:                 for (difference_type i = 0; (it != m_last) && (i < m_stride); ++i)
Chris@16:                     ++it;
Chris@16:             }
Chris@16: 
Chris@16:             void decrement()
Chris@16:             {
Chris@16:                 base_iterator& it = this->base_reference();
Chris@16:                 for (difference_type i = 0; (it != m_first) && (i < m_stride); ++i)
Chris@16:                     --it;
Chris@16:             }
Chris@16: 
Chris@16:             base_iterator m_first;
Chris@16:             base_iterator m_last;
Chris@16:             difference_type m_stride;
Chris@16:         };
Chris@16: 
Chris@16:         // strided_iterator implementation for wrapping a random access iterator
Chris@16:         template<class BaseIterator>
Chris@16:         class strided_iterator<BaseIterator, random_access_traversal_tag>
Chris@16:             : public iterator_adaptor<
Chris@16:                         strided_iterator<BaseIterator, random_access_traversal_tag>
Chris@16:                       , BaseIterator
Chris@16:                       , use_default
Chris@16:                       , random_access_traversal_tag
Chris@16:                     >
Chris@16:         {
Chris@16:             friend class ::boost::iterator_core_access;
Chris@16: 
Chris@16:             typedef iterator_adaptor<
Chris@16:                         strided_iterator<BaseIterator, random_access_traversal_tag>
Chris@16:                       , BaseIterator
Chris@16:                       , use_default
Chris@16:                       , random_access_traversal_tag
Chris@16:                     > super_t;
Chris@16:         public:
Chris@16:             typedef BOOST_DEDUCED_TYPENAME super_t::difference_type difference_type;
Chris@16:             typedef BaseIterator base_iterator;
Chris@16: 
Chris@16:             strided_iterator()
Chris@16:                 : m_first()
Chris@16:                 , m_last()
Chris@16:                 , m_index(0)
Chris@16:                 , m_stride()
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             strided_iterator(BaseIterator first, BaseIterator it, BaseIterator last, difference_type stride)
Chris@16:                 : super_t(it)
Chris@16:                 , m_first(first)
Chris@16:                 , m_last(last)
Chris@16:                 , m_index(stride ? (it - first) / stride : 0)
Chris@16:                 , m_stride(stride)
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             template<class OtherIterator>
Chris@16:             strided_iterator(const strided_iterator<OtherIterator, random_access_traversal_tag>& other,
Chris@16:                              BOOST_DEDUCED_TYPENAME enable_if_convertible<OtherIterator, BaseIterator>::type* = 0)
Chris@16:                 : super_t(other.base())
Chris@16:                 , m_first(other.base_begin())
Chris@16:                 , m_last(other.base_end())
Chris@16:                 , m_index(other.get_index())
Chris@16:                 , m_stride(other.get_stride())
Chris@16:             {
Chris@16:             }
Chris@16: 
Chris@16:             base_iterator base_begin() const { return m_first; }
Chris@16:             base_iterator base_end() const { return m_last; }
Chris@16:             difference_type get_stride() const { return m_stride; }
Chris@16:             difference_type get_index() const { return m_index; }
Chris@16: 
Chris@16:         private:
Chris@16:             void increment()
Chris@16:             {
Chris@16:                 m_index += m_stride;
Chris@16:                 if (m_index < (m_last - m_first))
Chris@16:                     this->base_reference() = m_first + m_index;
Chris@16:                 else
Chris@16:                     this->base_reference() = m_last;
Chris@16:             }
Chris@16: 
Chris@16:             void decrement()
Chris@16:             {
Chris@16:                 m_index -= m_stride;
Chris@16:                 if (m_index >= 0)
Chris@16:                     this->base_reference() = m_first + m_index;
Chris@16:                 else
Chris@16:                     this->base_reference() = m_first;
Chris@16:             }
Chris@16: 
Chris@16:             void advance(difference_type offset)
Chris@16:             {
Chris@16:                 offset *= m_stride;
Chris@16:                 m_index += offset;
Chris@16:                 if (m_index < 0)
Chris@16:                     this->base_reference() = m_first;
Chris@16:                 else if (m_index > (m_last - m_first))
Chris@16:                     this->base_reference() = m_last;
Chris@16:                 else
Chris@16:                     this->base_reference() = m_first + m_index;
Chris@16:             }
Chris@16: 
Chris@16:             template<class OtherIterator>
Chris@16:             difference_type distance_to(const strided_iterator<OtherIterator, random_access_traversal_tag>& other,
Chris@16:                                         BOOST_DEDUCED_TYPENAME enable_if_convertible<OtherIterator, BaseIterator>::type* = 0) const
Chris@16:             {
Chris@16:                 if (other.base() >= this->base())
Chris@16:                     return (other.base() - this->base() + (m_stride - 1)) / m_stride;
Chris@16:                 return (other.base() - this->base() - (m_stride - 1)) / m_stride;
Chris@16:             }
Chris@16: 
Chris@16:             bool equal(const strided_iterator& other) const
Chris@16:             {
Chris@16:                 return this->base() == other.base();
Chris@16:             }
Chris@16: 
Chris@16:         private:
Chris@16:             base_iterator m_first;
Chris@16:             base_iterator m_last;
Chris@16:             difference_type m_index;
Chris@16:             difference_type m_stride;
Chris@16:         };
Chris@16: 
Chris@16:         template<class BaseIterator, class Difference> inline
Chris@16:         strided_iterator<BaseIterator, BOOST_DEDUCED_TYPENAME iterator_traversal<BaseIterator>::type>
Chris@16:         make_strided_iterator(BaseIterator first, BaseIterator it,
Chris@16:                               BaseIterator last, Difference stride)
Chris@16:         {
Chris@16:             BOOST_ASSERT( stride >= 0 );
Chris@16:             typedef BOOST_DEDUCED_TYPENAME iterator_traversal<BaseIterator>::type traversal_tag;
Chris@16:             return strided_iterator<BaseIterator, traversal_tag>(first, it, last, stride);
Chris@16:         }
Chris@16: 
Chris@16:         template< class Rng
Chris@16:                 , class Category = BOOST_DEDUCED_TYPENAME iterator_traversal<
Chris@16:                                     BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type
Chris@16:                                    >::type
Chris@16:          >
Chris@16:         class strided_range
Chris@16:             : public iterator_range<
Chris@16:                         range_detail::strided_iterator<
Chris@16:                             BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type,
Chris@16:                             Category
Chris@16:                         >
Chris@16:                      >
Chris@16:         {
Chris@16:             typedef range_detail::strided_iterator<
Chris@16:                         BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type,
Chris@16:                         Category
Chris@16:                     > iter_type;
Chris@16:             typedef iterator_range<iter_type> super_t;
Chris@16:         public:
Chris@16:             template<class Difference>
Chris@16:             strided_range(Difference stride, Rng& rng)
Chris@16:                 : super_t(make_strided_iterator(boost::begin(rng), boost::begin(rng), boost::end(rng), stride),
Chris@16:                           make_strided_iterator(boost::begin(rng), boost::end(rng), boost::end(rng), stride))
Chris@16:             {
Chris@16:                 BOOST_ASSERT( stride >= 0 );
Chris@16:             }
Chris@16:         };
Chris@16: 
Chris@16:         template<class Difference>
Chris@16:         class strided_holder : public holder<Difference>
Chris@16:         {
Chris@16:         public:
Chris@16:             explicit strided_holder(Difference value) : holder<Difference>(value) {}
Chris@16:         };
Chris@16: 
Chris@16:         template<class Rng, class Difference>
Chris@16:         inline strided_range<Rng>
Chris@16:         operator|(Rng& rng, const strided_holder<Difference>& stride)
Chris@16:         {
Chris@16:             return strided_range<Rng>(stride.val, rng);
Chris@16:         }
Chris@16: 
Chris@16:         template<class Rng, class Difference>
Chris@16:         inline strided_range<const Rng>
Chris@16:         operator|(const Rng& rng, const strided_holder<Difference>& stride)
Chris@16:         {
Chris@16:             return strided_range<const Rng>(stride.val, rng);
Chris@16:         }
Chris@16: 
Chris@16:     } // namespace range_detail
Chris@16: 
Chris@16:     using range_detail::strided_range;
Chris@16: 
Chris@16:     namespace adaptors
Chris@16:     {
Chris@16: 
Chris@16:         namespace
Chris@16:         {
Chris@16:             const range_detail::forwarder<range_detail::strided_holder>
Chris@16:                 strided = range_detail::forwarder<range_detail::strided_holder>();
Chris@16:         }
Chris@16: 
Chris@16:         template<class Range, class Difference>
Chris@16:         inline strided_range<Range>
Chris@16:         stride(Range& rng, Difference step)
Chris@16:         {
Chris@16:             return strided_range<Range>(step, rng);
Chris@16:         }
Chris@16: 
Chris@16:         template<class Range, class Difference>
Chris@16:         inline strided_range<const Range>
Chris@16:         stride(const Range& rng, Difference step)
Chris@16:         {
Chris@16:             return strided_range<const Range>(step, rng);
Chris@16:         }
Chris@16: 
Chris@16:     } // namespace 'adaptors'
Chris@16: } // namespace 'boost'
Chris@16: 
Chris@16: #endif