range/adaptor/strided.hpp

0001 // Boost.Range library
0002 //
0003 //  Copyright Neil Groves 2007. Use, modification and
0004 //  distribution is subject to the Boost Software License, Version
0005 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 //  http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 //
0009 // For more information, see http://www.boost.org/libs/range/
0010 //
0011 #ifndef BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
0012 #define BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
0013
0014 #include <boost/range/adaptor/argument_fwd.hpp>
0015 #include <boost/range/iterator_range.hpp>
0016 #include <boost/iterator/iterator_facade.hpp>
0017 #include <boost/iterator/enable_if_convertible.hpp>
0018 #include <iterator>
0019
0020 namespace boost
0021 {
0022     namespace range_detail
0023     {
0024         // strided_iterator for wrapping a forward traversal iterator
0025         template<class BaseIterator, class Category>
0026         class strided_iterator
0027             : public iterator_facade<
0028                 strided_iterator<BaseIterator, Category>
0029                 , typename iterator_value<BaseIterator>::type
0030                 , forward_traversal_tag
0031                 , typename iterator_reference<BaseIterator>::type
0032                 , typename iterator_difference<BaseIterator>::type
0033             >
0034         {
0035             friend class ::boost::iterator_core_access;
0036
0037             typedef iterator_facade<
0038                 strided_iterator<BaseIterator, Category>
0039                 , typename iterator_value<BaseIterator>::type
0040                 , forward_traversal_tag
0041                 , typename iterator_reference<BaseIterator>::type
0042                 , typename iterator_difference<BaseIterator>::type
0043             > super_t;
0044
0045         public:
0046             typedef typename super_t::difference_type difference_type;
0047             typedef typename super_t::reference reference;
0048             typedef BaseIterator base_iterator;
0049             typedef std::forward_iterator_tag iterator_category;
0050
0051             strided_iterator()
0052                 : m_it()
0053                 , m_last()
0054                 , m_stride()
0055             {
0056             }
0057
0058             strided_iterator(base_iterator   it,
0059                              base_iterator   last,
0060                              difference_type stride)
0061                 : m_it(it)
0062                 , m_last(last)
0063                 , m_stride(stride)
0064             {
0065             }
0066
0067             template<class OtherIterator>
0068             strided_iterator(
0069                 const strided_iterator<OtherIterator, Category>& other,
0070                 typename iterators::enable_if_convertible<
0071                     OtherIterator,
0072                     base_iterator
0073                 >::type* = 0
0074             )
0075                 : m_it(other.base())
0076                 , m_last(other.base_end())
0077                 , m_stride(other.get_stride())
0078             {
0079             }
0080
0081             base_iterator base() const
0082             {
0083                 return m_it;
0084             }
0085
0086             base_iterator base_end() const
0087             {
0088                 return m_last;
0089             }
0090
0091             difference_type get_stride() const
0092             {
0093                 return m_stride;
0094             }
0095
0096         private:
0097             void increment()
0098             {
0099                 for (difference_type i = 0;
0100                         (m_it != m_last) && (i < m_stride); ++i)
0101                 {
0102                     ++m_it;
0103                 }
0104             }
0105
0106             reference dereference() const
0107             {
0108                 return *m_it;
0109             }
0110
0111             template<class OtherIterator>
0112             bool equal(
0113                 const strided_iterator<OtherIterator, Category>& other,
0114                 typename iterators::enable_if_convertible<
0115                     OtherIterator,
0116                     base_iterator
0117                 >::type* = 0) const
0118             {
0119                 return m_it == other.m_it;
0120             }
0121
0122             base_iterator m_it;
0123             base_iterator m_last;
0124             difference_type m_stride;
0125         };
0126
0127         // strided_iterator for wrapping a bidirectional iterator
0128         template<class BaseIterator>
0129         class strided_iterator<BaseIterator, bidirectional_traversal_tag>
0130             : public iterator_facade<
0131                 strided_iterator<BaseIterator, bidirectional_traversal_tag>
0132                 , typename iterator_value<BaseIterator>::type
0133                 , bidirectional_traversal_tag
0134                 , typename iterator_reference<BaseIterator>::type
0135                 , typename iterator_difference<BaseIterator>::type
0136             >
0137         {
0138             friend class ::boost::iterator_core_access;
0139
0140             typedef iterator_facade<
0141                 strided_iterator<BaseIterator, bidirectional_traversal_tag>
0142                 , typename iterator_value<BaseIterator>::type
0143                 , bidirectional_traversal_tag
0144                 , typename iterator_reference<BaseIterator>::type
0145                 , typename iterator_difference<BaseIterator>::type
0146             > super_t;
0147         public:
0148             typedef typename super_t::difference_type difference_type;
0149             typedef typename super_t::reference reference;
0150             typedef BaseIterator base_iterator;
0151             typedef typename boost::make_unsigned<difference_type>::type
0152                         size_type;
0153             typedef std::bidirectional_iterator_tag iterator_category;
0154
0155             strided_iterator()
0156                 : m_it()
0157                 , m_offset()
0158                 , m_index()
0159                 , m_stride()
0160             {
0161             }
0162
0163             strided_iterator(base_iterator   it,
0164                              size_type       index,
0165                              difference_type stride)
0166                 : m_it(it)
0167                 , m_offset()
0168                 , m_index(index)
0169                 , m_stride(stride)
0170             {
0171                 if (stride && ((m_index % stride) != 0))
0172                     m_index += (stride - (m_index % stride));
0173             }
0174
0175             template<class OtherIterator>
0176             strided_iterator(
0177                 const strided_iterator<
0178                     OtherIterator,
0179                     bidirectional_traversal_tag
0180                 >& other,
0181                 typename iterators::enable_if_convertible<
0182                     OtherIterator,
0183                     base_iterator
0184                 >::type* = 0
0185             )
0186                 : m_it(other.base())
0187                 , m_offset(other.get_offset())
0188                 , m_index(other.get_index())
0189                 , m_stride(other.get_stride())
0190             {
0191             }
0192
0193             base_iterator base() const
0194             {
0195                 return m_it;
0196             }
0197
0198             difference_type get_offset() const
0199             {
0200                 return m_offset;
0201             }
0202
0203             size_type get_index() const
0204             {
0205                 return m_index;
0206             }
0207
0208             difference_type get_stride() const
0209             {
0210                 return m_stride;
0211             }
0212
0213         private:
0214             void increment()
0215             {
0216                 m_offset += m_stride;
0217             }
0218
0219             void decrement()
0220             {
0221                 m_offset -= m_stride;
0222             }
0223
0224             reference dereference() const
0225             {
0226                 update();
0227                 return *m_it;
0228             }
0229
0230             void update() const
0231             {
0232                 std::advance(m_it, m_offset);
0233                 m_index += m_offset;
0234                 m_offset = 0;
0235             }
0236
0237             template<class OtherIterator>
0238             bool equal(
0239                 const strided_iterator<
0240                     OtherIterator,
0241                     bidirectional_traversal_tag
0242                 >& other,
0243                 typename iterators::enable_if_convertible<
0244                     OtherIterator,
0245                     base_iterator
0246                 >::type* = 0) const
0247             {
0248                 return (m_index + m_offset) ==
0249                             (other.get_index() + other.get_offset());
0250             }
0251
0252             mutable base_iterator m_it;
0253             mutable difference_type m_offset;
0254             mutable size_type m_index;
0255             difference_type m_stride;
0256         };
0257
0258         // strided_iterator implementation for wrapping a random access iterator
0259         template<class BaseIterator>
0260         class strided_iterator<BaseIterator, random_access_traversal_tag>
0261             : public iterator_facade<
0262                 strided_iterator<BaseIterator, random_access_traversal_tag>
0263                 , typename iterator_value<BaseIterator>::type
0264                 , random_access_traversal_tag
0265                 , typename iterator_reference<BaseIterator>::type
0266                 , typename iterator_difference<BaseIterator>::type
0267             >
0268         {
0269             friend class ::boost::iterator_core_access;
0270
0271             typedef iterator_facade<
0272                 strided_iterator<BaseIterator, random_access_traversal_tag>
0273                 , typename iterator_value<BaseIterator>::type
0274                 , random_access_traversal_tag
0275                 , typename iterator_reference<BaseIterator>::type
0276                 , typename iterator_difference<BaseIterator>::type
0277             > super_t;
0278         public:
0279             typedef typename super_t::difference_type difference_type;
0280             typedef typename super_t::reference reference;
0281             typedef BaseIterator base_iterator;
0282             typedef std::random_access_iterator_tag iterator_category;
0283
0284             strided_iterator()
0285                 : m_it()
0286                 , m_first()
0287                 , m_index(0)
0288                 , m_stride()
0289             {
0290             }
0291
0292             strided_iterator(
0293                 base_iterator   first,
0294                 base_iterator   it,
0295                 difference_type stride
0296             )
0297                 : m_it(it)
0298                 , m_first(first)
0299                 , m_index(stride ? (it - first) : difference_type())
0300                 , m_stride(stride)
0301             {
0302                 if (stride && ((m_index % stride) != 0))
0303                     m_index += (stride - (m_index % stride));
0304             }
0305
0306             template<class OtherIterator>
0307             strided_iterator(
0308                 const strided_iterator<
0309                     OtherIterator,
0310                     random_access_traversal_tag
0311                 >& other,
0312                 typename iterators::enable_if_convertible<
0313                     OtherIterator,
0314                     base_iterator
0315                 >::type* = 0
0316             )
0317                 : m_it(other.base())
0318                 , m_first(other.base_begin())
0319                 , m_index(other.get_index())
0320                 , m_stride(other.get_stride())
0321             {
0322             }
0323
0324             base_iterator base_begin() const
0325             {
0326                 return m_first;
0327             }
0328
0329             base_iterator base() const
0330             {
0331                 return m_it;
0332             }
0333
0334             difference_type get_stride() const
0335             {
0336                 return m_stride;
0337             }
0338
0339             difference_type get_index() const
0340             {
0341                 return m_index;
0342             }
0343
0344         private:
0345             void increment()
0346             {
0347                 m_index += m_stride;
0348             }
0349
0350             void decrement()
0351             {
0352                 m_index -= m_stride;
0353             }
0354
0355             void advance(difference_type offset)
0356             {
0357                 m_index += (m_stride * offset);
0358             }
0359
0360             // Implementation detail: only update the actual underlying iterator
0361             // at the point of dereference. This is done so that the increment
0362             // and decrement can overshoot the valid sequence as is required
0363             // by striding. Since we can do all comparisons just with the index
0364             // simply, and all dereferences must be within the valid range.
0365             void update() const
0366             {
0367                 m_it = m_first + m_index;
0368             }
0369
0370             template<class OtherIterator>
0371             difference_type distance_to(
0372                 const strided_iterator<
0373                     OtherIterator,
0374                     random_access_traversal_tag
0375                 >& other,
0376                 typename iterators::enable_if_convertible<
0377                             OtherIterator, base_iterator>::type* = 0) const
0378             {
0379                 BOOST_ASSERT((other.m_index - m_index) % m_stride == difference_type());
0380                 return (other.m_index - m_index) / m_stride;
0381             }
0382
0383             template<class OtherIterator>
0384             bool equal(
0385                 const strided_iterator<
0386                     OtherIterator,
0387                     random_access_traversal_tag
0388                 >& other,
0389                 typename iterators::enable_if_convertible<
0390                             OtherIterator, base_iterator>::type* = 0) const
0391             {
0392                 return m_index == other.m_index;
0393             }
0394
0395             reference dereference() const
0396             {
0397                 update();
0398                 return *m_it;
0399             }
0400
0401         private:
0402             mutable base_iterator m_it;
0403             base_iterator m_first;
0404             difference_type m_index;
0405             difference_type m_stride;
0406         };
0407
0408         template<class Rng, class Difference> inline
0409         strided_iterator<
0410             typename range_iterator<Rng>::type,
0411             forward_traversal_tag
0412         >
0413         make_begin_strided_iterator(
0414             Rng& rng,
0415             Difference stride,
0416             forward_traversal_tag)
0417         {
0418             return strided_iterator<
0419                 typename range_iterator<Rng>::type,
0420                 forward_traversal_tag
0421             >(boost::begin(rng), boost::end(rng), stride);
0422         }
0423
0424         template<class Rng, class Difference> inline
0425         strided_iterator<
0426             typename range_iterator<const Rng>::type,
0427             forward_traversal_tag
0428         >
0429         make_begin_strided_iterator(
0430             const Rng& rng,
0431             Difference stride,
0432             forward_traversal_tag)
0433         {
0434             return strided_iterator<
0435                 typename range_iterator<const Rng>::type,
0436                 forward_traversal_tag
0437             >(boost::begin(rng), boost::end(rng), stride);
0438         }
0439
0440         template<class Rng, class Difference> inline
0441         strided_iterator<
0442             typename range_iterator<Rng>::type,
0443             forward_traversal_tag
0444         >
0445         make_end_strided_iterator(
0446             Rng& rng,
0447             Difference stride,
0448             forward_traversal_tag)
0449         {
0450             return strided_iterator<
0451                 typename range_iterator<Rng>::type,
0452                 forward_traversal_tag
0453             >(boost::end(rng), boost::end(rng), stride);
0454         }
0455
0456         template<class Rng, class Difference> inline
0457         strided_iterator<
0458             typename range_iterator<const Rng>::type,
0459             forward_traversal_tag
0460         >
0461         make_end_strided_iterator(
0462             const Rng& rng,
0463             Difference stride,
0464             forward_traversal_tag)
0465         {
0466             return strided_iterator<
0467                 typename range_iterator<const Rng>::type,
0468                 forward_traversal_tag
0469             >(boost::end(rng), boost::end(rng), stride);
0470         }
0471
0472         template<class Rng, class Difference> inline
0473         strided_iterator<
0474             typename range_iterator<Rng>::type,
0475             bidirectional_traversal_tag
0476         >
0477         make_begin_strided_iterator(
0478             Rng& rng,
0479             Difference stride,
0480             bidirectional_traversal_tag)
0481         {
0482             typedef typename range_difference<Rng>::type difference_type;
0483
0484             return strided_iterator<
0485                 typename range_iterator<Rng>::type,
0486                 bidirectional_traversal_tag
0487             >(boost::begin(rng), difference_type(), stride);
0488         }
0489
0490         template<class Rng, class Difference> inline
0491         strided_iterator<
0492             typename range_iterator<const Rng>::type,
0493             bidirectional_traversal_tag
0494         >
0495         make_begin_strided_iterator(
0496             const Rng& rng,
0497             Difference stride,
0498             bidirectional_traversal_tag)
0499         {
0500             typedef typename range_difference<const Rng>::type difference_type;
0501
0502             return strided_iterator<
0503                 typename range_iterator<const Rng>::type,
0504                 bidirectional_traversal_tag
0505             >(boost::begin(rng), difference_type(), stride);
0506         }
0507
0508         template<class Rng, class Difference> inline
0509         strided_iterator<
0510             typename range_iterator<Rng>::type,
0511             bidirectional_traversal_tag
0512         >
0513         make_end_strided_iterator(
0514             Rng& rng,
0515             Difference stride,
0516             bidirectional_traversal_tag)
0517         {
0518             return strided_iterator<
0519                 typename range_iterator<Rng>::type,
0520                 bidirectional_traversal_tag
0521             >(boost::end(rng), boost::size(rng), stride);
0522         }
0523
0524         template<class Rng, class Difference> inline
0525         strided_iterator<
0526             typename range_iterator<const Rng>::type,
0527             bidirectional_traversal_tag
0528         >
0529         make_end_strided_iterator(
0530             const Rng& rng,
0531             Difference stride,
0532             bidirectional_traversal_tag)
0533         {
0534             return strided_iterator<
0535                 typename range_iterator<const Rng>::type,
0536                 bidirectional_traversal_tag
0537             >(boost::end(rng), boost::size(rng), stride);
0538         }
0539
0540         template<class Rng, class Difference> inline
0541         strided_iterator<
0542             typename range_iterator<Rng>::type,
0543             random_access_traversal_tag
0544         >
0545         make_begin_strided_iterator(
0546             Rng& rng,
0547             Difference stride,
0548             random_access_traversal_tag)
0549         {
0550             return strided_iterator<
0551                 typename range_iterator<Rng>::type,
0552                 random_access_traversal_tag
0553             >(boost::begin(rng), boost::begin(rng), stride);
0554         }
0555
0556         template<class Rng, class Difference> inline
0557         strided_iterator<
0558             typename range_iterator<const Rng>::type,
0559             random_access_traversal_tag
0560         >
0561         make_begin_strided_iterator(
0562             const Rng& rng,
0563             Difference stride,
0564             random_access_traversal_tag)
0565         {
0566             return strided_iterator<
0567                 typename range_iterator<const Rng>::type,
0568                 random_access_traversal_tag
0569             >(boost::begin(rng), boost::begin(rng), stride);
0570         }
0571
0572         template<class Rng, class Difference> inline
0573         strided_iterator<
0574             typename range_iterator<Rng>::type,
0575             random_access_traversal_tag
0576         >
0577         make_end_strided_iterator(
0578             Rng& rng,
0579             Difference stride,
0580             random_access_traversal_tag)
0581         {
0582             return strided_iterator<
0583                 typename range_iterator<Rng>::type,
0584                 random_access_traversal_tag
0585             >(boost::begin(rng), boost::end(rng), stride);
0586         }
0587
0588         template<class Rng, class Difference> inline
0589         strided_iterator<
0590             typename range_iterator<const Rng>::type,
0591             random_access_traversal_tag
0592         >
0593         make_end_strided_iterator(
0594             const Rng& rng,
0595             Difference stride,
0596             random_access_traversal_tag)
0597         {
0598             return strided_iterator<
0599                 typename range_iterator<const Rng>::type,
0600                 random_access_traversal_tag
0601             >(boost::begin(rng), boost::end(rng), stride);
0602         }
0603
0604         template<
0605             class Rng,
0606             class Category =
0607                 typename iterators::pure_iterator_traversal<
0608                     typename range_iterator<Rng>::type
0609                 >::type
0610         >
0611         class strided_range
0612             : public iterator_range<
0613                 range_detail::strided_iterator<
0614                     typename range_iterator<Rng>::type,
0615                     Category
0616                 >
0617             >
0618         {
0619             typedef range_detail::strided_iterator<
0620                 typename range_iterator<Rng>::type,
0621                 Category
0622             > iter_type;
0623             typedef iterator_range<iter_type> super_t;
0624         public:
0625             template<class Difference>
0626             strided_range(Difference stride, Rng& rng)
0627                 : super_t(
0628                     range_detail::make_begin_strided_iterator(
0629                         rng, stride,
0630                         typename iterator_traversal<
0631                             typename range_iterator<Rng>::type
0632                         >::type()),
0633                     range_detail::make_end_strided_iterator(
0634                         rng, stride,
0635                         typename iterator_traversal<
0636                             typename range_iterator<Rng>::type
0637                         >::type()))
0638             {
0639                 BOOST_ASSERT( stride >= 0 );
0640             }
0641         };
0642
0643         template<class Difference>
0644         class strided_holder : public holder<Difference>
0645         {
0646         public:
0647             explicit strided_holder(Difference value)
0648                 : holder<Difference>(value)
0649             {
0650             }
0651         };
0652
0653         template<class Rng, class Difference>
0654         inline strided_range<Rng>
0655         operator|(Rng& rng, const strided_holder<Difference>& stride)
0656         {
0657             return strided_range<Rng>(stride.val, rng);
0658         }
0659
0660         template<class Rng, class Difference>
0661         inline strided_range<const Rng>
0662         operator|(const Rng& rng, const strided_holder<Difference>& stride)
0663         {
0664             return strided_range<const Rng>(stride.val, rng);
0665         }
0666
0667     } // namespace range_detail
0668
0669     using range_detail::strided_range;
0670
0671     namespace adaptors
0672     {
0673
0674         namespace
0675         {
0676             const range_detail::forwarder<range_detail::strided_holder>
0677                 strided = range_detail::forwarder<
0678                             range_detail::strided_holder>();
0679         }
0680
0681         template<class Range, class Difference>
0682         inline strided_range<Range>
0683         stride(Range& rng, Difference step)
0684         {
0685             return strided_range<Range>(step, rng);
0686         }
0687
0688         template<class Range, class Difference>
0689         inline strided_range<const Range>
0690         stride(const Range& rng, Difference step)
0691         {
0692             return strided_range<const Range>(step, rng);
0693         }
0694
0695     } // namespace 'adaptors'
0696 } // namespace 'boost'
0697
0698 #endif