281 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 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++2020//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++2027 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{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 the210 // 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 if239 // `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