255 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___ALGORITHM_IS_PERMUTATION_H11#define _LIBCPP___CXX03___ALGORITHM_IS_PERMUTATION_H12 13#include <__cxx03/__algorithm/comp.h>14#include <__cxx03/__algorithm/iterator_operations.h>15#include <__cxx03/__config>16#include <__cxx03/__functional/identity.h>17#include <__cxx03/__iterator/distance.h>18#include <__cxx03/__iterator/iterator_traits.h>19#include <__cxx03/__iterator/next.h>20#include <__cxx03/__type_traits/invoke.h>21#include <__cxx03/__type_traits/is_callable.h>22#include <__cxx03/__utility/move.h>23 24#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)25# pragma GCC system_header26#endif27 28_LIBCPP_PUSH_MACROS29#include <__cxx03/__undef_macros>30 31_LIBCPP_BEGIN_NAMESPACE_STD32 33template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class = void>34struct _ConstTimeDistance : false_type {};35 36template <class _Iter1, class _Iter2>37struct _ConstTimeDistance<38 _Iter1,39 _Iter1,40 _Iter2,41 _Iter2,42 __enable_if_t< is_same<typename iterator_traits<_Iter1>::iterator_category, random_access_iterator_tag>::value &&43 is_same<typename iterator_traits<_Iter2>::iterator_category, random_access_iterator_tag>::value > >44 : true_type {};45 46// Internal functions47 48// For each element in [f1, l1) see if there are the same number of equal elements in [f2, l2)49template <class _AlgPolicy,50 class _Iter1,51 class _Sent1,52 class _Iter2,53 class _Sent2,54 class _Proj1,55 class _Proj2,56 class _Pred>57_LIBCPP_HIDE_FROM_ABI bool __is_permutation_impl(58 _Iter1 __first1,59 _Sent1 __last1,60 _Iter2 __first2,61 _Sent2 __last2,62 _Pred&& __pred,63 _Proj1&& __proj1,64 _Proj2&& __proj2) {65 using _D1 = __iter_diff_t<_Iter1>;66 67 for (auto __i = __first1; __i != __last1; ++__i) {68 // Have we already counted the number of *__i in [f1, l1)?69 auto __match = __first1;70 for (; __match != __i; ++__match) {71 if (std::__invoke(__pred, std::__invoke(__proj1, *__match), std::__invoke(__proj1, *__i)))72 break;73 }74 75 if (__match == __i) {76 // Count number of *__i in [f2, l2)77 _D1 __c2 = 0;78 for (auto __j = __first2; __j != __last2; ++__j) {79 if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j)))80 ++__c2;81 }82 if (__c2 == 0)83 return false;84 85 // Count number of *__i in [__i, l1) (we can start with 1)86 _D1 __c1 = 1;87 for (auto __j = _IterOps<_AlgPolicy>::next(__i); __j != __last1; ++__j) {88 if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj1, *__j)))89 ++__c1;90 }91 if (__c1 != __c2)92 return false;93 }94 }95 96 return true;97}98 99// 2+1 iterators, predicate. Not used by range algorithms.100template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _BinaryPredicate>101_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool __is_permutation(102 _ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, _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 != *__first2113 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),121 std::move(__last1),122 std::move(__first2),123 std::move(__last2),124 __pred,125 __identity(),126 __identity());127}128 129// 2+2 iterators, predicate, non-constant time `distance`.130template <class _AlgPolicy,131 class _Iter1,132 class _Sent1,133 class _Iter2,134 class _Sent2,135 class _Proj1,136 class _Proj2,137 class _Pred>138_LIBCPP_HIDE_FROM_ABI bool __is_permutation(139 _Iter1 __first1,140 _Sent1 __last1,141 _Iter2 __first2,142 _Sent2 __last2,143 _Pred&& __pred,144 _Proj1&& __proj1,145 _Proj2&& __proj2,146 /*_ConstTimeDistance=*/false_type) {147 // Shorten sequences as much as possible by lopping of any equal prefix.148 while (__first1 != __last1 && __first2 != __last2) {149 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))150 break;151 ++__first1;152 ++__first2;153 }154 155 if (__first1 == __last1)156 return __first2 == __last2;157 if (__first2 == __last2) // Second range is shorter158 return false;159 160 using _D1 = __iter_diff_t<_Iter1>;161 _D1 __l1 = _IterOps<_AlgPolicy>::distance(__first1, __last1);162 163 using _D2 = __iter_diff_t<_Iter2>;164 _D2 __l2 = _IterOps<_AlgPolicy>::distance(__first2, __last2);165 if (__l1 != __l2)166 return false;167 168 return std::__is_permutation_impl<_AlgPolicy>(169 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __pred, __proj1, __proj2);170}171 172// 2+2 iterators, predicate, specialization for constant-time `distance` call.173template <class _AlgPolicy,174 class _Iter1,175 class _Sent1,176 class _Iter2,177 class _Sent2,178 class _Proj1,179 class _Proj2,180 class _Pred>181_LIBCPP_HIDE_FROM_ABI bool __is_permutation(182 _Iter1 __first1,183 _Sent1 __last1,184 _Iter2 __first2,185 _Sent2 __last2,186 _Pred&& __pred,187 _Proj1&& __proj1,188 _Proj2&& __proj2,189 /*_ConstTimeDistance=*/true_type) {190 if (std::distance(__first1, __last1) != std::distance(__first2, __last2))191 return false;192 return std::__is_permutation<_AlgPolicy>(193 std::move(__first1),194 std::move(__last1),195 std::move(__first2),196 std::move(__last2),197 __pred,198 __proj1,199 __proj2,200 /*_ConstTimeDistance=*/false_type());201}202 203// 2+2 iterators, predicate204template <class _AlgPolicy,205 class _Iter1,206 class _Sent1,207 class _Iter2,208 class _Sent2,209 class _Proj1,210 class _Proj2,211 class _Pred>212_LIBCPP_HIDE_FROM_ABI bool __is_permutation(213 _Iter1 __first1,214 _Sent1 __last1,215 _Iter2 __first2,216 _Sent2 __last2,217 _Pred&& __pred,218 _Proj1&& __proj1,219 _Proj2&& __proj2) {220 return std::__is_permutation<_AlgPolicy>(221 std::move(__first1),222 std::move(__last1),223 std::move(__first2),224 std::move(__last2),225 __pred,226 __proj1,227 __proj2,228 _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2>());229}230 231// Public interface232 233// 2+1 iterators, predicate234template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>235_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool is_permutation(236 _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) {237 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value,238 "The predicate has to be callable");239 240 return std::__is_permutation<_ClassicAlgPolicy>(std::move(__first1), std::move(__last1), std::move(__first2), __pred);241}242 243// 2+1 iterators244template <class _ForwardIterator1, class _ForwardIterator2>245_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI bool246is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {247 return std::is_permutation(__first1, __last1, __first2, __equal_to());248}249 250_LIBCPP_END_NAMESPACE_STD251 252_LIBCPP_POP_MACROS253 254#endif // _LIBCPP___CXX03___ALGORITHM_IS_PERMUTATION_H255