1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___ITERATOR_ADVANCE_H
11#define _LIBCPP___ITERATOR_ADVANCE_H
12
13#include <__assert>
14#include <__concepts/assignable.h>
15#include <__concepts/same_as.h>
16#include <__config>
17#include <__iterator/concepts.h>
18#include <__iterator/incrementable_traits.h>
19#include <__iterator/iterator_traits.h>
20#include <__type_traits/enable_if.h>
21#include <__type_traits/is_integral.h>
22#include <__utility/convert_to_integral.h>
23#include <__utility/declval.h>
24#include <__utility/move.h>
25#include <__utility/unreachable.h>
26#include <limits>
27
28#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
29# pragma GCC system_header
30#endif
31
32_LIBCPP_PUSH_MACROS
33#include <__undef_macros>
34
35_LIBCPP_BEGIN_NAMESPACE_STD
36
37template <class _InputIter>
38_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void
39__advance(_InputIter& __i, typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag) {
40 for (; __n > 0; --__n)
41 ++__i;
42}
43
44template <class _BiDirIter>
45_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void
46__advance(_BiDirIter& __i, typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag) {
47 if (__n >= 0)
48 for (; __n > 0; --__n)
49 ++__i;
50 else
51 for (; __n < 0; ++__n)
52 --__i;
53}
54
55template <class _RandIter>
56_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void
57__advance(_RandIter& __i, typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag) {
58 __i += __n;
59}
60
61template < class _InputIter,
62 class _Distance,
63 class _IntegralDistance = decltype(std::__convert_to_integral(std::declval<_Distance>())),
64 __enable_if_t<is_integral<_IntegralDistance>::value, int> = 0>
65_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void advance(_InputIter& __i, _Distance __orig_n) {
66 typedef typename iterator_traits<_InputIter>::difference_type _Difference;
67 _Difference __n = static_cast<_Difference>(std::__convert_to_integral(__orig_n));
68 _LIBCPP_ASSERT_PEDANTIC(__has_bidirectional_iterator_category<_InputIter>::value || __n >= 0,
69 "std::advance: Can only pass a negative `n` with a bidirectional_iterator.");
70 std::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
71}
72
73#if _LIBCPP_STD_VER >= 20
74
75// [range.iter.op.advance]
76
77namespace ranges {
78struct __advance {
79private:
80 template <class _Ip>
81 _LIBCPP_HIDE_FROM_ABI static constexpr void __advance_forward(_Ip& __i, iter_difference_t<_Ip> __n) {
82 while (__n > 0) {
83 --__n;
84 ++__i;
85 }
86 }
87
88 template <class _Ip>
89 _LIBCPP_HIDE_FROM_ABI static constexpr void __advance_backward(_Ip& __i, iter_difference_t<_Ip> __n) {
90 while (__n < 0) {
91 ++__n;
92 --__i;
93 }
94 }
95
96public:
97 // Preconditions: If `I` does not model `bidirectional_iterator`, `n` is not negative.
98 template <input_or_output_iterator _Ip>
99 _LIBCPP_HIDE_FROM_ABI constexpr void operator()(_Ip& __i, iter_difference_t<_Ip> __n) const {
100 _LIBCPP_ASSERT_PEDANTIC(bidirectional_iterator<_Ip> || __n >= 0,
101 "ranges::advance: Can only pass a negative `n` with a bidirectional_iterator.");
102
103 // If `I` models `random_access_iterator`, equivalent to `i += n`.
104 if constexpr (random_access_iterator<_Ip>) {
105 __i += __n;
106 return;
107 } else if constexpr (bidirectional_iterator<_Ip>) {
108 // Otherwise, if `n` is non-negative, increments `i` by `n`.
109 __advance_forward(__i, __n);
110 // Otherwise, decrements `i` by `-n`.
111 __advance_backward(__i, __n);
112 return;
113 } else {
114 // Otherwise, if `n` is non-negative, increments `i` by `n`.
115 __advance_forward(__i, __n);
116 return;
117 }
118 }
119
120 // Preconditions: Either `assignable_from<I&, S> || sized_sentinel_for<S, I>` is modeled, or [i, bound_sentinel)
121 // denotes a range.
122 template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
123 _LIBCPP_HIDE_FROM_ABI constexpr void operator()(_Ip& __i, _Sp __bound_sentinel) const {
124 // If `I` and `S` model `assignable_from<I&, S>`, equivalent to `i = std::move(bound_sentinel)`.
125 if constexpr (assignable_from<_Ip&, _Sp>) {
126 __i = std::move(__bound_sentinel);
127 }
128 // Otherwise, if `S` and `I` model `sized_sentinel_for<S, I>`, equivalent to `ranges::advance(i, bound_sentinel -
129 // i)`.
130 else if constexpr (sized_sentinel_for<_Sp, _Ip>) {
131 (*this)(__i, __bound_sentinel - __i);
132 }
133 // Otherwise, while `bool(i != bound_sentinel)` is true, increments `i`.
134 else {
135 while (__i != __bound_sentinel) {
136 ++__i;
137 }
138 }
139 }
140
141 // Preconditions:
142 // * If `n > 0`, [i, bound_sentinel) denotes a range.
143 // * If `n == 0`, [i, bound_sentinel) or [bound_sentinel, i) denotes a range.
144 // * If `n < 0`, [bound_sentinel, i) denotes a range, `I` models `bidirectional_iterator`, and `I` and `S` model
145 // `same_as<I, S>`.
146 // Returns: `n - M`, where `M` is the difference between the ending and starting position.
147 template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
148 _LIBCPP_HIDE_FROM_ABI constexpr iter_difference_t<_Ip>
149 operator()(_Ip& __i, iter_difference_t<_Ip> __n, _Sp __bound_sentinel) const {
150 _LIBCPP_ASSERT_PEDANTIC(
151 (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) || (__n >= 0),
152 "ranges::advance: Can only pass a negative `n` with a bidirectional_iterator coming from a common_range.");
153 // If `S` and `I` model `sized_sentinel_for<S, I>`:
154 if constexpr (sized_sentinel_for<_Sp, _Ip>) {
155 // If |n| >= |bound_sentinel - i|, equivalent to `ranges::advance(i, bound_sentinel)`.
156 // __magnitude_geq(a, b) returns |a| >= |b|, assuming they have the same sign.
157 auto __magnitude_geq = [](auto __a, auto __b) { return __a == 0 ? __b == 0 : __a > 0 ? __a >= __b : __a <= __b; };
158 if (const auto __m = __bound_sentinel - __i; __magnitude_geq(__n, __m)) {
159 (*this)(__i, __bound_sentinel);
160 return __n - __m;
161 }
162
163 // Otherwise, equivalent to `ranges::advance(i, n)`.
164 (*this)(__i, __n);
165 return 0;
166 } else {
167 // Otherwise, if `n` is non-negative, while `bool(i != bound_sentinel)` is true, increments `i` but at
168 // most `n` times.
169 while (__n > 0 && __i != __bound_sentinel) {
170 ++__i;
171 --__n;
172 }
173
174 // Otherwise, while `bool(i != bound_sentinel)` is true, decrements `i` but at most `-n` times.
175 if constexpr (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) {
176 while (__n < 0 && __i != __bound_sentinel) {
177 --__i;
178 ++__n;
179 }
180 }
181 return __n;
182 }
183
184 __libcpp_unreachable();
185 }
186};
187
188inline namespace __cpo {
189inline constexpr auto advance = __advance{};
190} // namespace __cpo
191} // namespace ranges
192
193#endif // _LIBCPP_STD_VER >= 20
194
195_LIBCPP_END_NAMESPACE_STD
196
197_LIBCPP_POP_MACROS
198
199#endif // _LIBCPP___ITERATOR_ADVANCE_H
200