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// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
12
13// template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
14// indirect_unary_predicate<projected<I, Proj>> Pred>
15// constexpr subrange<I> ranges::find_last_if(I first, S last, Pred pred, Proj proj = {});
16// template<forward_range R, class Proj = identity,
17// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
18// constexpr borrowed_subrange_t<R> ranges::find_last_if(R&& r, Pred pred, Proj proj = {});
19
20#include <algorithm>
21#include <array>
22#include <cassert>
23#include <ranges>
24
25#include "almost_satisfies_types.h"
26#include "test_iterators.h"
27
28struct Predicate {
29 bool operator()(int);
30};
31
32template <class It, class Sent = It>
33concept HasFindLastIfIt = requires(It it, Sent sent) { std::ranges::find_last_if(it, sent, Predicate{}); };
34static_assert(HasFindLastIfIt<int*>);
35static_assert(HasFindLastIfIt<forward_iterator<int*>>);
36static_assert(!HasFindLastIfIt<cpp20_input_iterator<int*>>);
37static_assert(!HasFindLastIfIt<ForwardIteratorNotDerivedFrom>);
38static_assert(!HasFindLastIfIt<ForwardIteratorNotIncrementable>);
39static_assert(!HasFindLastIfIt<forward_iterator<int*>, SentinelForNotSemiregular>);
40static_assert(!HasFindLastIfIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
41
42static_assert(!HasFindLastIfIt<int*, int>);
43static_assert(!HasFindLastIfIt<int, int*>);
44
45template <class Pred>
46concept HasFindLastIfPred = requires(int* it, Pred pred) { std::ranges::find_last_if(it, it, pred); };
47
48static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotCopyConstructible>);
49static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotPredicate>);
50
51template <class R>
52concept HasFindLastIfR = requires(R r) { std::ranges::find_last_if(r, Predicate{}); };
53static_assert(HasFindLastIfR<std::array<int, 0>>);
54static_assert(!HasFindLastIfR<int>);
55static_assert(!HasFindLastIfR<ForwardRangeNotDerivedFrom>);
56static_assert(!HasFindLastIfR<ForwardRangeNotIncrementable>);
57static_assert(!HasFindLastIfR<ForwardRangeNotSentinelSemiregular>);
58static_assert(!HasFindLastIfR<ForwardRangeNotSentinelEqualityComparableWith>);
59
60template <class It, class Sent>
61constexpr auto make_range(auto& a) {
62 return std::ranges::subrange(It(std::ranges::begin(a)), Sent(It(std::ranges::end(a))));
63}
64
65template <template <class> class IteratorT, template <class> class SentinelT>
66constexpr void test_iterator_classes() {
67 {
68 using it = IteratorT<int*>;
69 using sent = SentinelT<it>;
70
71 {
72 int a[] = {1, 2, 3, 4};
73 std::same_as<std::ranges::subrange<it>> auto ret =
74 std::ranges::find_last_if(it(a), sent(it(a + 4)), [](int x) { return x == 4; });
75 assert(base(ret.begin()) == a + 3);
76 assert(*ret.begin() == 4);
77 }
78 {
79 int a[] = {1, 2, 3, 4};
80
81 std::same_as<std::ranges::subrange<it>> auto ret =
82 std::ranges::find_last_if(make_range<it, sent>(a), [](int x) { return x == 4; });
83 assert(ret.begin() == it(a + 3));
84 assert(*ret.begin() == 4);
85 }
86 }
87
88 { // check that an empty range works
89 using it = IteratorT<std::ranges::iterator_t<std::array<int, 0>&>>;
90 using sent = SentinelT<it>;
91
92 {
93 std::array<int, 0> a = {};
94
95 auto ret = std::ranges::find_last_if(it(a.begin()), sent(it(a.end())), [](auto&&) { return true; }).begin();
96 assert(ret == it(a.end()));
97 }
98 {
99 std::array<int, 0> a = {};
100
101 auto ret = std::ranges::find_last_if(make_range<it, sent>(a), [](auto&&) { return true; }).begin();
102 assert(ret == it(a.end()));
103 }
104 }
105
106 { // check that last is returned with no match
107 using it = IteratorT<int*>;
108 using sent = SentinelT<it>;
109
110 {
111 int a[] = {1, 1, 1};
112
113 auto ret = std::ranges::find_last_if(it(a), sent(it(a + 3)), [](auto&&) { return false; }).begin();
114 assert(ret == it(a + 3));
115 }
116 {
117 int a[] = {1, 1, 1};
118
119 auto ret = std::ranges::find_last_if(make_range<it, sent>(a), [](auto&&) { return false; }).begin();
120 assert(ret == it(a + 3));
121 }
122 }
123
124 { // check that the last element is returned
125 struct S {
126 int comp;
127 int other;
128 };
129 using it = IteratorT<S*>;
130 using sent = SentinelT<it>;
131
132 S a[] = {{0, 0}, {0, 2}, {0, 1}};
133
134 auto ret = std::ranges::find_last_if(
135 it(std::begin(a)), sent(it(std::end(a))), [](int c) { return c == 0; }, &S::comp)
136 .begin();
137 assert(ret == it(a + 2));
138 assert((*ret).comp == 0);
139 assert((*ret).other == 1);
140 }
141
142 {
143 // count projection and predicate invocation count
144 {
145 int a[] = {1, 2, 3, 4};
146 int predicate_count = 0;
147 int projection_count = 0;
148
149 using it = IteratorT<int*>;
150 using sent = SentinelT<it>;
151
152 auto ret =
153 std::ranges::find_last_if(
154 it(a),
155 sent(it(a + 4)),
156 [&](int i) {
157 ++predicate_count;
158 return i == 2;
159 },
160 [&](int i) {
161 ++projection_count;
162 return i;
163 })
164 .begin();
165 assert(ret == it(a + 1));
166 assert(*ret == 2);
167
168 if constexpr (std::bidirectional_iterator<it>) {
169 assert(predicate_count == 3);
170 assert(projection_count == 3);
171 } else {
172 assert(predicate_count == 4);
173 assert(projection_count == 4);
174 }
175 }
176 }
177}
178
179struct NonConstComparable {
180 friend constexpr bool operator==(const NonConstComparable&, const NonConstComparable&) { return false; }
181 friend constexpr bool operator==(NonConstComparable&, NonConstComparable&) { return false; }
182 friend constexpr bool operator==(const NonConstComparable&, NonConstComparable&) { return false; }
183 friend constexpr bool operator==(NonConstComparable&, const NonConstComparable&) { return true; }
184};
185
186// TODO: this should really use `std::const_iterator`
187template <class T>
188struct add_const_to_ptr {
189 using type = T;
190};
191template <class T>
192struct add_const_to_ptr<T*> {
193 using type = const T*;
194};
195template <class T>
196using add_const_to_ptr_t = typename add_const_to_ptr<T>::type;
197
198constexpr bool test() {
199 test_iterator_classes<std::type_identity_t, std::type_identity_t>();
200 test_iterator_classes<add_const_to_ptr_t, std::type_identity_t>();
201 test_iterator_classes<contiguous_iterator, std::type_identity_t>();
202 test_iterator_classes<random_access_iterator, std::type_identity_t>();
203 test_iterator_classes<bidirectional_iterator, std::type_identity_t>();
204 test_iterator_classes<forward_iterator, std::type_identity_t>();
205 test_iterator_classes<forward_iterator, sentinel_wrapper>();
206
207 {
208 // check that projections are used properly and that they are called with the iterator directly
209 {
210 int a[] = {1, 2, 3, 4};
211 auto ret =
212 std::ranges::find_last_if(a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }).begin();
213 assert(ret == a + 3);
214 }
215 {
216 int a[] = {1, 2, 3, 4};
217 auto ret = std::ranges::find_last_if(a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }).begin();
218 assert(ret == a + 3);
219 }
220 }
221
222 {
223 // check that ranges::dangling is returned
224 [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret =
225 std::ranges::find_last_if(std::array{1, 2}, [](int) { return false; });
226 }
227
228 {
229 // check that a subrange is returned with a borrowing range
230 int a[] = {1, 2, 3, 4};
231 std::same_as<std::ranges::subrange<int*>> auto ret =
232 std::ranges::find_last_if(std::views::all(a), [](int) { return true; });
233 assert(ret.begin() == a + 3);
234 assert(*ret.begin() == 4);
235 }
236
237 {
238 // check that the return type of `iter::operator*` doesn't change
239 {
240 NonConstComparable a[] = {NonConstComparable{}};
241
242 auto ret = std::ranges::find_last_if(a, a + 1, [](auto&& e) { return e == NonConstComparable{}; }).begin();
243 assert(ret == a);
244 }
245 {
246 NonConstComparable a[] = {NonConstComparable{}};
247
248 auto ret = std::ranges::find_last_if(a, [](auto&& e) { return e == NonConstComparable{}; }).begin();
249 assert(ret == a);
250 }
251 }
252
253 return true;
254}
255
256int main(int, char**) {
257 test();
258 static_assert(test());
259
260 return 0;
261}
262

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.find.last/ranges.find_last_if.pass.cpp