1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H
10 #define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H
11
12 #include <__config>
13 #include <__functional/identity.h>
14 #include <__functional/invoke.h>
15 #include <__functional/ranges_operations.h>
16 #include <__iterator/concepts.h>
17 #include <__iterator/indirectly_comparable.h>
18 #include <__iterator/next.h>
19 #include <__iterator/prev.h>
20 #include <__iterator/projected.h>
21 #include <__ranges/access.h>
22 #include <__ranges/concepts.h>
23 #include <__ranges/subrange.h>
24 #include <__utility/move.h>
25
26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
27 # pragma GCC system_header
28 #endif
29
30 _LIBCPP_PUSH_MACROS
31 #include <__undef_macros>
32
33 #if _LIBCPP_STD_VER >= 23
34
35 _LIBCPP_BEGIN_NAMESPACE_STD
36
37 namespace ranges {
38
39 template <class _Iter, class _Sent, class _Pred, class _Proj>
40 _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
__find_last_impl(_Iter __first,_Sent __last,_Pred __pred,_Proj & __proj)41 __find_last_impl(_Iter __first, _Sent __last, _Pred __pred, _Proj& __proj) {
42 if (__first == __last) {
43 return subrange<_Iter>(__first, __first);
44 }
45
46 if constexpr (bidirectional_iterator<_Iter>) {
47 auto __last_it = ranges::next(__first, __last);
48 for (auto __it = ranges::prev(__last_it); __it != __first; --__it) {
49 if (__pred(std::invoke(__proj, *__it))) {
50 return subrange<_Iter>(std::move(__it), std::move(__last_it));
51 }
52 }
53 if (__pred(std::invoke(__proj, *__first))) {
54 return subrange<_Iter>(std::move(__first), std::move(__last_it));
55 }
56 return subrange<_Iter>(__last_it, __last_it);
57 } else {
58 bool __found = false;
59 _Iter __found_it;
60 for (; __first != __last; ++__first) {
61 if (__pred(std::invoke(__proj, *__first))) {
62 __found = true;
63 __found_it = __first;
64 }
65 }
66
67 if (__found) {
68 return subrange<_Iter>(std::move(__found_it), std::move(__first));
69 } else {
70 return subrange<_Iter>(__first, __first);
71 }
72 }
73 }
74
75 namespace __find_last {
76 struct __fn {
77 template <class _Type>
78 struct __op {
79 const _Type& __value;
80 template <class _Elem>
decltype__fn::__op81 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
82 return std::forward<_Elem>(__elem) == __value;
83 }
84 };
85
86 template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity>
87 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*>
88 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
operator__fn89 operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) {
90 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Type>{__value}, __proj);
91 }
92
93 template <forward_range _Range, class _Type, class _Proj = identity>
94 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
95 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
operator__fn96 operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) {
97 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Type>{__value}, __proj);
98 }
99 };
100 } // namespace __find_last
101
102 namespace __find_last_if {
103 struct __fn {
104 template <class _Pred>
105 struct __op {
106 _Pred& __pred;
107 template <class _Elem>
decltype__fn::__op108 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
109 return std::invoke(__pred, std::forward<_Elem>(__elem));
110 }
111 };
112
113 template <forward_iterator _Iter,
114 sentinel_for<_Iter> _Sent,
115 class _Proj = identity,
116 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
117 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
operator__fn118 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) {
119 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj);
120 }
121
122 template <forward_range _Range,
123 class _Proj = identity,
124 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
125 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
operator__fn126 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) {
127 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj);
128 }
129 };
130 } // namespace __find_last_if
131
132 namespace __find_last_if_not {
133 struct __fn {
134 template <class _Pred>
135 struct __op {
136 _Pred& __pred;
137 template <class _Elem>
decltype__fn::__op138 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
139 return !std::invoke(__pred, std::forward<_Elem>(__elem));
140 }
141 };
142
143 template <forward_iterator _Iter,
144 sentinel_for<_Iter> _Sent,
145 class _Proj = identity,
146 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
147 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
operator__fn148 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) {
149 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj);
150 }
151
152 template <forward_range _Range,
153 class _Proj = identity,
154 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
155 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
operator__fn156 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) {
157 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj);
158 }
159 };
160 } // namespace __find_last_if_not
161
162 inline namespace __cpo {
163 inline constexpr auto find_last = __find_last::__fn{};
164 inline constexpr auto find_last_if = __find_last_if::__fn{};
165 inline constexpr auto find_last_if_not = __find_last_if_not::__fn{};
166 } // namespace __cpo
167 } // namespace ranges
168
169 _LIBCPP_END_NAMESPACE_STD
170
171 #endif // _LIBCPP_STD_VER >= 23
172
173 _LIBCPP_POP_MACROS
174
175 #endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H
176