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_REVERSE_ITERATOR_H |
11 | #define _LIBCPP___ITERATOR_REVERSE_ITERATOR_H |
12 | |
13 | #include <__algorithm/unwrap_iter.h> |
14 | #include <__compare/compare_three_way_result.h> |
15 | #include <__compare/three_way_comparable.h> |
16 | #include <__concepts/convertible_to.h> |
17 | #include <__config> |
18 | #include <__iterator/concepts.h> |
19 | #include <__iterator/incrementable_traits.h> |
20 | #include <__iterator/iter_move.h> |
21 | #include <__iterator/iter_swap.h> |
22 | #include <__iterator/iterator.h> |
23 | #include <__iterator/iterator_traits.h> |
24 | #include <__iterator/prev.h> |
25 | #include <__iterator/readable_traits.h> |
26 | #include <__memory/addressof.h> |
27 | #include <__utility/move.h> |
28 | #include <type_traits> |
29 | |
30 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
31 | # pragma GCC system_header |
32 | #endif |
33 | |
34 | _LIBCPP_BEGIN_NAMESPACE_STD |
35 | |
36 | _LIBCPP_SUPPRESS_DEPRECATED_PUSH |
37 | template <class _Iter> |
38 | class _LIBCPP_TEMPLATE_VIS reverse_iterator |
39 | #if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) |
40 | : public iterator<typename iterator_traits<_Iter>::iterator_category, |
41 | typename iterator_traits<_Iter>::value_type, |
42 | typename iterator_traits<_Iter>::difference_type, |
43 | typename iterator_traits<_Iter>::pointer, |
44 | typename iterator_traits<_Iter>::reference> |
45 | #endif |
46 | { |
47 | _LIBCPP_SUPPRESS_DEPRECATED_POP |
48 | private: |
49 | #ifndef _LIBCPP_ABI_NO_ITERATOR_BASES |
50 | _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break |
51 | #endif |
52 | |
53 | #if _LIBCPP_STD_VER > 17 |
54 | static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value || bidirectional_iterator<_Iter>, |
55 | "reverse_iterator<It> requires It to be a bidirectional iterator." ); |
56 | #endif // _LIBCPP_STD_VER > 17 |
57 | |
58 | protected: |
59 | _Iter current; |
60 | public: |
61 | using iterator_type = _Iter; |
62 | |
63 | using iterator_category = _If<__is_cpp17_random_access_iterator<_Iter>::value, |
64 | random_access_iterator_tag, |
65 | typename iterator_traits<_Iter>::iterator_category>; |
66 | using pointer = typename iterator_traits<_Iter>::pointer; |
67 | #if _LIBCPP_STD_VER > 17 |
68 | using iterator_concept = _If<__is_cpp17_random_access_iterator<_Iter>::value, |
69 | random_access_iterator_tag, |
70 | bidirectional_iterator_tag>; |
71 | using value_type = iter_value_t<_Iter>; |
72 | using difference_type = iter_difference_t<_Iter>; |
73 | using reference = iter_reference_t<_Iter>; |
74 | #else |
75 | using value_type = typename iterator_traits<_Iter>::value_type; |
76 | using difference_type = typename iterator_traits<_Iter>::difference_type; |
77 | using reference = typename iterator_traits<_Iter>::reference; |
78 | #endif |
79 | |
80 | #ifndef _LIBCPP_ABI_NO_ITERATOR_BASES |
81 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
82 | reverse_iterator() : __t(), current() {} |
83 | |
84 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
85 | explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {} |
86 | |
87 | template <class _Up, class = __enable_if_t< |
88 | !is_same<_Up, _Iter>::value && is_convertible<_Up const&, _Iter>::value |
89 | > > |
90 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
91 | reverse_iterator(const reverse_iterator<_Up>& __u) |
92 | : __t(__u.base()), current(__u.base()) |
93 | { } |
94 | |
95 | template <class _Up, class = __enable_if_t< |
96 | !is_same<_Up, _Iter>::value && |
97 | is_convertible<_Up const&, _Iter>::value && |
98 | is_assignable<_Iter&, _Up const&>::value |
99 | > > |
100 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
101 | reverse_iterator& operator=(const reverse_iterator<_Up>& __u) { |
102 | __t = current = __u.base(); |
103 | return *this; |
104 | } |
105 | #else |
106 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
107 | reverse_iterator() : current() {} |
108 | |
109 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
110 | explicit reverse_iterator(_Iter __x) : current(__x) {} |
111 | |
112 | template <class _Up, class = __enable_if_t< |
113 | !is_same<_Up, _Iter>::value && is_convertible<_Up const&, _Iter>::value |
114 | > > |
115 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
116 | reverse_iterator(const reverse_iterator<_Up>& __u) |
117 | : current(__u.base()) |
118 | { } |
119 | |
120 | template <class _Up, class = __enable_if_t< |
121 | !is_same<_Up, _Iter>::value && |
122 | is_convertible<_Up const&, _Iter>::value && |
123 | is_assignable<_Iter&, _Up const&>::value |
124 | > > |
125 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
126 | reverse_iterator& operator=(const reverse_iterator<_Up>& __u) { |
127 | current = __u.base(); |
128 | return *this; |
129 | } |
130 | #endif |
131 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
132 | _Iter base() const {return current;} |
133 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
134 | reference operator*() const {_Iter __tmp = current; return *--__tmp;} |
135 | |
136 | #if _LIBCPP_STD_VER > 17 |
137 | _LIBCPP_INLINE_VISIBILITY |
138 | constexpr pointer operator->() const |
139 | requires is_pointer_v<_Iter> || requires(const _Iter __i) { __i.operator->(); } |
140 | { |
141 | if constexpr (is_pointer_v<_Iter>) { |
142 | return std::prev(current); |
143 | } else { |
144 | return std::prev(current).operator->(); |
145 | } |
146 | } |
147 | #else |
148 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
149 | pointer operator->() const { |
150 | return std::addressof(operator*()); |
151 | } |
152 | #endif // _LIBCPP_STD_VER > 17 |
153 | |
154 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
155 | reverse_iterator& operator++() {--current; return *this;} |
156 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
157 | reverse_iterator operator++(int) {reverse_iterator __tmp(*this); --current; return __tmp;} |
158 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
159 | reverse_iterator& operator--() {++current; return *this;} |
160 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
161 | reverse_iterator operator--(int) {reverse_iterator __tmp(*this); ++current; return __tmp;} |
162 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
163 | reverse_iterator operator+(difference_type __n) const {return reverse_iterator(current - __n);} |
164 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
165 | reverse_iterator& operator+=(difference_type __n) {current -= __n; return *this;} |
166 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
167 | reverse_iterator operator-(difference_type __n) const {return reverse_iterator(current + __n);} |
168 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
169 | reverse_iterator& operator-=(difference_type __n) {current += __n; return *this;} |
170 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
171 | reference operator[](difference_type __n) const {return *(*this + __n);} |
172 | |
173 | #if _LIBCPP_STD_VER > 17 |
174 | _LIBCPP_HIDE_FROM_ABI friend constexpr |
175 | iter_rvalue_reference_t<_Iter> iter_move(const reverse_iterator& __i) |
176 | noexcept(is_nothrow_copy_constructible_v<_Iter> && |
177 | noexcept(ranges::iter_move(--declval<_Iter&>()))) { |
178 | auto __tmp = __i.base(); |
179 | return ranges::iter_move(--__tmp); |
180 | } |
181 | |
182 | template <indirectly_swappable<_Iter> _Iter2> |
183 | _LIBCPP_HIDE_FROM_ABI friend constexpr |
184 | void iter_swap(const reverse_iterator& __x, const reverse_iterator<_Iter2>& __y) |
185 | noexcept(is_nothrow_copy_constructible_v<_Iter> && |
186 | is_nothrow_copy_constructible_v<_Iter2> && |
187 | noexcept(ranges::iter_swap(--declval<_Iter&>(), --declval<_Iter2&>()))) { |
188 | auto __xtmp = __x.base(); |
189 | auto __ytmp = __y.base(); |
190 | ranges::iter_swap(--__xtmp, --__ytmp); |
191 | } |
192 | #endif // _LIBCPP_STD_VER > 17 |
193 | }; |
194 | |
195 | template <class _Iter1, class _Iter2> |
196 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
197 | bool |
198 | operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
199 | #if _LIBCPP_STD_VER > 17 |
200 | requires requires { |
201 | { __x.base() == __y.base() } -> convertible_to<bool>; |
202 | } |
203 | #endif // _LIBCPP_STD_VER > 17 |
204 | { |
205 | return __x.base() == __y.base(); |
206 | } |
207 | |
208 | template <class _Iter1, class _Iter2> |
209 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
210 | bool |
211 | operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
212 | #if _LIBCPP_STD_VER > 17 |
213 | requires requires { |
214 | { __x.base() > __y.base() } -> convertible_to<bool>; |
215 | } |
216 | #endif // _LIBCPP_STD_VER > 17 |
217 | { |
218 | return __x.base() > __y.base(); |
219 | } |
220 | |
221 | template <class _Iter1, class _Iter2> |
222 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
223 | bool |
224 | operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
225 | #if _LIBCPP_STD_VER > 17 |
226 | requires requires { |
227 | { __x.base() != __y.base() } -> convertible_to<bool>; |
228 | } |
229 | #endif // _LIBCPP_STD_VER > 17 |
230 | { |
231 | return __x.base() != __y.base(); |
232 | } |
233 | |
234 | template <class _Iter1, class _Iter2> |
235 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
236 | bool |
237 | operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
238 | #if _LIBCPP_STD_VER > 17 |
239 | requires requires { |
240 | { __x.base() < __y.base() } -> convertible_to<bool>; |
241 | } |
242 | #endif // _LIBCPP_STD_VER > 17 |
243 | { |
244 | return __x.base() < __y.base(); |
245 | } |
246 | |
247 | template <class _Iter1, class _Iter2> |
248 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
249 | bool |
250 | operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
251 | #if _LIBCPP_STD_VER > 17 |
252 | requires requires { |
253 | { __x.base() <= __y.base() } -> convertible_to<bool>; |
254 | } |
255 | #endif // _LIBCPP_STD_VER > 17 |
256 | { |
257 | return __x.base() <= __y.base(); |
258 | } |
259 | |
260 | template <class _Iter1, class _Iter2> |
261 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
262 | bool |
263 | operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
264 | #if _LIBCPP_STD_VER > 17 |
265 | requires requires { |
266 | { __x.base() >= __y.base() } -> convertible_to<bool>; |
267 | } |
268 | #endif // _LIBCPP_STD_VER > 17 |
269 | { |
270 | return __x.base() >= __y.base(); |
271 | } |
272 | |
273 | #if _LIBCPP_STD_VER > 17 |
274 | template <class _Iter1, three_way_comparable_with<_Iter1> _Iter2> |
275 | _LIBCPP_HIDE_FROM_ABI constexpr |
276 | compare_three_way_result_t<_Iter1, _Iter2> |
277 | operator<=>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
278 | { |
279 | return __y.base() <=> __x.base(); |
280 | } |
281 | #endif // _LIBCPP_STD_VER > 17 |
282 | |
283 | #ifndef _LIBCPP_CXX03_LANG |
284 | template <class _Iter1, class _Iter2> |
285 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
286 | auto |
287 | operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
288 | -> decltype(__y.base() - __x.base()) |
289 | { |
290 | return __y.base() - __x.base(); |
291 | } |
292 | #else |
293 | template <class _Iter1, class _Iter2> |
294 | inline _LIBCPP_INLINE_VISIBILITY |
295 | typename reverse_iterator<_Iter1>::difference_type |
296 | operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) |
297 | { |
298 | return __y.base() - __x.base(); |
299 | } |
300 | #endif |
301 | |
302 | template <class _Iter> |
303 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
304 | reverse_iterator<_Iter> |
305 | operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x) |
306 | { |
307 | return reverse_iterator<_Iter>(__x.base() - __n); |
308 | } |
309 | |
310 | #if _LIBCPP_STD_VER > 17 |
311 | template <class _Iter1, class _Iter2> |
312 | requires (!sized_sentinel_for<_Iter1, _Iter2>) |
313 | inline constexpr bool disable_sized_sentinel_for<reverse_iterator<_Iter1>, reverse_iterator<_Iter2>> = true; |
314 | #endif // _LIBCPP_STD_VER > 17 |
315 | |
316 | #if _LIBCPP_STD_VER > 11 |
317 | template <class _Iter> |
318 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
319 | reverse_iterator<_Iter> make_reverse_iterator(_Iter __i) |
320 | { |
321 | return reverse_iterator<_Iter>(__i); |
322 | } |
323 | #endif |
324 | |
325 | template <class _Iter> |
326 | using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >; |
327 | |
328 | template <class _Iter, bool __b> |
329 | struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> { |
330 | static _LIBCPP_CONSTEXPR decltype(std::__unwrap_iter(std::declval<_Iter>())) |
331 | __apply(_ReverseWrapper<_Iter> __i) _NOEXCEPT { |
332 | return std::__unwrap_iter(__i.base().base()); |
333 | } |
334 | }; |
335 | |
336 | template <class _OrigIter, class _UnwrappedIter> |
337 | struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> { |
338 | template <class _Iter> |
339 | struct _ReverseWrapperCount { |
340 | static _LIBCPP_CONSTEXPR const size_t value = 1; |
341 | }; |
342 | |
343 | template <class _Iter> |
344 | struct _ReverseWrapperCount<_ReverseWrapper<_Iter> > { |
345 | static _LIBCPP_CONSTEXPR const size_t value = 1 + _ReverseWrapperCount<_Iter>::value; |
346 | }; |
347 | |
348 | template <size_t _RewrapCount, class _OIter, class _UIter, __enable_if_t<_RewrapCount != 0, int> = 0> |
349 | _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR _ReverseWrapper<_OIter> __rewrap(_ReverseWrapper<_OIter> __iter1, |
350 | _UIter __iter2) { |
351 | return _ReverseWrapper<_OIter>( |
352 | reverse_iterator<_OIter>(__rewrap<_RewrapCount - 1>(__iter1.base().base(), __iter2))); |
353 | } |
354 | |
355 | template <size_t _RewrapCount, class _OIter, class _UIter, __enable_if_t<_RewrapCount == 0, int> = 0> |
356 | _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR decltype(std::__rewrap_iter(std::declval<_OIter>(), |
357 | std::declval<_UIter>())) |
358 | __rewrap(_OIter __iter1, _UIter __iter2) { |
359 | return std::__rewrap_iter(__iter1, __iter2); |
360 | } |
361 | |
362 | _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR _ReverseWrapper<_OrigIter> __apply(_ReverseWrapper<_OrigIter> __iter1, |
363 | _UnwrappedIter __iter2) { |
364 | return __rewrap<_ReverseWrapperCount<_OrigIter>::value>(__iter1, __iter2); |
365 | } |
366 | }; |
367 | |
368 | _LIBCPP_END_NAMESPACE_STD |
369 | |
370 | #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H |
371 | |