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