v1/__algorithm/is_permutation.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___ALGORITHM_IS_PERMUTATION_H
0011 #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H
0012
0013 #include <__algorithm/comp.h>
0014 #include <__algorithm/iterator_operations.h>
0015 #include <__config>
0016 #include <__functional/identity.h>
0017 #include <__iterator/concepts.h>
0018 #include <__iterator/distance.h>
0019 #include <__iterator/iterator_traits.h>
0020 #include <__type_traits/enable_if.h>
0021 #include <__type_traits/invoke.h>
0022 #include <__type_traits/is_callable.h>
0023 #include <__type_traits/is_same.h>
0024 #include <__utility/move.h>
0025
0026 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0027 #  pragma GCC system_header
0028 #endif
0029
0030 _LIBCPP_PUSH_MACROS
0031 #include <__undef_macros>
0032
0033 _LIBCPP_BEGIN_NAMESPACE_STD
0034
0035 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class = void>
0036 struct _ConstTimeDistance : false_type {};
0037
0038 #if _LIBCPP_STD_VER >= 20
0039
0040 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2>
0041 struct _ConstTimeDistance<_Iter1,
0042                           _Sent1,
0043                           _Iter2,
0044                           _Sent2,
0045                           __enable_if_t< sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2> >>
0046     : true_type {};
0047
0048 #else
0049
0050 template <class _Iter1, class _Iter2>
0051 struct _ConstTimeDistance<
0052     _Iter1,
0053     _Iter1,
0054     _Iter2,
0055     _Iter2,
0056     __enable_if_t< is_same<typename iterator_traits<_Iter1>::iterator_category, random_access_iterator_tag>::value &&
0057                    is_same<typename iterator_traits<_Iter2>::iterator_category, random_access_iterator_tag>::value > >
0058     : true_type {};
0059
0060 #endif // _LIBCPP_STD_VER >= 20
0061
0062 // Internal functions
0063
0064 // For each element in [f1, l1) see if there are the same number of equal elements in [f2, l2)
0065 template <class _AlgPolicy,
0066           class _Iter1,
0067           class _Sent1,
0068           class _Iter2,
0069           class _Sent2,
0070           class _Proj1,
0071           class _Proj2,
0072           class _Pred>
0073 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation_impl(
0074     _Iter1 __first1,
0075     _Sent1 __last1,
0076     _Iter2 __first2,
0077     _Sent2 __last2,
0078     _Pred&& __pred,
0079     _Proj1&& __proj1,
0080     _Proj2&& __proj2) {
0081   using _D1 = __iter_diff_t<_Iter1>;
0082
0083   for (auto __i = __first1; __i != __last1; ++__i) {
0084     //  Have we already counted the number of *__i in [f1, l1)?
0085     auto __match = __first1;
0086     for (; __match != __i; ++__match) {
0087       if (std::__invoke(__pred, std::__invoke(__proj1, *__match), std::__invoke(__proj1, *__i)))
0088         break;
0089     }
0090
0091     if (__match == __i) {
0092       // Count number of *__i in [f2, l2)
0093       _D1 __c2 = 0;
0094       for (auto __j = __first2; __j != __last2; ++__j) {
0095         if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j)))
0096           ++__c2;
0097       }
0098       if (__c2 == 0)
0099         return false;
0100
0101       // Count number of *__i in [__i, l1) (we can start with 1)
0102       _D1 __c1 = 1;
0103       for (auto __j = _IterOps<_AlgPolicy>::next(__i); __j != __last1; ++__j) {
0104         if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj1, *__j)))
0105           ++__c1;
0106       }
0107       if (__c1 != __c2)
0108         return false;
0109     }
0110   }
0111
0112   return true;
0113 }
0114
0115 // 2+1 iterators, predicate. Not used by range algorithms.
0116 template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _BinaryPredicate>
0117 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
0118     _ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, _BinaryPredicate&& __pred) {
0119   // Shorten sequences as much as possible by lopping of any equal prefix.
0120   for (; __first1 != __last1; ++__first1, (void)++__first2) {
0121     if (!__pred(*__first1, *__first2))
0122       break;
0123   }
0124
0125   if (__first1 == __last1)
0126     return true;
0127
0128   //  __first1 != __last1 && *__first1 != *__first2
0129   using _D1 = __iter_diff_t<_ForwardIterator1>;
0130   _D1 __l1  = _IterOps<_AlgPolicy>::distance(__first1, __last1);
0131   if (__l1 == _D1(1))
0132     return false;
0133   auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __l1);
0134
0135   return std::__is_permutation_impl<_AlgPolicy>(
0136       std::move(__first1),
0137       std::move(__last1),
0138       std::move(__first2),
0139       std::move(__last2),
0140       __pred,
0141       __identity(),
0142       __identity());
0143 }
0144
0145 // 2+2 iterators, predicate, non-constant time `distance`.
0146 template <class _AlgPolicy,
0147           class _Iter1,
0148           class _Sent1,
0149           class _Iter2,
0150           class _Sent2,
0151           class _Proj1,
0152           class _Proj2,
0153           class _Pred>
0154 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
0155     _Iter1 __first1,
0156     _Sent1 __last1,
0157     _Iter2 __first2,
0158     _Sent2 __last2,
0159     _Pred&& __pred,
0160     _Proj1&& __proj1,
0161     _Proj2&& __proj2,
0162     /*_ConstTimeDistance=*/false_type) {
0163   // Shorten sequences as much as possible by lopping of any equal prefix.
0164   while (__first1 != __last1 && __first2 != __last2) {
0165     if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
0166       break;
0167     ++__first1;
0168     ++__first2;
0169   }
0170
0171   if (__first1 == __last1)
0172     return __first2 == __last2;
0173   if (__first2 == __last2) // Second range is shorter
0174     return false;
0175
0176   using _D1 = __iter_diff_t<_Iter1>;
0177   _D1 __l1  = _IterOps<_AlgPolicy>::distance(__first1, __last1);
0178
0179   using _D2 = __iter_diff_t<_Iter2>;
0180   _D2 __l2  = _IterOps<_AlgPolicy>::distance(__first2, __last2);
0181   if (__l1 != __l2)
0182     return false;
0183
0184   return std::__is_permutation_impl<_AlgPolicy>(
0185       std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __pred, __proj1, __proj2);
0186 }
0187
0188 // 2+2 iterators, predicate, specialization for constant-time `distance` call.
0189 template <class _AlgPolicy,
0190           class _Iter1,
0191           class _Sent1,
0192           class _Iter2,
0193           class _Sent2,
0194           class _Proj1,
0195           class _Proj2,
0196           class _Pred>
0197 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
0198     _Iter1 __first1,
0199     _Sent1 __last1,
0200     _Iter2 __first2,
0201     _Sent2 __last2,
0202     _Pred&& __pred,
0203     _Proj1&& __proj1,
0204     _Proj2&& __proj2,
0205     /*_ConstTimeDistance=*/true_type) {
0206   if (std::distance(__first1, __last1) != std::distance(__first2, __last2))
0207     return false;
0208   return std::__is_permutation<_AlgPolicy>(
0209       std::move(__first1),
0210       std::move(__last1),
0211       std::move(__first2),
0212       std::move(__last2),
0213       __pred,
0214       __proj1,
0215       __proj2,
0216       /*_ConstTimeDistance=*/false_type());
0217 }
0218
0219 // 2+2 iterators, predicate
0220 template <class _AlgPolicy,
0221           class _Iter1,
0222           class _Sent1,
0223           class _Iter2,
0224           class _Sent2,
0225           class _Proj1,
0226           class _Proj2,
0227           class _Pred>
0228 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
0229     _Iter1 __first1,
0230     _Sent1 __last1,
0231     _Iter2 __first2,
0232     _Sent2 __last2,
0233     _Pred&& __pred,
0234     _Proj1&& __proj1,
0235     _Proj2&& __proj2) {
0236   return std::__is_permutation<_AlgPolicy>(
0237       std::move(__first1),
0238       std::move(__last1),
0239       std::move(__first2),
0240       std::move(__last2),
0241       __pred,
0242       __proj1,
0243       __proj2,
0244       _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2>());
0245 }
0246
0247 // Public interface
0248
0249 // 2+1 iterators, predicate
0250 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
0251 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation(
0252     _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) {
0253   static_assert(__is_callable<_BinaryPredicate&, decltype(*__first1), decltype(*__first2)>::value,
0254                 "The comparator has to be callable");
0255
0256   return std::__is_permutation<_ClassicAlgPolicy>(std::move(__first1), std::move(__last1), std::move(__first2), __pred);
0257 }
0258
0259 // 2+1 iterators
0260 template <class _ForwardIterator1, class _ForwardIterator2>
0261 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
0262 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {
0263   return std::is_permutation(__first1, __last1, __first2, __equal_to());
0264 }
0265
0266 #if _LIBCPP_STD_VER >= 14
0267
0268 // 2+2 iterators
0269 template <class _ForwardIterator1, class _ForwardIterator2>
0270 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation(
0271     _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
0272   return std::__is_permutation<_ClassicAlgPolicy>(
0273       std::move(__first1),
0274       std::move(__last1),
0275       std::move(__first2),
0276       std::move(__last2),
0277       __equal_to(),
0278       __identity(),
0279       __identity());
0280 }
0281
0282 // 2+2 iterators, predicate
0283 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
0284 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation(
0285     _ForwardIterator1 __first1,
0286     _ForwardIterator1 __last1,
0287     _ForwardIterator2 __first2,
0288     _ForwardIterator2 __last2,
0289     _BinaryPredicate __pred) {
0290   static_assert(__is_callable<_BinaryPredicate&, decltype(*__first1), decltype(*__first2)>::value,
0291                 "The comparator has to be callable");
0292
0293   return std::__is_permutation<_ClassicAlgPolicy>(
0294       std::move(__first1),
0295       std::move(__last1),
0296       std::move(__first2),
0297       std::move(__last2),
0298       __pred,
0299       __identity(),
0300       __identity());
0301 }
0302
0303 #endif // _LIBCPP_STD_VER >= 14
0304
0305 _LIBCPP_END_NAMESPACE_STD
0306
0307 _LIBCPP_POP_MACROS
0308
0309 #endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H