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 | // ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare |
14 | // MSVC warning C4242: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data |
15 | // MSVC warning C4244: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data |
16 | // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd4244 |
17 | |
18 | // template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity> |
19 | // requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> |
20 | // constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); |
21 | // template<input_range R, class T, class Proj = identity> |
22 | // requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> |
23 | // constexpr borrowed_iterator_t<R> |
24 | // ranges::find(R&& r, const T& value, Proj proj = {}); |
25 | |
26 | #include <algorithm> |
27 | #include <array> |
28 | #include <cassert> |
29 | #include <deque> |
30 | #include <ranges> |
31 | #include <vector> |
32 | |
33 | #include "almost_satisfies_types.h" |
34 | #include "test_iterators.h" |
35 | |
36 | struct NotEqualityComparable {}; |
37 | |
38 | template <class It, class Sent = It> |
39 | concept HasFindIt = requires(It it, Sent sent) { std::ranges::find(it, sent, *it); }; |
40 | static_assert(HasFindIt<int*>); |
41 | static_assert(!HasFindIt<NotEqualityComparable*>); |
42 | static_assert(!HasFindIt<InputIteratorNotDerivedFrom>); |
43 | static_assert(!HasFindIt<InputIteratorNotIndirectlyReadable>); |
44 | static_assert(!HasFindIt<InputIteratorNotInputOrOutputIterator>); |
45 | static_assert(!HasFindIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); |
46 | static_assert(!HasFindIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); |
47 | |
48 | static_assert(!HasFindIt<int*, int>); |
49 | static_assert(!HasFindIt<int, int*>); |
50 | |
51 | template <class Range, class ValT> |
52 | concept HasFindR = requires(Range r) { std::ranges::find(r, ValT{}); }; |
53 | static_assert(HasFindR<std::array<int, 1>, int>); |
54 | static_assert(!HasFindR<int, int>); |
55 | static_assert(!HasFindR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); |
56 | static_assert(!HasFindR<InputRangeNotDerivedFrom, int>); |
57 | static_assert(!HasFindR<InputRangeNotIndirectlyReadable, int>); |
58 | static_assert(!HasFindR<InputRangeNotInputOrOutputIterator, int>); |
59 | static_assert(!HasFindR<InputRangeNotSentinelSemiregular, int>); |
60 | static_assert(!HasFindR<InputRangeNotSentinelEqualityComparableWith, int>); |
61 | |
62 | static std::vector<int> comparable_data; |
63 | |
64 | template <class It, class Sent = It> |
65 | constexpr void test_iterators() { |
66 | using ValueT = std::iter_value_t<It>; |
67 | { // simple test |
68 | { |
69 | ValueT a[] = {1, 2, 3, 4}; |
70 | std::same_as<It> auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4); |
71 | assert(base(ret) == a + 3); |
72 | assert(*ret == 4); |
73 | } |
74 | { |
75 | ValueT a[] = {1, 2, 3, 4}; |
76 | auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); |
77 | std::same_as<It> auto ret = std::ranges::find(range, 4); |
78 | assert(base(ret) == a + 3); |
79 | assert(*ret == 4); |
80 | } |
81 | } |
82 | |
83 | { // check that an empty range works |
84 | { |
85 | std::array<ValueT, 0> a = {}; |
86 | auto ret = std::ranges::find(It(a.data()), Sent(It(a.data())), 1); |
87 | assert(base(ret) == a.data()); |
88 | } |
89 | { |
90 | std::array<ValueT, 0> a = {}; |
91 | auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data()))); |
92 | auto ret = std::ranges::find(range, 1); |
93 | assert(base(ret) == a.data()); |
94 | } |
95 | } |
96 | |
97 | { // check that last is returned with no match |
98 | { |
99 | ValueT a[] = {1, 1, 1}; |
100 | auto ret = std::ranges::find(a, a + 3, 0); |
101 | assert(ret == a + 3); |
102 | } |
103 | { |
104 | ValueT a[] = {1, 1, 1}; |
105 | auto ret = std::ranges::find(a, 0); |
106 | assert(ret == a + 3); |
107 | } |
108 | } |
109 | |
110 | if (!std::is_constant_evaluated()) |
111 | comparable_data.clear(); |
112 | } |
113 | |
114 | template <class ElementT> |
115 | class TriviallyComparable { |
116 | ElementT el_; |
117 | |
118 | public: |
119 | TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {} |
120 | bool operator==(const TriviallyComparable&) const = default; |
121 | }; |
122 | |
123 | constexpr bool test() { |
124 | types::for_each(types::type_list<char, wchar_t, int, long, TriviallyComparable<char>, TriviallyComparable<wchar_t>>{}, |
125 | []<class T> { |
126 | types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> { |
127 | if constexpr (std::forward_iterator<Iter>) |
128 | test_iterators<Iter>(); |
129 | test_iterators<Iter, sentinel_wrapper<Iter>>(); |
130 | test_iterators<Iter, sized_sentinel<Iter>>(); |
131 | }); |
132 | }); |
133 | |
134 | // TODO: Remove the `_LIBCPP_ENABLE_EXPERIMENTAL` check once we have the FTM guarded or views::join isn't |
135 | // experimental anymore |
136 | #if TEST_STD_VER >= 20 && (!defined(_LIBCPP_VERSION) || defined(_LIBCPP_ENABLE_EXPERIMENTAL)) |
137 | { |
138 | std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; |
139 | auto view = vec | std::views::join; |
140 | assert(std::ranges::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3)); |
141 | assert(std::ranges::find(view, 4) == std::next(view.begin(), 3)); |
142 | } |
143 | #endif |
144 | |
145 | { // check that the first element is returned |
146 | { |
147 | struct S { |
148 | int comp; |
149 | int other; |
150 | }; |
151 | S a[] = { {.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 1} }; |
152 | auto ret = std::ranges::find(a, 0, &S::comp); |
153 | assert(ret == a); |
154 | assert(ret->comp == 0); |
155 | assert(ret->other == 0); |
156 | } |
157 | { |
158 | struct S { |
159 | int comp; |
160 | int other; |
161 | }; |
162 | S a[] = { {.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 1} }; |
163 | auto ret = std::ranges::find(a, a + 3, 0, &S::comp); |
164 | assert(ret == a); |
165 | assert(ret->comp == 0); |
166 | assert(ret->other == 0); |
167 | } |
168 | } |
169 | |
170 | { |
171 | // check that an iterator is returned with a borrowing range |
172 | int a[] = {1, 2, 3, 4}; |
173 | std::same_as<int*> auto ret = std::ranges::find(std::views::all(a), 1); |
174 | assert(ret == a); |
175 | assert(*ret == 1); |
176 | } |
177 | |
178 | { |
179 | // count invocations of the projection |
180 | { |
181 | int a[] = {1, 2, 3, 4}; |
182 | int projection_count = 0; |
183 | auto ret = std::ranges::find(a, a + 4, 2, [&](int i) { ++projection_count; return i; }); |
184 | assert(ret == a + 1); |
185 | assert(*ret == 2); |
186 | assert(projection_count == 2); |
187 | } |
188 | { |
189 | int a[] = {1, 2, 3, 4}; |
190 | int projection_count = 0; |
191 | auto ret = std::ranges::find(a, 2, [&](int i) { ++projection_count; return i; }); |
192 | assert(ret == a + 1); |
193 | assert(*ret == 2); |
194 | assert(projection_count == 2); |
195 | } |
196 | } |
197 | |
198 | return true; |
199 | } |
200 | |
201 | template <class IndexT> |
202 | class Comparable { |
203 | IndexT index_; |
204 | |
205 | public: |
206 | Comparable(IndexT i) |
207 | : index_([&]() { |
208 | IndexT size = static_cast<IndexT>(comparable_data.size()); |
209 | comparable_data.push_back(i); |
210 | return size; |
211 | }()) {} |
212 | |
213 | bool operator==(const Comparable& other) const { |
214 | return comparable_data[other.index_] == comparable_data[index_]; |
215 | } |
216 | |
217 | friend bool operator==(const Comparable& lhs, long long rhs) { return comparable_data[lhs.index_] == rhs; } |
218 | }; |
219 | |
220 | void test_deque() { |
221 | { // empty deque |
222 | std::deque<int> data; |
223 | assert(std::ranges::find(data, 4) == data.end()); |
224 | assert(std::ranges::find(data.begin(), data.end(), 4) == data.end()); |
225 | } |
226 | |
227 | { // single element - match |
228 | std::deque<int> data = {4}; |
229 | assert(std::ranges::find(data, 4) == data.begin()); |
230 | assert(std::ranges::find(data.begin(), data.end(), 4) == data.begin()); |
231 | } |
232 | |
233 | { // single element - no match |
234 | std::deque<int> data = {3}; |
235 | assert(std::ranges::find(data, 4) == data.end()); |
236 | assert(std::ranges::find(data.begin(), data.end(), 4) == data.end()); |
237 | } |
238 | |
239 | // many elements |
240 | for (auto size : {2, 3, 1023, 1024, 1025, 2047, 2048, 2049}) { |
241 | { // last element match |
242 | std::deque<int> data; |
243 | data.resize(new_size: size); |
244 | std::fill(first: data.begin(), last: data.end(), value: 3); |
245 | data[size - 1] = 4; |
246 | assert(std::ranges::find(data, 4) == data.end() - 1); |
247 | assert(std::ranges::find(data.begin(), data.end(), 4) == data.end() - 1); |
248 | } |
249 | |
250 | { // second-last element match |
251 | std::deque<int> data; |
252 | data.resize(new_size: size); |
253 | std::fill(first: data.begin(), last: data.end(), value: 3); |
254 | data[size - 2] = 4; |
255 | assert(std::ranges::find(data, 4) == data.end() - 2); |
256 | assert(std::ranges::find(data.begin(), data.end(), 4) == data.end() - 2); |
257 | } |
258 | |
259 | { // no match |
260 | std::deque<int> data; |
261 | data.resize(new_size: size); |
262 | std::fill(first: data.begin(), last: data.end(), value: 3); |
263 | assert(std::ranges::find(data, 4) == data.end()); |
264 | assert(std::ranges::find(data.begin(), data.end(), 4) == data.end()); |
265 | } |
266 | } |
267 | } |
268 | |
269 | int main(int, char**) { |
270 | test_deque(); |
271 | test(); |
272 | static_assert(test()); |
273 | |
274 | types::for_each(types::cpp20_input_iterator_list<Comparable<char>*>{}, []<class Iter> { |
275 | if constexpr (std::forward_iterator<Iter>) |
276 | test_iterators<Iter>(); |
277 | test_iterators<Iter, sentinel_wrapper<Iter>>(); |
278 | test_iterators<Iter, sized_sentinel<Iter>>(); |
279 | }); |
280 | |
281 | types::for_each(types::cpp20_input_iterator_list<Comparable<wchar_t>*>{}, []<class Iter> { |
282 | if constexpr (std::forward_iterator<Iter>) |
283 | test_iterators<Iter>(); |
284 | test_iterators<Iter, sentinel_wrapper<Iter>>(); |
285 | test_iterators<Iter, sized_sentinel<Iter>>(); |
286 | }); |
287 | |
288 | return 0; |
289 | } |
290 | |