v3/view/iota.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013
0014 #ifndef RANGES_V3_VIEW_IOTA_HPP
0015 #define RANGES_V3_VIEW_IOTA_HPP
0016
0017 #include <climits>
0018 #include <cstdint>
0019 #include <limits>
0020 #include <type_traits>
0021
0022 #include <meta/meta.hpp>
0023
0024 #include <concepts/concepts.hpp>
0025
0026 #include <range/v3/range_fwd.hpp>
0027
0028 #include <range/v3/iterator/default_sentinel.hpp>
0029 #include <range/v3/iterator/diffmax_t.hpp>
0030 #include <range/v3/utility/static_const.hpp>
0031 #include <range/v3/view/delimit.hpp>
0032 #include <range/v3/view/facade.hpp>
0033
0034 #include <range/v3/detail/prologue.hpp>
0035
0036 RANGES_DIAGNOSTIC_PUSH
0037 RANGES_DIAGNOSTIC_IGNORE_UNSIGNED_MATH
0038 RANGES_DIAGNOSTIC_IGNORE_TRUNCATION
0039
0040 namespace ranges
0041 {
0042     /// \cond
0043     namespace detail
0044     {
0045         template<std::size_t N, typename = void>
0046         struct promote_as_signed_
0047         {
0048             // This shouldn't cause us to LOSE precision, but maybe it doesn't
0049             // net us any either.
0050             static_assert(sizeof(std::intmax_t) * CHAR_BIT >= N,
0051                           "Possible extended integral type?");
0052             using difference_type = diffmax_t;
0053         };
0054
0055         template<std::size_t N>
0056         struct promote_as_signed_<N, enable_if_t<(N < 16)>>
0057         {
0058             using difference_type = std::int_fast16_t;
0059         };
0060
0061         template<std::size_t N>
0062         struct promote_as_signed_<N, enable_if_t<(N >= 16 && N < 32)>>
0063         {
0064             using difference_type = std::int_fast32_t;
0065         };
0066
0067         template<std::size_t N>
0068         struct promote_as_signed_<N, enable_if_t<(N >= 32 && N < 64)>>
0069         {
0070             using difference_type = std::int_fast64_t;
0071         };
0072
0073         template<typename I>
0074         using iota_difference_t = typename meta::conditional_t<
0075             std::is_integral<I>::value && sizeof(I) == sizeof(iter_difference_t<I>),
0076             promote_as_signed_<sizeof(iter_difference_t<I>) * CHAR_BIT>,
0077             with_difference_type_<iter_difference_t<I>>>::difference_type;
0078
0079         // clang-format off
0080         /// \concept _decrementable_
0081         /// \brief The \c _decrementable_ concept
0082         template<typename I>
0083         CPP_requires(_decrementable_,
0084             requires(I i) //
0085             (
0086                 --i,
0087                 i--,
0088                 concepts::requires_<same_as<I&, decltype(--i)>>,
0089                 concepts::requires_<same_as<I, decltype(i--)>>
0090             ));
0091         /// \concept decrementable_
0092         /// \brief The \c decrementable_ concept
0093         template<typename I>
0094         CPP_concept decrementable_ =
0095             incrementable<I> &&
0096             CPP_requires_ref(detail::_decrementable_, I);
0097
0098         /// \concept _advanceable_
0099         /// \brief The \c _advanceable_ concept
0100         template<typename I>
0101         CPP_requires(_advanceable_,
0102             requires(I i, I const j, iota_difference_t<I> const n) //
0103             (
0104                 j - j,
0105                 i += n,
0106                 i -= n,
0107                 static_cast<I>(j - n),
0108                 static_cast<I>(j + n),
0109                 static_cast<I>(n + j),
0110                 // NOT TO SPEC:
0111                 // Unsigned integers are advanceable, but subtracting them results in
0112                 // an unsigned integral, which is not the same as the difference type,
0113                 // which is signed.
0114                 concepts::requires_<convertible_to<decltype(j - j), iota_difference_t<I>>>,
0115                 concepts::requires_<same_as<I&, decltype(i += n)>>,
0116                 concepts::requires_<same_as<I&, decltype(i -= n)>> //,
0117                 // concepts::requires_<convertible_to<decltype(i - n), I>>,
0118                 // concepts::requires_<convertible_to<decltype(i + n), I>>,
0119                 // concepts::requires_<convertible_to<decltype(n + i), I>>
0120             ));
0121         /// \concept advanceable_
0122         /// \brief The \c advanceable_ concept
0123         template<typename I>
0124         CPP_concept advanceable_ =
0125             decrementable_<I> && totally_ordered<I> &&
0126             CPP_requires_ref(detail::_advanceable_, I);
0127         // clang-format on
0128
0129         template(typename I)(
0130             requires (!unsigned_integral<I>)) //
0131         void iota_advance_(I & i, iota_difference_t<I> n)
0132         {
0133             // TODO: bounds-check this
0134             i += n;
0135         }
0136
0137         template(typename Int)(
0138             requires unsigned_integral<Int>)
0139         void iota_advance_(Int & i, iota_difference_t<Int> n)
0140         {
0141             // TODO: bounds-check this
0142             if(n >= 0)
0143                 i += static_cast<Int>(n);
0144             else
0145                 i -= static_cast<Int>(-n);
0146         }
0147
0148         template(typename I)(
0149             requires advanceable_<I> AND (!integral<I>)) //
0150         iota_difference_t<I> iota_distance_(I const & i, I const & s)
0151         {
0152             return static_cast<iota_difference_t<I>>(s - i);
0153         }
0154
0155         template(typename Int)(
0156             requires signed_integral<Int>)
0157         iota_difference_t<Int> iota_distance_(Int i0, Int i1)
0158         {
0159             // TODO: bounds-check this
0160             return static_cast<iota_difference_t<Int>>(
0161                 static_cast<iota_difference_t<Int>>(i1) -
0162                 static_cast<iota_difference_t<Int>>(i0));
0163         }
0164
0165         template(typename Int)(
0166             requires unsigned_integral<Int>)
0167         iota_difference_t<Int> iota_distance_(Int i0, Int i1)
0168         {
0169             // TODO: bounds-check this
0170             return (i0 > i1) ? static_cast<iota_difference_t<Int>>(
0171                                    -static_cast<iota_difference_t<Int>>(i0 - i1))
0172                              : static_cast<iota_difference_t<Int>>(i1 - i0);
0173         }
0174     } // namespace detail
0175     /// \endcond
0176
0177     /// \addtogroup group-views
0178     /// @{
0179
0180     /// An iota view in a closed range
0181     template<typename From, typename To /* = From */>
0182     struct RANGES_EMPTY_BASES closed_iota_view
0183       : view_facade<closed_iota_view<From, To>, finite>
0184     {
0185     private:
0186         friend range_access;
0187
0188         From from_ = From();
0189         RANGES_NO_UNIQUE_ADDRESS To to_ = To();
0190
0191         struct cursor
0192         {
0193             using difference_type = detail::iota_difference_t<From>;
0194
0195         private:
0196             friend range_access;
0197             From from_ = From();
0198             RANGES_NO_UNIQUE_ADDRESS To to_ = To();
0199             bool done_ = false;
0200
0201             From read() const
0202             {
0203                 RANGES_EXPECT(!done_);
0204                 return from_;
0205             }
0206             void next()
0207             {
0208                 RANGES_EXPECT(!done_);
0209                 if(from_ == to_)
0210                     done_ = true;
0211                 else
0212                     ++from_;
0213             }
0214             bool equal(default_sentinel_t) const
0215             {
0216                 return done_;
0217             }
0218             CPP_member
0219             auto equal(cursor const & that) const //
0220                 -> CPP_ret(bool)(
0221                     requires equality_comparable<From>)
0222             {
0223                 return that.from_ == from_ && that.done_ == done_;
0224             }
0225             CPP_member
0226             auto prev() //
0227                 -> CPP_ret(void)(
0228                     requires detail::decrementable_<From>)
0229             {
0230                 if(done_)
0231                     done_ = false;
0232                 else
0233                     --from_;
0234             }
0235             CPP_member
0236             auto advance(difference_type n) //
0237                 -> CPP_ret(void)(
0238                     requires detail::advanceable_<From>)
0239             {
0240                 if(n > 0)
0241                 {
0242                     RANGES_ENSURE(detail::iota_distance_(from_, to_) >= n - !done_);
0243                     detail::iota_advance_(
0244                         from_,
0245                         n - (done_ = (detail::iota_distance_(from_, to_) <= n - !done_)));
0246                 }
0247                 else if(n < 0)
0248                     detail::iota_advance_(from_, n + std::exchange(done_, false));
0249             }
0250             CPP_member
0251             auto distance_to(cursor const & that) const //
0252                 -> CPP_ret(difference_type)(
0253                     requires detail::advanceable_<From>)
0254             {
0255                 using D = difference_type;
0256                 return static_cast<D>(detail::iota_distance_(from_, that.from_)) +
0257                        ((D)that.done_ - (D)done_);
0258             }
0259             CPP_member
0260             auto distance_to(default_sentinel_t) const //
0261                 -> CPP_ret(difference_type)(
0262                     requires sized_sentinel_for<To, From>)
0263             {
0264                 return difference_type(to_ - from_) + !done_;
0265             }
0266
0267         public:
0268             cursor() = default;
0269             constexpr cursor(From from, To to, bool done = false)
0270               : from_(std::move(from))
0271               , to_(std::move(to))
0272               , done_(done)
0273             {}
0274         };
0275
0276         cursor begin_cursor() const
0277         {
0278             return {from_, to_};
0279         }
0280         CPP_member
0281         auto end_cursor() const //
0282             -> CPP_ret(cursor)(
0283                 requires same_as<From, To>)
0284         {
0285             return {to_, to_, true};
0286         }
0287         CPP_member
0288         auto end_cursor() const //
0289             -> CPP_ret(default_sentinel_t)(
0290                 requires (!same_as<From, To>))
0291         {
0292             return {};
0293         }
0294
0295         constexpr void check_bounds_(std::true_type)
0296         {
0297             RANGES_EXPECT(from_ <= to_);
0298         }
0299         constexpr void check_bounds_(std::false_type)
0300         {}
0301
0302     public:
0303         closed_iota_view() = default;
0304         constexpr closed_iota_view(meta::id_t<From> from, meta::id_t<To> to)
0305           : from_(std::move(from))
0306           , to_(std::move(to))
0307         {
0308             check_bounds_(meta::bool_<totally_ordered_with<From, To>>{});
0309         }
0310     };
0311
0312     template<typename From, typename To>
0313     RANGES_INLINE_VAR constexpr bool enable_borrowed_range<closed_iota_view<From, To>> =
0314         true;
0315
0316 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0317     template(typename From, typename To)(
0318         requires weakly_incrementable<From> AND semiregular<To> AND
0319         (!integral<From> || !integral<To> ||
0320          std::is_signed<From>::value == std::is_signed<To>::value)) //
0321         closed_iota_view(From, To)
0322             ->closed_iota_view<From, To>;
0323 #endif
0324
0325     template<typename From, typename To /* = unreachable_sentinel_t*/>
0326     struct RANGES_EMPTY_BASES iota_view
0327       : view_facade<iota_view<From, To>,
0328                     same_as<To, unreachable_sentinel_t>
0329                         ? infinite
0330                         : std::is_integral<From>::value && std::is_integral<To>::value
0331                               ? finite
0332                               : unknown>
0333     {
0334     private:
0335         friend range_access;
0336         From from_ = From();
0337         RANGES_NO_UNIQUE_ADDRESS To to_ = To();
0338
0339         struct cursor;
0340         struct sentinel
0341         {
0342         private:
0343             friend struct cursor;
0344             RANGES_NO_UNIQUE_ADDRESS To to_;
0345
0346         public:
0347             sentinel() = default;
0348             constexpr explicit sentinel(To to)
0349               : to_(std::move(to))
0350             {}
0351         };
0352
0353         struct cursor
0354         {
0355             using difference_type = detail::iota_difference_t<From>;
0356
0357         private:
0358             friend range_access;
0359             From from_;
0360
0361             From read() const
0362             {
0363                 return from_;
0364             }
0365             void next()
0366             {
0367                 ++from_;
0368             }
0369             bool equal(sentinel const & that) const
0370             {
0371                 return from_ == that.to_;
0372             }
0373             CPP_member
0374             auto equal(cursor const & that) const //
0375                 -> CPP_ret(bool)(
0376                     requires equality_comparable<From>)
0377             {
0378                 return that.from_ == from_;
0379             }
0380             CPP_member
0381             auto prev() //
0382                 -> CPP_ret(void)(
0383                     requires detail::decrementable_<From>)
0384             {
0385                 --from_;
0386             }
0387             CPP_member
0388             auto advance(difference_type n) //
0389                 -> CPP_ret(void)(
0390                     requires detail::advanceable_<From>)
0391             {
0392                 detail::iota_advance_(from_, n);
0393             }
0394             // Not to spec: TODO the relational operators will effectively be constrained
0395             // with Advanceable, but they should be constrained with totally_ordered.
0396             // Reimplement iota_view without view_facade or basic_iterator.
0397             CPP_member
0398             auto distance_to(cursor const & that) const //
0399                 -> CPP_ret(difference_type)(
0400                     requires detail::advanceable_<From>)
0401             {
0402                 return detail::iota_distance_(from_, that.from_);
0403             }
0404             // Extension: see https://github.com/ericniebler/stl2/issues/613
0405             CPP_member
0406             auto distance_to(sentinel const & that) const //
0407                 -> CPP_ret(difference_type)(
0408                     requires sized_sentinel_for<To, From>)
0409             {
0410                 return that.to_ - from_;
0411             }
0412
0413         public:
0414             cursor() = default;
0415             constexpr explicit cursor(From from)
0416               : from_(std::move(from))
0417             {}
0418         };
0419         cursor begin_cursor() const
0420         {
0421             return cursor{from_};
0422         }
0423         CPP_auto_member
0424         auto CPP_fun(end_cursor)()(const //
0425             requires(same_as<To, unreachable_sentinel_t>))
0426         {
0427             return unreachable;
0428         }
0429         CPP_auto_member
0430         auto CPP_fun(end_cursor)()(const //
0431             requires(!same_as<To, unreachable_sentinel_t>))
0432         {
0433             return meta::conditional_t<same_as<From, To>, cursor, sentinel>{to_};
0434         }
0435         constexpr void check_bounds_(std::true_type)
0436         {
0437             RANGES_EXPECT(from_ <= to_);
0438         }
0439         constexpr void check_bounds_(std::false_type)
0440         {}
0441
0442     public:
0443 #ifdef RANGES_WORKAROUND_MSVC_934264
0444         constexpr
0445 #endif // RANGES_WORKAROUND_MSVC_934264
0446             iota_view() = default;
0447         constexpr explicit iota_view(From from)
0448           : from_(std::move(from))
0449         {}
0450         constexpr iota_view(meta::id_t<From> from, meta::id_t<To> to)
0451           : from_(std::move(from))
0452           , to_(std::move(to))
0453         {
0454             check_bounds_(meta::bool_<totally_ordered_with<From, To>>{});
0455         }
0456     };
0457
0458     template<typename From, typename To>
0459     RANGES_INLINE_VAR constexpr bool enable_borrowed_range<iota_view<From, To>> = true;
0460
0461 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0462     template(typename From, typename To)(
0463         requires weakly_incrementable<From> AND semiregular<To> AND
0464         (!integral<From> || !integral<To> ||
0465          std::is_signed<From>::value == std::is_signed<To>::value)) //
0466         iota_view(From, To)
0467             ->iota_view<From, To>;
0468 #endif
0469
0470     namespace views
0471     {
0472         struct iota_fn
0473         {
0474             template(typename From)(
0475                 requires weakly_incrementable<From>)
0476             iota_view<From> operator()(From value) const
0477             {
0478                 return iota_view<From>{std::move(value)};
0479             }
0480             template(typename From, typename To)(
0481                 requires weakly_incrementable<From> AND semiregular<To> AND
0482                     detail::weakly_equality_comparable_with_<From, To> AND
0483                 (!integral<From> || !integral<To> ||
0484                  std::is_signed<From>::value == std::is_signed<To>::value)) //
0485             iota_view<From, To> operator()(From from, To to) const
0486             {
0487                 return {std::move(from), std::move(to)};
0488             }
0489         };
0490
0491         struct closed_iota_fn
0492         {
0493             template(typename From, typename To)(
0494                 requires weakly_incrementable<From> AND semiregular<To> AND
0495                         detail::weakly_equality_comparable_with_<From, To> AND
0496                     (!integral<From> || !integral<To> ||
0497                      std::is_signed<From>::value == std::is_signed<To>::value)) //
0498             closed_iota_view<From, To> operator()(From from, To to) const
0499             {
0500                 return {std::move(from), std::move(to)};
0501             }
0502         };
0503
0504         /// \relates iota_fn
0505         /// \ingroup group-views
0506         RANGES_INLINE_VARIABLE(iota_fn, iota)
0507
0508         /// \relates closed_iota_fn
0509         /// \ingroup group-views
0510         RANGES_INLINE_VARIABLE(closed_iota_fn, closed_iota)
0511
0512         /// # ranges::views::ints
0513         /// The ints view returns a range of monotonically increasing ints.
0514         ///
0515         /// ## Example
0516         /// \snippet example/view/ints.cpp ints example
0517         ///
0518         /// ### Output
0519         /// \include example/view/ints_golden.txt
0520         ///
0521         /// ## Syntax
0522         /// ```cpp
0523         /// auto output_range = ranges::views::ints(lower_bound, upper_bound);
0524         /// ```
0525         ///
0526         /// ## Parameters
0527         /// <pre><b>lower_bound</b></pre>
0528         ///   - Optional lower bound
0529         ///
0530         /// <pre><b>upper_bound</b></pre>
0531         ///   - Exclusive upper bound
0532         ///   - Required when `lower_bound` is specified
0533         ///     - To create an infinite range with a `lower_bound`, use
0534         ///     `ranges::unreachable` as the `upper_bound`
0535         ///
0536         /// <pre><b>output_range</b></pre>
0537         ///   - Range of monotonically increasing ints
0538         ///   - When an `upper_bound` is not specified, the range is quasi-infinite
0539         ///
0540         struct ints_fn : iota_view<int>
0541         {
0542             ints_fn() = default;
0543
0544             template(typename Val)(
0545                 requires integral<Val>)
0546             RANGES_DEPRECATED(
0547                 "This potentially confusing API is deprecated. Prefer to "
0548                 "explicitly specify the upper bound as with ranges::unreachable, as in "
0549                 "views::ints( n, unreachable )")
0550             constexpr iota_view<Val> operator()(Val value) const //
0551             {
0552                 return iota_view<Val>{value};
0553             }
0554             template(typename Val)(
0555                 requires integral<Val>)
0556             constexpr iota_view<Val> operator()(Val value, unreachable_sentinel_t) const
0557             {
0558                 return iota_view<Val>{value};
0559             }
0560             template(typename Val)(
0561                 requires integral<Val>)
0562             constexpr iota_view<Val, Val> operator()(Val from, Val to) const
0563             {
0564                 return {from, to};
0565             }
0566         };
0567
0568         /// \relates ints_fn
0569         /// \ingroup group-views
0570         RANGES_INLINE_VARIABLE(ints_fn, ints)
0571     } // namespace views
0572
0573     namespace cpp20
0574     {
0575         namespace views
0576         {
0577             using ranges::views::iota;
0578         }
0579     } // namespace cpp20
0580     /// @}
0581 } // namespace ranges
0582
0583 #include <range/v3/detail/satisfy_boost_range.hpp>
0584 RANGES_SATISFY_BOOST_RANGE(::ranges::closed_iota_view)
0585 RANGES_SATISFY_BOOST_RANGE(::ranges::iota_view)
0586
0587 RANGES_DIAGNOSTIC_POP
0588
0589 #include <range/v3/detail/epilogue.hpp>
0590
0591 #endif