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