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