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 <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>
  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>
 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
 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
 385 int main(int, char**) {
 386   test();
 387   static_assert(test());
 388
 389   return 0;
 390 }