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