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 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
13 
14 // template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
15 //          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
16 //   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
17 //   constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
18 //                                Pred pred = {},
19 //                                Proj1 proj1 = {}, Proj2 proj2 = {});
20 // template<input_range R1, input_range R2, class Pred = ranges::equal_to,
21 //          class Proj1 = identity, class Proj2 = identity>
22 //   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
23 //   constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
24 //                                Proj1 proj1 = {}, Proj2 proj2 = {});
25 
26 #include <algorithm>
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 the predicate is used (return true)
93     {
94       int a[] = {1, 2, 3, 4};
95       int b[] = {2, 3, 4, 5};
96       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)),
97                                     [](int l, int r) { return l != r; });
98       assert(ret);
99     }
100     {
101       int a[] = {1, 2, 3, 4};
102       int b[] = {2, 3, 4, 5};
103       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
104       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
105       auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });
106       assert(ret);
107     }
108   }
109 
110   { // check that the predicate is used (return false)
111     {
112       int a[] = {1, 2, 3, 4};
113       int b[] = {2, 3, 3, 5};
114       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)),
115                                     [](int l, int r) { return l != r; });
116       assert(!ret);
117     }
118     {
119       int a[] = {1, 2, 3, 4};
120       int b[] = {2, 3, 3, 5};
121       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
122       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
123       auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });
124       assert(!ret);
125     }
126   }
127 
128   { // check that the projections are used
129     {
130       int a[] = {1, 2, 3, 4, 5};
131       int b[] = {6, 10, 14, 18, 22};
132       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)),
133                                     Iter2(b), Sent2(Iter2(b + 5)),
134                                     {},
135                                     [](int i) { return i * 4; },
136                                     [](int i) { return i - 2; });
137       assert(ret);
138     }
139     {
140       int a[] = {1, 2, 3, 4, 5};
141       int b[] = {6, 10, 14, 18, 22};
142       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
143       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));
144       auto ret = std::ranges::equal(range1,
145                                     range2,
146                                     {},
147                                     [](int i) { return i * 4; },
148                                     [](int i) { return i - 2; });
149       assert(ret);
150     }
151   }
152 
153   { // check that different sized ranges work
154     {
155       int a[] = {4, 3, 2, 1};
156       int b[] = {4, 3, 2, 1, 5, 6, 7};
157       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7)));
158       assert(!ret);
159     }
160     {
161       int a[] = {4, 3, 2, 1};
162       int b[] = {4, 3, 2, 1, 5, 6, 7};
163       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
164       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7)));
165       auto ret = std::ranges::equal(range1, range2);
166       assert(!ret);
167     }
168   }
169 
170   { // check that two ranges with the same size but different values are different
171     {
172       int a[] = {4, 6, 34, 76, 5};
173       int b[] = {4, 6, 34, 67, 5};
174       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5)));
175       assert(!ret);
176     }
177     {
178       int a[] = {4, 6, 34, 76, 5};
179       int b[] = {4, 6, 34, 67, 5};
180       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
181       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));
182       auto ret = std::ranges::equal(range1, range2);
183       assert(!ret);
184     }
185   }
186 
187   { // check that two empty ranges work
188     {
189       int a[] = {};
190       int b[] = {};
191       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b)));
192       assert(ret);
193     }
194     {
195       int a[] = {};
196       int b[] = {};
197       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
198       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b)));
199       auto ret = std::ranges::equal(range1, range2);
200       assert(ret);
201     }
202   }
203 
204   { // check that it works with the first range empty
205     {
206       int a[] = {};
207       int b[] = {1, 2};
208       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b + 2)));
209       assert(!ret);
210     }
211     {
212       int a[] = {};
213       int b[] = {1, 2};
214       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
215       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2)));
216       auto ret = std::ranges::equal(range1, range2);
217       assert(!ret);
218     }
219   }
220 
221   { // check that it works with the second range empty
222     {
223       int a[] = {1, 2};
224       int b[] = {};
225       auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b), Sent2(Iter2(b)));
226       assert(!ret);
227     }
228     {
229       int a[] = {1, 2};
230       int b[] = {};
231       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2)));
232       auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b)));
233       auto ret = std::ranges::equal(range1, range2);
234       assert(!ret);
235     }
236   }
237 }
238 
239 template<class Iter1, class Sent1 = Iter1>
test_iterators2()240 constexpr void test_iterators2() {
241   test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
242   test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
243   test_iterators<Iter1, Sent1, forward_iterator<int*>>();
244   test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
245   test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
246   test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
247   test_iterators<Iter1, Sent1, int*>();
248   test_iterators<Iter1, Sent1, const int*>();
249 }
250 
test()251 constexpr bool test() {
252   test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
253   test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
254   test_iterators2<forward_iterator<int*>>();
255   test_iterators2<bidirectional_iterator<int*>>();
256   test_iterators2<random_access_iterator<int*>>();
257   test_iterators2<contiguous_iterator<int*>>();
258   test_iterators2<int*>();
259   test_iterators2<const int*>();
260 
261   { // check that std::invoke is used
262     struct S {
263       constexpr S(int i_) : i(i_) {}
264       constexpr bool equal(int o) { return i == o; }
265       constexpr S& identity() { return *this; }
266       int i;
267     };
268     {
269       S a[] = {7, 8, 9};
270       S b[] = {7, 8, 9};
271       auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i);
272       assert(ret);
273     }
274     {
275       S a[] = {7, 8, 9};
276       S b[] = {7, 8, 9};
277       auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i);
278       assert(ret);
279     }
280   }
281 
282   { // check that the complexity requirements are met
283     { // different size
284       {
285         int a[] = {1, 2, 3};
286         int b[] = {1, 2, 3, 4};
287         int predCount = 0;
288         int projCount = 0;
289         auto pred = [&](int l, int r) { ++predCount; return l == r; };
290         auto proj = [&](int i) { ++projCount; return i; };
291         auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj);
292         assert(!ret);
293         assert(predCount == 0);
294         assert(projCount == 0);
295       }
296       {
297         int a[] = {1, 2, 3};
298         int b[] = {1, 2, 3, 4};
299         int predCount = 0;
300         int projCount = 0;
301         auto pred = [&](int l, int r) { ++predCount; return l == r; };
302         auto proj = [&](int i) { ++projCount; return i; };
303         auto ret = std::ranges::equal(a, b, pred, proj, proj);
304         assert(!ret);
305         assert(predCount == 0);
306         assert(projCount == 0);
307       }
308     }
309 
310     { // not a sized sentinel
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, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj);
319         assert(!ret);
320         assert(predCount <= 4);
321         assert(projCount <= 7);
322       }
323       {
324         int a[] = {1, 2, 3};
325         int b[] = {1, 2, 3, 4};
326         int predCount = 0;
327         int projCount = 0;
328         auto pred = [&](int l, int r) { ++predCount; return l == r; };
329         auto proj = [&](int i) { ++projCount; return i; };
330         auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3));
331         auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4));
332         auto ret = std::ranges::equal(range1, range2, pred, proj, proj);
333         assert(!ret);
334         assert(predCount <= 4);
335         assert(projCount <= 7);
336       }
337     }
338 
339     { // same size
340       {
341         int a[] = {1, 2, 3};
342         int b[] = {1, 2, 3};
343         int predCount = 0;
344         int projCount = 0;
345         auto pred = [&](int l, int r) { ++predCount; return l == r; };
346         auto proj = [&](int i) { ++projCount; return i; };
347         auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj);
348         assert(ret);
349         assert(predCount == 3);
350         assert(projCount == 6);
351       }
352       {
353         int a[] = {1, 2, 3};
354         int b[] = {1, 2, 3};
355         int predCount = 0;
356         int projCount = 0;
357         auto pred = [&](int l, int r) { ++predCount; return l == r; };
358         auto proj = [&](int i) { ++projCount; return i; };
359         auto ret = std::ranges::equal(a, b, pred, proj, proj);
360         assert(ret);
361         assert(predCount == 3);
362         assert(projCount == 6);
363       }
364     }
365   }
366 
367   return true;
368 }
369 
main(int,char **)370 int main(int, char**) {
371   test();
372   static_assert(test());
373 
374   return 0;
375 }
376