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
33template <class Iter1, class Sent1 = Iter1>
34concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) {
35 std::ranges::search_n(first1, last1, 0, 0);
36};
37
38static_assert(HasSearchNIt<int*>);
39static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>);
40static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>);
41static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>);
42static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
43static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable
44
45template <class Range1, class Range2 = UncheckedRange<int*>>
46concept HasSearchNR = requires (Range1 range) {
47 std::ranges::search_n(range, 0, 0);
48};
49
50static_assert(HasSearchNR<UncheckedRange<int*>>);
51static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>);
52static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>);
53static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>);
54static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>);
55static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable
56
57template <class Iter, class Sent = Iter>
58constexpr 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}
247constexpr 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[] = {{.i: 1}, {.i: 2}, {.i: 3}, {.i: 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[] = {{.i: 1}, {.i: 2}, {.i: 3}, {.i: 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
292int main(int, char**) {
293 test();
294 static_assert(test());
295
296 return 0;
297}
298

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp