boost/range/adaptor/strided.hpp
// Boost.Range library // // Copyright Neil Groves 2007. Use, modification and // distribution is subject to the Boost Software License, Version // 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // // For more information, see http://www.boost.org/libs/range/ // #ifndef BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED #define BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED #include <boost/range/adaptor/argument_fwd.hpp> #include <boost/range/iterator_range.hpp> #include <boost/iterator/iterator_facade.hpp> #include <iterator> namespace boost { namespace range_detail { // strided_iterator for wrapping a forward traversal iterator template<class BaseIterator, class Category> class strided_iterator : public iterator_facade< strided_iterator<BaseIterator, Category> , typename iterator_value<BaseIterator>::type , forward_traversal_tag , typename iterator_reference<BaseIterator>::type , typename iterator_difference<BaseIterator>::type > { friend class ::boost::iterator_core_access; typedef iterator_facade< strided_iterator<BaseIterator, Category> , typename iterator_value<BaseIterator>::type , forward_traversal_tag , typename iterator_reference<BaseIterator>::type , typename iterator_difference<BaseIterator>::type > super_t; public: typedef typename super_t::difference_type difference_type; typedef typename super_t::reference reference; typedef BaseIterator base_iterator; typedef std::forward_iterator_tag iterator_category; strided_iterator() : m_it() , m_last() , m_stride() { } strided_iterator(base_iterator it, base_iterator last, difference_type stride) : m_it(it) , m_last(last) , m_stride(stride) { } template<class OtherIterator> strided_iterator( const strided_iterator<OtherIterator, Category>& other, typename enable_if_convertible< OtherIterator, base_iterator >::type* = 0 ) : m_it(other.base()) , m_last(other.base_end()) , m_stride(other.get_stride()) { } base_iterator base() const { return m_it; } base_iterator base_end() const { return m_last; } difference_type get_stride() const { return m_stride; } private: void increment() { for (difference_type i = 0; (m_it != m_last) && (i < m_stride); ++i) { ++m_it; } } reference dereference() const { return *m_it; } template<class OtherIterator> bool equal( const strided_iterator<OtherIterator, Category>& other, typename enable_if_convertible< OtherIterator, base_iterator >::type* = 0) const { return m_it == other.m_it; } base_iterator m_it; base_iterator m_last; difference_type m_stride; }; // strided_iterator for wrapping a bidirectional iterator template<class BaseIterator> class strided_iterator<BaseIterator, bidirectional_traversal_tag> : public iterator_facade< strided_iterator<BaseIterator, bidirectional_traversal_tag> , typename iterator_value<BaseIterator>::type , bidirectional_traversal_tag , typename iterator_reference<BaseIterator>::type , typename iterator_difference<BaseIterator>::type > { friend class ::boost::iterator_core_access; typedef iterator_facade< strided_iterator<BaseIterator, bidirectional_traversal_tag> , typename iterator_value<BaseIterator>::type , bidirectional_traversal_tag , typename iterator_reference<BaseIterator>::type , typename iterator_difference<BaseIterator>::type > super_t; public: typedef typename super_t::difference_type difference_type; typedef typename super_t::reference reference; typedef BaseIterator base_iterator; typedef typename boost::make_unsigned<difference_type>::type size_type; typedef std::bidirectional_iterator_tag iterator_category; strided_iterator() : m_it() , m_offset() , m_index() , m_stride() { } strided_iterator(base_iterator it, size_type index, difference_type stride) : m_it(it) , m_offset() , m_index(index) , m_stride(stride) { if (stride && ((m_index % stride) != 0)) m_index += (stride - (m_index % stride)); } template<class OtherIterator> strided_iterator( const strided_iterator< OtherIterator, bidirectional_traversal_tag >& other, typename enable_if_convertible< OtherIterator, base_iterator >::type* = 0 ) : m_it(other.base()) , m_offset(other.get_offset()) , m_index(other.get_index()) , m_stride(other.get_stride()) { } base_iterator base() const { return m_it; } difference_type get_offset() const { return m_offset; } size_type get_index() const { return m_index; } difference_type get_stride() const { return m_stride; } private: void increment() { m_offset += m_stride; } void decrement() { m_offset -= m_stride; } reference dereference() const { update(); return *m_it; } void update() const { std::advance(m_it, m_offset); m_index += m_offset; m_offset = 0; } template<class OtherIterator> bool equal( const strided_iterator< OtherIterator, bidirectional_traversal_tag >& other, typename enable_if_convertible< OtherIterator, base_iterator >::type* = 0) const { return (m_index + m_offset) == (other.get_index() + other.get_offset()); } mutable base_iterator m_it; mutable difference_type m_offset; mutable size_type m_index; difference_type m_stride; }; // strided_iterator implementation for wrapping a random access iterator template<class BaseIterator> class strided_iterator<BaseIterator, random_access_traversal_tag> : public iterator_facade< strided_iterator<BaseIterator, random_access_traversal_tag> , typename iterator_value<BaseIterator>::type , random_access_traversal_tag , typename iterator_reference<BaseIterator>::type , typename iterator_difference<BaseIterator>::type > { friend class ::boost::iterator_core_access; typedef iterator_facade< strided_iterator<BaseIterator, random_access_traversal_tag> , typename iterator_value<BaseIterator>::type , random_access_traversal_tag , typename iterator_reference<BaseIterator>::type , typename iterator_difference<BaseIterator>::type > super_t; public: typedef typename super_t::difference_type difference_type; typedef typename super_t::reference reference; typedef BaseIterator base_iterator; typedef std::random_access_iterator_tag iterator_category; strided_iterator() : m_it() , m_first() , m_index(0) , m_stride() { } strided_iterator( base_iterator first, base_iterator it, difference_type stride ) : m_it(it) , m_first(first) , m_index(stride ? (it - first) : difference_type()) , m_stride(stride) { if (stride && ((m_index % stride) != 0)) m_index += (stride - (m_index % stride)); } template<class OtherIterator> strided_iterator( const strided_iterator< OtherIterator, random_access_traversal_tag >& other, typename enable_if_convertible< OtherIterator, base_iterator >::type* = 0 ) : m_it(other.base()) , m_first(other.base_begin()) , m_index(other.get_index()) , m_stride(other.get_stride()) { } base_iterator base_begin() const { return m_first; } base_iterator base() const { return m_it; } difference_type get_stride() const { return m_stride; } difference_type get_index() const { return m_index; } private: void increment() { m_index += m_stride; } void decrement() { m_index -= m_stride; } void advance(difference_type offset) { m_index += (m_stride * offset); } // Implementation detail: only update the actual underlying iterator // at the point of dereference. This is done so that the increment // and decrement can overshoot the valid sequence as is required // by striding. Since we can do all comparisons just with the index // simply, and all dereferences must be within the valid range. void update() const { m_it = m_first + m_index; } template<class OtherIterator> difference_type distance_to( const strided_iterator< OtherIterator, random_access_traversal_tag >& other, typename enable_if_convertible< OtherIterator, base_iterator>::type* = 0) const { BOOST_ASSERT((other.m_index - m_index) % m_stride == difference_type()); return (other.m_index - m_index) / m_stride; } template<class OtherIterator> bool equal( const strided_iterator< OtherIterator, random_access_traversal_tag >& other, typename enable_if_convertible< OtherIterator, base_iterator>::type* = 0) const { return m_index == other.m_index; } reference dereference() const { update(); return *m_it; } private: mutable base_iterator m_it; base_iterator m_first; difference_type m_index; difference_type m_stride; }; template<class Rng, class Difference> inline strided_iterator< typename range_iterator<Rng>::type, forward_traversal_tag > make_begin_strided_iterator( Rng& rng, Difference stride, forward_traversal_tag) { return strided_iterator< typename range_iterator<Rng>::type, forward_traversal_tag >(boost::begin(rng), boost::end(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<const Rng>::type, forward_traversal_tag > make_begin_strided_iterator( const Rng& rng, Difference stride, forward_traversal_tag) { return strided_iterator< typename range_iterator<const Rng>::type, forward_traversal_tag >(boost::begin(rng), boost::end(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<Rng>::type, forward_traversal_tag > make_end_strided_iterator( Rng& rng, Difference stride, forward_traversal_tag) { return strided_iterator< typename range_iterator<Rng>::type, forward_traversal_tag >(boost::end(rng), boost::end(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<const Rng>::type, forward_traversal_tag > make_end_strided_iterator( const Rng& rng, Difference stride, forward_traversal_tag) { return strided_iterator< typename range_iterator<const Rng>::type, forward_traversal_tag >(boost::end(rng), boost::end(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<Rng>::type, bidirectional_traversal_tag > make_begin_strided_iterator( Rng& rng, Difference stride, bidirectional_traversal_tag) { typedef typename range_difference<Rng>::type difference_type; return strided_iterator< typename range_iterator<Rng>::type, bidirectional_traversal_tag >(boost::begin(rng), difference_type(), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<const Rng>::type, bidirectional_traversal_tag > make_begin_strided_iterator( const Rng& rng, Difference stride, bidirectional_traversal_tag) { typedef typename range_difference<const Rng>::type difference_type; return strided_iterator< typename range_iterator<const Rng>::type, bidirectional_traversal_tag >(boost::begin(rng), difference_type(), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<Rng>::type, bidirectional_traversal_tag > make_end_strided_iterator( Rng& rng, Difference stride, bidirectional_traversal_tag) { return strided_iterator< typename range_iterator<Rng>::type, bidirectional_traversal_tag >(boost::end(rng), boost::size(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<const Rng>::type, bidirectional_traversal_tag > make_end_strided_iterator( const Rng& rng, Difference stride, bidirectional_traversal_tag) { return strided_iterator< typename range_iterator<const Rng>::type, bidirectional_traversal_tag >(boost::end(rng), boost::size(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<Rng>::type, random_access_traversal_tag > make_begin_strided_iterator( Rng& rng, Difference stride, random_access_traversal_tag) { return strided_iterator< typename range_iterator<Rng>::type, random_access_traversal_tag >(boost::begin(rng), boost::begin(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<const Rng>::type, random_access_traversal_tag > make_begin_strided_iterator( const Rng& rng, Difference stride, random_access_traversal_tag) { return strided_iterator< typename range_iterator<const Rng>::type, random_access_traversal_tag >(boost::begin(rng), boost::begin(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<Rng>::type, random_access_traversal_tag > make_end_strided_iterator( Rng& rng, Difference stride, random_access_traversal_tag) { return strided_iterator< typename range_iterator<Rng>::type, random_access_traversal_tag >(boost::begin(rng), boost::end(rng), stride); } template<class Rng, class Difference> inline strided_iterator< typename range_iterator<const Rng>::type, random_access_traversal_tag > make_end_strided_iterator( const Rng& rng, Difference stride, random_access_traversal_tag) { return strided_iterator< typename range_iterator<const Rng>::type, random_access_traversal_tag >(boost::begin(rng), boost::end(rng), stride); } template< class Rng, class Category = typename iterators::pure_iterator_traversal< typename range_iterator<Rng>::type >::type > class strided_range : public iterator_range< range_detail::strided_iterator< typename range_iterator<Rng>::type, Category > > { typedef range_detail::strided_iterator< typename range_iterator<Rng>::type, Category > iter_type; typedef iterator_range<iter_type> super_t; public: template<class Difference> strided_range(Difference stride, Rng& rng) : super_t( range_detail::make_begin_strided_iterator( rng, stride, typename iterator_traversal< typename range_iterator<Rng>::type >::type()), range_detail::make_end_strided_iterator( rng, stride, typename iterator_traversal< typename range_iterator<Rng>::type >::type())) { BOOST_ASSERT( stride >= 0 ); } }; template<class Difference> class strided_holder : public holder<Difference> { public: explicit strided_holder(Difference value) : holder<Difference>(value) { } }; template<class Rng, class Difference> inline strided_range<Rng> operator|(Rng& rng, const strided_holder<Difference>& stride) { return strided_range<Rng>(stride.val, rng); } template<class Rng, class Difference> inline strided_range<const Rng> operator|(const Rng& rng, const strided_holder<Difference>& stride) { return strided_range<const Rng>(stride.val, rng); } } // namespace range_detail using range_detail::strided_range; namespace adaptors { namespace { const range_detail::forwarder<range_detail::strided_holder> strided = range_detail::forwarder< range_detail::strided_holder>(); } template<class Range, class Difference> inline strided_range<Range> stride(Range& rng, Difference step) { return strided_range<Range>(step, rng); } template<class Range, class Difference> inline strided_range<const Range> stride(const Range& rng, Difference step) { return strided_range<const Range>(step, rng); } } // namespace 'adaptors' } // namespace 'boost' #endif