1 /// \file cycle.hpp
2 // Range v3 library
3 //
4 //  Copyright Eric Niebler 2013-present
5 //  Copyright Gonzalo Brito Gadeschi 2015
6 //  Copyright Casey Carter 2015
7 //
8 //  Use, modification and distribution is subject to the
9 //  Boost Software License, Version 1.0. (See accompanying
10 //  file LICENSE_1_0.txt or copy at
11 //  http://www.boost.org/LICENSE_1_0.txt)
12 //
13 // Project home: https://github.com/ericniebler/range-v3
14 //
15 
16 #ifndef RANGES_V3_VIEW_CYCLE_HPP
17 #define RANGES_V3_VIEW_CYCLE_HPP
18 
19 #include <type_traits>
20 #include <utility>
21 
22 #include <meta/meta.hpp>
23 
24 #include <range/v3/range_fwd.hpp>
25 
26 #include <range/v3/iterator/operations.hpp>
27 #include <range/v3/iterator/unreachable_sentinel.hpp>
28 #include <range/v3/range/access.hpp>
29 #include <range/v3/range/concepts.hpp>
30 #include <range/v3/range/primitives.hpp>
31 #include <range/v3/range/traits.hpp>
32 #include <range/v3/utility/box.hpp>
33 #include <range/v3/utility/get.hpp>
34 #include <range/v3/utility/optional.hpp>
35 #include <range/v3/utility/static_const.hpp>
36 #include <range/v3/view/all.hpp>
37 #include <range/v3/view/facade.hpp>
38 #include <range/v3/view/view.hpp>
39 
40 #include <range/v3/detail/prologue.hpp>
41 
42 namespace ranges
43 {
44     /// \addtogroup group-views
45     /// @{
46     template<typename Rng, bool /* = (bool) is_infinite<Rng>() */>
47     struct RANGES_EMPTY_BASES cycled_view
48       : view_facade<cycled_view<Rng>, infinite>
49       , private detail::non_propagating_cache<iterator_t<Rng>, cycled_view<Rng>,
50                                               !common_range<Rng>>
51     {
52     private:
53         CPP_assert(forward_range<Rng> && !is_infinite<Rng>::value);
54         friend range_access;
55         Rng rng_;
56 
57         using cache_t = detail::non_propagating_cache<iterator_t<Rng>, cycled_view<Rng>,
58                                                       !common_range<Rng>>;
59 
60         template<bool IsConst>
61         struct cursor
62         {
63         private:
64             friend struct cursor<!IsConst>;
65             template<typename T>
66             using constify_if = meta::const_if_c<IsConst, T>;
67             using cycled_view_t = constify_if<cycled_view>;
68             using CRng = constify_if<Rng>;
69             using iterator = iterator_t<CRng>;
70 
71             cycled_view_t * rng_{};
72             iterator it_{};
73             std::intmax_t n_ = 0;
74 
get_end_ranges::cycled_view::cursor75             iterator get_end_(std::true_type, bool = false) const
76             {
77                 return ranges::end(rng_->rng_);
78             }
79             template<bool CanBeEmpty = false>
get_end_ranges::cycled_view::cursor80             iterator get_end_(std::false_type, meta::bool_<CanBeEmpty> = {}) const
81             {
82                 auto & end_ = static_cast<cache_t &>(*rng_);
83                 RANGES_EXPECT(CanBeEmpty || end_);
84                 if(CanBeEmpty && !end_)
85                     end_ = ranges::next(it_, ranges::end(rng_->rng_));
86                 return *end_;
87             }
set_end_ranges::cycled_view::cursor88             void set_end_(std::true_type) const
89             {}
set_end_ranges::cycled_view::cursor90             void set_end_(std::false_type) const
91             {
92                 auto & end_ = static_cast<cache_t &>(*rng_);
93                 if(!end_)
94                     end_ = it_;
95             }
96 
97         public:
98             cursor() = default;
cursorranges::cycled_view::cursor99             cursor(cycled_view_t * rng)
100               : rng_(rng)
101               , it_(ranges::begin(rng->rng_))
102             {}
103             template(bool Other)(
104                 /// \pre
105                 requires IsConst AND CPP_NOT(Other)) //
106             cursor(cursor<Other> that)
107               : rng_(that.rng_)
108               , it_(std::move(that.it_))
109             {}
110             // clang-format off
111             auto CPP_auto_fun(read)()(const)
112             (
113                 return *it_
114             )
115             // clang-format on
116             CPP_member
117             auto equal(cursor const & pos) const //
118                 -> CPP_ret(bool)(
119                     /// \pre
120                     requires equality_comparable<iterator>)
121             {
122                 RANGES_EXPECT(rng_ == pos.rng_);
123                 return n_ == pos.n_ && it_ == pos.it_;
124             }
125             void next()
126             {
127                 auto const last = ranges::end(rng_->rng_);
128                 RANGES_EXPECT(it_ != last);
129                 if(++it_ == last)
130                 {
131                     ++n_;
132                     this->set_end_(meta::bool_<(bool)common_range<CRng>>{});
133                     it_ = ranges::begin(rng_->rng_);
134                 }
135             }
136             CPP_member
137             auto prev() //
138                 -> CPP_ret(void)(
139                     /// \pre
140                     requires bidirectional_range<CRng>)
141             {
142                 if(it_ == ranges::begin(rng_->rng_))
143                 {
144                     RANGES_EXPECT(n_ > 0); // decrementing the begin iterator?!
145                     --n_;
146                     it_ = this->get_end_(meta::bool_<(bool)common_range<CRng>>{});
147                 }
148                 --it_;
149             }
150             template(typename Diff)(
151                 /// \pre
152                 requires random_access_range<CRng> AND
153                     detail::integer_like_<Diff>) void advance(Diff n)
154             {
155                 auto const first = ranges::begin(rng_->rng_);
156                 auto const last = this->get_end_(meta::bool_<(bool)common_range<CRng>>{},
157                                                  meta::bool_<true>());
158                 auto const dist = last - first;
159                 auto const d = it_ - first;
160                 auto const off = (d + n) % dist;
161                 n_ += (d + n) / dist;
162                 RANGES_EXPECT(n_ >= 0);
163                 using D = range_difference_t<Rng>;
164                 it_ = first + static_cast<D>(off < 0 ? off + dist : off);
165             }
166             CPP_member
167             auto CPP_fun(distance_to)(cursor const & that)(
168                 const requires sized_sentinel_for<iterator, iterator>)
169             {
170                 RANGES_EXPECT(that.rng_ == rng_);
171                 auto const first = ranges::begin(rng_->rng_);
172                 auto const last = this->get_end_(meta::bool_<(bool)common_range<Rng>>{},
173                                                  meta::bool_<true>());
174                 auto const dist = last - first;
175                 return (that.n_ - n_) * dist + (that.it_ - it_);
176             }
177         };
178 
179         CPP_member
180         auto begin_cursor() //
181             -> CPP_ret(cursor<false>)(
182                 /// \pre
183                 requires (!simple_view<Rng>() || !common_range<Rng const>))
184         {
185             return {this};
186         }
187         CPP_member
188         auto begin_cursor() const //
189             -> CPP_ret(cursor<true>)(
190                 /// \pre
191                 requires common_range<Rng const>)
192         {
193             return {this};
194         }
195         unreachable_sentinel_t end_cursor() const
196         {
197             return unreachable;
198         }
199 
200     public:
201         cycled_view() = default;
202         /// \pre <tt>!empty(rng)</tt>
203         explicit cycled_view(Rng rng)
204           : rng_(std::move(rng))
205         {
206             RANGES_EXPECT(!ranges::empty(rng_));
207         }
208     };
209 
210     template<typename Rng>
211     struct cycled_view<Rng, true> : identity_adaptor<Rng>
212     {
213         CPP_assert(is_infinite<Rng>::value);
214         using identity_adaptor<Rng>::identity_adaptor;
215     };
216 
217 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
218     template<typename Rng>
219     cycled_view(Rng &&) //
220         -> cycled_view<views::all_t<Rng>>;
221 #endif
222 
223     namespace views
224     {
225         /// Returns an infinite range that endlessly repeats the source
226         /// range.
227         struct cycle_fn
228         {
229             /// \pre <tt>!empty(rng)</tt>
230             template(typename Rng)(
231                 /// \pre
232                 requires viewable_range<Rng> AND forward_range<Rng>)
233             cycled_view<all_t<Rng>> operator()(Rng && rng) const
234             {
235                 return cycled_view<all_t<Rng>>{all(static_cast<Rng &&>(rng))};
236             }
237         };
238 
239         /// \relates cycle_fn
240         /// \ingroup group-views
241         RANGES_INLINE_VARIABLE(view_closure<cycle_fn>, cycle)
242     } // namespace views
243       /// @}
244 } // namespace ranges
245 
246 #include <range/v3/detail/epilogue.hpp>
247 
248 #include <range/v3/detail/satisfy_boost_range.hpp>
249 RANGES_SATISFY_BOOST_RANGE(::ranges::cycled_view)
250 
251 #endif
252