Horizon
stride.hpp
Go to the documentation of this file.
1 // 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 
23 #include <range/v3/range_fwd.hpp>
24 
31 #include <range/v3/utility/static_const.hpp>
33 #include <range/v3/view/all.hpp>
34 #include <range/v3/view/view.hpp>
35 
36 #include <range/v3/detail/prologue.hpp>
37 
38 namespace 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> &&
142  (sized_range<Rng const> || !bidirectional_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> &&
155  (sized_range<CRng> || !bidirectional_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)(
190  requires bidirectional_range<CRng>)
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)(
216  requires random_access_range<CRng>)
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)(
310  requires viewable_range<Rng> AND input_range<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 
333  } // namespace views
335 } // namespace ranges
336 
337 #include <range/v3/detail/epilogue.hpp>
338 #include <range/v3/detail/satisfy_boost_range.hpp>
339 RANGES_SATISFY_BOOST_RANGE(::ranges::stride_view)
340 
341 #endif
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
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition: meta.hpp:168
defer< bind_back, Fn, Ts... > bind_back
Definition: meta.hpp:994
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
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: stride.hpp:132
Definition: stride.hpp:308
Definition: stride.hpp:319