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