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 
37 template <class _InputIter>
38 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
39 void __advance(_InputIter& __i, typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag) {
40   for (; __n > 0; --__n)
41     ++__i;
42 }
43 
44 template <class _BiDirIter>
45 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
46 void __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 
55 template <class _RandIter>
56 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
57 void __advance(_RandIter& __i, typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag) {
58   __i += __n;
59 }
60 
61 template <
62     class _InputIter, class _Distance,
63     class _IntegralDistance = decltype(_VSTD::__convert_to_integral(std::declval<_Distance>())),
64     class = __enable_if_t<is_integral<_IntegralDistance>::value> >
65 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
66 void advance(_InputIter& __i, _Distance __orig_n) {
67   typedef typename iterator_traits<_InputIter>::difference_type _Difference;
68   _Difference __n = static_cast<_Difference>(_VSTD::__convert_to_integral(__orig_n));
69   _LIBCPP_ASSERT_UNCATEGORIZED(__n >= 0 || __has_bidirectional_iterator_category<_InputIter>::value,
70                                "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
71   _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
72 }
73 
74 #if _LIBCPP_STD_VER >= 20
75 
76 // [range.iter.op.advance]
77 
78 namespace ranges {
79 namespace __advance {
80 
81 struct __fn {
82 private:
83   template <class _Ip>
84   _LIBCPP_HIDE_FROM_ABI
85   static constexpr void __advance_forward(_Ip& __i, iter_difference_t<_Ip> __n) {
86     while (__n > 0) {
87       --__n;
88       ++__i;
89     }
90   }
91 
92   template <class _Ip>
93   _LIBCPP_HIDE_FROM_ABI
94   static constexpr void __advance_backward(_Ip& __i, iter_difference_t<_Ip> __n) {
95     while (__n < 0) {
96       ++__n;
97       --__i;
98     }
99   }
100 
101 public:
102   // Preconditions: If `I` does not model `bidirectional_iterator`, `n` is not negative.
103   template <input_or_output_iterator _Ip>
104   _LIBCPP_HIDE_FROM_ABI
105   constexpr void operator()(_Ip& __i, iter_difference_t<_Ip> __n) const {
106     _LIBCPP_ASSERT_UNCATEGORIZED(__n >= 0 || bidirectional_iterator<_Ip>,
107                                  "If `n < 0`, then `bidirectional_iterator<I>` must be true.");
108 
109     // If `I` models `random_access_iterator`, equivalent to `i += n`.
110     if constexpr (random_access_iterator<_Ip>) {
111       __i += __n;
112       return;
113     } else if constexpr (bidirectional_iterator<_Ip>) {
114       // Otherwise, if `n` is non-negative, increments `i` by `n`.
115       __advance_forward(__i, __n);
116       // Otherwise, decrements `i` by `-n`.
117       __advance_backward(__i, __n);
118       return;
119     } else {
120       // Otherwise, if `n` is non-negative, increments `i` by `n`.
121       __advance_forward(__i, __n);
122       return;
123     }
124   }
125 
126   // Preconditions: Either `assignable_from<I&, S> || sized_sentinel_for<S, I>` is modeled, or [i, bound_sentinel) denotes a range.
127   template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
128   _LIBCPP_HIDE_FROM_ABI constexpr void operator()(_Ip& __i, _Sp __bound_sentinel) const {
129     // If `I` and `S` model `assignable_from<I&, S>`, equivalent to `i = std::move(bound_sentinel)`.
130     if constexpr (assignable_from<_Ip&, _Sp>) {
131       __i = _VSTD::move(__bound_sentinel);
132     }
133     // Otherwise, if `S` and `I` model `sized_sentinel_for<S, I>`, equivalent to `ranges::advance(i, bound_sentinel - i)`.
134     else if constexpr (sized_sentinel_for<_Sp, _Ip>) {
135       (*this)(__i, __bound_sentinel - __i);
136     }
137     // Otherwise, while `bool(i != bound_sentinel)` is true, increments `i`.
138     else {
139       while (__i != __bound_sentinel) {
140         ++__i;
141       }
142     }
143   }
144 
145   // Preconditions:
146   //   * If `n > 0`, [i, bound_sentinel) denotes a range.
147   //   * If `n == 0`, [i, bound_sentinel) or [bound_sentinel, i) denotes a range.
148   //   * If `n < 0`, [bound_sentinel, i) denotes a range, `I` models `bidirectional_iterator`, and `I` and `S` model `same_as<I, S>`.
149   // Returns: `n - M`, where `M` is the difference between the ending and starting position.
150   template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
151   _LIBCPP_HIDE_FROM_ABI constexpr iter_difference_t<_Ip> operator()(_Ip& __i, iter_difference_t<_Ip> __n,
152                                                                     _Sp __bound_sentinel) const {
153     _LIBCPP_ASSERT_UNCATEGORIZED((__n >= 0) || (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>),
154                                  "If `n < 0`, then `bidirectional_iterator<I> && same_as<I, S>` must be true.");
155     // If `S` and `I` model `sized_sentinel_for<S, I>`:
156     if constexpr (sized_sentinel_for<_Sp, _Ip>) {
157       // If |n| >= |bound_sentinel - i|, equivalent to `ranges::advance(i, bound_sentinel)`.
158       // __magnitude_geq(a, b) returns |a| >= |b|, assuming they have the same sign.
159       auto __magnitude_geq = [](auto __a, auto __b) {
160         return __a == 0 ? __b == 0 :
161                __a > 0  ? __a >= __b :
162                           __a <= __b;
163       };
164       if (const auto __m = __bound_sentinel - __i; __magnitude_geq(__n, __m)) {
165         (*this)(__i, __bound_sentinel);
166         return __n - __m;
167       }
168 
169       // Otherwise, equivalent to `ranges::advance(i, n)`.
170       (*this)(__i, __n);
171       return 0;
172     } else {
173       // Otherwise, if `n` is non-negative, while `bool(i != bound_sentinel)` is true, increments `i` but at
174       // most `n` times.
175       while (__i != __bound_sentinel && __n > 0) {
176         ++__i;
177         --__n;
178       }
179 
180       // Otherwise, while `bool(i != bound_sentinel)` is true, decrements `i` but at most `-n` times.
181       if constexpr (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) {
182         while (__i != __bound_sentinel && __n < 0) {
183           --__i;
184           ++__n;
185         }
186       }
187       return __n;
188     }
189 
190     __libcpp_unreachable();
191   }
192 };
193 
194 } // namespace __advance
195 
196 inline namespace __cpo {
197   inline constexpr auto advance = __advance::__fn{};
198 } // namespace __cpo
199 } // namespace ranges
200 
201 #endif // _LIBCPP_STD_VER >= 20
202 
203 _LIBCPP_END_NAMESPACE_STD
204 
205 _LIBCPP_POP_MACROS
206 
207 #endif // _LIBCPP___ITERATOR_ADVANCE_H
208