libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp

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