1// Boost.Range library
2//
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)
7//
8//
9// For more information, see http://www.boost.org/libs/range/
10//
11#ifndef BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
12#define BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
13
14#include <boost/range/adaptor/argument_fwd.hpp>
15#include <boost/range/iterator_range.hpp>
16#include <boost/iterator/iterator_facade.hpp>
17#include <iterator>
18
19namespace boost
20{
21 namespace range_detail
22 {
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
32 >
33 {
34 friend class ::boost::iterator_core_access;
35
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
42 > super_t;
43
44 public:
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;
49
50 strided_iterator()
51 : m_it()
52 , m_last()
53 , m_stride()
54 {
55 }
56
57 strided_iterator(base_iterator it,
58 base_iterator last,
59 difference_type stride)
60 : m_it(it)
61 , m_last(last)
62 , m_stride(stride)
63 {
64 }
65
66 template<class OtherIterator>
67 strided_iterator(
68 const strided_iterator<OtherIterator, Category>& other,
69 typename enable_if_convertible<
70 OtherIterator,
71 base_iterator
72 >::type* = 0
73 )
74 : m_it(other.base())
75 , m_last(other.base_end())
76 , m_stride(other.get_stride())
77 {
78 }
79
80 base_iterator base() const
81 {
82 return m_it;
83 }
84
85 base_iterator base_end() const
86 {
87 return m_last;
88 }
89
90 difference_type get_stride() const
91 {
92 return m_stride;
93 }
94
95 private:
96 void increment()
97 {
98 for (difference_type i = 0;
99 (m_it != m_last) && (i < m_stride); ++i)
100 {
101 ++m_it;
102 }
103 }
104
105 reference dereference() const
106 {
107 return *m_it;
108 }
109
110 template<class OtherIterator>
111 bool equal(
112 const strided_iterator<OtherIterator, Category>& other,
113 typename enable_if_convertible<
114 OtherIterator,
115 base_iterator
116 >::type* = 0) const
117 {
118 return m_it == other.m_it;
119 }
120
121 base_iterator m_it;
122 base_iterator m_last;
123 difference_type m_stride;
124 };
125
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
135 >
136 {
137 friend class ::boost::iterator_core_access;
138
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
145 > super_t;
146 public:
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
151 size_type;
152 typedef std::bidirectional_iterator_tag iterator_category;
153
154 strided_iterator()
155 : m_it()
156 , m_offset()
157 , m_index()
158 , m_stride()
159 {
160 }
161
162 strided_iterator(base_iterator it,
163 size_type index,
164 difference_type stride)
165 : m_it(it)
166 , m_offset()
167 , m_index(index)
168 , m_stride(stride)
169 {
170 if (stride && ((m_index % stride) != 0))
171 m_index += (stride - (m_index % stride));
172 }
173
174 template<class OtherIterator>
175 strided_iterator(
176 const strided_iterator<
177 OtherIterator,
178 bidirectional_traversal_tag
179 >& other,
180 typename enable_if_convertible<
181 OtherIterator,
182 base_iterator
183 >::type* = 0
184 )
185 : m_it(other.base())
186 , m_offset(other.get_offset())
187 , m_index(other.get_index())
188 , m_stride(other.get_stride())
189 {
190 }
191
192 base_iterator base() const
193 {
194 return m_it;
195 }
196
197 difference_type get_offset() const
198 {
199 return m_offset;
200 }
201
202 size_type get_index() const
203 {
204 return m_index;
205 }
206
207 difference_type get_stride() const
208 {
209 return m_stride;
210 }
211
212 private:
213 void increment()
214 {
215 m_offset += m_stride;
216 }
217
218 void decrement()
219 {
220 m_offset -= m_stride;
221 }
222
223 reference dereference() const
224 {
225 update();
226 return *m_it;
227 }
228
229 void update() const
230 {
231 std::advance(m_it, m_offset);
232 m_index += m_offset;
233 m_offset = 0;
234 }
235
236 template<class OtherIterator>
237 bool equal(
238 const strided_iterator<
239 OtherIterator,
240 bidirectional_traversal_tag
241 >& other,
242 typename enable_if_convertible<
243 OtherIterator,
244 base_iterator
245 >::type* = 0) const
246 {
247 return (m_index + m_offset) ==
248 (other.get_index() + other.get_offset());
249 }
250
251 mutable base_iterator m_it;
252 mutable difference_type m_offset;
253 mutable size_type m_index;
254 difference_type m_stride;
255 };
256
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
266 >
267 {
268 friend class ::boost::iterator_core_access;
269
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
276 > super_t;
277 public:
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;
282
283 strided_iterator()
284 : m_it()
285 , m_first()
286 , m_index(0)
287 , m_stride()
288 {
289 }
290
291 strided_iterator(
292 base_iterator first,
293 base_iterator it,
294 difference_type stride
295 )
296 : m_it(it)
297 , m_first(first)
298 , m_index(stride ? (it - first) : difference_type())
299 , m_stride(stride)
300 {
301 if (stride && ((m_index % stride) != 0))
302 m_index += (stride - (m_index % stride));
303 }
304
305 template<class OtherIterator>
306 strided_iterator(
307 const strided_iterator<
308 OtherIterator,
309 random_access_traversal_tag
310 >& other,
311 typename enable_if_convertible<
312 OtherIterator,
313 base_iterator
314 >::type* = 0
315 )
316 : m_it(other.base())
317 , m_first(other.base_begin())
318 , m_index(other.get_index())
319 , m_stride(other.get_stride())
320 {
321 }
322
323 base_iterator base_begin() const
324 {
325 return m_first;
326 }
327
328 base_iterator base() const
329 {
330 return m_it;
331 }
332
333 difference_type get_stride() const
334 {
335 return m_stride;
336 }
337
338 difference_type get_index() const
339 {
340 return m_index;
341 }
342
343 private:
344 void increment()
345 {
346 m_index += m_stride;
347 }
348
349 void decrement()
350 {
351 m_index -= m_stride;
352 }
353
354 void advance(difference_type offset)
355 {
356 m_index += (m_stride * offset);
357 }
358
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.
364 void update() const
365 {
366 m_it = m_first + m_index;
367 }
368
369 template<class OtherIterator>
370 difference_type distance_to(
371 const strided_iterator<
372 OtherIterator,
373 random_access_traversal_tag
374 >& other,
375 typename enable_if_convertible<
376 OtherIterator, base_iterator>::type* = 0) const
377 {
378 BOOST_ASSERT((other.m_index - m_index) % m_stride == difference_type());
379 return (other.m_index - m_index) / m_stride;
380 }
381
382 template<class OtherIterator>
383 bool equal(
384 const strided_iterator<
385 OtherIterator,
386 random_access_traversal_tag
387 >& other,
388 typename enable_if_convertible<
389 OtherIterator, base_iterator>::type* = 0) const
390 {
391 return m_index == other.m_index;
392 }
393
394 reference dereference() const
395 {
396 update();
397 return *m_it;
398 }
399
400 private:
401 mutable base_iterator m_it;
402 base_iterator m_first;
403 difference_type m_index;
404 difference_type m_stride;
405 };
406
407 template<class Rng, class Difference> inline
408 strided_iterator<
409 typename range_iterator<Rng>::type,
410 forward_traversal_tag
411 >
412 make_begin_strided_iterator(
413 Rng& rng,
414 Difference stride,
415 forward_traversal_tag)
416 {
417 return strided_iterator<
418 typename range_iterator<Rng>::type,
419 forward_traversal_tag
420 >(boost::begin(rng), boost::end(rng), stride);
421 }
422
423 template<class Rng, class Difference> inline
424 strided_iterator<
425 typename range_iterator<const Rng>::type,
426 forward_traversal_tag
427 >
428 make_begin_strided_iterator(
429 const Rng& rng,
430 Difference stride,
431 forward_traversal_tag)
432 {
433 return strided_iterator<
434 typename range_iterator<const Rng>::type,
435 forward_traversal_tag
436 >(boost::begin(rng), boost::end(rng), stride);
437 }
438
439 template<class Rng, class Difference> inline
440 strided_iterator<
441 typename range_iterator<Rng>::type,
442 forward_traversal_tag
443 >
444 make_end_strided_iterator(
445 Rng& rng,
446 Difference stride,
447 forward_traversal_tag)
448 {
449 return strided_iterator<
450 typename range_iterator<Rng>::type,
451 forward_traversal_tag
452 >(boost::end(rng), boost::end(rng), stride);
453 }
454
455 template<class Rng, class Difference> inline
456 strided_iterator<
457 typename range_iterator<const Rng>::type,
458 forward_traversal_tag
459 >
460 make_end_strided_iterator(
461 const Rng& rng,
462 Difference stride,
463 forward_traversal_tag)
464 {
465 return strided_iterator<
466 typename range_iterator<const Rng>::type,
467 forward_traversal_tag
468 >(boost::end(rng), boost::end(rng), stride);
469 }
470
471 template<class Rng, class Difference> inline
472 strided_iterator<
473 typename range_iterator<Rng>::type,
474 bidirectional_traversal_tag
475 >
476 make_begin_strided_iterator(
477 Rng& rng,
478 Difference stride,
479 bidirectional_traversal_tag)
480 {
481 typedef typename range_difference<Rng>::type difference_type;
482
483 return strided_iterator<
484 typename range_iterator<Rng>::type,
485 bidirectional_traversal_tag
486 >(boost::begin(rng), difference_type(), stride);
487 }
488
489 template<class Rng, class Difference> inline
490 strided_iterator<
491 typename range_iterator<const Rng>::type,
492 bidirectional_traversal_tag
493 >
494 make_begin_strided_iterator(
495 const Rng& rng,
496 Difference stride,
497 bidirectional_traversal_tag)
498 {
499 typedef typename range_difference<const Rng>::type difference_type;
500
501 return strided_iterator<
502 typename range_iterator<const Rng>::type,
503 bidirectional_traversal_tag
504 >(boost::begin(rng), difference_type(), stride);
505 }
506
507 template<class Rng, class Difference> inline
508 strided_iterator<
509 typename range_iterator<Rng>::type,
510 bidirectional_traversal_tag
511 >
512 make_end_strided_iterator(
513 Rng& rng,
514 Difference stride,
515 bidirectional_traversal_tag)
516 {
517 return strided_iterator<
518 typename range_iterator<Rng>::type,
519 bidirectional_traversal_tag
520 >(boost::end(rng), boost::size(rng), stride);
521 }
522
523 template<class Rng, class Difference> inline
524 strided_iterator<
525 typename range_iterator<const Rng>::type,
526 bidirectional_traversal_tag
527 >
528 make_end_strided_iterator(
529 const Rng& rng,
530 Difference stride,
531 bidirectional_traversal_tag)
532 {
533 return strided_iterator<
534 typename range_iterator<const Rng>::type,
535 bidirectional_traversal_tag
536 >(boost::end(rng), boost::size(rng), stride);
537 }
538
539 template<class Rng, class Difference> inline
540 strided_iterator<
541 typename range_iterator<Rng>::type,
542 random_access_traversal_tag
543 >
544 make_begin_strided_iterator(
545 Rng& rng,
546 Difference stride,
547 random_access_traversal_tag)
548 {
549 return strided_iterator<
550 typename range_iterator<Rng>::type,
551 random_access_traversal_tag
552 >(boost::begin(rng), boost::begin(rng), stride);
553 }
554
555 template<class Rng, class Difference> inline
556 strided_iterator<
557 typename range_iterator<const Rng>::type,
558 random_access_traversal_tag
559 >
560 make_begin_strided_iterator(
561 const Rng& rng,
562 Difference stride,
563 random_access_traversal_tag)
564 {
565 return strided_iterator<
566 typename range_iterator<const Rng>::type,
567 random_access_traversal_tag
568 >(boost::begin(rng), boost::begin(rng), stride);
569 }
570
571 template<class Rng, class Difference> inline
572 strided_iterator<
573 typename range_iterator<Rng>::type,
574 random_access_traversal_tag
575 >
576 make_end_strided_iterator(
577 Rng& rng,
578 Difference stride,
579 random_access_traversal_tag)
580 {
581 return strided_iterator<
582 typename range_iterator<Rng>::type,
583 random_access_traversal_tag
584 >(boost::begin(rng), boost::end(rng), stride);
585 }
586
587 template<class Rng, class Difference> inline
588 strided_iterator<
589 typename range_iterator<const Rng>::type,
590 random_access_traversal_tag
591 >
592 make_end_strided_iterator(
593 const Rng& rng,
594 Difference stride,
595 random_access_traversal_tag)
596 {
597 return strided_iterator<
598 typename range_iterator<const Rng>::type,
599 random_access_traversal_tag
600 >(boost::begin(rng), boost::end(rng), stride);
601 }
602
603 template<
604 class Rng,
605 class Category =
606 typename iterators::pure_iterator_traversal<
607 typename range_iterator<Rng>::type
608 >::type
609 >
610 class strided_range
611 : public iterator_range<
612 range_detail::strided_iterator<
613 typename range_iterator<Rng>::type,
614 Category
615 >
616 >
617 {
618 typedef range_detail::strided_iterator<
619 typename range_iterator<Rng>::type,
620 Category
621 > iter_type;
622 typedef iterator_range<iter_type> super_t;
623 public:
624 template<class Difference>
625 strided_range(Difference stride, Rng& rng)
626 : super_t(
627 range_detail::make_begin_strided_iterator(
628 rng, stride,
629 typename iterator_traversal<
630 typename range_iterator<Rng>::type
631 >::type()),
632 range_detail::make_end_strided_iterator(
633 rng, stride,
634 typename iterator_traversal<
635 typename range_iterator<Rng>::type
636 >::type()))
637 {
638 BOOST_ASSERT( stride >= 0 );
639 }
640 };
641
642 template<class Difference>
643 class strided_holder : public holder<Difference>
644 {
645 public:
646 explicit strided_holder(Difference value)
647 : holder<Difference>(value)
648 {
649 }
650 };
651
652 template<class Rng, class Difference>
653 inline strided_range<Rng>
654 operator|(Rng& rng, const strided_holder<Difference>& stride)
655 {
656 return strided_range<Rng>(stride.val, rng);
657 }
658
659 template<class Rng, class Difference>
660 inline strided_range<const Rng>
661 operator|(const Rng& rng, const strided_holder<Difference>& stride)
662 {
663 return strided_range<const Rng>(stride.val, rng);
664 }
665
666 } // namespace range_detail
667
668 using range_detail::strided_range;
669
670 namespace adaptors
671 {
672
673 namespace
674 {
675 const range_detail::forwarder<range_detail::strided_holder>
676 strided = range_detail::forwarder<
677 range_detail::strided_holder>();
678 }
679
680 template<class Range, class Difference>
681 inline strided_range<Range>
682 stride(Range& rng, Difference step)
683 {
684 return strided_range<Range>(step, rng);
685 }
686
687 template<class Range, class Difference>
688 inline strided_range<const Range>
689 stride(const Range& rng, Difference step)
690 {
691 return strided_range<const Range>(step, rng);
692 }
693
694 } // namespace 'adaptors'
695} // namespace 'boost'
696
697#endif
698

source code of boost/boost/range/adaptor/strided.hpp