Horizon
operations.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2014-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 #ifndef RANGES_V3_ITERATOR_OPERATIONS_HPP
14 #define RANGES_V3_ITERATOR_OPERATIONS_HPP
15 
16 #include <type_traits>
17 #include <utility>
18 
19 #include <range/v3/range_fwd.hpp>
20 
24 
25 #include <range/v3/detail/prologue.hpp>
26 
27 namespace ranges
28 {
31 
33  template<typename I>
34  // requires input_or_output_iterator<I>
35  struct counted_iterator;
37 
38  struct advance_fn
39  {
40 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
41  template(typename I)(
42  requires input_or_output_iterator<I>)
43  constexpr void operator()(I & i, iter_difference_t<I> n) const
44  // [[expects: n >= 0 || bidirectional_iterator<I>]]
45  {
46  if constexpr(random_access_iterator<I>)
47  {
48  i += n;
49  }
50  else
51  {
52  if constexpr(bidirectional_iterator<I>)
53  for(; 0 > n; ++n)
54  --i;
55  RANGES_EXPECT(0 <= n);
56  for(; 0 < n; --n)
57  ++i;
58  }
59  }
60 
61  template(typename I, typename S)(
62  requires sentinel_for<S, I>)
63  constexpr void operator()(I & i, S bound) const
64  // [[expects axiom: reachable(i, bound)]]
65  {
66  if constexpr(assignable_from<I &, S>)
67  {
68  i = std::move(bound);
69  }
70  else if constexpr(sized_sentinel_for<S, I>)
71  {
72  iter_difference_t<I> d = bound - i;
73  RANGES_EXPECT(0 <= d);
74  (*this)(i, d);
75  }
76  else
77  while(i != bound)
78  ++i;
79  }
80 
81  template(typename I, typename S)(
82  requires sentinel_for<S, I>)
83  constexpr iter_difference_t<I> //
84  operator()(I & i, iter_difference_t<I> n, S bound) const
85  // [[expects axiom: 0 == n ||
86  // (0 < n && reachable(i, bound)) ||
87  // (0 > n && same_as<I, S> && bidirectional_iterator<I> && reachable(bound,
88  // i))]]
89  {
90  if constexpr(sized_sentinel_for<S, I>)
91  {
92  if(0 == n)
93  return 0;
94  const auto d = bound - i;
95  if constexpr(bidirectional_iterator<I> && same_as<I, S>)
96  {
97  RANGES_EXPECT(0 <= n ? 0 <= d : 0 >= d);
98  if(0 <= n ? d <= n : d >= n)
99  {
100  i = std::move(bound);
101  return n - d;
102  }
103  }
104  else
105  {
106  RANGES_EXPECT(0 <= n && 0 <= d);
107  if(d <= n)
108  {
109  (*this)(i, std::move(bound));
110  return n - d;
111  }
112  }
113  (*this)(i, n);
114  return 0;
115  }
116  else
117  {
118  if constexpr(bidirectional_iterator<I> && same_as<I, S>)
119  {
120  if(0 > n)
121  {
122  do
123  {
124  --i;
125  ++n;
126  } while(0 != n && i != bound);
127  return n;
128  }
129  }
130  RANGES_EXPECT(0 <= n);
131  while(0 != n && i != bound)
132  {
133  ++i;
134  --n;
135  }
136  return n;
137  }
138  }
139 #else
140  private:
141  template<typename I>
142  static constexpr void n_(I & i, iter_difference_t<I> n, std::input_iterator_tag);
143  template<typename I>
144  static constexpr void n_(I & i, iter_difference_t<I> n,
145  std::bidirectional_iterator_tag);
146  template<typename I>
147  static constexpr void n_(I & i, iter_difference_t<I> n,
148  std::random_access_iterator_tag);
149  template<typename I, typename S>
150  static constexpr void to_impl_(I & i, S s, sentinel_tag);
151  template<typename I, typename S>
152  static constexpr void to_impl_(I & i, S s, sized_sentinel_tag);
153  template<typename I, typename S>
154  static constexpr void to_(I & i, S s, std::true_type); // assignable
155  template<typename I, typename S>
156  static constexpr void to_(I & i, S s, std::false_type); // !assignable
157  template<typename I, typename S>
158  static constexpr iter_difference_t<I> bounded_(I & it, iter_difference_t<I> n,
159  S bound, sentinel_tag,
160  std::input_iterator_tag);
161  template<typename I>
162  static constexpr iter_difference_t<I> bounded_(I & it, iter_difference_t<I> n,
163  I bound, sentinel_tag,
164  std::bidirectional_iterator_tag);
165  template<typename I, typename S, typename Concept>
166  static constexpr iter_difference_t<I> bounded_(I & it, iter_difference_t<I> n,
167  S bound, sized_sentinel_tag,
168  Concept);
169 
170  public:
171  // Advance a certain number of steps:
172  template(typename I)(
173  requires input_or_output_iterator<I>)
174  constexpr void operator()(I & i, iter_difference_t<I> n) const
175  {
176  advance_fn::n_(i, n, iterator_tag_of<I>{});
177  }
178  // Advance to a certain position:
179  template(typename I, typename S)(
180  requires sentinel_for<S, I>)
181  constexpr void operator()(I & i, S s) const
182  {
183  advance_fn::to_(
184  i, static_cast<S &&>(s), meta::bool_<assignable_from<I &, S>>());
185  }
186  // Advance a certain number of times, with a bound:
187  template(typename I, typename S)(
188  requires sentinel_for<S, I>)
189  constexpr iter_difference_t<I> //
190  operator()(I & it, iter_difference_t<I> n, S bound) const
191  {
192  return advance_fn::bounded_(it,
193  n,
194  static_cast<S &&>(bound),
195  sentinel_tag_of<S, I>(),
196  iterator_tag_of<I>());
197  }
198 #endif
199 
200  template(typename I)(
201  requires input_or_output_iterator<I>)
202  constexpr void operator()(counted_iterator<I> & i, iter_difference_t<I> n) const;
203  };
204 
207 
208 #if RANGES_CXX_IF_CONSTEXPR < RANGES_CXX_IF_CONSTEXPR_17
209  template<typename I>
210  constexpr void advance_fn::n_(I & i, iter_difference_t<I> n, std::input_iterator_tag)
211  {
212  RANGES_EXPECT(n >= 0);
213  for(; n > 0; --n)
214  ++i;
215  }
216  template<typename I>
217  constexpr void advance_fn::n_(I & i, iter_difference_t<I> n,
218  std::bidirectional_iterator_tag)
219  {
220  if(n > 0)
221  for(; n > 0; --n)
222  ++i;
223  else
224  for(; n < 0; ++n)
225  --i;
226  }
227  template<typename I>
228  constexpr void advance_fn::n_(I & i, iter_difference_t<I> n,
229  std::random_access_iterator_tag)
230  {
231  i += n;
232  }
233  template<typename I, typename S>
234  constexpr void advance_fn::to_impl_(I & i, S s, sentinel_tag)
235  {
236  while(i != s)
237  ++i;
238  }
239  template<typename I, typename S>
240  constexpr void advance_fn::to_impl_(I & i, S s, sized_sentinel_tag)
241  {
242  iter_difference_t<I> d = s - i;
243  RANGES_EXPECT(0 <= d);
244  advance(i, d);
245  }
246  // Advance to a certain position:
247  template<typename I, typename S>
248  constexpr void advance_fn::to_(I & i, S s, std::true_type)
249  {
250  i = static_cast<S &&>(s);
251  }
252  template<typename I, typename S>
253  constexpr void advance_fn::to_(I & i, S s, std::false_type)
254  {
255  advance_fn::to_impl_(i, static_cast<S &&>(s), sentinel_tag_of<S, I>());
256  }
257  template<typename I, typename S>
258  constexpr iter_difference_t<I> advance_fn::bounded_(I & it, iter_difference_t<I> n,
259  S bound, sentinel_tag,
260  std::input_iterator_tag)
261  {
262  RANGES_EXPECT(0 <= n);
263  for(; 0 != n && it != bound; --n)
264  ++it;
265  return n;
266  }
267  template<typename I>
268  constexpr iter_difference_t<I> advance_fn::bounded_(I & it, iter_difference_t<I> n,
269  I bound, sentinel_tag,
270  std::bidirectional_iterator_tag)
271  {
272  if(0 <= n)
273  for(; 0 != n && it != bound; --n)
274  ++it;
275  else
276  for(; 0 != n && it != bound; ++n)
277  --it;
278  return n;
279  }
280  template<typename I, typename S, typename Concept>
281  constexpr iter_difference_t<I> advance_fn::bounded_(I & it, iter_difference_t<I> n,
282  S bound, sized_sentinel_tag,
283  Concept)
284  {
285  RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
286  if(n == 0)
287  return 0;
288  iter_difference_t<I> d = bound - it;
289  RANGES_EXPECT(0 <= n ? 0 <= d : 0 >= d);
290  if(0 <= n ? n >= d : n <= d)
291  {
292  advance(it, static_cast<S &&>(bound));
293  return n - d;
294  }
295  advance(it, n);
296  return 0;
297  }
298 #endif
299 
300  struct next_fn
301  {
302  template(typename I)(
303  requires input_or_output_iterator<I>)
304  constexpr I operator()(I it) const
305  {
306  return ++it;
307  }
308  template(typename I)(
309  requires input_or_output_iterator<I>)
310  constexpr I operator()(I it, iter_difference_t<I> n) const
311  {
312  advance(it, n);
313  return it;
314  }
315  template(typename I, typename S)(
316  requires sentinel_for<S, I>)
317  constexpr I operator()(I it, S s) const
318  {
319  advance(it, static_cast<S &&>(s));
320  return it;
321  }
322  template(typename I, typename S)(
323  requires sentinel_for<S, I>)
324  constexpr I operator()(I it, iter_difference_t<I> n, S bound) const
325  {
326  advance(it, n, static_cast<S &&>(bound));
327  return it;
328  }
329  };
330 
333 
334  struct prev_fn
335  {
336  template(typename I)(
337  requires bidirectional_iterator<I>)
338  constexpr I operator()(I it) const
339  {
340  return --it;
341  }
342  template(typename I)(
343  requires bidirectional_iterator<I>)
344  constexpr I operator()(I it, iter_difference_t<I> n) const
345  {
346  advance(it, -n);
347  return it;
348  }
349  template(typename I)(
350  requires bidirectional_iterator<I>)
351  constexpr I operator()(I it, iter_difference_t<I> n, I bound) const
352  {
353  advance(it, -n, static_cast<I &&>(bound));
354  return it;
355  }
356  };
357 
360 
362  {
363  private:
364  template(typename I, typename S)(
365  requires (!sized_sentinel_for<I, I>)) //
366  static constexpr std::pair<iter_difference_t<I>, I> //
367  impl_i(I first, S last, sentinel_tag)
368  {
369  iter_difference_t<I> d = 0;
370  for(; first != last; ++first)
371  ++d;
372  return {d, first};
373  }
374  template(typename I, typename S)(
375  requires sized_sentinel_for<I, I>)
376  static constexpr std::pair<iter_difference_t<I>, I> //
377  impl_i(I first, S end_, sentinel_tag)
378  {
379  I last = ranges::next(first, end_);
380  auto n = static_cast<iter_difference_t<I>>(last - first);
381  RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
382  return {n, last};
383  }
384  template<typename I, typename S>
385  static constexpr std::pair<iter_difference_t<I>, I> //
386  impl_i(I first, S last, sized_sentinel_tag)
387  {
388  auto n = static_cast<iter_difference_t<I>>(last - first);
389  RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
390  return {n, ranges::next(first, last)};
391  }
392 
393  public:
394  template(typename I, typename S)(
395  requires sentinel_for<S, I>)
396  constexpr std::pair<iter_difference_t<I>, I> operator()(I first, S last) const
397  {
398  return iter_enumerate_fn::impl_i(static_cast<I &&>(first),
399  static_cast<S &&>(last),
400  sentinel_tag_of<S, I>());
401  }
402  };
403 
406 
408  {
409  private:
410  template<typename I, typename S>
411  static constexpr iter_difference_t<I> impl_i(I first, S last, sentinel_tag)
412  {
413  return iter_enumerate(static_cast<I &&>(first), static_cast<S &&>(last))
414  .first;
415  }
416  template<typename I, typename S>
417  static constexpr iter_difference_t<I> impl_i(I first, S last, sized_sentinel_tag)
418  {
419  auto n = static_cast<iter_difference_t<I>>(last - first);
420  RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
421  return n;
422  }
423 
424  public:
425  template(typename I, typename S)(
426  requires input_or_output_iterator<I> AND sentinel_for<S, I>)
427  constexpr iter_difference_t<I> operator()(I first, S last) const
428  {
429  return iter_distance_fn::impl_i(static_cast<I &&>(first),
430  static_cast<S &&>(last),
431  sentinel_tag_of<S, I>());
432  }
433  };
434 
437 
439  {
440  private:
441  template<typename I, typename S>
442  static constexpr int impl_i(I first, S last, iter_difference_t<I> n, sentinel_tag)
443  {
444  if(n < 0)
445  return 1;
446  for(; n > 0; --n, ++first)
447  {
448  if(first == last)
449  return -1;
450  }
451  return first == last ? 0 : 1;
452  }
453  template<typename I, typename S>
454  static constexpr int impl_i(I first, S last, iter_difference_t<I> n,
456  {
457  iter_difference_t<I> dist = last - first;
458  if(n < dist)
459  return 1;
460  if(dist < n)
461  return -1;
462  return 0;
463  }
464 
465  public:
466  template(typename I, typename S)(
467  requires input_iterator<I> AND sentinel_for<S, I>)
468  constexpr int operator()(I first, S last, iter_difference_t<I> n) const
469  {
470  return iter_distance_compare_fn::impl_i(static_cast<I &&>(first),
471  static_cast<S &&>(last),
472  n,
473  sentinel_tag_of<S, I>());
474  }
475  };
476 
478  RANGES_INLINE_VARIABLE(iter_distance_compare_fn, iter_distance_compare)
479 
480  // Like distance(b,e), but guaranteed to be O(1)
482  {
483  template(typename I, typename S)(
484  requires sized_sentinel_for<S, I>)
486  operator()(I const & first, S last) const
487  {
489  iter_difference_t<I> n = last - first;
490  RANGES_EXPECT(0 <= n);
491  return static_cast<size_type>(n);
492  }
493  };
494 
497 
498 
499  namespace adl_uncounted_recounted_detail
500  {
501  template<typename I>
502  constexpr I uncounted(I i)
503  {
504  return i;
505  }
506 
507  template<typename I>
508  constexpr I recounted(I const &, I i, iter_difference_t<I>)
509  {
510  return i;
511  }
512 
513  struct uncounted_fn
514  {
515  template<typename I>
516  constexpr auto operator()(I i) const -> decltype(uncounted((I &&) i))
517  {
518  return uncounted((I &&) i);
519  }
520  };
521 
522  struct recounted_fn
523  {
524  template<typename I, typename J>
525  constexpr auto operator()(I i, J j, iter_difference_t<J> n) const
526  -> decltype(recounted((I &&) i, (J &&) j, n))
527  {
528  return recounted((I &&) i, (J &&) j, n);
529  }
530  };
531  } // namespace adl_uncounted_recounted_detail
533 
534  RANGES_INLINE_VARIABLE(adl_uncounted_recounted_detail::uncounted_fn, uncounted)
535  RANGES_INLINE_VARIABLE(adl_uncounted_recounted_detail::recounted_fn, recounted)
536 
538  {
539  private:
540  template<typename Rng>
541  static constexpr std::pair<range_difference_t<Rng>, iterator_t<Rng>> impl_r(
542  Rng & rng, range_tag, range_tag)
543  {
544  return iter_enumerate(begin(rng), end(rng));
545  }
546  template<typename Rng>
547  static constexpr std::pair<range_difference_t<Rng>, iterator_t<Rng>> impl_r(
548  Rng & rng, common_range_tag, sized_range_tag)
549  {
550  return {static_cast<range_difference_t<Rng>>(size(rng)), end(rng)};
551  }
552 
553  public:
554  using iter_enumerate_fn::operator();
555 
556  template(typename Rng)(
557  requires range<Rng>)
558  constexpr std::pair<range_difference_t<Rng>, iterator_t<Rng>> operator()(Rng && rng) const
559  {
560  // Better not be trying to compute the distance of an infinite range:
561  RANGES_EXPECT(!is_infinite<Rng>::value);
562  return enumerate_fn::impl_r(
563  rng, common_range_tag_of<Rng>(), sized_range_tag_of<Rng>());
564  }
565  };
566 
569 
571  {
572  private:
573  template<typename Rng>
574  static range_difference_t<Rng> impl_r(Rng & rng, range_tag)
575  {
576  return enumerate(rng).first;
577  }
578  template<typename Rng>
579  static constexpr range_difference_t<Rng> impl_r(Rng & rng, sized_range_tag)
580  {
581  return static_cast<range_difference_t<Rng>>(size(rng));
582  }
583 
584  public:
585  using iter_distance_fn::operator();
586 
587  template(typename Rng)(
588  requires range<Rng>)
589  constexpr range_difference_t<Rng> operator()(Rng && rng) const
590  {
591  // Better not be trying to compute the distance of an infinite range:
592  RANGES_EXPECT(!is_infinite<Rng>::value);
593  return distance_fn::impl_r(rng, sized_range_tag_of<Rng>());
594  }
595  };
596 
599 
600  // The interface of distance_compare is taken from Util.listLengthCmp in the GHC API.
602  {
603  private:
604  template<typename Rng>
605  static constexpr int impl_r(Rng & rng, range_difference_t<Rng> n, range_tag)
606  {
607  // Infinite ranges are always compared to be larger than a finite number.
608  return is_infinite<Rng>::value
609  ? 1
610  : iter_distance_compare(begin(rng), end(rng), n);
611  }
612  template<typename Rng>
613  static constexpr int impl_r(Rng & rng, range_difference_t<Rng> n, sized_range_tag)
614  {
615  auto dist = distance(rng); // O(1) since rng is a sized_range
616  if(dist > n)
617  return 1;
618  else if(dist < n)
619  return -1;
620  else
621  return 0;
622  }
623 
624  public:
625  using iter_distance_compare_fn::operator();
626 
627  template(typename Rng)(
628  requires range<Rng>)
629  constexpr int operator()(Rng && rng, range_difference_t<Rng> n) const
630  {
631  return distance_compare_fn::impl_r(rng, n, sized_range_tag_of<Rng>());
632  }
633  };
634 
637 
638  namespace cpp20
639  {
640  using ranges::advance;
641  using ranges::distance;
642  using ranges::next;
643  using ranges::prev;
644  } // namespace cpp20
646 } // namespace ranges
647 
648 #include <range/v3/detail/epilogue.hpp>
649 
650 #endif // RANGES_V3_ITERATOR_OPERATIONS_HPP
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
typename T::type _t
Type alias for T::type.
Definition: meta.hpp:141
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
list< F, S > pair
A list with exactly two elements.
Definition: meta.hpp:2246
Definition: operations.hpp:39
Definition: concepts.hpp:305
Definition: operations.hpp:602
Definition: operations.hpp:571
Definition: operations.hpp:538
Definition: operations.hpp:439
Definition: operations.hpp:408
Definition: operations.hpp:362
Definition: operations.hpp:482
Definition: operations.hpp:301
Definition: operations.hpp:335
Definition: concepts.hpp:268
Definition: concepts.hpp:871
Definition: concepts.hpp:316
Definition: concepts.hpp:873