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 <__config> 15 #include <__iterator/distance.h> 16 #include <__iterator/iterator_traits.h> 17 #include <__iterator/next.h> 18 #include <type_traits> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 #pragma GCC system_header 22 #endif 23 24 _LIBCPP_PUSH_MACROS 25 #include <__undef_macros> 26 27 _LIBCPP_BEGIN_NAMESPACE_STD 28 29 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 30 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 31 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, 32 _BinaryPredicate __pred) { 33 // shorten sequences as much as possible by lopping of any equal prefix 34 for (; __first1 != __last1; ++__first1, (void)++__first2) 35 if (!__pred(*__first1, *__first2)) 36 break; 37 if (__first1 == __last1) 38 return true; 39 40 // __first1 != __last1 && *__first1 != *__first2 41 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; 42 _D1 __l1 = _VSTD::distance(__first1, __last1); 43 if (__l1 == _D1(1)) 44 return false; 45 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1); 46 // For each element in [f1, l1) see if there are the same number of 47 // equal elements in [f2, l2) 48 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { 49 // Have we already counted the number of *__i in [f1, l1)? 50 _ForwardIterator1 __match = __first1; 51 for (; __match != __i; ++__match) 52 if (__pred(*__match, *__i)) 53 break; 54 if (__match == __i) { 55 // Count number of *__i in [f2, l2) 56 _D1 __c2 = 0; 57 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) 58 if (__pred(*__i, *__j)) 59 ++__c2; 60 if (__c2 == 0) 61 return false; 62 // Count number of *__i in [__i, l1) (we can start with 1) 63 _D1 __c1 = 1; 64 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) 65 if (__pred(*__i, *__j)) 66 ++__c1; 67 if (__c1 != __c2) 68 return false; 69 } 70 } 71 return true; 72 } 73 74 template <class _ForwardIterator1, class _ForwardIterator2> 75 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 76 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { 77 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; 78 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; 79 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); 80 } 81 82 #if _LIBCPP_STD_VER > 11 83 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> 84 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 85 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, 86 _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { 87 // shorten sequences as much as possible by lopping of any equal prefix 88 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) 89 if (!__pred(*__first1, *__first2)) 90 break; 91 if (__first1 == __last1) 92 return __first2 == __last2; 93 else if (__first2 == __last2) 94 return false; 95 96 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; 97 _D1 __l1 = _VSTD::distance(__first1, __last1); 98 99 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2; 100 _D2 __l2 = _VSTD::distance(__first2, __last2); 101 if (__l1 != __l2) 102 return false; 103 104 // For each element in [f1, l1) see if there are the same number of 105 // equal elements in [f2, l2) 106 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { 107 // Have we already counted the number of *__i in [f1, l1)? 108 _ForwardIterator1 __match = __first1; 109 for (; __match != __i; ++__match) 110 if (__pred(*__match, *__i)) 111 break; 112 if (__match == __i) { 113 // Count number of *__i in [f2, l2) 114 _D1 __c2 = 0; 115 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) 116 if (__pred(*__i, *__j)) 117 ++__c2; 118 if (__c2 == 0) 119 return false; 120 // Count number of *__i in [__i, l1) (we can start with 1) 121 _D1 __c1 = 1; 122 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) 123 if (__pred(*__i, *__j)) 124 ++__c1; 125 if (__c1 != __c2) 126 return false; 127 } 128 } 129 return true; 130 } 131 132 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> 133 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, 134 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, 135 _BinaryPredicate __pred, random_access_iterator_tag, 136 random_access_iterator_tag) { 137 if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) 138 return false; 139 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, 140 typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, 141 __pred); 142 } 143 144 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 145 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 146 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, 147 _ForwardIterator2 __last2, _BinaryPredicate __pred) { 148 return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>( 149 __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), 150 typename iterator_traits<_ForwardIterator2>::iterator_category()); 151 } 152 153 template <class _ForwardIterator1, class _ForwardIterator2> 154 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 155 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, 156 _ForwardIterator2 __last2) { 157 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; 158 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; 159 return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), 160 typename iterator_traits<_ForwardIterator1>::iterator_category(), 161 typename iterator_traits<_ForwardIterator2>::iterator_category()); 162 } 163 #endif 164 165 _LIBCPP_END_NAMESPACE_STD 166 167 _LIBCPP_POP_MACROS 168 169 #endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H 170