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 strided_iterator()50 strided_iterator() 51 : m_it() 52 , m_last() 53 , m_stride() 54 { 55 } 56 strided_iterator(base_iterator it,base_iterator last,difference_type stride)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> strided_iterator(const strided_iterator<OtherIterator,Category> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0)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 base() const80 base_iterator base() const 81 { 82 return m_it; 83 } 84 base_end() const85 base_iterator base_end() const 86 { 87 return m_last; 88 } 89 get_stride() const90 difference_type get_stride() const 91 { 92 return m_stride; 93 } 94 95 private: increment()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 dereference() const105 reference dereference() const 106 { 107 return *m_it; 108 } 109 110 template<class OtherIterator> equal(const strided_iterator<OtherIterator,Category> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0) const111 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 strided_iterator()154 strided_iterator() 155 : m_it() 156 , m_offset() 157 , m_index() 158 , m_stride() 159 { 160 } 161 strided_iterator(base_iterator it,size_type index,difference_type stride)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> strided_iterator(const strided_iterator<OtherIterator,bidirectional_traversal_tag> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0)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 base() const192 base_iterator base() const 193 { 194 return m_it; 195 } 196 get_offset() const197 difference_type get_offset() const 198 { 199 return m_offset; 200 } 201 get_index() const202 size_type get_index() const 203 { 204 return m_index; 205 } 206 get_stride() const207 difference_type get_stride() const 208 { 209 return m_stride; 210 } 211 212 private: increment()213 void increment() 214 { 215 m_offset += m_stride; 216 } 217 decrement()218 void decrement() 219 { 220 m_offset -= m_stride; 221 } 222 dereference() const223 reference dereference() const 224 { 225 update(); 226 return *m_it; 227 } 228 update() const229 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> equal(const strided_iterator<OtherIterator,bidirectional_traversal_tag> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0) const237 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 strided_iterator()283 strided_iterator() 284 : m_it() 285 , m_first() 286 , m_index(0) 287 , m_stride() 288 { 289 } 290 strided_iterator(base_iterator first,base_iterator it,difference_type stride)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> strided_iterator(const strided_iterator<OtherIterator,random_access_traversal_tag> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0)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 base_begin() const323 base_iterator base_begin() const 324 { 325 return m_first; 326 } 327 base() const328 base_iterator base() const 329 { 330 return m_it; 331 } 332 get_stride() const333 difference_type get_stride() const 334 { 335 return m_stride; 336 } 337 get_index() const338 difference_type get_index() const 339 { 340 return m_index; 341 } 342 343 private: increment()344 void increment() 345 { 346 m_index += m_stride; 347 } 348 decrement()349 void decrement() 350 { 351 m_index -= m_stride; 352 } 353 advance(difference_type offset)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. update() const364 void update() const 365 { 366 m_it = m_first + m_index; 367 } 368 369 template<class OtherIterator> distance_to(const strided_iterator<OtherIterator,random_access_traversal_tag> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0) const370 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> equal(const strided_iterator<OtherIterator,random_access_traversal_tag> & other,typename enable_if_convertible<OtherIterator,base_iterator>::type * =0) const383 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 dereference() const394 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 > make_begin_strided_iterator(Rng & rng,Difference stride,forward_traversal_tag)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 > make_begin_strided_iterator(const Rng & rng,Difference stride,forward_traversal_tag)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 > make_end_strided_iterator(Rng & rng,Difference stride,forward_traversal_tag)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 > make_end_strided_iterator(const Rng & rng,Difference stride,forward_traversal_tag)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 > make_begin_strided_iterator(Rng & rng,Difference stride,bidirectional_traversal_tag)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 > make_begin_strided_iterator(const Rng & rng,Difference stride,bidirectional_traversal_tag)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 > make_end_strided_iterator(Rng & rng,Difference stride,bidirectional_traversal_tag)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 > make_end_strided_iterator(const Rng & rng,Difference stride,bidirectional_traversal_tag)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 > make_begin_strided_iterator(Rng & rng,Difference stride,random_access_traversal_tag)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 > make_begin_strided_iterator(const Rng & rng,Difference stride,random_access_traversal_tag)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 > make_end_strided_iterator(Rng & rng,Difference stride,random_access_traversal_tag)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 > make_end_strided_iterator(const Rng & rng,Difference stride,random_access_traversal_tag)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> strided_range(Difference stride,Rng & rng)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: strided_holder(Difference value)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> operator |(Rng & rng,const strided_holder<Difference> & stride)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> operator |(const Rng & rng,const strided_holder<Difference> & stride)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> stride(Range & rng,Difference step)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> stride(const Range & rng,Difference step)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