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