libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.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 // UNSUPPORTED: c++03, c++11, c++14, c++17
  10
  11 // <algorithm>
  12
  13 // template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
  14 //        sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
  15 //        indirect_equivalence_relation<projected<I1, Proj1>,
  16 //                                      projected<I2, Proj2>> Pred = ranges::equal_to>
  17 // constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
  18 //                                       Pred pred = {},
  19 //                                       Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
  20 //
  21 // template<forward_range R1, forward_range R2,
  22 //        class Proj1 = identity, class Proj2 = identity,
  23 //        indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
  24 //                                      projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  25 // constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
  26 //                                       Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
  27
  28 #include <algorithm>
  29 #include <array>
  30 #include <concepts>
  31 #include <list>
  32 #include <ranges>
  33
  34 #include "almost_satisfies_types.h"
  35 #include "counting_predicates.h"
  36 #include "counting_projection.h"
  37 #include "test_iterators.h"
  38
  39 template <class Iter1, class Sent1 = int*, class Iter2 = int*, class Sent2 = int*>
  40 concept HasIsPermutationIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
  41   std::ranges::is_permutation(first1, last1, first2, last2);
  42 };
  43
  44 template <class Range1, class Range2 = UncheckedRange<int*>>
  45 concept HasIsPermutationR = requires(Range1 range1, Range2 range2) {
  46   std::ranges::is_permutation(range1, range2);
  47 };
  48
  49 static_assert(HasIsPermutationIt<int*>);
  50 static_assert(!HasIsPermutationIt<ForwardIteratorNotDerivedFrom>);
  51 static_assert(!HasIsPermutationIt<ForwardIteratorNotIncrementable>);
  52 static_assert(!HasIsPermutationIt<int*, SentinelForNotSemiregular>);
  53 static_assert(!HasIsPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
  54 static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotDerivedFrom>);
  55 static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotIncrementable>);
  56 static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotSemiregular>);
  57 static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
  58 // !indirect_equivalence_relation<Pred, projected<I1, Proj1>, projected<I2, Proj2>>;
  59 static_assert(!HasIsPermutationIt<int*, int*, int**, int**>);
  60
  61 static_assert(HasIsPermutationR<UncheckedRange<int*>>);
  62 static_assert(!HasIsPermutationR<ForwardRangeNotDerivedFrom>);
  63 static_assert(!HasIsPermutationR<ForwardRangeNotIncrementable>);
  64 static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelSemiregular>);
  65 static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelEqualityComparableWith>);
  66 static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
  67 static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
  68 static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
  69 static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
  70 // !indirect_equivalence_relation<Pred, projected<iterator_t<I1>, Proj1>, projected<iterator_t<I2>, Proj2>>;
  71 static_assert(!HasIsPermutationIt<UncheckedRange<int*>, UncheckedRange<int**>>);
  72
  73 template <int N, int M>
  74 struct Data {
  75   std::array<int, N> input1;
  76   std::array<int, M> input2;
  77   bool expected;
  78 };
  79
  80 template <class Iter1, class Sent1, class Iter2, class Sent2, int N, int M>
  81 constexpr void test(Data<N, M> d) {
  82   {
  83     std::same_as<bool> decltype(auto) ret = std::ranges::is_permutation(Iter1(d.input1.data()),
  84                                                                         Sent1(Iter1(d.input1.data() + N)),
  85                                                                         Iter1(d.input2.data()),
  86                                                                         Sent1(Iter1(d.input2.data() + M)));
  87     assert(ret == d.expected);
  88   }
  89   {
  90     auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + N)));
  91     auto range2 = std::ranges::subrange(Iter1(d.input2.data()), Sent1(Iter1(d.input2.data() + M)));
  92     std::same_as<bool> decltype(auto) ret = std::ranges::is_permutation(range1, range2);
  93     assert(ret == d.expected);
  94   }
  95 }
  96
  97 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
  98 constexpr void test_iterators() {
  99   // Ranges are identical.
 100   test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {1, 2, 3, 4}, .expected = true});
 101
 102   // Ranges are reversed.
 103   test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {4, 3, 2, 1}, .expected = true});
 104
 105   // Two elements are swapped.
 106   test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {4, 2, 3, 1}, .input2 = {1, 2, 3, 4}, .expected = true});
 107
 108   // The first range is shorter.
 109   test<Iter1, Sent1, Iter2, Sent2, 4, 5>({.input1 = {4, 2, 3, 1}, .input2 = {4, 3, 2, 1, 5}, .expected = false});
 110
 111   // The first range is longer.
 112   test<Iter1, Sent1, Iter2, Sent2, 5, 4>({.input1 = {4, 2, 3, 1, 5}, .input2 = {4, 3, 2, 1}, .expected = false});
 113
 114   // The first range is empty.
 115   test<Iter1, Sent1, Iter2, Sent2, 0, 4>({.input1 = {}, .input2 = {4, 3, 2, 1}, .expected = false});
 116
 117   // The second range is empty.
 118   test<Iter1, Sent1, Iter2, Sent2, 5, 0>({.input1 = {4, 2, 3, 1, 5}, .input2 = {}, .expected = false});
 119
 120   // Both ranges are empty.
 121   test<Iter1, Sent1, Iter2, Sent2, 0, 0>({.input1 = {}, .input2 = {}, .expected = true});
 122
 123   // 1-element range, same value.
 124   test<Iter1, Sent1, Iter2, Sent2, 1, 1>({.input1 = {1}, .input2 = {1}, .expected = true});
 125
 126   // 1-element range, different values.
 127   test<Iter1, Sent1, Iter2, Sent2, 1, 1>({.input1 = {1}, .input2 = {2}, .expected = false});
 128 }
 129
 130 template <class Iter1, class Sent1 = Iter1>
 131 constexpr void test_iterators1() {
 132   test_iterators<Iter1, Sent1, forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
 133   test_iterators<Iter1, Sent1, forward_iterator<int*>>();
 134   test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
 135   test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
 136   test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
 137   test_iterators<Iter1, Sent1, int*>();
 138   test_iterators<Iter1, Sent1, const int*>();
 139 }
 140
 141 constexpr bool test() {
 142   test_iterators1<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
 143   test_iterators1<forward_iterator<int*>>();
 144   test_iterators1<bidirectional_iterator<int*>>();
 145   test_iterators1<random_access_iterator<int*>>();
 146   test_iterators1<contiguous_iterator<int*>>();
 147   test_iterators1<int*>();
 148   test_iterators1<const int*>();
 149
 150   { // A custom comparator works.
 151     struct A {
 152       int a;
 153       constexpr bool pred(const A& rhs) const { return a == rhs.a; }
 154     };
 155
 156     std::array in1 = {A{2}, A{3}, A{1}};
 157     std::array in2 = {A{1}, A{2}, A{3}};
 158
 159     {
 160       auto ret = std::ranges::is_permutation(in1.begin(), in1.end(), in2.begin(), in2.end(), &A::pred);
 161       assert(ret);
 162     }
 163
 164     {
 165       auto ret = std::ranges::is_permutation(in1, in2, &A::pred);
 166       assert(ret);
 167     }
 168   }
 169
 170   { // A custom projection works.
 171     struct A {
 172       int a;
 173
 174       constexpr bool operator==(const A&) const = default;
 175
 176       constexpr A x2() const { return A{a * 2}; }
 177       constexpr A div2() const { return A{a / 2}; }
 178     };
 179
 180     std::array in1 = {A{1}, A{2}, A{3}};  // [2, 4, 6] after applying `x2`.
 181     std::array in2 = {A{4}, A{8}, A{12}}; // [2, 4, 6] after applying `div2`.
 182
 183     {
 184       auto ret = std::ranges::is_permutation(
 185           in1.begin(), in1.end(), in2.begin(), in2.end(), {}, &A::x2, &A::div2);
 186       assert(ret);
 187     }
 188
 189     {
 190       auto ret = std::ranges::is_permutation(in1, in2, {}, &A::x2, &A::div2);
 191       assert(ret);
 192     }
 193   }
 194
 195
 196   { // Check that complexity requirements are met.
 197     int predCount = 0;
 198     int proj1Count = 0;
 199     int proj2Count = 0;
 200     auto reset_counters = [&] {
 201       predCount = proj1Count = proj2Count = 0;
 202     };
 203
 204     counting_predicate pred(std::ranges::equal_to{}, predCount);
 205     counting_projection<> proj1(proj1Count);
 206     counting_projection<> proj2(proj2Count);
 207
 208     {
 209       // 1. No applications of the corresponding predicate if `ForwardIterator1` and `ForwardIterator2` meet the
 210       //    requirements of random access iterators and `last1 - first1 != last2 - first2`.
 211       int a[] = {1, 2, 3, 4, 5};
 212       int b[] = {1, 2, 3, 4};
 213       // Make sure that the iterators have different types.
 214       auto b_begin = random_access_iterator<int*>(std::begin(b));
 215       auto b_end = random_access_iterator<int*>(std::end(b));
 216
 217       {
 218         auto ret = std::ranges::is_permutation(a, a + 5, b_begin, b_end, pred, proj1, proj2);
 219         assert(!ret);
 220
 221         assert(predCount == 0);
 222         assert(proj1Count == 0);
 223         assert(proj2Count == 0);
 224         reset_counters();
 225       }
 226
 227       {
 228         auto ret = std::ranges::is_permutation(a, std::ranges::subrange(b_begin, b_end), pred, proj1, proj2);
 229         assert(!ret);
 230
 231         assert(predCount == 0);
 232         assert(proj1Count == 0);
 233         assert(proj2Count == 0);
 234         reset_counters();
 235       }
 236     }
 237
 238     // 2. Otherwise, exactly last1 - first1 applications of the corresponding predicate if
 239     // `equal(first1, last1, first2, last2, pred)` would return true.
 240     {
 241       int a[] = {1, 2, 3, 4, 5};
 242       int b[] = {1, 2, 3, 4, 5};
 243       int expected = 5;
 244
 245       {
 246         auto ret = std::ranges::is_permutation(a, a + 5, b, b + 5, pred, proj1, proj2);
 247         assert(ret);
 248
 249         assert(predCount == expected);
 250         assert(proj1Count == expected);
 251         assert(proj2Count == expected);
 252         reset_counters();
 253       }
 254
 255       {
 256         auto ret = std::ranges::is_permutation(a, b, pred, proj1, proj2);
 257         assert(ret);
 258
 259         assert(predCount == expected);
 260         assert(proj1Count == expected);
 261         assert(proj2Count == expected);
 262         reset_counters();
 263       }
 264     }
 265
 266     // Note: we currently don't have the setup to test big-O complexity, but copying the requirement for completeness'
 267     // sake.
 268     // 3. Otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`.
 269   }
 270
 271
 272   return true;
 273 }
 274
 275 int main(int, char**) {
 276   test();
 277   static_assert(test());
 278
 279   return 0;
 280 }