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