diff options
Diffstat (limited to 'libcxx/include/__algorithm/is_permutation.h')
| -rw-r--r-- | libcxx/include/__algorithm/is_permutation.h | 260 |
1 files changed, 168 insertions, 92 deletions
diff --git a/libcxx/include/__algorithm/is_permutation.h b/libcxx/include/__algorithm/is_permutation.h index cdd742048412..005445652e9d 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 <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,140 +28,210 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_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 <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class = void> +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 <class _Iter1, class _Sent1, class _Iter2, class _Sent2> +struct _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2, __enable_if_t< + sized_sentinel_for<_Sent1, _Iter1> && + sized_sentinel_for<_Sent2, _Iter2> +>> : true_type {}; + +#else + +template <class _Iter1, class _Iter2> +struct _ConstTimeDistance<_Iter1, _Iter1, _Iter2, _Iter2, __enable_if_t< + is_same<typename iterator_traits<_Iter1>::iterator_category, random_access_iterator_tag>::value && + is_same<typename iterator_traits<_Iter2>::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 <class _AlgPolicy, + class _Iter1, class _Sent1, class _Iter2, class _Sent2, + class _Proj1, class _Proj2, class _Pred> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 <class _ForwardIterator1, class _ForwardIterator2> -_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 <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _BinaryPredicate> +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> -_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 <class _AlgPolicy, + class _Iter1, class _Sent1, class _Iter2, class _Sent2, + class _Proj1, class _Proj2, class _Pred> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_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 <class _AlgPolicy, + class _Iter1, class _Sent1, class _Iter2, class _Sent2, + class _Proj1, class _Proj2, class _Pred> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 <class _AlgPolicy, + class _Iter1, class _Sent1, class _Iter2, class _Sent2, + class _Proj1, class _Proj2, class _Pred> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 <class _ForwardIterator1, class _ForwardIterator2> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { + return std::is_permutation(__first1, __last1, __first2, __equal_to()); } +#if _LIBCPP_STD_VER > 11 + +// 2+2 iterators template <class _ForwardIterator1, class _ForwardIterator2> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation( + _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + return std::__is_permutation<_ClassicAlgPolicy>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + __equal_to(), + __identity(), + __identity()); +} + +// 2+2 iterators, predicate +template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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()); + _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 + +#endif // _LIBCPP_STD_VER > 11 _LIBCPP_END_NAMESPACE_STD |