diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -33,7 +33,7 @@ Read-only,is_heap,Not assigned,n/a,Not started Read-only,is_heap_until,Not assigned,n/a,Not started Read-only,clamp,Nikolas Klauser,`D126193 `_,Under review -Read-only,is_permutation,Not assigned,n/a,Not started +Read-only,is_permutation,Nikolas Klauser,` `_,✅ Read-only,for_each,Nikolas Klauser,`D124332 `_,✅ Read-only,for_each_n,Nikolas Klauser,`D124332 `_,✅ Write,copy,Nikolas Klauser,`D122982 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -85,6 +85,7 @@ __algorithm/ranges_for_each.h __algorithm/ranges_for_each_n.h __algorithm/ranges_is_partitioned.h + __algorithm/ranges_is_permutation.h __algorithm/ranges_is_sorted.h __algorithm/ranges_is_sorted_until.h __algorithm/ranges_lower_bound.h diff --git a/libcxx/include/__algorithm/is_permutation.h b/libcxx/include/__algorithm/is_permutation.h --- a/libcxx/include/__algorithm/is_permutation.h +++ b/libcxx/include/__algorithm/is_permutation.h @@ -12,9 +12,11 @@ #include <__algorithm/comp.h> #include <__config> +#include <__iterator/concepts.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -27,37 +29,39 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) { // shorten sequences as much as possible by lopping of any equal prefix - for (; __first1 != __last1; ++__first1, (void)++__first2) + for (; __first1 != __last1; ++__first1, (void)++__first2) { if (!__pred(*__first1, *__first2)) break; + } + if (__first1 == __last1) return true; // __first1 != __last1 && *__first1 != *__first2 - typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; - _D1 __l1 = _VSTD::distance(__first1, __last1); + using _D1 = __iter_diff_t<_ForwardIterator1>; + _D1 __l1 = std::distance(__first1, __last1); if (__l1 == _D1(1)) return false; - _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1); + auto __last2 = std::next(__first2, __l1); // For each element in [f1, l1) see if there are the same number of // equal elements in [f2, l2) - for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { + for (auto __i = __first1; __i != __last1; ++__i) { // Have we already counted the number of *__i in [f1, l1)? - _ForwardIterator1 __match = __first1; + auto __match = __first1; for (; __match != __i; ++__match) if (__pred(*__match, *__i)) break; if (__match == __i) { // Count number of *__i in [f2, l2) _D1 __c2 = 0; - for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) + for (auto __j = __first2; __j != __last2; ++__j) if (__pred(*__i, *__j)) ++__c2; if (__c2 == 0) return false; // Count number of *__i in [__i, l1) (we can start with 1) _D1 __c1 = 1; - for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) + for (auto __j = std::next(__i); __j != __last1; ++__j) if (__pred(*__i, *__j)) ++__c1; if (__c1 != __c2) @@ -70,53 +74,69 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); + using __v1 = __iter_value_type<_ForwardIterator1>; + using __v2 = __iter_value_type<_ForwardIterator2>; + return std::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); } #if _LIBCPP_STD_VER > 11 -template +template _LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { +__is_permutation(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + if constexpr (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>) { + if (__last1 - __first1 != __last2 - __first2) + return false; + } +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + // shorten sequences as much as possible by lopping of any equal prefix - for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) - if (!__pred(*__first1, *__first2)) + while (__first1 != __last1 && __first2 != __last2) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; + ++__first1; + ++__first2; + } + if (__first1 == __last1) return __first2 == __last2; - else if (__first2 == __last2) + if (__first2 == __last2) return false; - typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; - _D1 __l1 = _VSTD::distance(__first1, __last1); + using _D1 = __iter_diff_t<_Iter1>; + _D1 __l1 = std::__ranges_distance(__first1, __last1); - typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2; - _D2 __l2 = _VSTD::distance(__first2, __last2); + using _D2 = __iter_diff_t<_Iter2>; + _D2 __l2 = std::__ranges_distance(__first2, __last2); if (__l1 != __l2) return false; // For each element in [f1, l1) see if there are the same number of // equal elements in [f2, l2) - for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { + for (auto __i = __first1; __i != __last1; ++__i) { // Have we already counted the number of *__i in [f1, l1)? - _ForwardIterator1 __match = __first1; - for (; __match != __i; ++__match) - if (__pred(*__match, *__i)) + auto __match = __first1; + for (; __match != __i; ++__match) { + if (std::__invoke(__pred, std::__invoke(__proj1, *__match), std::__invoke(__proj1, *__i))) break; + } + if (__match == __i) { // Count number of *__i in [f2, l2) _D1 __c2 = 0; - for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) - if (__pred(*__i, *__j)) + for (auto __j = __first2; __j != __last2; ++__j) + if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j))) ++__c2; if (__c2 == 0) return false; // Count number of *__i in [__i, l1) (we can start with 1) _D1 __c1 = 1; - for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) - if (__pred(*__i, *__j)) + for (auto __j = std::next(__i); __j != __last1; ++__j) + if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j))) ++__c1; if (__c1 != __c2) return false; @@ -130,9 +150,9 @@ _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { - if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) + if (std::distance(__first1, __last1) != std::distance(__first2, __last2)) return false; - return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, + return std::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, _BinaryPredicate&>(__first1, __last1, __first2, __pred); } @@ -149,8 +169,8 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + typedef __iter_value_type<_ForwardIterator1> __v1; + typedef __iter_value_type<_ForwardIterator2> __v2; return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category()); diff --git a/libcxx/include/__algorithm/ranges_is_permutation.h b/libcxx/include/__algorithm/ranges_is_permutation.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_permutation.h @@ -0,0 +1,75 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_IS_PERMUTATION_H +#define _LIBCPP___ALGORITHM_RANGES_IS_PERMUTATION_H + +#include <__algorithm/is_permutation.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __is_permutation { +struct __fn { + + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Proj1 = identity, + class _Proj2 = identity, + indirect_equivalence_relation, + projected<_Iter2, _Proj2>> _Pred = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return std::__is_permutation(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + } + + template , _Proj1>, projected, _Proj2>> _Pred = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + if constexpr (sized_range<_Range1> && sized_range<_Range2>) { + if (ranges::distance(__range1) != ranges::distance(__range2)) + return false; + } + + return std::__is_permutation(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + } +}; +} // namespace __is_permutation + +inline namespace __cpo { + inline constexpr auto is_permutation = __is_permutation::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_RANGES_IS_PERMUTATION_H diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h --- a/libcxx/include/__iterator/iterator_traits.h +++ b/libcxx/include/__iterator/iterator_traits.h @@ -492,6 +492,12 @@ typename add_const::value_type::first_type>::type, typename iterator_traits<_InputIterator>::value_type::second_type>; +template +using __iter_diff_t = typename iterator_traits<_Iter>::difference_type; + +template +using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1126,6 +1126,7 @@ #include <__algorithm/ranges_for_each.h> #include <__algorithm/ranges_for_each_n.h> #include <__algorithm/ranges_is_partitioned.h> +#include <__algorithm/ranges_is_permutation.h> #include <__algorithm/ranges_is_sorted.h> #include <__algorithm/ranges_is_sorted_until.h> #include <__algorithm/ranges_lower_bound.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -317,6 +317,7 @@ module ranges_for_each { private header "__algorithm/ranges_for_each.h" } module ranges_for_each_n { private header "__algorithm/ranges_for_each_n.h" } module ranges_is_partitioned { private header "__algorithm/ranges_is_partitioned.h" } + module ranges_is_permutation { private header "__algorithm/ranges_is_permutation.h" } module ranges_is_sorted { private header "__algorithm/ranges_is_sorted.h" } module ranges_is_sorted_until { private header "__algorithm/ranges_is_sorted_until.h" } module ranges_lower_bound { private header "__algorithm/ranges_lower_bound.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -132,8 +132,8 @@ //(void)std::ranges::is_heap_until(a, Less(&copies)); assert(copies == 0); (void)std::ranges::is_partitioned(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::is_partitioned(a, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::is_permutation(first, last, first2, last2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::is_permutation(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::is_permutation(first, last, first2, last2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::is_permutation(a, b, Equal(&copies)); assert(copies == 0); (void)std::ranges::is_sorted(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::is_sorted(a, Less(&copies)); assert(copies == 0); (void)std::ranges::is_sorted_until(first, last, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -115,8 +115,8 @@ //(void)std::ranges::is_heap_until(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_partitioned(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_partitioned(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::is_permutation(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::is_permutation(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::is_permutation(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::is_permutation(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_sorted(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_sorted(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_sorted_until(first, last, Less(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -122,6 +122,7 @@ #include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}} #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}} #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}} +#include <__algorithm/ranges_is_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_permutation.h'}} #include <__algorithm/ranges_is_sorted.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted.h'}} #include <__algorithm/ranges_is_sorted_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted_until.h'}} #include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp @@ -0,0 +1,224 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +template +concept HasIsPermutationIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { + std::ranges::is_permutation(first1, last1, first2, last2); +}; + +template > +concept HasIsPermutationR = requires(Range1 range1, Range2 range2) { + std::ranges::is_permutation(range1, range2); +}; + +static_assert(HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); +static_assert(!HasIsPermutationIt); + +static_assert(HasIsPermutationR>); +static_assert(!HasIsPermutationR); +static_assert(!HasIsPermutationR); +static_assert(!HasIsPermutationR); +static_assert(!HasIsPermutationR); +static_assert(!HasIsPermutationR, ForwardRangeNotDerivedFrom>); +static_assert(!HasIsPermutationR, ForwardRangeNotIncrementable>); +static_assert(!HasIsPermutationR, ForwardRangeNotSentinelSemiregular>); +static_assert(!HasIsPermutationR, ForwardRangeNotSentinelEqualityComparableWith>); + +template +struct Data { + std::array input1; + std::array input2; + bool expected; +}; + +template +constexpr void test(Data d) { + { + std::same_as decltype(auto) ret = std::ranges::is_permutation(Iter1(d.input1.data()), + Sent1(Iter1(d.input1.data() + N)), + Iter1(d.input2.data()), + Sent1(Iter1(d.input2.data() + M))); + assert(ret == d.expected); + } + { + auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + N))); + auto range2 = std::ranges::subrange(Iter1(d.input2.data()), Sent1(Iter1(d.input2.data() + M))); + std::same_as decltype(auto) ret = std::ranges::is_permutation(range1, range2); + assert(ret == d.expected); + } +} + +template +constexpr void test_iterators() { + // ranges are identical + test({.input1 = {1, 2, 3, 4}, .input2 = {1, 2, 3, 4}, .expected = true}); + + // ranges are reversed + test({.input1 = {1, 2, 3, 4}, .input2 = {4, 3, 2, 1}, .expected = true}); + + // two elements are changed + test({.input1 = {4, 2, 3, 1}, .input2 = {4, 3, 2, 1}, .expected = true}); + + // ranges have different lengths + test({.input1 = {4, 2, 3, 1, 5}, .input2 = {4, 3, 2, 1}, .expected = false}); + + // the first range is empty + test({.input1 = {}, .input2 = {4, 3, 2, 1}, .expected = false}); + + // the second range is empty + test({.input1 = {4, 2, 3, 1, 5}, .input2 = {}, .expected = false}); + + // both ranges are empty + test({.input1 = {}, .input2 = {}, .expected = true}); + +} + +template +constexpr void test_iterators1() { + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); +} + +constexpr bool test() { + test_iterators1, sentinel_wrapper>>(); + test_iterators1>(); + test_iterators1>(); + test_iterators1>(); + test_iterators1>(); + test_iterators1(); + test_iterators1(); + + { // check that the complexity requirements are met with identical ranges + { + int predCount = 0; + auto pred = [&](int, int) { ++predCount; return true; }; + auto proj1Count = 0; + auto proj1 = [&](int i) { ++proj1Count; return i; }; + auto proj2Count = 0; + auto proj2 = [&](int i) { ++proj2Count; return i; }; + int a[] = {1, 2, 3, 4, 5}; + auto ret = std::ranges::is_permutation(a, a + 5, a, a + 5, pred, proj1, proj2); + assert(ret); + assert(predCount == 5); + assert(proj1Count == 5); + assert(proj2Count == 5); + } + { + int predCount = 0; + auto pred = [&](int, int) { ++predCount; return true; }; + auto proj1Count = 0; + auto proj1 = [&](int i) { ++proj1Count; return i; }; + auto proj2Count = 0; + auto proj2 = [&](int i) { ++proj2Count; return i; }; + int a[] = {1, 2, 3, 4, 5}; + auto ret = std::ranges::is_permutation(a, a, pred, proj1, proj2); + assert(ret); + assert(predCount == 5); + assert(proj1Count == 5); + assert(proj2Count == 5); + } + } + + { // check that std::invoke is used + struct S { + constexpr S(int i_) : i(i_) {} + constexpr bool compare(const S& j) const { return j.i == i; } + constexpr const S& identity() const { return *this; } + int i; + }; + { + S a[] = {1, 2, 3, 4}; + auto ret = std::ranges::is_permutation(std::begin(a), std::end(a), + std::begin(a), std::end(a), + &S::compare, &S::identity, &S::identity); + assert(ret); + } + { + S a[] = {1, 2, 3, 4}; + auto ret = std::ranges::is_permutation(a, a, &S::compare, &S::identity, &S::identity); + assert(ret); + } + } + + { // check that the implicit conversion to bool works + { + int a[] = {1, 2, 2, 4}; + auto ret = std::ranges::is_permutation(a, a + 4, a, a + 4, [](int i, int j) { return BooleanTestable{i == j}; }); + assert(ret); + } + { + int a[] = {1, 2, 2, 4}; + auto ret = std::ranges::is_permutation(a, a, [](int i, int j) { return BooleanTestable{i == j}; }); + assert(ret); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + { // check that the complexity requirements are met with identical ranges + { + int predCount = 0; + auto pred = [&](int, int) { ++predCount; return true; }; + auto proj1Count = 0; + auto proj1 = [&](int i) { ++proj1Count; return i; }; + auto proj2Count = 0; + auto proj2 = [&](int i) { ++proj2Count; return i; }; + int a[] = {1, 2, 3, 4, 5}; + int b[] = {1, 2, 3, 4}; + auto ret = std::ranges::is_permutation(a, a + 5, b, b + 4, pred, proj1, proj2); + assert(!ret); + assert(predCount == 0); + assert(proj1Count == 0); + assert(proj2Count == 0); + } + { + int predCount = 0; + auto pred = [&](int, int) { ++predCount; return true; }; + auto proj1Count = 0; + auto proj1 = [&](int i) { ++proj1Count; return i; }; + auto proj2Count = 0; + auto proj2 = [&](int i) { ++proj2Count; return i; }; + int a[] = {1, 2, 3, 4, 5}; + std::list b = {1, 2, 3, 4}; + auto ret = std::ranges::is_permutation(a, b, pred, proj1, proj2); + assert(!ret); + assert(predCount == 0); + assert(proj1Count == 0); + assert(proj2Count == 0); + } + } + + return 0; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -90,7 +90,7 @@ //static_assert(test(std::ranges::is_heap, a)); //static_assert(test(std::ranges::is_heap_until, a)); static_assert(test(std::ranges::is_partitioned, a, odd)); -//static_assert(test(std::ranges::is_permutation, a, a)); +static_assert(test(std::ranges::is_permutation, a, a)); static_assert(test(std::ranges::is_sorted, a)); static_assert(test(std::ranges::is_sorted_until, a)); //static_assert(test(std::ranges::lexicographical_compare, a, a));