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