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 | |
19 | namespace 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 | |