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___RANGES_REVERSE_VIEW_H
11#define _LIBCPP___RANGES_REVERSE_VIEW_H
12
13#include <__concepts/constructible.h>
14#include <__config>
15#include <__iterator/concepts.h>
16#include <__iterator/next.h>
17#include <__iterator/reverse_iterator.h>
18#include <__ranges/access.h>
19#include <__ranges/all.h>
20#include <__ranges/concepts.h>
21#include <__ranges/enable_borrowed_range.h>
22#include <__ranges/non_propagating_cache.h>
23#include <__ranges/range_adaptor.h>
24#include <__ranges/size.h>
25#include <__ranges/subrange.h>
26#include <__ranges/view_interface.h>
27#include <__type_traits/conditional.h>
28#include <__type_traits/remove_cvref.h>
29#include <__utility/forward.h>
30#include <__utility/move.h>
31
32#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
33# pragma GCC system_header
34#endif
35
36_LIBCPP_PUSH_MACROS
37#include <__undef_macros>
38
39_LIBCPP_BEGIN_NAMESPACE_STD
40
41#if _LIBCPP_STD_VER >= 20
42
43namespace ranges {
44template <view _View>
45 requires bidirectional_range<_View>
46class reverse_view : public view_interface<reverse_view<_View>> {
47 // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an
48 // amortized O(1) begin() method.
49 static constexpr bool _UseCache = !random_access_range<_View> && !common_range<_View>;
50 using _Cache _LIBCPP_NODEBUG =
51 _If<_UseCache, __non_propagating_cache<reverse_iterator<iterator_t<_View>>>, __empty_cache>;
52 _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache();
53 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
54
55public:
56 _LIBCPP_HIDE_FROM_ABI reverse_view()
57 requires default_initializable<_View>
58 = default;
59
60 _LIBCPP_HIDE_FROM_ABI constexpr explicit reverse_view(_View __view) : __base_(std::move(__view)) {}
61
62 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
63 requires copy_constructible<_View>
64 {
65 return __base_;
66 }
67
68 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
69
70 _LIBCPP_HIDE_FROM_ABI constexpr reverse_iterator<iterator_t<_View>> begin() {
71 if constexpr (_UseCache)
72 if (__cached_begin_.__has_value())
73 return *__cached_begin_;
74
75 auto __tmp = std::make_reverse_iterator(ranges::next(ranges::begin(__base_), ranges::end(__base_)));
76 if constexpr (_UseCache)
77 __cached_begin_.__emplace(__tmp);
78 return __tmp;
79 }
80
81 _LIBCPP_HIDE_FROM_ABI constexpr reverse_iterator<iterator_t<_View>> begin()
82 requires common_range<_View>
83 {
84 return std::make_reverse_iterator(ranges::end(__base_));
85 }
86
87 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
88 requires common_range<const _View>
89 {
90 return std::make_reverse_iterator(ranges::end(__base_));
91 }
92
93 _LIBCPP_HIDE_FROM_ABI constexpr reverse_iterator<iterator_t<_View>> end() {
94 return std::make_reverse_iterator(ranges::begin(__base_));
95 }
96
97 _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
98 requires common_range<const _View>
99 {
100 return std::make_reverse_iterator(ranges::begin(__base_));
101 }
102
103 _LIBCPP_HIDE_FROM_ABI constexpr auto size()
104 requires sized_range<_View>
105 {
106 return ranges::size(__base_);
107 }
108
109 _LIBCPP_HIDE_FROM_ABI constexpr auto size() const
110 requires sized_range<const _View>
111 {
112 return ranges::size(__base_);
113 }
114};
115
116template <class _Range>
117reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
118
119template <class _Tp>
120inline constexpr bool enable_borrowed_range<reverse_view<_Tp>> = enable_borrowed_range<_Tp>;
121
122namespace views {
123namespace __reverse {
124template <class _Tp>
125inline constexpr bool __is_reverse_view = false;
126
127template <class _Tp>
128inline constexpr bool __is_reverse_view<reverse_view<_Tp>> = true;
129
130template <class _Tp>
131inline constexpr bool __is_sized_reverse_subrange = false;
132
133template <class _Iter>
134inline constexpr bool
135 __is_sized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, subrange_kind::sized>> =
136 true;
137
138template <class _Tp>
139inline constexpr bool __is_unsized_reverse_subrange = false;
140
141template <class _Iter, subrange_kind _Kind>
142inline constexpr bool __is_unsized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> =
143 _Kind == subrange_kind::unsized;
144
145template <class _Tp>
146struct __unwrapped_reverse_subrange {
147 using type _LIBCPP_NODEBUG =
148 void; // avoid SFINAE-ing out the overload below -- let the concept requirements do it for better diagnostics
149};
150
151template <class _Iter, subrange_kind _Kind>
152struct __unwrapped_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> {
153 using type _LIBCPP_NODEBUG = subrange<_Iter, _Iter, _Kind>;
154};
155
156struct __fn : __range_adaptor_closure<__fn> {
157 template <class _Range>
158 requires __is_reverse_view<remove_cvref_t<_Range>>
159 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
160 noexcept(noexcept(std::forward<_Range>(__range).base())) -> decltype(std::forward<_Range>(__range).base()) {
161 return std::forward<_Range>(__range).base();
162 }
163
164 template <class _Range,
165 class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type>
166 requires __is_sized_reverse_subrange<remove_cvref_t<_Range>>
167 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
168 noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size())))
169 -> decltype(_UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size())) {
170 return _UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size());
171 }
172
173 template <class _Range,
174 class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type>
175 requires __is_unsized_reverse_subrange<remove_cvref_t<_Range>>
176 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
177 noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base())))
178 -> decltype(_UnwrappedSubrange(__range.end().base(), __range.begin().base())) {
179 return _UnwrappedSubrange(__range.end().base(), __range.begin().base());
180 }
181
182 template <class _Range>
183 requires(!__is_reverse_view<remove_cvref_t<_Range>> && !__is_sized_reverse_subrange<remove_cvref_t<_Range>> &&
184 !__is_unsized_reverse_subrange<remove_cvref_t<_Range>>)
185 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const noexcept(noexcept(reverse_view{
186 std::forward<_Range>(__range)})) -> decltype(reverse_view{std::forward<_Range>(__range)}) {
187 return reverse_view{std::forward<_Range>(__range)};
188 }
189};
190} // namespace __reverse
191
192inline namespace __cpo {
193inline constexpr auto reverse = __reverse::__fn{};
194} // namespace __cpo
195} // namespace views
196} // namespace ranges
197
198#endif // _LIBCPP_STD_VER >= 20
199
200_LIBCPP_END_NAMESPACE_STD
201
202_LIBCPP_POP_MACROS
203
204#endif // _LIBCPP___RANGES_REVERSE_VIEW_H
205