Horizon
Loading...
Searching...
No Matches
stride.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2013-present
5// Copyright Casey Carter 2017
6//
7// Use, modification and distribution is subject to the
8// Boost Software License, Version 1.0. (See accompanying
9// file LICENSE_1_0.txt or copy at
10// http://www.boost.org/LICENSE_1_0.txt)
11//
12// Project home: https://github.com/ericniebler/range-v3
13//
14
15#ifndef RANGES_V3_VIEW_STRIDE_HPP
16#define RANGES_V3_VIEW_STRIDE_HPP
17
18#include <type_traits>
19#include <utility>
20
21#include <meta/meta.hpp>
22
24
31#include <range/v3/utility/static_const.hpp>
33#include <range/v3/view/all.hpp>
35
36#include <range/v3/detail/prologue.hpp>
37
38namespace ranges
39{
41 template<typename Rng>
42 struct stride_view;
43
44 namespace detail
45 {
46 template<typename Rng>
47 using stride_view_adaptor =
48 view_adaptor<stride_view<Rng>, Rng,
49 is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>;
50
51 // Bidirectional stride views need to remember the distance between
52 // the penultimate iterator and the last iterator - which may be less
53 // than the stride - so that decrementing an last iterator properly
54 // produces the penultimate iterator. stride_view_base specializes on
55 // that distinction so that only Bidirectional stride views have the
56 // data member "offset_".
57 template<typename Rng, bool BidiRange>
58 struct stride_view_base_;
59 template<typename Rng>
60 using stride_view_base = stride_view_base_<Rng, (bool)bidirectional_range<Rng>>;
61
62 template<typename Rng, bool /*= bidirectional_range<Rng>*/>
63 struct stride_view_base_ : stride_view_adaptor<Rng>
64 {
65 stride_view_base_() = default;
66 constexpr stride_view_base_(Rng && rng, range_difference_t<Rng> const stride)
67 : stride_view_adaptor<Rng>{std::move(rng)}
68 , stride_{(RANGES_EXPECT(0 < stride), stride)}
69 , offset_{calc_offset(meta::bool_<sized_range<Rng>>{})}
70 {}
71
72 protected:
73 constexpr void set_offset(range_difference_t<Rng> const delta) noexcept
74 {
75 RANGES_EXPECT(0 <= delta && delta < stride_);
76 if(0 > offset_)
77 offset_ = delta;
78 else
79 RANGES_EXPECT(offset_ == delta);
80 }
81 constexpr void set_offset(range_difference_t<Rng> const) const noexcept
82 {}
83 constexpr range_difference_t<Rng> get_offset(bool check = true) const noexcept
84 {
85 RANGES_EXPECT(!check || 0 <= offset_);
86 return offset_;
87 }
88
89 range_difference_t<Rng> stride_;
90 range_difference_t<Rng> offset_ = -1;
91
92 private:
93 constexpr range_difference_t<Rng> calc_offset(std::true_type)
94 {
95 if(auto const rem = ranges::distance(this->base()) % stride_)
96 return stride_ - rem;
97 else
98 return 0;
99 }
100 constexpr range_difference_t<Rng> calc_offset(std::false_type) const noexcept
101 {
102 return -1;
103 }
104 };
105
106 template<typename Rng>
107 struct stride_view_base_<Rng, false> : stride_view_adaptor<Rng>
108 {
109 stride_view_base_() = default;
110 constexpr stride_view_base_(Rng && rng, range_difference_t<Rng> const stride)
111 : stride_view_adaptor<Rng>{std::move(rng)}
112 , stride_{(RANGES_EXPECT(0 < stride), stride)}
113 {}
114
115 protected:
116 constexpr void set_offset(range_difference_t<Rng> const) const noexcept
117 {}
118 constexpr range_difference_t<Rng> get_offset(bool = true) const noexcept
119 {
120 return 0;
121 }
122
123 range_difference_t<Rng> stride_;
124 };
125 } // namespace detail
127
130 template<typename Rng>
131 struct stride_view : detail::stride_view_base<Rng>
132 {
133 private:
134 friend range_access;
135
136 // stride_view const models Range if Rng const models Range, and
137 // either (1) Rng is sized, so we can pre-calculate offset_, or (2)
138 // Rng is !Bidirectional, so it does not need offset_.
139 static constexpr bool const_iterable() noexcept
140 {
141 return range<Rng const> &&
143 }
144
145 // If the underlying range doesn't model common_range, then we can't
146 // decrement the last and there's no reason to adapt the sentinel. Strictly
147 // speaking, we don't have to adapt the last iterator of input and forward
148 // ranges, but in the interests of making the resulting stride view model
149 // common_range, adapt it anyway.
150 template<bool Const>
151 static constexpr bool can_bound() noexcept
152 {
153 using CRng = meta::const_if_c<Const, Rng>;
154 return common_range<CRng> &&
156 }
157
158 template<bool Const>
159 struct adaptor : adaptor_base
160 {
161 private:
162 friend struct adaptor<!Const>;
163 using CRng = meta::const_if_c<Const, Rng>;
164 using stride_view_t = meta::const_if_c<Const, stride_view>;
165 stride_view_t * rng_;
166
167 public:
168 adaptor() = default;
169 constexpr adaptor(stride_view_t * rng) noexcept
170 : rng_(rng)
171 {}
172 template(bool Other)(
173 requires Const AND CPP_NOT(Other)) //
174 adaptor(adaptor<Other> that)
175 : rng_(that.rng_)
176 {}
177 constexpr void next(iterator_t<CRng> & it)
178 {
179 auto const last = ranges::end(rng_->base());
180 RANGES_EXPECT(it != last);
181 auto const delta = ranges::advance(it, rng_->stride_, last);
182 if(it == last)
183 {
184 rng_->set_offset(delta);
185 }
186 }
187 CPP_member
188 constexpr auto prev(iterator_t<CRng> & it) //
189 -> CPP_ret(void)(
191 {
192 RANGES_EXPECT(it != ranges::begin(rng_->base()));
193 auto delta = -rng_->stride_;
194 if(it == ranges::end(rng_->base()))
195 {
196 RANGES_EXPECT(rng_->get_offset() >= 0);
197 delta += rng_->get_offset();
198 }
199 ranges::advance(it, delta);
200 }
201 template(typename Other)(
202 requires sized_sentinel_for<Other, iterator_t<CRng>>)
203 constexpr range_difference_t<Rng> distance_to(iterator_t<CRng> const & here,
204 Other const & there) const
205 {
206 range_difference_t<Rng> delta = there - here;
207 if(delta < 0)
208 delta -= rng_->stride_ - 1;
209 else
210 delta += rng_->stride_ - 1;
211 return delta / rng_->stride_;
212 }
213 CPP_member
214 constexpr auto advance(iterator_t<CRng> & it, range_difference_t<Rng> n) //
215 -> CPP_ret(void)(
217 {
218 if(0 == n)
219 return;
220 n *= rng_->stride_;
221 auto const last = ranges::end(rng_->base());
222 if(it == last)
223 {
224 RANGES_EXPECT(n < 0);
225 RANGES_EXPECT(rng_->get_offset() >= 0);
226 n += rng_->get_offset();
227 }
228 if(0 < n)
229 {
230 auto delta = ranges::advance(it, n, last);
231 if(it == last)
232 {
233 // advance hit the last of the base range.
234 rng_->set_offset(delta % rng_->stride_);
235 }
236 }
237 else if(0 > n)
238 {
239#ifdef NDEBUG
240 ranges::advance(it, n);
241#else
242 auto const first = ranges::begin(rng_->base());
243 auto const delta = ranges::advance(it, n, first);
244 RANGES_EXPECT(delta == 0);
245#endif
246 }
247 }
248 };
249 constexpr adaptor<false> begin_adaptor() noexcept
250 {
251 return adaptor<false>{this};
252 }
253 CPP_member
254 constexpr auto begin_adaptor() const noexcept
255 -> CPP_ret(adaptor<true>)(
256 requires(const_iterable()))
257 {
258 return adaptor<true>{this};
259 }
260
261 constexpr meta::if_c<can_bound<false>(), adaptor<false>, adaptor_base> //
262 end_adaptor() noexcept
263 {
264 return {this};
265 }
266 CPP_member
267 constexpr auto end_adaptor() const noexcept //
268 -> CPP_ret(meta::if_c<can_bound<true>(), adaptor<true>, adaptor_base>)(
269 requires (const_iterable()))
270 {
271 return {this};
272 }
273
274 public:
275 stride_view() = default;
276 constexpr stride_view(Rng rng, range_difference_t<Rng> const stride)
277 : detail::stride_view_base<Rng>{std::move(rng), stride}
278 {}
279 CPP_auto_member
280 constexpr auto CPP_fun(size)()(
281 requires sized_range<Rng>)
282 {
283 using size_type = range_size_t<Rng>;
284 auto const n = ranges::size(this->base());
285 return (n + static_cast<size_type>(this->stride_) - 1) /
286 static_cast<size_type>(this->stride_);
287 }
288 CPP_auto_member
289 constexpr auto CPP_fun(size)()(const //
290 requires sized_range<Rng const>)
291 {
292 using size_type = range_size_t<Rng const>;
293 auto const n = ranges::size(this->base());
294 return (n + static_cast<size_type>(this->stride_) - 1) /
295 static_cast<size_type>(this->stride_);
296 }
297 };
298
299#if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
300 template<typename Rng>
301 stride_view(Rng &&, range_difference_t<Rng>)
303#endif
304
305 namespace views
306 {
308 {
309 template(typename Rng)(
311 constexpr stride_view<all_t<Rng>> //
312 operator()(Rng && rng, range_difference_t<Rng> step) const
313 {
314 return stride_view<all_t<Rng>>{all(static_cast<Rng &&>(rng)), step};
315 }
316 };
317
319 {
320 using stride_base_fn::operator();
321
322 template(typename Difference)(
323 requires detail::integer_like_<Difference>)
324 constexpr auto operator()(Difference step) const
325 {
326 return make_view_closure(bind_back(stride_base_fn{}, step));
327 }
328 };
329
332 RANGES_INLINE_VARIABLE(stride_fn, stride)
333 } // namespace views
335} // namespace ranges
336
337#include <range/v3/detail/epilogue.hpp>
338#include <range/v3/detail/satisfy_boost_range.hpp>
339RANGES_SATISFY_BOOST_RANGE(::ranges::stride_view)
340
341#endif
The bidirectional_range concept.
The common_range concept.
The input_range concept.
The random_access_range concept.
The range concept.
The sized_range concept.
The sized_sentinel_for concept.
The viewable_range concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition meta.hpp:168
Tiny meta-programming library.
Definition adaptor.hpp:110
Definition stride.hpp:132
Definition stride.hpp:308
Definition stride.hpp:319