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// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
14// class Proj1 = identity, class Proj2 = identity,
15// indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
16// ranges::less>
17// constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
18// Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20
19//
20// template<input_range R1, input_range R2, class Proj1 = identity,
21// class Proj2 = identity,
22// indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
23// projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
24// constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
25// Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20
26
27#include <algorithm>
28#include <array>
29#include <concepts>
30#include <functional>
31#include <ranges>
32#include <utility>
33
34#include "almost_satisfies_types.h"
35#include "test_iterators.h"
36
37template <
38 class Iter1 = int*,
39 class Sent1 = int*,
40 class Iter2 = int*,
41 class Sent2 = int*,
42 class Comp = std::ranges::less,
43 class Proj1 = std::identity,
44 class Proj2 = std::identity>
45concept HasIncludesIter =
46 requires(Iter1&& iter1, Sent1&& sent1, Iter2&& iter2, Sent2&& sent2, Comp&& comp, Proj1&& proj1, Proj2&& proj2) {
47 std::ranges::includes(
48 std::forward<Iter1>(iter1),
49 std::forward<Sent1>(sent1),
50 std::forward<Iter2>(iter2),
51 std::forward<Sent2>(sent2),
52 std::forward<Comp>(comp),
53 std::forward<Proj1>(proj1),
54 std::forward<Proj2>(proj2));
55 };
56
57static_assert(HasIncludesIter<int*, int*, int*, int*>);
58
59// !std::input_iterator<I1>
60static_assert(!HasIncludesIter<InputIteratorNotDerivedFrom>);
61
62// !std::sentinel_for<S1, I1>
63static_assert(!HasIncludesIter<int*, SentinelForNotSemiregular>);
64
65// !std::input_iterator<I2>
66static_assert(!HasIncludesIter<int*, int*, InputIteratorNotDerivedFrom>);
67
68// !std::sentinel_for<S2, I2>
69static_assert(!HasIncludesIter<int*, int*, int*, SentinelForNotSemiregular>);
70
71// !indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
72struct NotAComparator {};
73static_assert(!HasIncludesIter<int*, int*, int*, int*, NotAComparator>);
74
75template <
76 class Range1,
77 class Range2,
78 class Comp = std::ranges::less,
79 class Proj1 = std::identity,
80 class Proj2 = std::identity>
81concept HasIncludesRange =
82 requires(Range1&& range1, Range2&& range2, Comp&& comp, Proj1&& proj1, Proj2&& proj2) {
83 std::ranges::includes(
84 std::forward<Range1>(range1),
85 std::forward<Range2>(range2),
86 std::forward<Comp>(comp),
87 std::forward<Proj1>(proj1),
88 std::forward<Proj2>(proj2));
89 };
90
91template <class T>
92using R = UncheckedRange<T>;
93
94static_assert(HasIncludesRange<R<int*>, R<int*>>);
95
96// !std::input_range<R2>
97static_assert(!HasIncludesRange<R<InputIteratorNotDerivedFrom>, R<int*>>);
98
99// !std::input_range<R2>
100static_assert(!HasIncludesRange<R<int*>, R<InputIteratorNotDerivedFrom>>);
101
102// !indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
103// projected<iterator_t<R2>, Proj2>>
104static_assert(!HasIncludesRange<R<int*>, R<int*>, NotAComparator>);
105
106template <class In1, class In2, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
107constexpr void testIncludesImpl(std::array<int, N1> in1, std::array<int, N2> in2, bool expected) {
108 using Sent1 = SentWrapper<In1>;
109 using Sent2 = SentWrapper<In2>;
110
111 // iterator overload
112 {
113 std::same_as<bool> decltype(auto) result = std::ranges::includes(
114 In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}, In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}});
115 assert(result == expected);
116 }
117
118 // range overload
119 {
120 std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}};
121 std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}};
122 std::same_as<bool> decltype(auto) result = std::ranges::includes(r1, r2);
123 assert(result == expected);
124 }
125}
126
127template <class In1, class In2, template <class> class SentWrapper>
128constexpr void testImpl() {
129 // range 1 shorter than range2
130 {
131 std::array in1{0, 1, 5, 6, 9, 10};
132 std::array in2{3, 6, 7, 9, 13, 15, 100};
133 bool expected = false;
134 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
135 }
136 // range 2 shorter than range 1 but not subsequence
137 {
138 std::array in1{2, 6, 8, 12, 15, 16};
139 std::array in2{0, 2, 8};
140 bool expected = false;
141 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
142 }
143
144 // range 1 and range 2 has the same length but different elements
145 {
146 std::array in1{2, 6, 8, 12, 15, 16};
147 std::array in2{0, 2, 8, 15, 17, 19};
148 bool expected = false;
149 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
150 }
151
152 // range 1 == range 2
153 {
154 std::array in1{0, 1, 2};
155 std::array in2{0, 1, 2};
156 bool expected = true;
157 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
158 }
159
160 // range 2 is subsequence of range 1
161 {
162 std::array in1{8, 9, 10, 12, 13};
163 std::array in2{8, 10};
164 bool expected = true;
165 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
166 }
167
168 // range 1 is subsequence of range 2
169 {
170 std::array in1{0, 1, 1};
171 std::array in2{0, 1, 1, 2, 5};
172 bool expected = false;
173 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
174 }
175
176 // range 2 is subsequence of range 1 with duplicated elements
177 {
178 std::array in1{8, 9, 10, 12, 12, 12};
179 std::array in2{8, 12, 12};
180 bool expected = true;
181 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
182 }
183
184 // range 2 is not a subsequence of range 1 because of duplicated elements
185 {
186 std::array in1{8, 9, 10, 12, 13};
187 std::array in2{8, 10, 10};
188 bool expected = false;
189 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
190 }
191
192 // range 1 is empty
193 {
194 std::array<int, 0> in1{};
195 std::array in2{3, 4, 5};
196 bool expected = false;
197 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
198 }
199
200 // range 2 is empty
201 {
202 std::array in1{3, 4, 5};
203 std::array<int, 0> in2{};
204 bool expected = true;
205 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
206 }
207
208 // both ranges are empty
209 {
210 std::array<int, 0> in1{};
211 std::array<int, 0> in2{};
212 bool expected = true;
213 testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
214 }
215}
216
217template <class Iter2, template <class> class SentWrapper>
218constexpr void withAllPermutationsOfIter1() {
219 // C++17 InputIterator may or may not satisfy std::input_iterator
220 testImpl<cpp20_input_iterator<int*>, Iter2, sentinel_wrapper>();
221 testImpl<forward_iterator<int*>, Iter2, SentWrapper>();
222 testImpl<bidirectional_iterator<int*>, Iter2, SentWrapper>();
223 testImpl<random_access_iterator<int*>, Iter2, SentWrapper>();
224 testImpl<contiguous_iterator<int*>, Iter2, SentWrapper>();
225 testImpl<int*, Iter2, SentWrapper>();
226}
227
228template <template <class> class SentWrapper>
229constexpr void withAllPermutationsOfIter1AndIter2() {
230 withAllPermutationsOfIter1<cpp20_input_iterator<int*>, sentinel_wrapper>();
231 withAllPermutationsOfIter1<forward_iterator<int*>, SentWrapper>();
232 withAllPermutationsOfIter1<bidirectional_iterator<int*>, SentWrapper>();
233 withAllPermutationsOfIter1<random_access_iterator<int*>, SentWrapper>();
234 withAllPermutationsOfIter1<contiguous_iterator<int*>, SentWrapper>();
235 withAllPermutationsOfIter1<int*, SentWrapper>();
236}
237
238constexpr bool test() {
239 withAllPermutationsOfIter1AndIter2<std::type_identity_t>();
240 withAllPermutationsOfIter1AndIter2<sentinel_wrapper>();
241
242 struct Data {
243 int data;
244 };
245
246 // Test custom comparator
247 {
248 std::array r1{Data{.data: 4}, Data{.data: 8}, Data{.data: 12}};
249 std::array r2{Data{.data: 4}, Data{.data: 12}};
250
251 const auto comp = [](const Data& x, const Data& y) { return x.data < y.data; };
252 bool expected = true;
253
254 // iterator overload
255 {
256 auto result = std::ranges::includes(r1.begin(), r1.end(), r2.begin(), r2.end(), comp);
257 assert(result == expected);
258 }
259
260 // range overload
261 {
262 auto result = std::ranges::includes(r1, r2, comp);
263 assert(result == expected);
264 }
265 }
266
267 // Test custom projection
268 {
269 std::array r1{Data{.data: 4}, Data{.data: 8}, Data{.data: 12}};
270 std::array r2{Data{.data: 4}, Data{.data: 9}};
271
272 const auto proj = &Data::data;
273 bool expected = false;
274
275 // iterator overload
276 {
277 auto result = std::ranges::includes(r1.begin(), r1.end(), r2.begin(), r2.end(), {}, proj, proj);
278 assert(result == expected);
279 }
280
281 // range overload
282 {
283 auto result = std::ranges::includes(r1, r2, {}, proj, proj);
284 assert(result == expected);
285 }
286 }
287
288 // Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
289 // comparisons and applications of each projection.
290 {
291 struct CompProjs {
292 std::size_t numberOfComp = 0;
293 std::size_t numberOfProj1 = 0;
294 std::size_t numberOfProj2 = 0;
295
296 constexpr auto comp() {
297 return [this](int x, int y) {
298 ++numberOfComp;
299 return x < y;
300 };
301 }
302
303 constexpr auto proj1() {
304 return [this](const Data& d) {
305 ++numberOfProj1;
306 return d.data;
307 };
308 }
309
310 constexpr auto proj2() {
311 return [this](const Data& d) {
312 ++numberOfProj2;
313 return d.data;
314 };
315 }
316 };
317 std::array<Data, 4> r1{._M_elems: {{.data: 0}, {.data: 1}, {.data: 2}, {.data: 3}}};
318 std::array<Data, 2> r2{._M_elems: {{.data: 4}, {.data: 5}}};
319 const std::size_t maxOperation = 2 * (r1.size() + r2.size()) - 1;
320
321 // iterator overload
322 {
323 CompProjs compProjs{};
324
325 auto result = std::ranges::includes(
326 r1.begin(), r1.end(), r2.begin(), r2.end(), compProjs.comp(), compProjs.proj1(), compProjs.proj2());
327 assert(!result);
328 assert(compProjs.numberOfComp < maxOperation);
329 assert(compProjs.numberOfProj1 < maxOperation);
330 assert(compProjs.numberOfProj2 < maxOperation);
331 }
332
333 // range overload
334 {
335 CompProjs compProjs{};
336
337 auto result = std::ranges::includes(r1, r2, compProjs.comp(), compProjs.proj1(), compProjs.proj2());
338 assert(!result);
339 assert(compProjs.numberOfComp < maxOperation);
340 assert(compProjs.numberOfProj1 < maxOperation);
341 assert(compProjs.numberOfProj2 < maxOperation);
342 }
343 }
344
345 return true;
346}
347
348int main(int, char**) {
349 test();
350 static_assert(test());
351
352 return 0;
353}
354

source code of libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp