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