Horizon
Loading...
Searching...
No Matches
chunk.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2013-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13
14#ifndef RANGES_V3_VIEW_CHUNK_HPP
15#define RANGES_V3_VIEW_CHUNK_HPP
16
17#include <limits>
18#include <utility>
19
20#include <meta/meta.hpp>
21
23
31#include <range/v3/utility/optional.hpp> // for non_propagating_cache
32#include <range/v3/utility/static_const.hpp>
34#include <range/v3/view/all.hpp>
38
39#include <range/v3/detail/prologue.hpp>
40
41namespace ranges
42{
44 namespace detail
45 {
46 template<typename Rng, bool Const>
47 constexpr bool can_sized_sentinel_() noexcept
48 {
49 using I = iterator_t<meta::const_if_c<Const, Rng>>;
50 return (bool)sized_sentinel_for<I, I>;
51 }
52
53 template<typename T>
54 struct zero
55 {
56 zero() = default;
57 constexpr explicit zero(T const &) noexcept
58 {}
59 constexpr zero & operator=(T const &) noexcept
60 {
61 return *this;
62 }
63 constexpr zero const & operator=(T const &) const noexcept
64 {
65 return *this;
66 }
67 constexpr operator T() const
68 {
69 return T(0);
70 }
71 constexpr T exchange(T const &) const
72 {
73 return T(0);
74 }
75 };
76 } // namespace detail
78
81 template<typename Rng, bool IsForwardRange>
83 : view_adaptor<chunk_view_<Rng, IsForwardRange>, Rng,
84 is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
85 {
86 private:
87 friend range_access;
88 CPP_assert(forward_range<Rng>);
89
90 template<bool Const>
91 using offset_t =
92 meta::if_c<bidirectional_range<meta::const_if_c<Const, Rng>> ||
93 detail::can_sized_sentinel_<Rng, Const>(),
94 range_difference_t<Rng>, detail::zero<range_difference_t<Rng>>>;
95
96 range_difference_t<Rng> n_ = 0;
97
98 template<bool Const>
99 struct RANGES_EMPTY_BASES adaptor
101 , private box<offset_t<Const>>
102 {
103 private:
104 friend adaptor<!Const>;
105 using CRng = meta::const_if_c<Const, Rng>;
106
107 range_difference_t<CRng> n_;
108 sentinel_t<CRng> end_;
109
110 constexpr offset_t<Const> const & offset() const
111 {
112 offset_t<Const> const & result = this->box<offset_t<Const>>::get();
113 RANGES_EXPECT(0 <= result && result < n_);
114 return result;
115 }
116 constexpr offset_t<Const> & offset()
117 {
118 return const_cast<offset_t<Const> &>(
119 const_cast<adaptor const &>(*this).offset());
120 }
121
122 public:
123 adaptor() = default;
124 constexpr adaptor(meta::const_if_c<Const, chunk_view_> * cv)
126 , n_((RANGES_EXPECT(0 < cv->n_), cv->n_))
127 , end_(ranges::end(cv->base()))
128 {}
129 template(bool Other)(
130 requires Const AND CPP_NOT(Other)) //
131 constexpr adaptor(adaptor<Other> that)
132 : box<offset_t<Const>>(that.offset())
133 , n_(that.n_)
134 , end_(that.end_)
135 {}
136 constexpr auto read(iterator_t<CRng> const & it) const
137 -> decltype(views::take(make_subrange(it, end_), n_))
138 {
139 RANGES_EXPECT(it != end_);
140 RANGES_EXPECT(0 == offset());
141 return views::take(make_subrange(it, end_), n_);
142 }
143 constexpr void next(iterator_t<CRng> & it)
144 {
145 RANGES_EXPECT(it != end_);
146 RANGES_EXPECT(0 == offset());
147 offset() = ranges::advance(it, n_, end_);
148 }
149 CPP_member
150 constexpr auto prev(iterator_t<CRng> & it) //
151 -> CPP_ret(void)(
153 {
154 ranges::advance(it, -n_ + offset());
155 offset() = 0;
156 }
157 CPP_member
158 constexpr auto distance_to(iterator_t<CRng> const & here,
159 iterator_t<CRng> const & there,
160 adaptor const & that) const
161 -> CPP_ret(range_difference_t<Rng>)(
162 requires (detail::can_sized_sentinel_<Rng, Const>()))
163 {
164 auto const delta = (there - here) + (that.offset() - offset());
165 // This can fail for cyclic base ranges when the chunk size does not
166 // divide the cycle length. Such iterator pairs are NOT in the domain of
167 // -.
168 RANGES_ENSURE(0 == delta % n_);
169 return delta / n_;
170 }
171 CPP_member
172 constexpr auto advance(iterator_t<CRng> & it, range_difference_t<Rng> n) //
173 -> CPP_ret(void)(
175 {
176 using Limits = std::numeric_limits<range_difference_t<CRng>>;
177 if(0 < n)
178 {
179 RANGES_EXPECT(0 == offset());
180 RANGES_EXPECT(n <= Limits::max() / n_);
181 auto const remainder = ranges::advance(it, n * n_, end_) % n_;
182 RANGES_EXPECT(0 <= remainder && remainder < n_);
183 offset() = remainder;
184 }
185 else if(0 > n)
186 {
187 RANGES_EXPECT(n >= Limits::min() / n_);
188 ranges::advance(it, n * n_ + offset());
189 offset() = 0;
190 }
191 }
192 };
193
194 constexpr adaptor<simple_view<Rng>()> begin_adaptor()
195 {
196 return adaptor<simple_view<Rng>()>{this};
197 }
198 CPP_member
199 constexpr auto begin_adaptor() const //
200 -> CPP_ret(adaptor<true>)(
202 {
203 return adaptor<true>{this};
204 }
205 template<typename Size>
206 constexpr Size size_(Size base_size) const
207 {
208 auto const n = static_cast<Size>(n_);
209 return base_size / n + (0 != (base_size % n));
210 }
211
212 public:
213 chunk_view_() = default;
214 constexpr chunk_view_(Rng rng, range_difference_t<Rng> n)
215 : chunk_view_::view_adaptor(detail::move(rng))
216 , n_((RANGES_EXPECT(0 < n), n))
217 {}
218 CPP_auto_member
219 constexpr auto CPP_fun(size)()(const
220 requires sized_range<Rng const>)
221 {
222 return size_(ranges::size(this->base()));
223 }
224 CPP_auto_member
225 constexpr auto CPP_fun(size)()(
226 requires sized_range<Rng>)
227 {
228 return size_(ranges::size(this->base()));
229 }
230 };
231
232 template<typename Rng>
233 struct chunk_view_<Rng, false>
234 : view_facade<chunk_view_<Rng, false>,
235 is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
236 {
237 private:
238 friend range_access;
239 CPP_assert(input_range<Rng> && !forward_range<Rng>);
240
241 using iter_cache_t = detail::non_propagating_cache<iterator_t<Rng>>;
242
243 Rng base_;
244 range_difference_t<Rng> n_;
245 range_difference_t<Rng> remainder_;
246 mutable iter_cache_t it_cache_;
247
248 constexpr iterator_t<Rng> & it() noexcept
249 {
250 return *it_cache_;
251 }
252 constexpr iterator_t<Rng> const & it() const noexcept
253 {
254 return *it_cache_;
255 }
256
257 struct outer_cursor
258 {
259 private:
260 struct inner_view : view_facade<inner_view, finite>
261 {
262 private:
263 friend range_access;
264
265 using value_type = range_value_t<Rng>;
266
267 chunk_view_ * rng_ = nullptr;
268
269 constexpr bool done() const noexcept
270 {
271 RANGES_EXPECT(rng_);
272 return rng_->remainder_ == 0;
273 }
274 constexpr bool equal(default_sentinel_t) const noexcept
275 {
276 return done();
277 }
278 constexpr iter_reference_t<iterator_t<Rng>> read() const
279 {
280 RANGES_EXPECT(!done());
281 return *rng_->it();
282 }
283 constexpr iter_rvalue_reference_t<iterator_t<Rng>> move() const
284 {
285 RANGES_EXPECT(!done());
286 return ranges::iter_move(rng_->it());
287 }
288 constexpr void next()
289 {
290 RANGES_EXPECT(!done());
291 ++rng_->it();
292 --rng_->remainder_;
293 if(rng_->remainder_ != 0 && rng_->it() == ranges::end(rng_->base_))
294 rng_->remainder_ = 0;
295 }
296 CPP_member
297 constexpr auto distance_to(default_sentinel_t) const
298 -> CPP_ret(range_difference_t<Rng>)(
300 {
301 RANGES_EXPECT(rng_);
302 auto const d = ranges::end(rng_->base_) - rng_->it();
303 return ranges::min(d, rng_->remainder_);
304 }
305
306 public:
307 inner_view() = default;
308 constexpr explicit inner_view(chunk_view_ * view) noexcept
309 : rng_{view}
310 {}
311 CPP_auto_member
312 constexpr auto CPP_fun(size)()(
313 requires sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>>)
314 {
315 using size_type = detail::iter_size_t<iterator_t<Rng>>;
316 return static_cast<size_type>(distance_to(default_sentinel_t{}));
317 }
318 };
319
320 chunk_view_ * rng_ = nullptr;
321
322 public:
323 using value_type = inner_view;
324
325 outer_cursor() = default;
326 constexpr explicit outer_cursor(chunk_view_ * view) noexcept
327 : rng_{view}
328 {}
329 constexpr inner_view read() const
330 {
331 RANGES_EXPECT(!done());
332 return inner_view{rng_};
333 }
334 constexpr bool done() const
335 {
336 RANGES_EXPECT(rng_);
337 return rng_->it() == ranges::end(rng_->base_) && rng_->remainder_ != 0;
338 }
339 constexpr bool equal(default_sentinel_t) const
340 {
341 return done();
342 }
343 constexpr void next()
344 {
345 RANGES_EXPECT(!done());
346 ranges::advance(rng_->it(), rng_->remainder_, ranges::end(rng_->base_));
347 rng_->remainder_ = rng_->n_;
348 }
349 CPP_member
350 constexpr auto distance_to(default_sentinel_t) const
351 -> CPP_ret(range_difference_t<Rng>)(
353 {
354 RANGES_EXPECT(rng_);
355 auto d = ranges::end(rng_->base_) - rng_->it();
356 if(d < rng_->remainder_)
357 return 1;
358
359 d -= rng_->remainder_;
360 d = (d + rng_->n_ - 1) / rng_->n_;
361 d += (rng_->remainder_ != 0);
362 return d;
363 }
364 };
365
366 constexpr outer_cursor begin_cursor() noexcept
367 {
368 it_cache_ = ranges::begin(base_);
369 return outer_cursor{this};
370 }
371 template<typename Size>
372 constexpr Size size_(Size base_size) const
373 {
374 auto const n = static_cast<Size>(this->n_);
375 return base_size / n + (0 != base_size % n);
376 }
377
378 public:
379 chunk_view_() = default;
380 constexpr chunk_view_(Rng rng, range_difference_t<Rng> n)
381 : base_(detail::move(rng))
382 , n_((RANGES_EXPECT(0 < n), n))
383 , remainder_(n)
384 , it_cache_{nullopt}
385 {}
386 CPP_auto_member
387 constexpr auto CPP_fun(size)()(const
388 requires sized_range<Rng const>)
389 {
390 return size_(ranges::size(base_));
391 }
392 CPP_auto_member
393 constexpr auto CPP_fun(size)()(
394 requires sized_range<Rng>)
395 {
396 return size_(ranges::size(base_));
397 }
398 Rng base() const
399 {
400 return base_;
401 }
402 };
403
404 template<typename Rng>
405 struct chunk_view : chunk_view_<Rng, (bool)forward_range<Rng>>
406 {
407 chunk_view() = default;
408 constexpr chunk_view(Rng rng, range_difference_t<Rng> n)
409 : chunk_view_<Rng, (bool)forward_range<Rng>>(static_cast<Rng &&>(rng), n)
410 {}
411 };
412
413 // Need to keep extra state for input_range, but forward_range is transparent
414 template<typename Rng>
415 RANGES_INLINE_VAR constexpr bool enable_borrowed_range<chunk_view<Rng>> =
416 enable_borrowed_range<Rng> && forward_range<Rng>;
417
418#if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
419 template<typename Rng>
420 chunk_view(Rng &&, range_difference_t<Rng>)
422#endif
423
424 namespace views
425 {
426 // In: range<T>
427 // Out: range<range<T>>, where each inner range has $n$ elements.
428 // The last range may have fewer.
430 {
431 template(typename Rng)(
433 constexpr chunk_view<all_t<Rng>> //
434 operator()(Rng && rng, range_difference_t<Rng> n) const
435 {
436 return {all(static_cast<Rng &&>(rng)), n};
437 }
438 };
439
441 {
442 using chunk_base_fn::operator();
443
444 template(typename Int)(
445 requires detail::integer_like_<Int>)
446 constexpr auto operator()(Int n) const
447 {
448 return make_view_closure(bind_back(chunk_base_fn{}, n));
449 }
450 };
451
454 RANGES_INLINE_VARIABLE(chunk_fn, chunk)
455 } // namespace views
457} // namespace ranges
458
459#include <range/v3/detail/epilogue.hpp>
460#include <range/v3/detail/satisfy_boost_range.hpp>
461RANGES_SATISFY_BOOST_RANGE(::ranges::chunk_view)
462
463#endif
Definition box.hpp:163
The bidirectional_range concept.
The forward_range concept.
The input_range concept.
The random_access_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
Tiny meta-programming library.
Definition adaptor.hpp:110
Definition chunk.hpp:85
Definition chunk.hpp:406
Definition default_sentinel.hpp:26
Definition adaptor.hpp:475
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition facade.hpp:66
Definition chunk.hpp:430
Definition chunk.hpp:441