Horizon
chunk.hpp
Go to the documentation of this file.
1 // 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 
22 #include <range/v3/range_fwd.hpp>
23 
30 #include <range/v3/utility/box.hpp>
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>
35 #include <range/v3/view/facade.hpp>
36 #include <range/v3/view/take.hpp>
37 #include <range/v3/view/view.hpp>
38 
39 #include <range/v3/detail/prologue.hpp>
40 
41 namespace 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>
82  struct chunk_view_
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
100  : adaptor_base
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)
125  : box<offset_t<Const>>{0}
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)(
152  requires bidirectional_range<CRng>)
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)(
174  requires random_access_range<CRng>)
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>)(
201  requires forward_range<Rng const>)
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>)(
299  requires sized_sentinel_for<sentinel_t<Rng>, iterator_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>)(
352  requires sized_sentinel_for<sentinel_t<Rng>, iterator_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)(
432  requires viewable_range<Rng> AND input_range<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 
455  } // namespace views
457 } // namespace ranges
458 
459 #include <range/v3/detail/epilogue.hpp>
460 #include <range/v3/detail/satisfy_boost_range.hpp>
461 RANGES_SATISFY_BOOST_RANGE(::ranges::chunk_view)
462 
463 #endif
Definition: box.hpp:163
CPP_concept sized_sentinel_for
\concept sized_sentinel_for
Definition: concepts.hpp:332
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
defer< bind_back, Fn, Ts... > bind_back
Definition: meta.hpp:994
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
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