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<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
14 // class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
15 // requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
16 // constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
17 // Pred pred = {},
18 // Proj1 proj1 = {}, Proj2 proj2 = {});
19 // template<input_range R1, input_range R2, class Pred = ranges::equal_to,
20 // class Proj1 = identity, class Proj2 = identity>
21 // requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
22 // constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
23 // Proj1 proj1 = {}, Proj2 proj2 = {});
24
25 #include <algorithm>
26 #include <array>
27 #include <cassert>
28 #include <concepts>
29 #include <functional>
30 #include <ranges>
31
32 #include "almost_satisfies_types.h"
33 #include "test_iterators.h"
34
35 template <class Iter1, class Sent1 = sentinel_wrapper<Iter1>,
36 class Iter2 = Iter1, class Sent2 = sentinel_wrapper<Iter2>>
37 concept HasEqualIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
38 std::ranges::equal(first1, last1, first2, last2);
39 };
40
41 static_assert(HasEqualIt<int*>);
42 static_assert(!HasEqualIt<InputIteratorNotDerivedFrom>);
43 static_assert(!HasEqualIt<InputIteratorNotIndirectlyReadable>);
44 static_assert(!HasEqualIt<InputIteratorNotInputOrOutputIterator>);
45 static_assert(!HasEqualIt<int*, int*, InputIteratorNotDerivedFrom>);
46 static_assert(!HasEqualIt<int*, int*, InputIteratorNotIndirectlyReadable>);
47 static_assert(!HasEqualIt<int*, int*, InputIteratorNotInputOrOutputIterator>);
48 static_assert(!HasEqualIt<int*, SentinelForNotSemiregular>);
49 static_assert(!HasEqualIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
50 static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotSemiregular>);
51 static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
52 static_assert(!HasEqualIt<int*, int*, int**>);
53
54 template <class Range1, class Range2>
55 concept HasEqualR = requires (Range1 range1, Range2 range2) {
56 std::ranges::equal(range1, range2);
57 };
58
59 static_assert(HasEqualR<UncheckedRange<int*>, UncheckedRange<int*>>);
60 static_assert(!HasEqualR<InputRangeNotDerivedFrom, UncheckedRange<int*>>);
61 static_assert(!HasEqualR<InputRangeNotIndirectlyReadable, UncheckedRange<int*>>);
62 static_assert(!HasEqualR<InputRangeNotInputOrOutputIterator, UncheckedRange<int*>>);
63 static_assert(!HasEqualR<InputRangeNotSentinelSemiregular, UncheckedRange<int*>>);
64 static_assert(!HasEqualR<InputRangeNotSentinelEqualityComparableWith, UncheckedRange<int*>>);
65 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotDerivedFrom>);
66 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>);
67 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>);
68 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);
69 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);
70 static_assert(!HasEqualR<UncheckedRange<int*>, UncheckedRange<int**>>);
71
72 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
test_iterators()73 constexpr void test_iterators() {
74 { // simple test
75 {
76 int a[] = {1, 2, 3, 4};
77 int b[] = {1, 2, 3, 4};
78 std::same_as<bool> decltype(auto) ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)),
79 Iter2(b), Sent2(Iter2(b + 4)));
80 assert(ret);
81 }
82 {
83 int a[] = {1, 2, 3, 4};
84 int b[] = {1, 2, 3, 4};
85 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
86 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
87 std::same_as<bool> decltype(auto) ret = std::ranges::equal(range1, range2);
88 assert(ret);
89 }
90 }
91
92 { // check that false is returned for non-equal ranges
93 {
94 int a[] = {1, 2, 3, 4};
95 int b[] = {1, 2, 4, 4};
96 assert(!std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4))));
97 }
98 {
99 int a[] = {1, 2, 3, 4};
100 int b[] = {1, 2, 4, 4};
101 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
102 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
103 assert(!std::ranges::equal(range1, range2));
104 }
105 }
106
107 { // check that the predicate is used (return true)
108 {
109 int a[] = {1, 2, 3, 4};
110 int b[] = {2, 3, 4, 5};
111 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)),
112 [](int l, int r) { return l != r; });
113 assert(ret);
114 }
115 {
116 int a[] = {1, 2, 3, 4};
117 int b[] = {2, 3, 4, 5};
118 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
119 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
120 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });
121 assert(ret);
122 }
123 }
124
125 { // check that the predicate is used (return false)
126 {
127 int a[] = {1, 2, 3, 4};
128 int b[] = {2, 3, 3, 5};
129 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)),
130 [](int l, int r) { return l != r; });
131 assert(!ret);
132 }
133 {
134 int a[] = {1, 2, 3, 4};
135 int b[] = {2, 3, 3, 5};
136 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
137 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
138 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });
139 assert(!ret);
140 }
141 }
142
143 { // check that the projections are used
144 {
145 int a[] = {1, 2, 3, 4, 5};
146 int b[] = {6, 10, 14, 18, 22};
147 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)),
148 Iter2(b), Sent2(Iter2(b + 5)),
149 {},
150 [](int i) { return i * 4; },
151 [](int i) { return i - 2; });
152 assert(ret);
153 }
154 {
155 int a[] = {1, 2, 3, 4, 5};
156 int b[] = {6, 10, 14, 18, 22};
157 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
158 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));
159 auto ret = std::ranges::equal(range1,
160 range2,
161 {},
162 [](int i) { return i * 4; },
163 [](int i) { return i - 2; });
164 assert(ret);
165 }
166 }
167
168 { // check that different sized ranges work
169 {
170 int a[] = {4, 3, 2, 1};
171 int b[] = {4, 3, 2, 1, 5, 6, 7};
172 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7)));
173 assert(!ret);
174 }
175 {
176 int a[] = {4, 3, 2, 1};
177 int b[] = {4, 3, 2, 1, 5, 6, 7};
178 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
179 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7)));
180 auto ret = std::ranges::equal(range1, range2);
181 assert(!ret);
182 }
183 }
184
185 { // check that two ranges with the same size but different values are different
186 {
187 int a[] = {4, 6, 34, 76, 5};
188 int b[] = {4, 6, 34, 67, 5};
189 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5)));
190 assert(!ret);
191 }
192 {
193 int a[] = {4, 6, 34, 76, 5};
194 int b[] = {4, 6, 34, 67, 5};
195 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
196 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));
197 auto ret = std::ranges::equal(range1, range2);
198 assert(!ret);
199 }
200 }
201
202 { // check that two empty ranges work
203 {
204 std::array<int, 0> a = {};
205 std::array<int, 0> b = {};
206 auto ret = std::ranges::equal(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(b.data()), Sent2(Iter2(b.data())));
207 assert(ret);
208 }
209 {
210 std::array<int, 0> a = {};
211 std::array<int, 0> b = {};
212 auto range1 = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));
213 auto range2 = std::ranges::subrange(Iter2(b.data()), Sent2(Iter2(b.data())));
214 auto ret = std::ranges::equal(range1, range2);
215 assert(ret);
216 }
217 }
218
219 { // check that it works with the first range empty
220 {
221 std::array<int, 0> a = {};
222 int b[] = {1, 2};
223 auto ret = std::ranges::equal(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(b), Sent2(Iter2(b + 2)));
224 assert(!ret);
225 }
226 {
227 std::array<int, 0> a = {};
228 int b[] = {1, 2};
229 auto range1 = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));
230 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2)));
231 auto ret = std::ranges::equal(range1, range2);
232 assert(!ret);
233 }
234 }
235
236 { // check that it works with the second range empty
237 {
238 int a[] = {1, 2};
239 std::array<int, 0> b = {};
240 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b.data()), Sent2(Iter2(b.data())));
241 assert(!ret);
242 }
243 {
244 int a[] = {1, 2};
245 std::array<int, 0> b = {};
246 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2)));
247 auto range2 = std::ranges::subrange(Iter2(b.data()), Sent2(Iter2(b.data())));
248 auto ret = std::ranges::equal(range1, range2);
249 assert(!ret);
250 }
251 }
252 }
253
254 template<class Iter1, class Sent1 = Iter1>
test_iterators2()255 constexpr void test_iterators2() {
256 test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
257 test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
258 test_iterators<Iter1, Sent1, forward_iterator<int*>>();
259 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
260 test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
261 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
262 test_iterators<Iter1, Sent1, int*>();
263 test_iterators<Iter1, Sent1, const int*>();
264 }
265
test()266 constexpr bool test() {
267 test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
268 test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
269 test_iterators2<forward_iterator<int*>>();
270 test_iterators2<bidirectional_iterator<int*>>();
271 test_iterators2<random_access_iterator<int*>>();
272 test_iterators2<contiguous_iterator<int*>>();
273 test_iterators2<int*>();
274 test_iterators2<const int*>();
275
276 { // check that std::invoke is used
277 struct S {
278 constexpr S(int i_) : i(i_) {}
279 constexpr bool equal(int o) { return i == o; }
280 constexpr S& identity() { return *this; }
281 int i;
282 };
283 {
284 S a[] = {7, 8, 9};
285 S b[] = {7, 8, 9};
286 auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i);
287 assert(ret);
288 }
289 {
290 S a[] = {7, 8, 9};
291 S b[] = {7, 8, 9};
292 auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i);
293 assert(ret);
294 }
295 }
296
297 { // check that the complexity requirements are met
298 { // different size
299 {
300 int a[] = {1, 2, 3};
301 int b[] = {1, 2, 3, 4};
302 int predCount = 0;
303 int projCount = 0;
304 auto pred = [&](int l, int r) { ++predCount; return l == r; };
305 auto proj = [&](int i) { ++projCount; return i; };
306 auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj);
307 assert(!ret);
308 assert(predCount == 0);
309 assert(projCount == 0);
310 }
311 {
312 int a[] = {1, 2, 3};
313 int b[] = {1, 2, 3, 4};
314 int predCount = 0;
315 int projCount = 0;
316 auto pred = [&](int l, int r) { ++predCount; return l == r; };
317 auto proj = [&](int i) { ++projCount; return i; };
318 auto ret = std::ranges::equal(a, b, pred, proj, proj);
319 assert(!ret);
320 assert(predCount == 0);
321 assert(projCount == 0);
322 }
323 }
324
325 { // not a sized sentinel
326 {
327 int a[] = {1, 2, 3};
328 int b[] = {1, 2, 3, 4};
329 int predCount = 0;
330 int projCount = 0;
331 auto pred = [&](int l, int r) { ++predCount; return l == r; };
332 auto proj = [&](int i) { ++projCount; return i; };
333 auto ret = std::ranges::equal(a, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj);
334 assert(!ret);
335 assert(predCount <= 4);
336 assert(projCount <= 7);
337 }
338 {
339 int a[] = {1, 2, 3};
340 int b[] = {1, 2, 3, 4};
341 int predCount = 0;
342 int projCount = 0;
343 auto pred = [&](int l, int r) { ++predCount; return l == r; };
344 auto proj = [&](int i) { ++projCount; return i; };
345 auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3));
346 auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4));
347 auto ret = std::ranges::equal(range1, range2, pred, proj, proj);
348 assert(!ret);
349 assert(predCount <= 4);
350 assert(projCount <= 7);
351 }
352 }
353
354 { // same size
355 {
356 int a[] = {1, 2, 3};
357 int b[] = {1, 2, 3};
358 int predCount = 0;
359 int projCount = 0;
360 auto pred = [&](int l, int r) { ++predCount; return l == r; };
361 auto proj = [&](int i) { ++projCount; return i; };
362 auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj);
363 assert(ret);
364 assert(predCount == 3);
365 assert(projCount == 6);
366 }
367 {
368 int a[] = {1, 2, 3};
369 int b[] = {1, 2, 3};
370 int predCount = 0;
371 int projCount = 0;
372 auto pred = [&](int l, int r) { ++predCount; return l == r; };
373 auto proj = [&](int i) { ++projCount; return i; };
374 auto ret = std::ranges::equal(a, b, pred, proj, proj);
375 assert(ret);
376 assert(predCount == 3);
377 assert(projCount == 6);
378 }
379 }
380 }
381
382 return true;
383 }
384
main(int,char **)385 int main(int, char**) {
386 test();
387 static_assert(test());
388
389 return 0;
390 }
391