Horizon
iota.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_IOTA_HPP
15 #define RANGES_V3_VIEW_IOTA_HPP
16 
17 #include <climits>
18 #include <cstdint>
19 #include <limits>
20 #include <type_traits>
21 
22 #include <meta/meta.hpp>
23 
24 #include <concepts/concepts.hpp>
25 
26 #include <range/v3/range_fwd.hpp>
27 
30 #include <range/v3/utility/static_const.hpp>
32 #include <range/v3/view/facade.hpp>
33 
34 #include <range/v3/detail/prologue.hpp>
35 
36 RANGES_DIAGNOSTIC_PUSH
37 RANGES_DIAGNOSTIC_IGNORE_UNSIGNED_MATH
38 RANGES_DIAGNOSTIC_IGNORE_TRUNCATION
39 
40 namespace ranges
41 {
43  namespace detail
44  {
45  template<std::size_t N, typename = void>
46  struct promote_as_signed_
47  {
48  // This shouldn't cause us to LOSE precision, but maybe it doesn't
49  // net us any either.
50  static_assert(sizeof(std::intmax_t) * CHAR_BIT >= N,
51  "Possible extended integral type?");
52  using difference_type = diffmax_t;
53  };
54 
55  template<std::size_t N>
56  struct promote_as_signed_<N, enable_if_t<(N < 16)>>
57  {
58  using difference_type = std::int_fast16_t;
59  };
60 
61  template<std::size_t N>
62  struct promote_as_signed_<N, enable_if_t<(N >= 16 && N < 32)>>
63  {
64  using difference_type = std::int_fast32_t;
65  };
66 
67  template<std::size_t N>
68  struct promote_as_signed_<N, enable_if_t<(N >= 32 && N < 64)>>
69  {
70  using difference_type = std::int_fast64_t;
71  };
72 
73  template<typename I>
74  using iota_difference_t = typename meta::conditional_t<
75  std::is_integral<I>::value && sizeof(I) == sizeof(iter_difference_t<I>),
76  promote_as_signed_<sizeof(iter_difference_t<I>) * CHAR_BIT>,
77  with_difference_type_<iter_difference_t<I>>>::difference_type;
78 
79  // clang-format off
82  template<typename I>
83  CPP_requires(_decrementable_,
84  requires(I i) //
85  (
86  --i,
87  i--,
88  concepts::requires_<same_as<I&, decltype(--i)>>,
89  concepts::requires_<same_as<I, decltype(i--)>>
90  ));
93  template<typename I>
94  CPP_concept decrementable_ =
95  incrementable<I> &&
96  CPP_requires_ref(detail::_decrementable_, I);
97 
100  template<typename I>
101  CPP_requires(_advanceable_,
102  requires(I i, I const j, iota_difference_t<I> const n) //
103  (
104  j - j,
105  i += n,
106  i -= n,
107  static_cast<I>(j - n),
108  static_cast<I>(j + n),
109  static_cast<I>(n + j),
110  // NOT TO SPEC:
111  // Unsigned integers are advanceable, but subtracting them results in
112  // an unsigned integral, which is not the same as the difference type,
113  // which is signed.
114  concepts::requires_<convertible_to<decltype(j - j), iota_difference_t<I>>>,
115  concepts::requires_<same_as<I&, decltype(i += n)>>,
116  concepts::requires_<same_as<I&, decltype(i -= n)>> //,
117  // concepts::requires_<convertible_to<decltype(i - n), I>>,
118  // concepts::requires_<convertible_to<decltype(i + n), I>>,
119  // concepts::requires_<convertible_to<decltype(n + i), I>>
120  ));
123  template<typename I>
124  CPP_concept advanceable_ =
125  decrementable_<I> && totally_ordered<I> &&
126  CPP_requires_ref(detail::_advanceable_, I);
127  // clang-format on
128 
129  template(typename I)(
130  requires (!unsigned_integral<I>)) //
131  void iota_advance_(I & i, iota_difference_t<I> n)
132  {
133  // TODO: bounds-check this
134  i += n;
135  }
136 
137  template(typename Int)(
138  requires unsigned_integral<Int>)
139  void iota_advance_(Int & i, iota_difference_t<Int> n)
140  {
141  // TODO: bounds-check this
142  if(n >= 0)
143  i += static_cast<Int>(n);
144  else
145  i -= static_cast<Int>(-n);
146  }
147 
148  template(typename I)(
149  requires advanceable_<I> AND (!integral<I>)) //
150  iota_difference_t<I> iota_distance_(I const & i, I const & s)
151  {
152  return static_cast<iota_difference_t<I>>(s - i);
153  }
154 
155  template(typename Int)(
156  requires signed_integral<Int>)
157  iota_difference_t<Int> iota_distance_(Int i0, Int i1)
158  {
159  // TODO: bounds-check this
160  return static_cast<iota_difference_t<Int>>(
161  static_cast<iota_difference_t<Int>>(i1) -
162  static_cast<iota_difference_t<Int>>(i0));
163  }
164 
165  template(typename Int)(
166  requires unsigned_integral<Int>)
167  iota_difference_t<Int> iota_distance_(Int i0, Int i1)
168  {
169  // TODO: bounds-check this
170  return (i0 > i1) ? static_cast<iota_difference_t<Int>>(
171  -static_cast<iota_difference_t<Int>>(i0 - i1))
172  : static_cast<iota_difference_t<Int>>(i1 - i0);
173  }
174  } // namespace detail
176 
179 
181  template<typename From, typename To /* = From */>
182  struct RANGES_EMPTY_BASES closed_iota_view
183  : view_facade<closed_iota_view<From, To>, finite>
184  {
185  private:
186  friend range_access;
187 
188  From from_ = From();
189  RANGES_NO_UNIQUE_ADDRESS To to_ = To();
190 
191  struct cursor
192  {
193  using difference_type = detail::iota_difference_t<From>;
194 
195  private:
196  friend range_access;
197  From from_ = From();
198  RANGES_NO_UNIQUE_ADDRESS To to_ = To();
199  bool done_ = false;
200 
201  From read() const
202  {
203  RANGES_EXPECT(!done_);
204  return from_;
205  }
206  void next()
207  {
208  RANGES_EXPECT(!done_);
209  if(from_ == to_)
210  done_ = true;
211  else
212  ++from_;
213  }
214  bool equal(default_sentinel_t) const
215  {
216  return done_;
217  }
218  CPP_member
219  auto equal(cursor const & that) const //
220  -> CPP_ret(bool)(
221  requires equality_comparable<From>)
222  {
223  return that.from_ == from_ && that.done_ == done_;
224  }
225  CPP_member
226  auto prev() //
227  -> CPP_ret(void)(
228  requires detail::decrementable_<From>)
229  {
230  if(done_)
231  done_ = false;
232  else
233  --from_;
234  }
235  CPP_member
236  auto advance(difference_type n) //
237  -> CPP_ret(void)(
238  requires detail::advanceable_<From>)
239  {
240  if(n > 0)
241  {
242  RANGES_ENSURE(detail::iota_distance_(from_, to_) >= n - !done_);
243  detail::iota_advance_(
244  from_,
245  n - (done_ = (detail::iota_distance_(from_, to_) <= n - !done_)));
246  }
247  else if(n < 0)
248  detail::iota_advance_(from_, n + std::exchange(done_, false));
249  }
250  CPP_member
251  auto distance_to(cursor const & that) const //
252  -> CPP_ret(difference_type)(
253  requires detail::advanceable_<From>)
254  {
255  using D = difference_type;
256  return static_cast<D>(detail::iota_distance_(from_, that.from_)) +
257  ((D)that.done_ - (D)done_);
258  }
259  CPP_member
260  auto distance_to(default_sentinel_t) const //
261  -> CPP_ret(difference_type)(
262  requires sized_sentinel_for<To, From>)
263  {
264  return difference_type(to_ - from_) + !done_;
265  }
266 
267  public:
268  cursor() = default;
269  constexpr cursor(From from, To to, bool done = false)
270  : from_(std::move(from))
271  , to_(std::move(to))
272  , done_(done)
273  {}
274  };
275 
276  cursor begin_cursor() const
277  {
278  return {from_, to_};
279  }
280  CPP_member
281  auto end_cursor() const //
282  -> CPP_ret(cursor)(
283  requires same_as<From, To>)
284  {
285  return {to_, to_, true};
286  }
287  CPP_member
288  auto end_cursor() const //
289  -> CPP_ret(default_sentinel_t)(
290  requires (!same_as<From, To>))
291  {
292  return {};
293  }
294 
295  constexpr void check_bounds_(std::true_type)
296  {
297  RANGES_EXPECT(from_ <= to_);
298  }
299  constexpr void check_bounds_(std::false_type)
300  {}
301 
302  public:
303  closed_iota_view() = default;
305  : from_(std::move(from))
306  , to_(std::move(to))
307  {
308  check_bounds_(meta::bool_<totally_ordered_with<From, To>>{});
309  }
310  };
311 
312  template<typename From, typename To>
313  RANGES_INLINE_VAR constexpr bool enable_borrowed_range<closed_iota_view<From, To>> =
314  true;
315 
316 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
317  template(typename From, typename To)(
318  requires weakly_incrementable<From> AND semiregular<To> AND
319  (!integral<From> || !integral<To> ||
320  std::is_signed<From>::value == std::is_signed<To>::value)) //
321  closed_iota_view(From, To)
322  ->closed_iota_view<From, To>;
323 #endif
324 
325  template<typename From, typename To /* = unreachable_sentinel_t*/>
326  struct RANGES_EMPTY_BASES iota_view
327  : view_facade<iota_view<From, To>,
328  same_as<To, unreachable_sentinel_t>
329  ? infinite
330  : std::is_integral<From>::value && std::is_integral<To>::value
331  ? finite
332  : unknown>
333  {
334  private:
335  friend range_access;
336  From from_ = From();
337  RANGES_NO_UNIQUE_ADDRESS To to_ = To();
338 
339  struct cursor;
340  struct sentinel
341  {
342  private:
343  friend struct cursor;
344  RANGES_NO_UNIQUE_ADDRESS To to_;
345 
346  public:
347  sentinel() = default;
348  constexpr explicit sentinel(To to)
349  : to_(std::move(to))
350  {}
351  };
352 
353  struct cursor
354  {
355  using difference_type = detail::iota_difference_t<From>;
356 
357  private:
358  friend range_access;
359  From from_;
360 
361  From read() const
362  {
363  return from_;
364  }
365  void next()
366  {
367  ++from_;
368  }
369  bool equal(sentinel const & that) const
370  {
371  return from_ == that.to_;
372  }
373  CPP_member
374  auto equal(cursor const & that) const //
375  -> CPP_ret(bool)(
376  requires equality_comparable<From>)
377  {
378  return that.from_ == from_;
379  }
380  CPP_member
381  auto prev() //
382  -> CPP_ret(void)(
383  requires detail::decrementable_<From>)
384  {
385  --from_;
386  }
387  CPP_member
388  auto advance(difference_type n) //
389  -> CPP_ret(void)(
390  requires detail::advanceable_<From>)
391  {
392  detail::iota_advance_(from_, n);
393  }
394  // Not to spec: TODO the relational operators will effectively be constrained
395  // with Advanceable, but they should be constrained with totally_ordered.
396  // Reimplement iota_view without view_facade or basic_iterator.
397  CPP_member
398  auto distance_to(cursor const & that) const //
399  -> CPP_ret(difference_type)(
400  requires detail::advanceable_<From>)
401  {
402  return detail::iota_distance_(from_, that.from_);
403  }
404  // Extension: see https://github.com/ericniebler/stl2/issues/613
405  CPP_member
406  auto distance_to(sentinel const & that) const //
407  -> CPP_ret(difference_type)(
408  requires sized_sentinel_for<To, From>)
409  {
410  return that.to_ - from_;
411  }
412 
413  public:
414  cursor() = default;
415  constexpr explicit cursor(From from)
416  : from_(std::move(from))
417  {}
418  };
419  cursor begin_cursor() const
420  {
421  return cursor{from_};
422  }
423  CPP_auto_member
424  auto CPP_fun(end_cursor)()(const //
425  requires(same_as<To, unreachable_sentinel_t>))
426  {
427  return unreachable;
428  }
429  CPP_auto_member
430  auto CPP_fun(end_cursor)()(const //
431  requires(!same_as<To, unreachable_sentinel_t>))
432  {
433  return meta::conditional_t<same_as<From, To>, cursor, sentinel>{to_};
434  }
435  constexpr void check_bounds_(std::true_type)
436  {
437  RANGES_EXPECT(from_ <= to_);
438  }
439  constexpr void check_bounds_(std::false_type)
440  {}
441 
442  public:
443 #ifdef RANGES_WORKAROUND_MSVC_934264
444  constexpr
445 #endif // RANGES_WORKAROUND_MSVC_934264
446  iota_view() = default;
447  constexpr explicit iota_view(From from)
448  : from_(std::move(from))
449  {}
450  constexpr iota_view(meta::id_t<From> from, meta::id_t<To> to)
451  : from_(std::move(from))
452  , to_(std::move(to))
453  {
454  check_bounds_(meta::bool_<totally_ordered_with<From, To>>{});
455  }
456  };
457 
458  template<typename From, typename To>
459  RANGES_INLINE_VAR constexpr bool enable_borrowed_range<iota_view<From, To>> = true;
460 
461 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
462  template(typename From, typename To)(
463  requires weakly_incrementable<From> AND semiregular<To> AND
464  (!integral<From> || !integral<To> ||
465  std::is_signed<From>::value == std::is_signed<To>::value)) //
466  iota_view(From, To)
467  ->iota_view<From, To>;
468 #endif
469 
470  namespace views
471  {
472  struct iota_fn
473  {
474  template(typename From)(
475  requires weakly_incrementable<From>)
476  iota_view<From> operator()(From value) const
477  {
478  return iota_view<From>{std::move(value)};
479  }
480  template(typename From, typename To)(
481  requires weakly_incrementable<From> AND semiregular<To> AND
482  detail::weakly_equality_comparable_with_<From, To> AND
483  (!integral<From> || !integral<To> ||
484  std::is_signed<From>::value == std::is_signed<To>::value)) //
485  iota_view<From, To> operator()(From from, To to) const
486  {
487  return {std::move(from), std::move(to)};
488  }
489  };
490 
492  {
493  template(typename From, typename To)(
494  requires weakly_incrementable<From> AND semiregular<To> AND
495  detail::weakly_equality_comparable_with_<From, To> AND
496  (!integral<From> || !integral<To> ||
497  std::is_signed<From>::value == std::is_signed<To>::value)) //
498  closed_iota_view<From, To> operator()(From from, To to) const
499  {
500  return {std::move(from), std::move(to)};
501  }
502  };
503 
507 
508 
511 
512 
540  struct ints_fn : iota_view<int>
541  {
542  ints_fn() = default;
543 
544  template(typename Val)(
545  requires integral<Val>)
546  RANGES_DEPRECATED(
547  "This potentially confusing API is deprecated. Prefer to "
548  "explicitly specify the upper bound as with ranges::unreachable, as in "
549  "views::ints( n, unreachable )")
550  constexpr iota_view<Val> operator()(Val value) const //
551  {
552  return iota_view<Val>{value};
553  }
554  template(typename Val)(
555  requires integral<Val>)
556  constexpr iota_view<Val> operator()(Val value, unreachable_sentinel_t) const
557  {
558  return iota_view<Val>{value};
559  }
560  template(typename Val)(
561  requires integral<Val>)
562  constexpr iota_view<Val, Val> operator()(Val from, Val to) const
563  {
564  return {from, to};
565  }
566  };
567 
571  } // namespace views
572 
573  namespace cpp20
574  {
575  namespace views
576  {
577  using ranges::views::iota;
578  }
579  } // namespace cpp20
581 } // namespace ranges
582 
583 #include <range/v3/detail/satisfy_boost_range.hpp>
584 RANGES_SATISFY_BOOST_RANGE(::ranges::closed_iota_view)
585 RANGES_SATISFY_BOOST_RANGE(::ranges::iota_view)
586 
587 RANGES_DIAGNOSTIC_POP
588 
589 #include <range/v3/detail/epilogue.hpp>
590 
591 #endif
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
typename detail::_cond< If >::template invoke< Then, Else > conditional_t
Select one type or another depending on a compile-time Boolean.
Definition: meta.hpp:1148
_t< id< T > > id_t
An alias for type T.
Definition: meta.hpp:577
Tiny meta-programming library.
An iota view in a closed range.
Definition: iota.hpp:184
Definition: default_sentinel.hpp:26
Definition: iota.hpp:333
Definition: unreachable_sentinel.hpp:27
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition: facade.hpp:66
Definition: iota.hpp:492
Definition: iota.hpp:541
Definition: iota.hpp:473