1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ALGORITHM_IS_PERMUTATION_H 11 #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H 12 13 #include <__algorithm/comp.h> 14 #include <__algorithm/iterator_operations.h> 15 #include <__config> 16 #include <__functional/identity.h> 17 #include <__functional/invoke.h> 18 #include <__iterator/concepts.h> 19 #include <__iterator/distance.h> 20 #include <__iterator/iterator_traits.h> 21 #include <__iterator/next.h> 22 #include <__type_traits/is_callable.h> 23 #include <__utility/move.h> 24 25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26 # pragma GCC system_header 27 #endif 28 29 _LIBCPP_PUSH_MACROS 30 #include <__undef_macros> 31 32 _LIBCPP_BEGIN_NAMESPACE_STD 33 34 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class = void> 35 struct _ConstTimeDistance : false_type {}; 36 37 #if _LIBCPP_STD_VER >= 20 38 39 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2> 40 struct _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2, __enable_if_t< 41 sized_sentinel_for<_Sent1, _Iter1> && 42 sized_sentinel_for<_Sent2, _Iter2> 43 >> : true_type {}; 44 45 #else 46 47 template <class _Iter1, class _Iter2> 48 struct _ConstTimeDistance<_Iter1, _Iter1, _Iter2, _Iter2, __enable_if_t< 49 is_same<typename iterator_traits<_Iter1>::iterator_category, random_access_iterator_tag>::value && 50 is_same<typename iterator_traits<_Iter2>::iterator_category, random_access_iterator_tag>::value 51 > > : true_type {}; 52 53 #endif // _LIBCPP_STD_VER >= 20 54 55 // Internal functions 56 57 // For each element in [f1, l1) see if there are the same number of equal elements in [f2, l2) 58 template <class _AlgPolicy, 59 class _Iter1, class _Sent1, class _Iter2, class _Sent2, 60 class _Proj1, class _Proj2, class _Pred> 61 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 62 __is_permutation_impl(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, 63 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2) { 64 using _D1 = __iter_diff_t<_Iter1>; 65 66 for (auto __i = __first1; __i != __last1; ++__i) { 67 // Have we already counted the number of *__i in [f1, l1)? 68 auto __match = __first1; 69 for (; __match != __i; ++__match) { 70 if (std::__invoke(__pred, std::__invoke(__proj1, *__match), std::__invoke(__proj1, *__i))) 71 break; 72 } 73 74 if (__match == __i) { 75 // Count number of *__i in [f2, l2) 76 _D1 __c2 = 0; 77 for (auto __j = __first2; __j != __last2; ++__j) { 78 if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j))) 79 ++__c2; 80 } 81 if (__c2 == 0) 82 return false; 83 84 // Count number of *__i in [__i, l1) (we can start with 1) 85 _D1 __c1 = 1; 86 for (auto __j = _IterOps<_AlgPolicy>::next(__i); __j != __last1; ++__j) { 87 if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj1, *__j))) 88 ++__c1; 89 } 90 if (__c1 != __c2) 91 return false; 92 } 93 } 94 95 return true; 96 } 97 98 // 2+1 iterators, predicate. Not used by range algorithms. 99 template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _BinaryPredicate> 100 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 101 __is_permutation(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, 102 _BinaryPredicate&& __pred) { 103 // Shorten sequences as much as possible by lopping of any equal prefix. 104 for (; __first1 != __last1; ++__first1, (void)++__first2) { 105 if (!__pred(*__first1, *__first2)) 106 break; 107 } 108 109 if (__first1 == __last1) 110 return true; 111 112 // __first1 != __last1 && *__first1 != *__first2 113 using _D1 = __iter_diff_t<_ForwardIterator1>; 114 _D1 __l1 = _IterOps<_AlgPolicy>::distance(__first1, __last1); 115 if (__l1 == _D1(1)) 116 return false; 117 auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __l1); 118 119 return std::__is_permutation_impl<_AlgPolicy>( 120 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 121 __pred, __identity(), __identity()); 122 } 123 124 // 2+2 iterators, predicate, non-constant time `distance`. 125 template <class _AlgPolicy, 126 class _Iter1, class _Sent1, class _Iter2, class _Sent2, 127 class _Proj1, class _Proj2, class _Pred> 128 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 129 __is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, 130 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2, 131 /*_ConstTimeDistance=*/false_type) { 132 // Shorten sequences as much as possible by lopping of any equal prefix. 133 while (__first1 != __last1 && __first2 != __last2) { 134 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 135 break; 136 ++__first1; 137 ++__first2; 138 } 139 140 if (__first1 == __last1) 141 return __first2 == __last2; 142 if (__first2 == __last2) // Second range is shorter 143 return false; 144 145 using _D1 = __iter_diff_t<_Iter1>; 146 _D1 __l1 = _IterOps<_AlgPolicy>::distance(__first1, __last1); 147 148 using _D2 = __iter_diff_t<_Iter2>; 149 _D2 __l2 = _IterOps<_AlgPolicy>::distance(__first2, __last2); 150 if (__l1 != __l2) 151 return false; 152 153 return std::__is_permutation_impl<_AlgPolicy>( 154 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 155 __pred, __proj1, __proj2); 156 } 157 158 // 2+2 iterators, predicate, specialization for constant-time `distance` call. 159 template <class _AlgPolicy, 160 class _Iter1, class _Sent1, class _Iter2, class _Sent2, 161 class _Proj1, class _Proj2, class _Pred> 162 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 163 __is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, 164 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2, 165 /*_ConstTimeDistance=*/true_type) { 166 if (std::distance(__first1, __last1) != std::distance(__first2, __last2)) 167 return false; 168 return std::__is_permutation<_AlgPolicy>( 169 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 170 __pred, __proj1, __proj2, 171 /*_ConstTimeDistance=*/false_type()); 172 } 173 174 // 2+2 iterators, predicate 175 template <class _AlgPolicy, 176 class _Iter1, class _Sent1, class _Iter2, class _Sent2, 177 class _Proj1, class _Proj2, class _Pred> 178 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 179 __is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, 180 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2) { 181 return std::__is_permutation<_AlgPolicy>( 182 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 183 __pred, __proj1, __proj2, 184 _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2>()); 185 } 186 187 // Public interface 188 189 // 2+1 iterators, predicate 190 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 191 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 192 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, 193 _BinaryPredicate __pred) { 194 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, 195 "The predicate has to be callable"); 196 197 return std::__is_permutation<_ClassicAlgPolicy>( 198 std::move(__first1), std::move(__last1), std::move(__first2), __pred); 199 } 200 201 // 2+1 iterators 202 template <class _ForwardIterator1, class _ForwardIterator2> 203 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 204 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { 205 return std::is_permutation(__first1, __last1, __first2, __equal_to()); 206 } 207 208 #if _LIBCPP_STD_VER >= 14 209 210 // 2+2 iterators 211 template <class _ForwardIterator1, class _ForwardIterator2> 212 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation( 213 _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { 214 return std::__is_permutation<_ClassicAlgPolicy>( 215 std::move(__first1), 216 std::move(__last1), 217 std::move(__first2), 218 std::move(__last2), 219 __equal_to(), 220 __identity(), 221 __identity()); 222 } 223 224 // 2+2 iterators, predicate 225 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 226 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 227 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, 228 _ForwardIterator2 __last2, _BinaryPredicate __pred) { 229 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, 230 "The predicate has to be callable"); 231 232 return std::__is_permutation<_ClassicAlgPolicy>( 233 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 234 __pred, __identity(), __identity()); 235 } 236 237 #endif // _LIBCPP_STD_VER >= 14 238 239 _LIBCPP_END_NAMESPACE_STD 240 241 _LIBCPP_POP_MACROS 242 243 #endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H 244