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

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp