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
33template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
34concept HasFindEndIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
35 std::ranges::find_end(first1, last1, first2, last2);
36};
37
38static_assert(HasFindEndIt<int*>);
39static_assert(!HasFindEndIt<ForwardIteratorNotDerivedFrom>);
40static_assert(!HasFindEndIt<ForwardIteratorNotIncrementable>);
41static_assert(!HasFindEndIt<int*, SentinelForNotSemiregular>);
42static_assert(!HasFindEndIt<int*, int*, int**>); // not indirectly comparable
43static_assert(!HasFindEndIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
44static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotDerivedFrom>);
45static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotIncrementable>);
46static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotSemiregular>);
47static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
48
49template <class Range1, class Range2 = UncheckedRange<int*>>
50concept HasFindEndR = requires (Range1 range1, Range2 range2) {
51 std::ranges::find_end(range1, range2);
52};
53
54static_assert(HasFindEndR<UncheckedRange<int*>>);
55static_assert(!HasFindEndR<ForwardRangeNotDerivedFrom>);
56static_assert(!HasFindEndR<ForwardIteratorNotIncrementable>);
57static_assert(!HasFindEndR<ForwardRangeNotSentinelSemiregular>);
58static_assert(!HasFindEndR<ForwardRangeNotSentinelEqualityComparableWith>);
59static_assert(!HasFindEndR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
60static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
61static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
62static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
63static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
64
65template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
66constexpr 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 std::array<int, 0> p = {};
186 auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p.data()), Sent2(Iter2(p.data())));
187 assert(base(ret.begin()) == a + 3);
188 assert(base(ret.end()) == a + 3);
189 }
190 {
191 int a[] = {6, 7, 8};
192 std::array<int, 0> p = {};
193 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
194 auto range2 = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));
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 std::array<int, 0> a = {};
204 int p[] = {6, 7, 8};
205 auto ret = std::ranges::find_end(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(p), Sent2(Iter2(p + 3)));
206 assert(base(ret.begin()) == a.data());
207 assert(base(ret.end()) == a.data());
208 }
209 {
210 std::array<int, 0> a = {};
211 int p[] = {6, 7, 8};
212 auto range1 = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));
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.data());
216 assert(base(ret.end()) == a.data());
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
288template <class Iter1, class Sent1 = Iter1>
289constexpr 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
301constexpr 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[] = {{.i: 1}, {.i: 2}, {.i: 3}, {.i: 4}};
326 S p[] = {{.i: 2}, {.i: 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[] = {{.i: 1}, {.i: 2}, {.i: 3}, {.i: 4}};
333 S p[] = {{.i: 2}, {.i: 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
348int main(int, char**) {
349 test();
350 static_assert(test());
351
352 return 0;
353}
354

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp