From 4038c859e58c12e997041927a87e880f2f3ef883 Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Thu, 4 Aug 2022 10:54:13 -0700 Subject: [PATCH] [libc++][ranges] Implement `ranges::is_permutation` Co-authored-by: Konstantin Varlamov Differential Revision: https://reviews.llvm.org/D127194 --- libcxx/docs/Status/RangesAlgorithms.csv | 2 +- libcxx/include/CMakeLists.txt | 1 + libcxx/include/__algorithm/is_permutation.h | 259 ++++++++++++------- libcxx/include/__algorithm/ranges_is_permutation.h | 89 +++++++ libcxx/include/__iterator/iterator_traits.h | 6 + libcxx/include/algorithm | 16 ++ libcxx/include/module.modulemap.in | 1 + ...ges_robust_against_copying_comparators.pass.cpp | 4 +- ...ges_robust_against_copying_projections.pass.cpp | 4 +- libcxx/test/libcxx/private_headers.verify.cpp | 1 + .../ranges.is_permutation.pass.cpp | 281 +++++++++++++++++++++ .../alg.sort/sort/sort_constexpr.pass.cpp | 26 +- .../alg.sort/sort/sort_constexpr_comp.pass.cpp | 26 +- ...s_robust_against_differing_projections.pass.cpp | 2 +- ...nges_robust_against_nonbool_predicates.pass.cpp | 2 +- .../ranges_robust_against_omitting_invoke.pass.cpp | 2 +- .../ranges_robust_against_proxy_iterators.pass.cpp | 2 +- .../niebloid.compile.pass.cpp | 2 +- 18 files changed, 601 insertions(+), 125 deletions(-) create mode 100644 libcxx/include/__algorithm/ranges_is_permutation.h create mode 100644 libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 6982f1e..6429896 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -33,7 +33,7 @@ Read-only,includes,Hui Xie,`D130116 `_,✅ Read-only,is_heap,Konstantin Varlamov,`D130547 `_,✅ Read-only,is_heap_until,Konstantin Varlamov,`D130547 `_,✅ Read-only,clamp,Nikolas Klauser,`D126193 `_,✅ -Read-only,is_permutation,Nikolas Klauser,`D127194 `_,Under review +Read-only,is_permutation,Nikolas Klauser,`D127194 `_,✅ 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 index 7ce9b66..f7c2d99 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -97,6 +97,7 @@ set(files __algorithm/ranges_is_heap.h __algorithm/ranges_is_heap_until.h __algorithm/ranges_is_partitioned.h + __algorithm/ranges_is_permutation.h __algorithm/ranges_is_sorted.h __algorithm/ranges_is_sorted_until.h __algorithm/ranges_iterator_concept.h diff --git a/libcxx/include/__algorithm/is_permutation.h b/libcxx/include/__algorithm/is_permutation.h index cdd7420..06a4949 100644 --- a/libcxx/include/__algorithm/is_permutation.h +++ b/libcxx/include/__algorithm/is_permutation.h @@ -11,10 +11,16 @@ #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> +#include <__utility/move.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,140 +28,211 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool -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) - if (!__pred(*__first1, *__first2)) - break; - if (__first1 == __last1) - return true; +template +struct _ConstTimeDistance : false_type {}; - // __first1 != __last1 && *__first1 != *__first2 - typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; - _D1 __l1 = _VSTD::distance(__first1, __last1); - if (__l1 == _D1(1)) - return false; - _ForwardIterator2 __last2 = _VSTD::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) { +#if _LIBCPP_STD_VER > 17 + +template +struct _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2, __enable_if_t< + sized_sentinel_for<_Sent1, _Iter1> && + sized_sentinel_for<_Sent2, _Iter2> +>> : true_type {}; + +#else + +template +struct _ConstTimeDistance<_Iter1, _Iter1, _Iter2, _Iter2, __enable_if_t< + is_same::iterator_category, random_access_iterator_tag>::value && + is_same::iterator_category, random_access_iterator_tag>::value +> > : true_type {}; + +#endif // _LIBCPP_STD_VER > 17 + +// Internal functions + +// For each element in [f1, l1) see if there are the same number of equal elements in [f2, l2) +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__is_permutation_impl(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2) { + using _D1 = __iter_diff_t<_Iter1>; + + 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 = _IterOps<_AlgPolicy>::next(__i); __j != __last1; ++__j) { + if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj1, *__j))) ++__c1; + } if (__c1 != __c2) return false; } } + return true; } -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>()); +// 2+1 iterators, predicate. Not used by range algorithms. +template +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__is_permutation(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, + _BinaryPredicate&& __pred) { + // Shorten sequences as much as possible by lopping of any equal prefix. + for (; __first1 != __last1; ++__first1, (void)++__first2) { + if (!__pred(*__first1, *__first2)) + break; + } + + if (__first1 == __last1) + return true; + + // __first1 != __last1 && *__first1 != *__first2 + using _D1 = __iter_diff_t<_ForwardIterator1>; + _D1 __l1 = _IterOps<_AlgPolicy>::distance(__first1, __last1); + if (__l1 == _D1(1)) + return false; + auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __l1); + + return std::__is_permutation_impl<_AlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __pred, __identity(), __identity()); } -#if _LIBCPP_STD_VER > 11 -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { - // shorten sequences as much as possible by lopping of any equal prefix - for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) - if (!__pred(*__first1, *__first2)) +// 2+2 iterators, predicate, non-constant time `distance`. +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2, + /*_ConstTimeDistance=*/false_type) { + // Shorten sequences as much as possible by lopping of any equal prefix. + 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) // Second range is shorter return false; - typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; - _D1 __l1 = _VSTD::distance(__first1, __last1); + using _D1 = __iter_diff_t<_Iter1>; + _D1 __l1 = _IterOps<_AlgPolicy>::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 = _IterOps<_AlgPolicy>::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) { - // Have we already counted the number of *__i in [f1, l1)? - _ForwardIterator1 __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) - 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) - if (__pred(*__i, *__j)) - ++__c1; - if (__c1 != __c2) - return false; - } - } - return true; + return std::__is_permutation_impl<_AlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __pred, __proj1, __proj2); } -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, - _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, - _BinaryPredicate __pred, random_access_iterator_tag, - random_access_iterator_tag) { - if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) +// 2+2 iterators, predicate, specialization for constant-time `distance` call. +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2, + /*_ConstTimeDistance=*/true_type) { + if (std::distance(__first1, __last1) != std::distance(__first2, __last2)) return false; - return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, - _BinaryPredicate&>(__first1, __last1, __first2, __pred); + return std::__is_permutation<_AlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __pred, __proj1, __proj2, + /*_ConstTimeDistance=*/false_type()); +} + +// 2+2 iterators, predicate +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2) { + return std::__is_permutation<_AlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __pred, __proj1, __proj2, + _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2>()); } +// Public interface + +// 2+1 iterators, predicate template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _BinaryPredicate __pred) { - return _VSTD::__is_permutation<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, + "The predicate has to be callable"); + + return std::__is_permutation<_ClassicAlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), __pred); } +// 2+1 iterators +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { + 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 + +// 2+2 iterators template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _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; - return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); + using __v1 = __iter_value_type<_ForwardIterator1>; + using __v2 = __iter_value_type<_ForwardIterator2>; + + return std::__is_permutation<_ClassicAlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __equal_to<__v1, __v2>(), __identity(), __identity()); } -#endif + +// 2+2 iterators, predicate +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, + "The predicate has to be callable"); + + return std::__is_permutation<_ClassicAlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __pred, __identity(), __identity()); +} + +#endif // _LIBCPP_STD_VER > 11 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_is_permutation.h b/libcxx/include/__algorithm/ranges_is_permutation.h new file mode 100644 index 0000000..41e302f --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_permutation.h @@ -0,0 +1,89 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__algorithm/iterator_operations.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> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __is_permutation { +struct __fn { + + template + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __is_permutation_func_impl(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { + return std::__is_permutation<_RangeAlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), + __pred, __proj1, __proj2); + } + + 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 __is_permutation_func_impl( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__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 __is_permutation_func_impl( + 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_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_IS_PERMUTATION_H diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h index 254f8c2..5600a2b 100644 --- a/libcxx/include/__iterator/iterator_traits.h +++ b/libcxx/include/__iterator/iterator_traits.h @@ -507,6 +507,12 @@ using __iterator_category_type = typename iterator_traits<_Iter>::iterator_categ template using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer; +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 index bf8a984..69ada03 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -793,6 +793,21 @@ namespace ranges { borrowed_iterator_t shuffle(R&& r, Gen&& g); // Since C++20 template S1, forward_iterator I2, + sentinel_for S2, class Proj1 = identity, class Proj2 = identity, + indirect_equivalence_relation, + projected> Pred = ranges::equal_to> + constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2, + Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template, Proj1>, + projected, Proj2>> Pred = ranges::equal_to> + constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template S1, forward_iterator I2, sentinel_for S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable @@ -1794,6 +1809,7 @@ template #include <__algorithm/ranges_is_heap.h> #include <__algorithm/ranges_is_heap_until.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_lexicographical_compare.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index 0b33ffd..204fe40 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -336,6 +336,7 @@ module std [system] { module ranges_is_heap { private header "__algorithm/ranges_is_heap.h" } module ranges_is_heap_until { private header "__algorithm/ranges_is_heap_until.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_iterator_concept { private header "__algorithm/ranges_iterator_concept.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 index 1582981..419e2eb 100644 --- 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 @@ constexpr bool all_the_algorithms() (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 index 074df6e..c0295b8 100644 --- 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 @@ constexpr bool all_the_algorithms() (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 index 49fce41..a6a07f4 100644 --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -134,6 +134,7 @@ END-SCRIPT #include <__algorithm/ranges_is_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_heap.h'}} #include <__algorithm/ranges_is_heap_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_heap_until.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_iterator_concept.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_iterator_concept.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 index 0000000..14bc747 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp @@ -0,0 +1,281 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// + +// template S1, forward_iterator I2, +// sentinel_for S2, class Proj1 = identity, class Proj2 = identity, +// indirect_equivalence_relation, +// projected> Pred = ranges::equal_to> +// constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2, +// Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 +// +// template, Proj1>, +// projected, Proj2>> Pred = ranges::equal_to> +// constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.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); +// !indirect_equivalence_relation, projected>; +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>); +// !indirect_equivalence_relation, Proj1>, projected, Proj2>>; +static_assert(!HasIsPermutationIt, UncheckedRange>); + +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 swapped. + test({.input1 = {4, 2, 3, 1}, .input2 = {1, 2, 3, 4}, .expected = true}); + + // The first range is shorter. + test({.input1 = {4, 2, 3, 1}, .input2 = {4, 3, 2, 1, 5}, .expected = false}); + + // The first range is longer. + 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}); + + // 1-element range, same value. + test({.input1 = {1}, .input2 = {1}, .expected = true}); + + // 1-element range, different values. + test({.input1 = {1}, .input2 = {2}, .expected = false}); +} + +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(); + + { // A custom comparator works. + struct A { + int a; + constexpr bool pred(const A& rhs) const { return a == rhs.a; } + }; + + std::array in1 = {A{2}, A{3}, A{1}}; + std::array in2 = {A{1}, A{2}, A{3}}; + + { + auto ret = std::ranges::is_permutation(in1.begin(), in1.end(), in2.begin(), in2.end(), &A::pred); + assert(ret); + } + + { + auto ret = std::ranges::is_permutation(in1, in2, &A::pred); + assert(ret); + } + } + + { // A custom projection works. + struct A { + int a; + + constexpr bool operator==(const A&) const = default; + + constexpr A x2() const { return A{a * 2}; } + constexpr A div2() const { return A{a / 2}; } + }; + + std::array in1 = {A{1}, A{2}, A{3}}; // [2, 4, 6] after applying `x2`. + std::array in2 = {A{4}, A{8}, A{12}}; // [2, 4, 6] after applying `div2`. + + { + auto ret = std::ranges::is_permutation( + in1.begin(), in1.end(), in2.begin(), in2.end(), {}, &A::x2, &A::div2); + assert(ret); + } + + { + auto ret = std::ranges::is_permutation(in1, in2, {}, &A::x2, &A::div2); + assert(ret); + } + } + + + { // Check that complexity requirements are met. + int predCount = 0; + int proj1Count = 0; + int proj2Count = 0; + auto reset_counters = [&] { + predCount = proj1Count = proj2Count = 0; + }; + + counting_predicate pred(std::ranges::equal_to{}, predCount); + counting_projection<> proj1(proj1Count); + counting_projection<> proj2(proj2Count); + + { + // 1. No applications of the corresponding predicate if `ForwardIterator1` and `ForwardIterator2` meet the + // requirements of random access iterators and `last1 - first1 != last2 - first2`. + int a[] = {1, 2, 3, 4, 5}; + int b[] = {1, 2, 3, 4}; + // Make sure that the iterators have different types. + auto b_begin = random_access_iterator(std::begin(b)); + auto b_end = random_access_iterator(std::end(b)); + + { + auto ret = std::ranges::is_permutation(a, a + 5, b_begin, b_end, pred, proj1, proj2); + assert(!ret); + + assert(predCount == 0); + assert(proj1Count == 0); + assert(proj2Count == 0); + reset_counters(); + } + + { + auto ret = std::ranges::is_permutation(a, std::ranges::subrange(b_begin, b_end), pred, proj1, proj2); + assert(!ret); + + assert(predCount == 0); + assert(proj1Count == 0); + assert(proj2Count == 0); + reset_counters(); + } + } + + // 2. Otherwise, exactly last1 - first1 applications of the corresponding predicate if + // `equal(first1, last1, first2, last2, pred)` would return true. + { + int a[] = {1, 2, 3, 4, 5}; + int b[] = {1, 2, 3, 4, 5}; + int expected = 5; + + { + auto ret = std::ranges::is_permutation(a, a + 5, b, b + 5, pred, proj1, proj2); + assert(ret); + + assert(predCount == expected); + assert(proj1Count == expected); + assert(proj2Count == expected); + reset_counters(); + } + + { + auto ret = std::ranges::is_permutation(a, b, pred, proj1, proj2); + assert(ret); + + assert(predCount == expected); + assert(proj1Count == expected); + assert(proj2Count == expected); + reset_counters(); + } + } + + // Note: we currently don't have the setup to test big-O complexity, but copying the requirement for completeness' + // sake. + // 3. Otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`. + } + + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp index d719f00..afe199d 100644 --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp @@ -21,6 +21,8 @@ #include "test_iterators.h" #include "MoveOnly.h" +const int LargeN = 128; + template TEST_CONSTEXPR_CXX20 bool test() { @@ -61,14 +63,14 @@ int main(int, char**) { test<7, int, int*>(); test<7, int, random_access_iterator >(); - test<257, int, int*>(); - test<257, int, random_access_iterator >(); + test(); + test >(); #if TEST_STD_VER >= 11 test<7, MoveOnly, MoveOnly*>(); test<7, MoveOnly, random_access_iterator >(); - test<257, MoveOnly, MoveOnly*>(); - test<257, MoveOnly, random_access_iterator >(); + test(); + test >(); #endif test_pointers<17, char, char**>(); @@ -80,9 +82,9 @@ int main(int, char**) #if TEST_STD_VER >= 20 test<7, int, contiguous_iterator>(); - test<257, int, contiguous_iterator>(); + test>(); test<7, MoveOnly, contiguous_iterator>(); - test<257, MoveOnly, contiguous_iterator>(); + test>(); test_pointers<17, char, contiguous_iterator>(); test_pointers<17, const char, contiguous_iterator>(); test_pointers<17, int, contiguous_iterator>(); @@ -90,16 +92,16 @@ int main(int, char**) static_assert(test<7, int, int*>()); static_assert(test<7, int, random_access_iterator>()); static_assert(test<7, int, contiguous_iterator>()); - static_assert(test<257, int, int*>()); - static_assert(test<257, int, random_access_iterator>()); - static_assert(test<257, int, contiguous_iterator>()); + static_assert(test()); + static_assert(test>()); + static_assert(test>()); static_assert(test<7, MoveOnly, MoveOnly*>()); static_assert(test<7, MoveOnly, random_access_iterator>()); static_assert(test<7, MoveOnly, contiguous_iterator>()); - static_assert(test<257, MoveOnly, MoveOnly*>()); - static_assert(test<257, MoveOnly, random_access_iterator>()); - static_assert(test<257, MoveOnly, contiguous_iterator>()); + static_assert(test()); + static_assert(test>()); + static_assert(test>()); static_assert(test_pointers<17, char, char**>()); static_assert(test_pointers<17, char, random_access_iterator>()); diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp index bfdefed..134830f 100644 --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp @@ -22,6 +22,8 @@ #include "test_iterators.h" #include "MoveOnly.h" +const int LargeN = 128; + template TEST_CONSTEXPR_CXX20 bool test() { @@ -62,14 +64,14 @@ int main(int, char**) { test<7, int, int*>(); test<7, int, random_access_iterator >(); - test<257, int, int*>(); - test<257, int, random_access_iterator >(); + test(); + test >(); #if TEST_STD_VER >= 11 test<7, MoveOnly, MoveOnly*>(); test<7, MoveOnly, random_access_iterator >(); - test<257, MoveOnly, MoveOnly*>(); - test<257, MoveOnly, random_access_iterator >(); + test(); + test >(); #endif test_pointers<17, char, char**>(); @@ -81,9 +83,9 @@ int main(int, char**) #if TEST_STD_VER >= 20 test<7, int, contiguous_iterator>(); - test<257, int, contiguous_iterator>(); + test>(); test<7, MoveOnly, contiguous_iterator>(); - test<257, MoveOnly, contiguous_iterator>(); + test>(); test_pointers<17, char, contiguous_iterator>(); test_pointers<17, const char, contiguous_iterator>(); test_pointers<17, int, contiguous_iterator>(); @@ -91,16 +93,16 @@ int main(int, char**) static_assert(test<7, int, int*>()); static_assert(test<7, int, random_access_iterator>()); static_assert(test<7, int, contiguous_iterator>()); - static_assert(test<257, int, int*>()); - static_assert(test<257, int, random_access_iterator>()); - static_assert(test<257, int, contiguous_iterator>()); + static_assert(test()); + static_assert(test>()); + static_assert(test>()); static_assert(test<7, MoveOnly, MoveOnly*>()); static_assert(test<7, MoveOnly, random_access_iterator>()); static_assert(test<7, MoveOnly, contiguous_iterator>()); - static_assert(test<257, MoveOnly, MoveOnly*>()); - static_assert(test<257, MoveOnly, random_access_iterator>()); - static_assert(test<257, MoveOnly, contiguous_iterator>()); + static_assert(test()); + static_assert(test>()); + static_assert(test>()); static_assert(test_pointers<17, char, char**>()); static_assert(test_pointers<17, char, random_access_iterator>()); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp index 5293fab..00a0b63 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp @@ -56,7 +56,7 @@ constexpr bool test_all() { test(std::ranges::equal, in, in2, eq, proj1, proj2); test(std::ranges::lexicographical_compare, in, in2, eq, proj1, proj2); - //test(std::ranges::is_permutation, in, in2, eq, proj1, proj2); + test(std::ranges::is_permutation, in, in2, eq, proj1, proj2); test(std::ranges::includes, in, in2, less, proj1, proj2); test(std::ranges::find_first_of, in, in2, eq, proj1, proj2); test(std::ranges::mismatch, in, in2, eq, proj1, proj2); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp index 114a099..367059b 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp @@ -110,7 +110,7 @@ constexpr bool test_all() { test(std::ranges::is_heap, in, binary_pred); test(std::ranges::is_heap_until, in, binary_pred); std::ranges::clamp(2, 1, 3, binary_pred); - //test(std::ranges::is_permutation, in, in2, binary_pred); + test(std::ranges::is_permutation, in, in2, binary_pred); test(std::ranges::copy_if, in, out, unary_pred); test(std::ranges::remove_copy_if, in, out, unary_pred); test(std::ranges::replace_if, in, unary_pred, x); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp index 787c92f..80416b02 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -117,7 +117,7 @@ constexpr bool test_all() { test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val); test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val); std::ranges::clamp(b, a, c, &Foo::binary_pred, &Bar::val); - //test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val); std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val); // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate. diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp index 709913d..5517e7b 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -104,7 +104,7 @@ constexpr void run_tests() { test(std::ranges::includes, in, in2); test(std::ranges::is_heap, in); test(std::ranges::is_heap_until, in); - //test(std::ranges::is_permutation, in, in2); + test(std::ranges::is_permutation, in, in2); test(std::ranges::for_each, in, std::identity{}); std::ranges::for_each_n(in.begin(), count, std::identity{}); if constexpr (std::copyable) { 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 index 2be8a7e..9e5398b 100644 --- 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 @@ -91,7 +91,7 @@ static_assert(test(std::ranges::inplace_merge, a, a+5)); 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)); -- 2.7.4