3 // Copyright Neil Groves 2007. Use, modification and
4 // distribution is subject to the Boost Software License, Version
5 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
9 // For more information, see http://www.boost.org/libs/range/
11 #ifndef BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
12 #define BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
14 #include <boost/range/adaptor/argument_fwd.hpp>
15 #include <boost/range/iterator_range.hpp>
16 #include <boost/iterator/iterator_facade.hpp>
21 namespace range_detail
23 // strided_iterator for wrapping a forward traversal iterator
24 template<class BaseIterator, class Category>
25 class strided_iterator
26 : public iterator_facade<
27 strided_iterator<BaseIterator, Category>
28 , typename iterator_value<BaseIterator>::type
29 , forward_traversal_tag
30 , typename iterator_reference<BaseIterator>::type
31 , typename iterator_difference<BaseIterator>::type
34 friend class ::boost::iterator_core_access;
36 typedef iterator_facade<
37 strided_iterator<BaseIterator, Category>
38 , typename iterator_value<BaseIterator>::type
39 , forward_traversal_tag
40 , typename iterator_reference<BaseIterator>::type
41 , typename iterator_difference<BaseIterator>::type
45 typedef typename super_t::difference_type difference_type;
46 typedef typename super_t::reference reference;
47 typedef BaseIterator base_iterator;
48 typedef std::forward_iterator_tag iterator_category;
57 strided_iterator(base_iterator it,
59 difference_type stride)
66 template<class OtherIterator>
68 const strided_iterator<OtherIterator, Category>& other,
69 typename enable_if_convertible<
75 , m_last(other.base_end())
76 , m_stride(other.get_stride())
80 base_iterator base() const
85 base_iterator base_end() const
90 difference_type get_stride() const
98 for (difference_type i = 0;
99 (m_it != m_last) && (i < m_stride); ++i)
105 reference dereference() const
110 template<class OtherIterator>
112 const strided_iterator<OtherIterator, Category>& other,
113 typename enable_if_convertible<
118 return m_it == other.m_it;
122 base_iterator m_last;
123 difference_type m_stride;
126 // strided_iterator for wrapping a bidirectional iterator
127 template<class BaseIterator>
128 class strided_iterator<BaseIterator, bidirectional_traversal_tag>
129 : public iterator_facade<
130 strided_iterator<BaseIterator, bidirectional_traversal_tag>
131 , typename iterator_value<BaseIterator>::type
132 , bidirectional_traversal_tag
133 , typename iterator_reference<BaseIterator>::type
134 , typename iterator_difference<BaseIterator>::type
137 friend class ::boost::iterator_core_access;
139 typedef iterator_facade<
140 strided_iterator<BaseIterator, bidirectional_traversal_tag>
141 , typename iterator_value<BaseIterator>::type
142 , bidirectional_traversal_tag
143 , typename iterator_reference<BaseIterator>::type
144 , typename iterator_difference<BaseIterator>::type
147 typedef typename super_t::difference_type difference_type;
148 typedef typename super_t::reference reference;
149 typedef BaseIterator base_iterator;
150 typedef typename boost::make_unsigned<difference_type>::type
152 typedef std::bidirectional_iterator_tag iterator_category;
162 strided_iterator(base_iterator it,
164 difference_type stride)
170 if (stride && ((m_index % stride) != 0))
171 m_index += (stride - (m_index % stride));
174 template<class OtherIterator>
176 const strided_iterator<
178 bidirectional_traversal_tag
180 typename enable_if_convertible<
186 , m_offset(other.get_offset())
187 , m_index(other.get_index())
188 , m_stride(other.get_stride())
192 base_iterator base() const
197 difference_type get_offset() const
202 size_type get_index() const
207 difference_type get_stride() const
215 m_offset += m_stride;
220 m_offset -= m_stride;
223 reference dereference() const
231 std::advance(m_it, m_offset);
236 template<class OtherIterator>
238 const strided_iterator<
240 bidirectional_traversal_tag
242 typename enable_if_convertible<
247 return (m_index + m_offset) ==
248 (other.get_index() + other.get_offset());
251 mutable base_iterator m_it;
252 mutable difference_type m_offset;
253 mutable size_type m_index;
254 difference_type m_stride;
257 // strided_iterator implementation for wrapping a random access iterator
258 template<class BaseIterator>
259 class strided_iterator<BaseIterator, random_access_traversal_tag>
260 : public iterator_facade<
261 strided_iterator<BaseIterator, random_access_traversal_tag>
262 , typename iterator_value<BaseIterator>::type
263 , random_access_traversal_tag
264 , typename iterator_reference<BaseIterator>::type
265 , typename iterator_difference<BaseIterator>::type
268 friend class ::boost::iterator_core_access;
270 typedef iterator_facade<
271 strided_iterator<BaseIterator, random_access_traversal_tag>
272 , typename iterator_value<BaseIterator>::type
273 , random_access_traversal_tag
274 , typename iterator_reference<BaseIterator>::type
275 , typename iterator_difference<BaseIterator>::type
278 typedef typename super_t::difference_type difference_type;
279 typedef typename super_t::reference reference;
280 typedef BaseIterator base_iterator;
281 typedef std::random_access_iterator_tag iterator_category;
294 difference_type stride
298 , m_index(stride ? (it - first) : difference_type())
301 if (stride && ((m_index % stride) != 0))
302 m_index += (stride - (m_index % stride));
305 template<class OtherIterator>
307 const strided_iterator<
309 random_access_traversal_tag
311 typename enable_if_convertible<
317 , m_first(other.base_begin())
318 , m_index(other.get_index())
319 , m_stride(other.get_stride())
323 base_iterator base_begin() const
328 base_iterator base() const
333 difference_type get_stride() const
338 difference_type get_index() const
354 void advance(difference_type offset)
356 m_index += (m_stride * offset);
359 // Implementation detail: only update the actual underlying iterator
360 // at the point of dereference. This is done so that the increment
361 // and decrement can overshoot the valid sequence as is required
362 // by striding. Since we can do all comparisons just with the index
363 // simply, and all dereferences must be within the valid range.
366 m_it = m_first + m_index;
369 template<class OtherIterator>
370 difference_type distance_to(
371 const strided_iterator<
373 random_access_traversal_tag
375 typename enable_if_convertible<
376 OtherIterator, base_iterator>::type* = 0) const
378 BOOST_ASSERT((other.m_index - m_index) % m_stride == difference_type());
379 return (other.m_index - m_index) / m_stride;
382 template<class OtherIterator>
384 const strided_iterator<
386 random_access_traversal_tag
388 typename enable_if_convertible<
389 OtherIterator, base_iterator>::type* = 0) const
391 return m_index == other.m_index;
394 reference dereference() const
401 mutable base_iterator m_it;
402 base_iterator m_first;
403 difference_type m_index;
404 difference_type m_stride;
407 template<class Rng, class Difference> inline
409 typename range_iterator<Rng>::type,
410 forward_traversal_tag
412 make_begin_strided_iterator(
415 forward_traversal_tag)
417 return strided_iterator<
418 typename range_iterator<Rng>::type,
419 forward_traversal_tag
420 >(boost::begin(rng), boost::end(rng), stride);
423 template<class Rng, class Difference> inline
425 typename range_iterator<const Rng>::type,
426 forward_traversal_tag
428 make_begin_strided_iterator(
431 forward_traversal_tag)
433 return strided_iterator<
434 typename range_iterator<const Rng>::type,
435 forward_traversal_tag
436 >(boost::begin(rng), boost::end(rng), stride);
439 template<class Rng, class Difference> inline
441 typename range_iterator<Rng>::type,
442 forward_traversal_tag
444 make_end_strided_iterator(
447 forward_traversal_tag)
449 return strided_iterator<
450 typename range_iterator<Rng>::type,
451 forward_traversal_tag
452 >(boost::end(rng), boost::end(rng), stride);
455 template<class Rng, class Difference> inline
457 typename range_iterator<const Rng>::type,
458 forward_traversal_tag
460 make_end_strided_iterator(
463 forward_traversal_tag)
465 return strided_iterator<
466 typename range_iterator<const Rng>::type,
467 forward_traversal_tag
468 >(boost::end(rng), boost::end(rng), stride);
471 template<class Rng, class Difference> inline
473 typename range_iterator<Rng>::type,
474 bidirectional_traversal_tag
476 make_begin_strided_iterator(
479 bidirectional_traversal_tag)
481 typedef typename range_difference<Rng>::type difference_type;
483 return strided_iterator<
484 typename range_iterator<Rng>::type,
485 bidirectional_traversal_tag
486 >(boost::begin(rng), difference_type(), stride);
489 template<class Rng, class Difference> inline
491 typename range_iterator<const Rng>::type,
492 bidirectional_traversal_tag
494 make_begin_strided_iterator(
497 bidirectional_traversal_tag)
499 typedef typename range_difference<const Rng>::type difference_type;
501 return strided_iterator<
502 typename range_iterator<const Rng>::type,
503 bidirectional_traversal_tag
504 >(boost::begin(rng), difference_type(), stride);
507 template<class Rng, class Difference> inline
509 typename range_iterator<Rng>::type,
510 bidirectional_traversal_tag
512 make_end_strided_iterator(
515 bidirectional_traversal_tag)
517 return strided_iterator<
518 typename range_iterator<Rng>::type,
519 bidirectional_traversal_tag
520 >(boost::end(rng), boost::size(rng), stride);
523 template<class Rng, class Difference> inline
525 typename range_iterator<const Rng>::type,
526 bidirectional_traversal_tag
528 make_end_strided_iterator(
531 bidirectional_traversal_tag)
533 return strided_iterator<
534 typename range_iterator<const Rng>::type,
535 bidirectional_traversal_tag
536 >(boost::end(rng), boost::size(rng), stride);
539 template<class Rng, class Difference> inline
541 typename range_iterator<Rng>::type,
542 random_access_traversal_tag
544 make_begin_strided_iterator(
547 random_access_traversal_tag)
549 return strided_iterator<
550 typename range_iterator<Rng>::type,
551 random_access_traversal_tag
552 >(boost::begin(rng), boost::begin(rng), stride);
555 template<class Rng, class Difference> inline
557 typename range_iterator<const Rng>::type,
558 random_access_traversal_tag
560 make_begin_strided_iterator(
563 random_access_traversal_tag)
565 return strided_iterator<
566 typename range_iterator<const Rng>::type,
567 random_access_traversal_tag
568 >(boost::begin(rng), boost::begin(rng), stride);
571 template<class Rng, class Difference> inline
573 typename range_iterator<Rng>::type,
574 random_access_traversal_tag
576 make_end_strided_iterator(
579 random_access_traversal_tag)
581 return strided_iterator<
582 typename range_iterator<Rng>::type,
583 random_access_traversal_tag
584 >(boost::begin(rng), boost::end(rng), stride);
587 template<class Rng, class Difference> inline
589 typename range_iterator<const Rng>::type,
590 random_access_traversal_tag
592 make_end_strided_iterator(
595 random_access_traversal_tag)
597 return strided_iterator<
598 typename range_iterator<const Rng>::type,
599 random_access_traversal_tag
600 >(boost::begin(rng), boost::end(rng), stride);
606 typename iterators::pure_iterator_traversal<
607 typename range_iterator<Rng>::type
611 : public iterator_range<
612 range_detail::strided_iterator<
613 typename range_iterator<Rng>::type,
618 typedef range_detail::strided_iterator<
619 typename range_iterator<Rng>::type,
622 typedef iterator_range<iter_type> super_t;
624 template<class Difference>
625 strided_range(Difference stride, Rng& rng)
627 range_detail::make_begin_strided_iterator(
629 typename iterator_traversal<
630 typename range_iterator<Rng>::type
632 range_detail::make_end_strided_iterator(
634 typename iterator_traversal<
635 typename range_iterator<Rng>::type
638 BOOST_ASSERT( stride >= 0 );
642 template<class Difference>
643 class strided_holder : public holder<Difference>
646 explicit strided_holder(Difference value)
647 : holder<Difference>(value)
652 template<class Rng, class Difference>
653 inline strided_range<Rng>
654 operator|(Rng& rng, const strided_holder<Difference>& stride)
656 return strided_range<Rng>(stride.val, rng);
659 template<class Rng, class Difference>
660 inline strided_range<const Rng>
661 operator|(const Rng& rng, const strided_holder<Difference>& stride)
663 return strided_range<const Rng>(stride.val, rng);
666 } // namespace range_detail
668 using range_detail::strided_range;
675 const range_detail::forwarder<range_detail::strided_holder>
676 strided = range_detail::forwarder<
677 range_detail::strided_holder>();
680 template<class Range, class Difference>
681 inline strided_range<Range>
682 stride(Range& rng, Difference step)
684 return strided_range<Range>(step, rng);
687 template<class Range, class Difference>
688 inline strided_range<const Range>
689 stride(const Range& rng, Difference step)
691 return strided_range<const Range>(step, rng);
694 } // namespace 'adaptors'
695 } // namespace 'boost'