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>
test(Data<N,M> d)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>
test_iterators()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>
test_iterators1()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 
test()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 
main(int,char **)275 int main(int, char**) {
276   test();
277   static_assert(test());
278 
279   return 0;
280 }
281