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 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
13 
14 // template<forward_iterator I, sentinel_for<I> S, class T,
15 //          class Pred = ranges::equal_to, class Proj = identity>
16 //   requires indirectly_comparable<I, const T*, Pred, Proj>
17 //   constexpr subrange<I>
18 //     ranges::search_n(I first, S last, iter_difference_t<I> count,
19 //                      const T& value, Pred pred = {}, Proj proj = {});
20 // template<forward_range R, class T, class Pred = ranges::equal_to,
21 //          class Proj = identity>
22 //   requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
23 //   constexpr borrowed_subrange_t<R>
24 //     ranges::search_n(R&& r, range_difference_t<R> count,
25 //                      const T& value, Pred pred = {}, Proj proj = {});
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>
35 concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) {
36   std::ranges::search_n(first1, last1, 0, 0);
37 };
38 
39 static_assert(HasSearchNIt<int*>);
40 static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>);
41 static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>);
42 static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>);
43 static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
44 static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable
45 
46 template <class Range1, class Range2 = UncheckedRange<int*>>
47 concept HasSearchNR = requires (Range1 range) {
48   std::ranges::search_n(range, 0, 0);
49 };
50 
51 static_assert(HasSearchNR<UncheckedRange<int*>>);
52 static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>);
53 static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>);
54 static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>);
55 static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>);
56 static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable
57 
58 template <class Iter, class Sent = Iter>
test_iterators()59 constexpr void test_iterators() {
60   { // simple test
61     {
62       int a[] = {1, 2, 3, 4, 5, 6};
63       std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret =
64           std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 1, 3);
65       assert(base(ret.begin()) == a + 2);
66       assert(base(ret.end()) == a + 3);
67     }
68     {
69       int a[] = {1, 2, 3, 4, 5, 6};
70       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
71       std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret = std::ranges::search_n(range, 1, 3);
72       assert(base(ret.begin()) == a + 2);
73       assert(base(ret.end()) == a + 3);
74     }
75   }
76 
77   { // matching part begins at the front
78     {
79       int a[] = {7, 7, 3, 7, 3, 6};
80       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 2, 7);
81       assert(base(ret.begin()) == a);
82       assert(base(ret.end()) == a + 2);
83     }
84     {
85       int a[] = {7, 7, 3, 7, 3, 6};
86       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
87       auto ret = std::ranges::search_n(range, 2, 7);
88       assert(base(ret.begin()) == a);
89       assert(base(ret.end()) == a + 2);
90     }
91   }
92 
93   { // matching part ends at the back
94     {
95       int a[] = {9, 3, 6, 4, 4};
96       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 2, 4);
97       assert(base(ret.begin()) == a + 3);
98       assert(base(ret.end()) == a + 5);
99     }
100     {
101       int a[] = {9, 3, 6, 4, 4};
102       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
103       auto ret = std::ranges::search_n(range, 2, 4);
104       assert(base(ret.begin()) == a + 3);
105       assert(base(ret.end()) == a + 5);
106     }
107   }
108 
109   { // pattern does not match
110     {
111       int a[] = {9, 3, 6, 4, 8};
112       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 1, 1);
113       assert(base(ret.begin()) == a + 5);
114       assert(base(ret.end()) == a + 5);
115     }
116     {
117       int a[] = {9, 3, 6, 4, 8};
118       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
119       auto ret = std::ranges::search_n(range, 1, 1);
120       assert(base(ret.begin()) == a + 5);
121       assert(base(ret.end()) == a + 5);
122     }
123   }
124 
125   { // range and pattern are identical
126     {
127       int a[] = {1, 1, 1, 1};
128       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 4)), 4, 1);
129       assert(base(ret.begin()) == a);
130       assert(base(ret.end()) == a + 4);
131     }
132     {
133       int a[] = {1, 1, 1, 1};
134       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
135       auto ret = std::ranges::search_n(range, 4, 1);
136       assert(base(ret.begin()) == a);
137       assert(base(ret.end()) == a + 4);
138     }
139   }
140 
141   { // pattern is longer than range
142     {
143       int a[] = {3, 3, 3};
144       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 4, 3);
145       assert(base(ret.begin()) == a + 3);
146       assert(base(ret.end()) == a + 3);
147     }
148     {
149       int a[] = {3, 3, 3};
150       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
151       auto ret = std::ranges::search_n(range, 4, 3);
152       assert(base(ret.begin()) == a + 3);
153       assert(base(ret.end()) == a + 3);
154     }
155   }
156 
157   { // pattern has zero length
158     {
159       int a[] = {6, 7, 8};
160       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 0, 7);
161       assert(base(ret.begin()) == a);
162       assert(base(ret.end()) == a);
163     }
164     {
165       int a[] = {6, 7, 8};
166       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
167       auto ret = std::ranges::search_n(range, 0, 7);
168       assert(base(ret.begin()) == a);
169       assert(base(ret.end()) == a);
170     }
171   }
172 
173   { // range has zero length
174     {
175       int a[] = {};
176       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a)), 1, 1);
177       assert(base(ret.begin()) == a);
178       assert(base(ret.end()) == a);
179     }
180     {
181       int a[] = {};
182       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a)));
183       auto ret = std::ranges::search_n(range, 1, 1);
184       assert(base(ret.begin()) == a);
185       assert(base(ret.end()) == a);
186     }
187   }
188 
189   { // check that the first match is returned
190     {
191       int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
192       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 9)), 2, 6);
193       assert(base(ret.begin()) == a);
194       assert(base(ret.end()) == a + 2);
195     }
196     {
197       int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
198       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 9)));
199       auto ret = std::ranges::search_n(range, 2, 6);
200       assert(base(ret.begin()) == a);
201       assert(base(ret.end()) == a + 2);
202     }
203   }
204 
205   { // check that the predicate is used
206     {
207       int a[] = {1, 4, 4, 3, 6, 1};
208       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
209                                        3,
210                                        4,
211                                        [](int l, int r) { return l == r || l == 1; });
212       assert(base(ret.begin()) == a);
213       assert(base(ret.end()) == a + 3);
214     }
215     {
216       int a[] = {1, 4, 4, 3, 6, 1};
217       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
218       auto ret = std::ranges::search_n(range, 3, 4, [](int l, int r) { return l == r || l == 1; });
219       assert(base(ret.begin()) == a);
220       assert(base(ret.end()) == a + 3);
221     }
222   }
223 
224   { // check that the projections are used
225     {
226       int a[] = {1, 3, 1, 6, 5, 6};
227       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
228                                        3,
229                                        6,
230                                        {},
231                                        [](int i) { return i % 2 == 0 ? i : i + 1; });
232       assert(base(ret.begin()) == a + 3);
233       assert(base(ret.end()) == a + 6);
234     }
235     {
236       int a[] = {1, 3, 1, 6, 5, 6};
237       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
238       auto ret = std::ranges::search_n(range,
239                                        3,
240                                        6,
241                                        {},
242                                        [](int i) { return i % 2 == 0 ? i : i + 1; });
243       assert(base(ret.begin()) == a + 3);
244       assert(base(ret.end()) == a + 6);
245     }
246   }
247 }
test()248 constexpr bool test() {
249   test_iterators<forward_iterator<int*>>();
250   test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
251   test_iterators<bidirectional_iterator<int*>>();
252   test_iterators<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
253   test_iterators<random_access_iterator<int*>>();
254   test_iterators<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
255   test_iterators<contiguous_iterator<int*>>();
256   test_iterators<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
257   test_iterators<int*>();
258 
259   { // check that std::invoke is used
260     struct S {
261       int i;
262 
263       constexpr S identity() {
264         return *this;
265       }
266 
267       constexpr bool compare(int o) {
268         return i == o;
269       }
270     };
271     {
272       S a[] = {{1}, {2}, {3}, {4}};
273       auto ret = std::ranges::search_n(a, a + 4, 1, 2, &S::compare, &S::identity);
274       assert(ret.begin() == a + 1);
275       assert(ret.end() == a + 2);
276     }
277     {
278       S a[] = {{1}, {2}, {3}, {4}};
279       auto ret = std::ranges::search_n(a, 1, 2, &S::compare, &S::identity);
280       assert(ret.begin() == a + 1);
281       assert(ret.end() == a + 2);
282     }
283   }
284 
285   { // check that std::ranges::dangling is returned
286     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
287         std::ranges::search_n(std::array {1, 2, 3, 4}, 1, 0);
288   }
289 
290   return true;
291 }
292 
main(int,char **)293 int main(int, char**) {
294   test();
295   static_assert(test());
296 
297   return 0;
298 }
299