1 /// \file 2 // Range v3 library 3 // 4 // Copyright Eric Niebler 2013-present 5 // 6 // Use, modification and distribution is subject to the 7 // Boost Software License, Version 1.0. (See accompanying 8 // file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 // 11 // Project home: https://github.com/ericniebler/range-v3 12 // 13 14 #ifndef RANGES_V3_VIEW_IOTA_HPP 15 #define RANGES_V3_VIEW_IOTA_HPP 16 17 #include <climits> 18 #include <cstdint> 19 #include <limits> 20 #include <type_traits> 21 22 #include <meta/meta.hpp> 23 24 #include <concepts/concepts.hpp> 25 26 #include <range/v3/range_fwd.hpp> 27 28 #include <range/v3/iterator/default_sentinel.hpp> 29 #include <range/v3/iterator/diffmax_t.hpp> 30 #include <range/v3/utility/static_const.hpp> 31 #include <range/v3/view/delimit.hpp> 32 #include <range/v3/view/facade.hpp> 33 34 #include <range/v3/detail/prologue.hpp> 35 36 RANGES_DIAGNOSTIC_PUSH 37 RANGES_DIAGNOSTIC_IGNORE_UNSIGNED_MATH 38 RANGES_DIAGNOSTIC_IGNORE_TRUNCATION 39 40 namespace ranges 41 { 42 /// \cond 43 namespace detail 44 { 45 template<std::size_t N, typename = void> 46 struct promote_as_signed_ 47 { 48 // This shouldn't cause us to LOSE precision, but maybe it doesn't 49 // net us any either. 50 static_assert(sizeof(std::intmax_t) * CHAR_BIT >= N, 51 "Possible extended integral type?"); 52 using difference_type = diffmax_t; 53 }; 54 55 template<std::size_t N> 56 struct promote_as_signed_<N, enable_if_t<(N < 16)>> 57 { 58 using difference_type = std::int_fast16_t; 59 }; 60 61 template<std::size_t N> 62 struct promote_as_signed_<N, enable_if_t<(N >= 16 && N < 32)>> 63 { 64 using difference_type = std::int_fast32_t; 65 }; 66 67 template<std::size_t N> 68 struct promote_as_signed_<N, enable_if_t<(N >= 32 && N < 64)>> 69 { 70 using difference_type = std::int_fast64_t; 71 }; 72 73 template<typename I> 74 using iota_difference_t = typename meta::conditional_t< 75 std::is_integral<I>::value && sizeof(I) == sizeof(iter_difference_t<I>), 76 promote_as_signed_<sizeof(iter_difference_t<I>) * CHAR_BIT>, 77 with_difference_type_<iter_difference_t<I>>>::difference_type; 78 79 // clang-format off 80 template<typename I> 81 CPP_requires(_decrementable_, 82 requires(I i) // 83 ( 84 --i, 85 i--, 86 concepts::requires_<same_as<I&, decltype(--i)>>, 87 concepts::requires_<same_as<I, decltype(i--)>> 88 )); 89 template<typename I> 90 CPP_concept decrementable_ = 91 incrementable<I> && 92 CPP_requires_ref(detail::_decrementable_, I); 93 94 template<typename I> 95 CPP_requires(_advanceable_, 96 requires(I i, I const j, iota_difference_t<I> const n) // 97 ( 98 j - j, 99 i += n, 100 i -= n, 101 static_cast<I>(j - n), 102 static_cast<I>(j + n), 103 static_cast<I>(n + j), 104 // NOT TO SPEC: 105 // Unsigned integers are advanceable, but subtracting them results in 106 // an unsigned integral, which is not the same as the difference type, 107 // which is signed. 108 concepts::requires_<convertible_to<decltype(j - j), iota_difference_t<I>>>, 109 concepts::requires_<same_as<I&, decltype(i += n)>>, 110 concepts::requires_<same_as<I&, decltype(i -= n)>> //, 111 // concepts::requires_<convertible_to<decltype(i - n), I>>, 112 // concepts::requires_<convertible_to<decltype(i + n), I>>, 113 // concepts::requires_<convertible_to<decltype(n + i), I>> 114 )); 115 template<typename I> 116 CPP_concept advanceable_ = 117 decrementable_<I> && totally_ordered<I> && 118 CPP_requires_ref(detail::_advanceable_, I); 119 // clang-format on 120 121 template(typename I)( 122 /// \pre 123 requires (!unsigned_integral<I>)) // 124 void iota_advance_(I & i, iota_difference_t<I> n) 125 { 126 // TODO: bounds-check this 127 i += n; 128 } 129 130 template(typename Int)( 131 /// \pre 132 requires unsigned_integral<Int>) 133 void iota_advance_(Int & i, iota_difference_t<Int> n) 134 { 135 // TODO: bounds-check this 136 if(n >= 0) 137 i += static_cast<Int>(n); 138 else 139 i -= static_cast<Int>(-n); 140 } 141 142 template(typename I)( 143 /// \pre 144 requires advanceable_<I> AND (!integral<I>)) // 145 iota_difference_t<I> iota_distance_(I const & i, I const & s) 146 { 147 return static_cast<iota_difference_t<I>>(s - i); 148 } 149 150 template(typename Int)( 151 /// \pre 152 requires signed_integral<Int>) iota_distance_(Int i0,Int i1)153 iota_difference_t<Int> iota_distance_(Int i0, Int i1) 154 { 155 // TODO: bounds-check this 156 return static_cast<iota_difference_t<Int>>( 157 static_cast<iota_difference_t<Int>>(i1) - 158 static_cast<iota_difference_t<Int>>(i0)); 159 } 160 161 template(typename Int)( 162 /// \pre 163 requires unsigned_integral<Int>) iota_distance_(Int i0,Int i1)164 iota_difference_t<Int> iota_distance_(Int i0, Int i1) 165 { 166 // TODO: bounds-check this 167 return (i0 > i1) ? static_cast<iota_difference_t<Int>>( 168 -static_cast<iota_difference_t<Int>>(i0 - i1)) 169 : static_cast<iota_difference_t<Int>>(i1 - i0); 170 } 171 } // namespace detail 172 /// \endcond 173 174 /// \addtogroup group-views 175 /// @{ 176 177 /// An iota view in a closed range 178 template<typename From, typename To /* = From */> 179 struct RANGES_EMPTY_BASES closed_iota_view 180 : view_facade<closed_iota_view<From, To>, finite> 181 { 182 private: 183 friend range_access; 184 185 From from_ = From(); 186 RANGES_NO_UNIQUE_ADDRESS To to_ = To(); 187 188 struct cursor 189 { 190 using difference_type = detail::iota_difference_t<From>; 191 192 private: 193 friend range_access; 194 From from_ = From(); 195 RANGES_NO_UNIQUE_ADDRESS To to_ = To(); 196 bool done_ = false; 197 readranges::closed_iota_view::cursor198 From read() const 199 { 200 RANGES_EXPECT(!done_); 201 return from_; 202 } nextranges::closed_iota_view::cursor203 void next() 204 { 205 RANGES_EXPECT(!done_); 206 if(from_ == to_) 207 done_ = true; 208 else 209 ++from_; 210 } equalranges::closed_iota_view::cursor211 bool equal(default_sentinel_t) const 212 { 213 return done_; 214 } 215 CPP_member equalranges::closed_iota_view::cursor216 auto equal(cursor const & that) const // 217 -> CPP_ret(bool)( 218 /// \pre 219 requires equality_comparable<From>) 220 { 221 return that.from_ == from_ && that.done_ == done_; 222 } 223 CPP_member prevranges::closed_iota_view::cursor224 auto prev() // 225 -> CPP_ret(void)( 226 /// \pre 227 requires detail::decrementable_<From>) 228 { 229 if(done_) 230 done_ = false; 231 else 232 --from_; 233 } 234 CPP_member advanceranges::closed_iota_view::cursor235 auto advance(difference_type n) // 236 -> CPP_ret(void)( 237 /// \pre 238 requires detail::advanceable_<From>) 239 { 240 if(n > 0) 241 { 242 RANGES_ENSURE(detail::iota_distance_(from_, to_) >= n - !done_); 243 detail::iota_advance_( 244 from_, 245 n - (done_ = (detail::iota_distance_(from_, to_) <= n - !done_))); 246 } 247 else if(n < 0) 248 detail::iota_advance_(from_, n + std::exchange(done_, false)); 249 } 250 CPP_member distance_toranges::closed_iota_view::cursor251 auto distance_to(cursor const & that) const // 252 -> CPP_ret(difference_type)( 253 /// \pre 254 requires detail::advanceable_<From>) 255 { 256 using D = difference_type; 257 return static_cast<D>(detail::iota_distance_(from_, that.from_)) + 258 ((D)that.done_ - (D)done_); 259 } 260 CPP_member distance_toranges::closed_iota_view::cursor261 auto distance_to(default_sentinel_t) const // 262 -> CPP_ret(difference_type)( 263 /// \pre 264 requires sized_sentinel_for<To, From>) 265 { 266 return difference_type(to_ - from_) + !done_; 267 } 268 269 public: 270 cursor() = default; cursorranges::closed_iota_view::cursor271 constexpr cursor(From from, To to, bool done = false) 272 : from_(std::move(from)) 273 , to_(std::move(to)) 274 , done_(done) 275 {} 276 }; 277 begin_cursorranges::closed_iota_view278 cursor begin_cursor() const 279 { 280 return {from_, to_}; 281 } 282 CPP_member end_cursorranges::closed_iota_view283 auto end_cursor() const // 284 -> CPP_ret(cursor)( 285 /// \pre 286 requires same_as<From, To>) 287 { 288 return {to_, to_, true}; 289 } 290 CPP_member end_cursorranges::closed_iota_view291 auto end_cursor() const // 292 -> CPP_ret(default_sentinel_t)( 293 /// \pre 294 requires (!same_as<From, To>)) 295 { 296 return {}; 297 } 298 check_bounds_ranges::closed_iota_view299 constexpr void check_bounds_(std::true_type) 300 { 301 RANGES_EXPECT(from_ <= to_); 302 } check_bounds_ranges::closed_iota_view303 constexpr void check_bounds_(std::false_type) 304 {} 305 306 public: 307 closed_iota_view() = default; closed_iota_viewranges::closed_iota_view308 constexpr closed_iota_view(meta::id_t<From> from, meta::id_t<To> to) 309 : from_(std::move(from)) 310 , to_(std::move(to)) 311 { 312 check_bounds_(meta::bool_<totally_ordered_with<From, To>>{}); 313 } 314 }; 315 316 template<typename From, typename To> 317 RANGES_INLINE_VAR constexpr bool enable_borrowed_range<closed_iota_view<From, To>> = 318 true; 319 320 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17 321 template(typename From, typename To)( 322 /// \pre 323 requires weakly_incrementable<From> AND semiregular<To> AND 324 (!integral<From> || !integral<To> || 325 std::is_signed<From>::value == std::is_signed<To>::value)) // 326 closed_iota_view(From, To) 327 ->closed_iota_view<From, To>; 328 #endif 329 330 template<typename From, typename To /* = unreachable_sentinel_t*/> 331 struct RANGES_EMPTY_BASES iota_view 332 : view_facade<iota_view<From, To>, 333 same_as<To, unreachable_sentinel_t> 334 ? infinite 335 : std::is_integral<From>::value && std::is_integral<To>::value 336 ? finite 337 : unknown> 338 { 339 private: 340 friend range_access; 341 From from_ = From(); 342 RANGES_NO_UNIQUE_ADDRESS To to_ = To(); 343 344 struct cursor; 345 struct sentinel 346 { 347 private: 348 friend struct cursor; 349 RANGES_NO_UNIQUE_ADDRESS To to_; 350 351 public: 352 sentinel() = default; sentinelranges::iota_view::sentinel353 constexpr explicit sentinel(To to) 354 : to_(std::move(to)) 355 {} 356 }; 357 358 struct cursor 359 { 360 using difference_type = detail::iota_difference_t<From>; 361 362 private: 363 friend range_access; 364 From from_; 365 readranges::iota_view::cursor366 From read() const 367 { 368 return from_; 369 } nextranges::iota_view::cursor370 void next() 371 { 372 ++from_; 373 } equalranges::iota_view::cursor374 bool equal(sentinel const & that) const 375 { 376 return from_ == that.to_; 377 } 378 CPP_member equalranges::iota_view::cursor379 auto equal(cursor const & that) const // 380 -> CPP_ret(bool)( 381 /// \pre 382 requires equality_comparable<From>) 383 { 384 return that.from_ == from_; 385 } 386 CPP_member prevranges::iota_view::cursor387 auto prev() // 388 -> CPP_ret(void)( 389 /// \pre 390 requires detail::decrementable_<From>) 391 { 392 --from_; 393 } 394 CPP_member advanceranges::iota_view::cursor395 auto advance(difference_type n) // 396 -> CPP_ret(void)( 397 /// \pre 398 requires detail::advanceable_<From>) 399 { 400 detail::iota_advance_(from_, n); 401 } 402 // Not to spec: TODO the relational operators will effectively be constrained 403 // with Advanceable, but they should be constrained with totally_ordered. 404 // Reimplement iota_view without view_facade or basic_iterator. 405 CPP_member distance_toranges::iota_view::cursor406 auto distance_to(cursor const & that) const // 407 -> CPP_ret(difference_type)( 408 /// \pre 409 requires detail::advanceable_<From>) 410 { 411 return detail::iota_distance_(from_, that.from_); 412 } 413 // Extension: see https://github.com/ericniebler/stl2/issues/613 414 CPP_member distance_toranges::iota_view::cursor415 auto distance_to(sentinel const & that) const // 416 -> CPP_ret(difference_type)( 417 /// \pre 418 requires sized_sentinel_for<To, From>) 419 { 420 return that.to_ - from_; 421 } 422 423 public: 424 cursor() = default; cursorranges::iota_view::cursor425 constexpr explicit cursor(From from) 426 : from_(std::move(from)) 427 {} 428 }; begin_cursorranges::iota_view429 cursor begin_cursor() const 430 { 431 return cursor{from_}; 432 } 433 CPP_member CPP_funranges::iota_view434 auto CPP_fun(end_cursor)()(const // 435 requires(same_as<To, unreachable_sentinel_t>)) 436 { 437 return unreachable; 438 } 439 CPP_member CPP_funranges::iota_view440 auto CPP_fun(end_cursor)()(const // 441 requires(!same_as<To, unreachable_sentinel_t>)) 442 { 443 return meta::conditional_t<same_as<From, To>, cursor, sentinel>{to_}; 444 } check_bounds_ranges::iota_view445 constexpr void check_bounds_(std::true_type) 446 { 447 RANGES_EXPECT(from_ <= to_); 448 } check_bounds_ranges::iota_view449 constexpr void check_bounds_(std::false_type) 450 {} 451 452 public: 453 #ifdef RANGES_WORKAROUND_MSVC_934264 454 constexpr 455 #endif // RANGES_WORKAROUND_MSVC_934264 456 iota_view() = default; iota_viewranges::iota_view457 constexpr explicit iota_view(From from) 458 : from_(std::move(from)) 459 {} iota_viewranges::iota_view460 constexpr iota_view(meta::id_t<From> from, meta::id_t<To> to) 461 : from_(std::move(from)) 462 , to_(std::move(to)) 463 { 464 check_bounds_(meta::bool_<totally_ordered_with<From, To>>{}); 465 } 466 }; 467 468 template<typename From, typename To> 469 RANGES_INLINE_VAR constexpr bool enable_borrowed_range<iota_view<From, To>> = true; 470 471 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17 472 template(typename From, typename To)( 473 /// \pre 474 requires weakly_incrementable<From> AND semiregular<To> AND 475 (!integral<From> || !integral<To> || 476 std::is_signed<From>::value == std::is_signed<To>::value)) // 477 iota_view(From, To) 478 ->iota_view<From, To>; 479 #endif 480 481 namespace views 482 { 483 struct iota_fn 484 { 485 template(typename From)( 486 /// \pre 487 requires weakly_incrementable<From>) operator ()ranges::views::iota_fn488 iota_view<From> operator()(From value) const 489 { 490 return iota_view<From>{std::move(value)}; 491 } 492 template(typename From, typename To)( 493 /// \pre 494 requires weakly_incrementable<From> AND semiregular<To> AND 495 detail::weakly_equality_comparable_with_<From, To> AND 496 (!integral<From> || !integral<To> || 497 std::is_signed<From>::value == std::is_signed<To>::value)) // operator ()ranges::views::iota_fn498 iota_view<From, To> operator()(From from, To to) const 499 { 500 return {std::move(from), std::move(to)}; 501 } 502 }; 503 504 struct closed_iota_fn 505 { 506 template(typename From, typename To)( 507 /// \pre 508 requires weakly_incrementable<From> AND semiregular<To> AND 509 detail::weakly_equality_comparable_with_<From, To> AND 510 (!integral<From> || !integral<To> || 511 std::is_signed<From>::value == std::is_signed<To>::value)) // operator ()ranges::views::closed_iota_fn512 closed_iota_view<From, To> operator()(From from, To to) const 513 { 514 return {std::move(from), std::move(to)}; 515 } 516 }; 517 518 /// \relates iota_fn 519 /// \ingroup group-views 520 RANGES_INLINE_VARIABLE(iota_fn, iota) 521 522 /// \relates closed_iota_fn 523 /// \ingroup group-views 524 RANGES_INLINE_VARIABLE(closed_iota_fn, closed_iota) 525 526 struct ints_fn : iota_view<int> 527 { 528 ints_fn() = default; 529 530 template(typename Val)( 531 /// \pre 532 requires integral<Val>) 533 RANGES_DEPRECATED( 534 "This potentially confusing API is deprecated. Prefer to " 535 "explicitly specify the upper bound as with ranges::unreachable, as in " 536 "views::ints( n, unreachable )") operator ()ranges::views::ints_fn537 constexpr iota_view<Val> operator()(Val value) const // 538 { 539 return iota_view<Val>{value}; 540 } 541 template(typename Val)( 542 /// \pre 543 requires integral<Val>) operator ()ranges::views::ints_fn544 constexpr iota_view<Val> operator()(Val value, unreachable_sentinel_t) const 545 { 546 return iota_view<Val>{value}; 547 } 548 template(typename Val)( 549 /// \pre 550 requires integral<Val>) operator ()ranges::views::ints_fn551 constexpr iota_view<Val, Val> operator()(Val from, Val to) const 552 { 553 return {from, to}; 554 } 555 }; 556 557 /// \relates ints_fn 558 /// \ingroup group-views 559 RANGES_INLINE_VARIABLE(ints_fn, ints) 560 } // namespace views 561 562 namespace cpp20 563 { 564 namespace views 565 { 566 using ranges::views::iota; 567 } 568 } // namespace cpp20 569 /// @} 570 } // namespace ranges 571 572 #include <range/v3/detail/satisfy_boost_range.hpp> 573 RANGES_SATISFY_BOOST_RANGE(::ranges::closed_iota_view) 574 RANGES_SATISFY_BOOST_RANGE(::ranges::iota_view) 575 576 RANGES_DIAGNOSTIC_POP 577 578 #include <range/v3/detail/epilogue.hpp> 579 580 #endif 581