master
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/forward.h>
25#include <__utility/move.h>
26
27#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
28# pragma GCC system_header
29#endif
30
31_LIBCPP_PUSH_MACROS
32#include <__undef_macros>
33
34#if _LIBCPP_STD_VER >= 23
35
36_LIBCPP_BEGIN_NAMESPACE_STD
37
38namespace ranges {
39
40template <class _Iter, class _Sent, class _Pred, class _Proj>
41_LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
42__find_last_impl(_Iter __first, _Sent __last, _Pred __pred, _Proj& __proj) {
43 if (__first == __last) {
44 return subrange<_Iter>(__first, __first);
45 }
46
47 if constexpr (bidirectional_iterator<_Iter>) {
48 auto __last_it = ranges::next(__first, __last);
49 for (auto __it = ranges::prev(__last_it); __it != __first; --__it) {
50 if (__pred(std::invoke(__proj, *__it))) {
51 return subrange<_Iter>(std::move(__it), std::move(__last_it));
52 }
53 }
54 if (__pred(std::invoke(__proj, *__first))) {
55 return subrange<_Iter>(std::move(__first), std::move(__last_it));
56 }
57 return subrange<_Iter>(__last_it, __last_it);
58 } else {
59 bool __found = false;
60 _Iter __found_it;
61 for (; __first != __last; ++__first) {
62 if (__pred(std::invoke(__proj, *__first))) {
63 __found = true;
64 __found_it = __first;
65 }
66 }
67
68 if (__found) {
69 return subrange<_Iter>(std::move(__found_it), std::move(__first));
70 } else {
71 return subrange<_Iter>(__first, __first);
72 }
73 }
74}
75
76struct __find_last {
77 template <class _Type>
78 struct __op {
79 const _Type& __value;
80 template <class _Elem>
81 _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>
89 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>
96 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
101struct __find_last_if {
102 template <class _Pred>
103 struct __op {
104 _Pred& __pred;
105 template <class _Elem>
106 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
107 return std::invoke(__pred, std::forward<_Elem>(__elem));
108 }
109 };
110
111 template <forward_iterator _Iter,
112 sentinel_for<_Iter> _Sent,
113 class _Proj = identity,
114 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
115 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
116 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) {
117 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj);
118 }
119
120 template <forward_range _Range,
121 class _Proj = identity,
122 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
123 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
124 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) {
125 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj);
126 }
127};
128
129struct __find_last_if_not {
130 template <class _Pred>
131 struct __op {
132 _Pred& __pred;
133 template <class _Elem>
134 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
135 return !std::invoke(__pred, std::forward<_Elem>(__elem));
136 }
137 };
138
139 template <forward_iterator _Iter,
140 sentinel_for<_Iter> _Sent,
141 class _Proj = identity,
142 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
143 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
144 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) {
145 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj);
146 }
147
148 template <forward_range _Range,
149 class _Proj = identity,
150 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
151 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
152 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) {
153 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj);
154 }
155};
156
157inline namespace __cpo {
158inline constexpr auto find_last = __find_last{};
159inline constexpr auto find_last_if = __find_last_if{};
160inline constexpr auto find_last_if_not = __find_last_if_not{};
161} // namespace __cpo
162} // namespace ranges
163
164_LIBCPP_END_NAMESPACE_STD
165
166#endif // _LIBCPP_STD_VER >= 23
167
168_LIBCPP_POP_MACROS
169
170#endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H