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
39template <class Iter1, class Sent1 = int*, class Iter2 = int*, class Sent2 = int*>
40concept HasIsPermutationIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
41 std::ranges::is_permutation(first1, last1, first2, last2);
42};
43
44template <class Range1, class Range2 = UncheckedRange<int*>>
45concept HasIsPermutationR = requires(Range1 range1, Range2 range2) {
46 std::ranges::is_permutation(range1, range2);
47};
48
49static_assert(HasIsPermutationIt<int*>);
50static_assert(!HasIsPermutationIt<ForwardIteratorNotDerivedFrom>);
51static_assert(!HasIsPermutationIt<ForwardIteratorNotIncrementable>);
52static_assert(!HasIsPermutationIt<int*, SentinelForNotSemiregular>);
53static_assert(!HasIsPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
54static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotDerivedFrom>);
55static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotIncrementable>);
56static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotSemiregular>);
57static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
58// !indirect_equivalence_relation<Pred, projected<I1, Proj1>, projected<I2, Proj2>>;
59static_assert(!HasIsPermutationIt<int*, int*, int**, int**>);
60
61static_assert(HasIsPermutationR<UncheckedRange<int*>>);
62static_assert(!HasIsPermutationR<ForwardRangeNotDerivedFrom>);
63static_assert(!HasIsPermutationR<ForwardRangeNotIncrementable>);
64static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelSemiregular>);
65static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelEqualityComparableWith>);
66static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
67static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
68static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
69static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
70// !indirect_equivalence_relation<Pred, projected<iterator_t<I1>, Proj1>, projected<iterator_t<I2>, Proj2>>;
71static_assert(!HasIsPermutationIt<UncheckedRange<int*>, UncheckedRange<int**>>);
72
73template <int N, int M>
74struct Data {
75 std::array<int, N> input1;
76 std::array<int, M> input2;
77 bool expected;
78};
79
80template <class Iter1, class Sent1, class Iter2, class Sent2, int N, int M>
81constexpr 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
97template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
98constexpr 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
130template <class Iter1, class Sent1 = Iter1>
131constexpr 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
141constexpr 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{.a: 2}, A{.a: 3}, A{.a: 1}};
157 std::array in2 = {A{.a: 1}, A{.a: 2}, A{.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: a * 2}; }
177 constexpr A div2() const { return A{.a: a / 2}; }
178 };
179
180 std::array in1 = {A{.a: 1}, A{.a: 2}, A{.a: 3}}; // [2, 4, 6] after applying `x2`.
181 std::array in2 = {A{.a: 4}, A{.a: 8}, A{.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(arr&: b));
215 auto b_end = random_access_iterator<int*>(std::end(arr&: 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
275int main(int, char**) {
276 test();
277 static_assert(test());
278
279 return 0;
280}
281

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp