Warning: This file is not a C or C++ file. It does not have highlighting.

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___CXX03___ALGORITHM_IS_PERMUTATION_H
11#define _LIBCPP___CXX03___ALGORITHM_IS_PERMUTATION_H
12
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_header
26#endif
27
28_LIBCPP_PUSH_MACROS
29#include <__cxx03/__undef_macros>
30
31_LIBCPP_BEGIN_NAMESPACE_STD
32
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 functions
47
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 != *__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),
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 shorter
158 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, predicate
204template <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 interface
232
233// 2+1 iterators, predicate
234template <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 iterators
244template <class _ForwardIterator1, class _ForwardIterator2>
245_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI bool
246is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {
247 return std::is_permutation(__first1, __last1, __first2, __equal_to());
248}
249
250_LIBCPP_END_NAMESPACE_STD
251
252_LIBCPP_POP_MACROS
253
254#endif // _LIBCPP___CXX03___ALGORITHM_IS_PERMUTATION_H
255

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__cxx03/__algorithm/is_permutation.h