Horizon
Loading...
Searching...
No Matches
operations.hpp
Go to the documentation of this file.
1
2// 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
20
24
25#include <range/v3/detail/prologue.hpp>
26
27namespace ranges
28{
31
33 template<typename I>
34 // requires input_or_output_iterator<I>
35 struct counted_iterator;
37
39 {
40#if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
41 template(typename 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)(
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)(
202 constexpr void operator()(counted_iterator<I> & i, iter_difference_t<I> n) const;
203 };
204
206 RANGES_INLINE_VARIABLE(advance_fn, advance)
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)(
304 constexpr I operator()(I it) const
305 {
306 return ++it;
307 }
308 template(typename 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
332 RANGES_INLINE_VARIABLE(next_fn, next)
333
334 struct prev_fn
335 {
336 template(typename I)(
338 constexpr I operator()(I it) const
339 {
340 return --it;
341 }
342 template(typename 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)(
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
359 RANGES_INLINE_VARIABLE(prev_fn, prev)
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)(
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
405 RANGES_INLINE_VARIABLE(iter_enumerate_fn, iter_enumerate)
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)(
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
436 RANGES_INLINE_VARIABLE(iter_distance_fn, iter_distance)
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)(
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)(
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
496 RANGES_INLINE_VARIABLE(iter_size_fn, iter_size)
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(
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
568 RANGES_INLINE_VARIABLE(enumerate_fn, enumerate)
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
598 RANGES_INLINE_VARIABLE(distance_fn, distance)
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
636 RANGES_INLINE_VARIABLE(distance_compare_fn, distance_compare)
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
The bidirectional_iterator concept.
The input_iterator concept.
The input_or_output_iterator concept.
The random_access_iterator concept.
The range concept.
The sentinel_for concept.
The sized_sentinel_for concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
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
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