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