xref: /llvm-project/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp (revision b8cb1dc9ea87faa8e8e9ab7a31710a8c0bb8b084) 
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<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
14 //          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
15 //   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
16 //   constexpr subrange<I1>
17 //     ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
18 //                      Proj1 proj1 = {}, Proj2 proj2 = {});
19 // template<forward_range R1, forward_range R2,
20 //          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
21 //   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
22 //   constexpr borrowed_subrange_t<R1>
23 //     ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
24 //                      Proj1 proj1 = {}, Proj2 proj2 = {});
25 
26 #include <algorithm>
27 #include <array>
28 #include <ranges>
29 
30 #include "almost_satisfies_types.h"
31 #include "test_iterators.h"
32 
33 template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
34 concept HasFindEndIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
35   std::ranges::find_end(first1, last1, first2, last2);
36 };
37 
38 static_assert(HasFindEndIt<int*>);
39 static_assert(!HasFindEndIt<ForwardIteratorNotDerivedFrom>);
40 static_assert(!HasFindEndIt<ForwardIteratorNotIncrementable>);
41 static_assert(!HasFindEndIt<int*, SentinelForNotSemiregular>);
42 static_assert(!HasFindEndIt<int*, int*, int**>); // not indirectly comparable
43 static_assert(!HasFindEndIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
44 static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotDerivedFrom>);
45 static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotIncrementable>);
46 static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotSemiregular>);
47 static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
48 
49 template <class Range1, class Range2 = UncheckedRange<int*>>
50 concept HasFindEndR = requires (Range1 range1, Range2 range2) {
51   std::ranges::find_end(range1, range2);
52 };
53 
54 static_assert(HasFindEndR<UncheckedRange<int*>>);
55 static_assert(!HasFindEndR<ForwardRangeNotDerivedFrom>);
56 static_assert(!HasFindEndR<ForwardIteratorNotIncrementable>);
57 static_assert(!HasFindEndR<ForwardRangeNotSentinelSemiregular>);
58 static_assert(!HasFindEndR<ForwardRangeNotSentinelEqualityComparableWith>);
59 static_assert(!HasFindEndR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
60 static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
61 static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
62 static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
63 static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
64 
65 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
66 constexpr void test_iterators() {
67   { // simple test
68     {
69       int a[] = {1, 2, 3, 4, 5, 6};
70       int p[] = {3, 4};
71       std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret =
72           std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)));
73       assert(base(ret.begin()) == a + 2);
74       assert(base(ret.end()) == a + 4);
75     }
76     {
77       int a[] = {1, 2, 3, 4, 5, 6};
78       int p[] = {3, 4};
79       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
80       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
81       std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret = std::ranges::find_end(range1, range2);
82       assert(base(ret.begin()) == a + 2);
83       assert(base(ret.end()) == a + 4);
84     }
85   }
86 
87   { // matching part begins at the front
88     {
89       int a[] = {7, 5, 3, 7, 3, 6};
90       int p[] = {7, 5, 3};
91       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3)));
92       assert(base(ret.begin()) == a);
93       assert(base(ret.end()) == a + 3);
94     }
95     {
96       int a[] = {7, 5, 3, 7, 3, 6};
97       int p[] = {7, 5, 3};
98       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
99       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
100       auto ret = std::ranges::find_end(range1, range2);
101       assert(base(ret.begin()) == a);
102       assert(base(ret.end()) == a + 3);
103     }
104   }
105 
106   { // matching part ends at the back
107     {
108       int a[] = {9, 3, 6, 4, 8};
109       int p[] = {4, 8};
110       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2)));
111       assert(base(ret.begin()) == a + 3);
112       assert(base(ret.end()) == a + 5);
113     }
114     {
115       int a[] = {9, 3, 6, 4, 8};
116       int p[] = {4, 8};
117       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
118       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
119       auto ret = std::ranges::find_end(range1, range2);
120       assert(base(ret.begin()) == a + 3);
121       assert(base(ret.end()) == a + 5);
122     }
123   }
124 
125   { // pattern does not match
126     {
127       int a[] = {9, 3, 6, 4, 8};
128       int p[] = {1};
129       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1)));
130       assert(base(ret.begin()) == a + 5);
131       assert(base(ret.end()) == a + 5);
132     }
133     {
134       int a[] = {9, 3, 6, 4, 8};
135       int p[] = {1};
136       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
137       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));
138       auto ret = std::ranges::find_end(range1, range2);
139       assert(base(ret.begin()) == a + 5);
140       assert(base(ret.end()) == a + 5);
141     }
142   }
143 
144   { // range and pattern are identical
145     {
146       int a[] = {6, 7, 8, 9};
147       int p[] = {6, 7, 8, 9};
148       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4)));
149       assert(base(ret.begin()) == a);
150       assert(base(ret.end()) == a + 4);
151     }
152     {
153       int a[] = {6, 7, 8, 9};
154       int p[] = {6, 7, 8, 9};
155       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
156       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
157       auto ret = std::ranges::find_end(range1, range2);
158       assert(base(ret.begin()) == a);
159       assert(base(ret.end()) == a + 4);
160     }
161   }
162 
163   { // pattern is longer than range
164     {
165       int a[] = {6, 7, 8};
166       int p[] = {6, 7, 8, 9};
167       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4)));
168       assert(base(ret.begin()) == a + 3);
169       assert(base(ret.end()) == a + 3);
170     }
171     {
172       int a[] = {6, 7, 8};
173       int p[] = {6, 7, 8, 9};
174       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
175       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
176       auto ret = std::ranges::find_end(range1, range2);
177       assert(base(ret.begin()) == a + 3);
178       assert(base(ret.end()) == a + 3);
179     }
180   }
181 
182   { // pattern has zero length
183     {
184       int a[] = {6, 7, 8};
185       int p[] = {};
186       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p)));
187       assert(base(ret.begin()) == a + 3);
188       assert(base(ret.end()) == a + 3);
189     }
190     {
191       int a[] = {6, 7, 8};
192       int p[] = {};
193       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
194       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p)));
195       auto ret = std::ranges::find_end(range1, range2);
196       assert(base(ret.begin()) == a + 3);
197       assert(base(ret.end()) == a + 3);
198     }
199   }
200 
201   { // range has zero length
202     {
203       int a[] = {};
204       int p[] = {6, 7, 8};
205       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3)));
206       assert(base(ret.begin()) == a);
207       assert(base(ret.end()) == a);
208     }
209     {
210       int a[] = {};
211       int p[] = {6, 7, 8};
212       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
213       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
214       auto ret = std::ranges::find_end(range1, range2);
215       assert(base(ret.begin()) == a);
216       assert(base(ret.end()) == a);
217     }
218   }
219 
220   { // check that the first match is returned
221     {
222       int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
223       int p[] = {6, 7, 8};
224       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3)));
225       assert(base(ret.begin()) == a + 6);
226       assert(base(ret.end()) == a + 9);
227     }
228     {
229       int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
230       int p[] = {6, 7, 8};
231       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9)));
232       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
233       auto ret = std::ranges::find_end(range1, range2);
234       assert(base(ret.begin()) == a + 6);
235       assert(base(ret.end()) == a + 9);
236     }
237   }
238 
239   { // check that the predicate is used
240     {
241       int a[] = {1, 2, 8, 1, 5, 6};
242       int p[] = {7, 0, 4};
243       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)),
244                                        Iter2(p), Sent2(Iter2(p + 3)),
245                                        [](int l, int r) { return l > r; });
246       assert(base(ret.begin()) == a + 2);
247       assert(base(ret.end()) == a + 5);
248     }
249     {
250       int a[] = {1, 2, 8, 1, 5, 6};
251       int p[] = {7, 0, 4};
252       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
253       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
254       auto ret = std::ranges::find_end(range1, range2, [](int l, int r) { return l > r; });
255       assert(base(ret.begin()) == a + 2);
256       assert(base(ret.end()) == a + 5);
257     }
258   }
259 
260   { // check that the projections are used
261     {
262       int a[] = {1, 3, 5, 1, 5, 6};
263       int p[] = {2, 3, 4};
264       auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)),
265                                        Iter2(p), Sent2(Iter2(p + 3)),
266                                        {},
267                                        [](int i) { return i + 3; },
268                                        [](int i) { return i * 2; });
269       assert(base(ret.begin()) == a);
270       assert(base(ret.end()) == a + 3);
271     }
272     {
273       int a[] = {1, 3, 5, 1, 5, 6};
274       int p[] = {2, 3, 4};
275       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
276       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
277       auto ret = std::ranges::find_end(range1,
278                                        range2,
279                                        {},
280                                        [](int i) { return i + 3; },
281                                        [](int i) { return i * 2; });
282       assert(base(ret.begin()) == a);
283       assert(base(ret.end()) == a + 3);
284     }
285   }
286 }
287 
288 template <class Iter1, class Sent1 = Iter1>
289 constexpr void test_iterators2() {
290   test_iterators<Iter1, Sent1, forward_iterator<int*>>();
291   test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
292   test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
293   test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
294   test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
295   test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
296   test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
297   test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
298   test_iterators<Iter1, Sent1, int*>();
299 }
300 
301 constexpr bool test() {
302   test_iterators2<forward_iterator<int*>>();
303   test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
304   test_iterators2<bidirectional_iterator<int*>>();
305   test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
306   test_iterators2<random_access_iterator<int*>>();
307   test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
308   test_iterators2<contiguous_iterator<int*>>();
309   test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
310   test_iterators2<int*>();
311 
312   { // check that std::invoke is used
313     struct S {
314       int i;
315 
316       constexpr S identity() {
317         return *this;
318       }
319 
320       constexpr bool compare(const S& s) {
321         return i == s.i;
322       }
323     };
324     {
325       S a[] = {{1}, {2}, {3}, {4}};
326       S p[] = {{2}, {3}};
327       auto ret = std::ranges::find_end(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity);
328       assert(ret.begin() == a + 1);
329       assert(ret.end() == a + 3);
330     }
331     {
332       S a[] = {{1}, {2}, {3}, {4}};
333       S p[] = {{2}, {3}};
334       auto ret = std::ranges::find_end(a, p, &S::compare, &S::identity, &S::identity);
335       assert(ret.begin() == a + 1);
336       assert(ret.end() == a + 3);
337     }
338   }
339 
340   { // check that std::ranges::dangling is returned
341     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
342         std::ranges::find_end(std::array {1, 2, 3, 4}, std::array {2, 3});
343   }
344 
345   return true;
346 }
347 
348 int main(int, char**) {
349   test();
350   static_assert(test());
351 
352   return 0;
353 }
354