v3/view/cycle.hpp

0001 /// \file cycle.hpp
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-present
0005 //  Copyright Gonzalo Brito Gadeschi 2015
0006 //  Copyright Casey Carter 2015
0007 //
0008 //  Use, modification and distribution is subject to the
0009 //  Boost Software License, Version 1.0. (See accompanying
0010 //  file LICENSE_1_0.txt or copy at
0011 //  http://www.boost.org/LICENSE_1_0.txt)
0012 //
0013 // Project home: https://github.com/ericniebler/range-v3
0014 //
0015
0016 #ifndef RANGES_V3_VIEW_CYCLE_HPP
0017 #define RANGES_V3_VIEW_CYCLE_HPP
0018
0019 #include <type_traits>
0020 #include <utility>
0021
0022 #include <meta/meta.hpp>
0023
0024 #include <range/v3/range_fwd.hpp>
0025
0026 #include <range/v3/iterator/operations.hpp>
0027 #include <range/v3/iterator/unreachable_sentinel.hpp>
0028 #include <range/v3/range/access.hpp>
0029 #include <range/v3/range/concepts.hpp>
0030 #include <range/v3/range/primitives.hpp>
0031 #include <range/v3/range/traits.hpp>
0032 #include <range/v3/utility/box.hpp>
0033 #include <range/v3/utility/get.hpp>
0034 #include <range/v3/utility/optional.hpp>
0035 #include <range/v3/utility/static_const.hpp>
0036 #include <range/v3/view/all.hpp>
0037 #include <range/v3/view/facade.hpp>
0038 #include <range/v3/view/view.hpp>
0039
0040 #include <range/v3/detail/prologue.hpp>
0041
0042 namespace ranges
0043 {
0044     /// \addtogroup group-views
0045     /// @{
0046     template<typename Rng, bool /* = (bool) is_infinite<Rng>() */>
0047     struct RANGES_EMPTY_BASES cycled_view
0048       : view_facade<cycled_view<Rng>, infinite>
0049       , private detail::non_propagating_cache<iterator_t<Rng>, cycled_view<Rng>,
0050                                               !common_range<Rng>>
0051     {
0052     private:
0053         CPP_assert(forward_range<Rng> && !is_infinite<Rng>::value);
0054         friend range_access;
0055         Rng rng_;
0056
0057         using cache_t = detail::non_propagating_cache<iterator_t<Rng>, cycled_view<Rng>,
0058                                                       !common_range<Rng>>;
0059
0060         template<bool IsConst>
0061         struct cursor
0062         {
0063         private:
0064             friend struct cursor<!IsConst>;
0065             template<typename T>
0066             using constify_if = meta::const_if_c<IsConst, T>;
0067             using cycled_view_t = constify_if<cycled_view>;
0068             using CRng = constify_if<Rng>;
0069             using iterator = iterator_t<CRng>;
0070
0071             cycled_view_t * rng_{};
0072             iterator it_{};
0073             std::intmax_t n_ = 0;
0074
0075             iterator get_end_(std::true_type, bool = false) const
0076             {
0077                 return ranges::end(rng_->rng_);
0078             }
0079             template<bool CanBeEmpty = false>
0080             iterator get_end_(std::false_type, meta::bool_<CanBeEmpty> = {}) const
0081             {
0082                 auto & end_ = static_cast<cache_t &>(*rng_);
0083                 RANGES_EXPECT(CanBeEmpty || end_);
0084                 if(CanBeEmpty && !end_)
0085                     end_ = ranges::next(it_, ranges::end(rng_->rng_));
0086                 return *end_;
0087             }
0088             void set_end_(std::true_type) const
0089             {}
0090             void set_end_(std::false_type) const
0091             {
0092                 auto & end_ = static_cast<cache_t &>(*rng_);
0093                 if(!end_)
0094                     end_ = it_;
0095             }
0096
0097         public:
0098             cursor() = default;
0099             cursor(cycled_view_t * rng)
0100               : rng_(rng)
0101               , it_(ranges::begin(rng->rng_))
0102             {}
0103             template(bool Other)(
0104                 requires IsConst AND CPP_NOT(Other)) //
0105             cursor(cursor<Other> that)
0106               : rng_(that.rng_)
0107               , it_(std::move(that.it_))
0108             {}
0109             // clang-format off
0110             auto CPP_auto_fun(read)()(const)
0111             (
0112                 return *it_
0113             )
0114             // clang-format on
0115             CPP_member
0116             auto equal(cursor const & pos) const //
0117                 -> CPP_ret(bool)(
0118                     requires equality_comparable<iterator>)
0119             {
0120                 RANGES_EXPECT(rng_ == pos.rng_);
0121                 return n_ == pos.n_ && it_ == pos.it_;
0122             }
0123             void next()
0124             {
0125                 auto const last = ranges::end(rng_->rng_);
0126                 RANGES_EXPECT(it_ != last);
0127                 if(++it_ == last)
0128                 {
0129                     ++n_;
0130                     this->set_end_(meta::bool_<(bool)common_range<CRng>>{});
0131                     it_ = ranges::begin(rng_->rng_);
0132                 }
0133             }
0134             CPP_member
0135             auto prev() //
0136                 -> CPP_ret(void)(
0137                     requires bidirectional_range<CRng>)
0138             {
0139                 if(it_ == ranges::begin(rng_->rng_))
0140                 {
0141                     RANGES_EXPECT(n_ > 0); // decrementing the begin iterator?!
0142                     --n_;
0143                     it_ = this->get_end_(meta::bool_<(bool)common_range<CRng>>{});
0144                 }
0145                 --it_;
0146             }
0147             template(typename Diff)(
0148                 requires random_access_range<CRng> AND
0149                     detail::integer_like_<Diff>)
0150             void advance(Diff n)
0151             {
0152                 auto const first = ranges::begin(rng_->rng_);
0153                 auto const last = this->get_end_(meta::bool_<(bool)common_range<CRng>>{},
0154                                                  meta::bool_<true>());
0155                 auto const dist = last - first;
0156                 auto const d = it_ - first;
0157                 auto const off = (d + n) % dist;
0158                 n_ += (d + n) / dist;
0159                 RANGES_EXPECT(n_ >= 0);
0160                 using D = range_difference_t<Rng>;
0161                 it_ = first + static_cast<D>(off < 0 ? off + dist : off);
0162             }
0163             CPP_auto_member
0164             auto CPP_fun(distance_to)(cursor const & that)(const //
0165                 requires sized_sentinel_for<iterator, iterator>)
0166             {
0167                 RANGES_EXPECT(that.rng_ == rng_);
0168                 auto const first = ranges::begin(rng_->rng_);
0169                 auto const last = this->get_end_(meta::bool_<(bool)common_range<Rng>>{},
0170                                                  meta::bool_<true>());
0171                 auto const dist = last - first;
0172                 return (that.n_ - n_) * dist + (that.it_ - it_);
0173             }
0174         };
0175
0176         CPP_member
0177         auto begin_cursor() //
0178             -> CPP_ret(cursor<false>)(
0179                 requires (!simple_view<Rng>() || !common_range<Rng const>))
0180         {
0181             return {this};
0182         }
0183         CPP_member
0184         auto begin_cursor() const //
0185             -> CPP_ret(cursor<true>)(
0186                 requires common_range<Rng const>)
0187         {
0188             return {this};
0189         }
0190         unreachable_sentinel_t end_cursor() const
0191         {
0192             return unreachable;
0193         }
0194
0195     public:
0196         cycled_view() = default;
0197         /// \pre <tt>!empty(rng)</tt>
0198         explicit cycled_view(Rng rng)
0199           : rng_(std::move(rng))
0200         {
0201             RANGES_EXPECT(!ranges::empty(rng_));
0202         }
0203     };
0204
0205     template<typename Rng>
0206     struct cycled_view<Rng, true> : identity_adaptor<Rng>
0207     {
0208         CPP_assert(is_infinite<Rng>::value);
0209         using identity_adaptor<Rng>::identity_adaptor;
0210     };
0211
0212 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0213     template<typename Rng>
0214     cycled_view(Rng &&) //
0215         -> cycled_view<views::all_t<Rng>>;
0216 #endif
0217
0218     namespace views
0219     {
0220         /// Returns an infinite range that endlessly repeats the source
0221         /// range.
0222         struct cycle_fn
0223         {
0224             /// \pre <tt>!empty(rng)</tt>
0225             template(typename Rng)(
0226                 requires viewable_range<Rng> AND forward_range<Rng>)
0227             cycled_view<all_t<Rng>> operator()(Rng && rng) const
0228             {
0229                 return cycled_view<all_t<Rng>>{all(static_cast<Rng &&>(rng))};
0230             }
0231         };
0232
0233         /// \relates cycle_fn
0234         /// \ingroup group-views
0235         RANGES_INLINE_VARIABLE(view_closure<cycle_fn>, cycle)
0236     } // namespace views
0237       /// @}
0238 } // namespace ranges
0239
0240 #include <range/v3/detail/epilogue.hpp>
0241
0242 #include <range/v3/detail/satisfy_boost_range.hpp>
0243 RANGES_SATISFY_BOOST_RANGE(::ranges::cycled_view)
0244
0245 #endif