Horizon
Loading...
Searching...
No Matches
permutation.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13//===-------------------------- algorithm ---------------------------------===//
14//
15// The LLVM Compiler Infrastructure
16//
17// This file is dual licensed under the MIT and the University of Illinois Open
18// Source Licenses. See LICENSE.TXT for details.
19//
20//===----------------------------------------------------------------------===//
21#ifndef RANGES_V3_ALGORITHM_PERMUTATION_HPP
22#define RANGES_V3_ALGORITHM_PERMUTATION_HPP
23
24#include <meta/meta.hpp>
25
27
39#include <range/v3/utility/static_const.hpp>
41
42#include <range/v3/detail/prologue.hpp>
43
44namespace ranges
45{
48
50 namespace detail
51 {
52 template<typename I1, typename S1, typename I2, typename S2, typename C,
53 typename P1, typename P2>
54 constexpr bool is_permutation_impl(I1 begin1,
55 S1 end1,
56 I2 begin2,
57 S2 end2,
58 C pred,
59 P1 proj1,
60 P2 proj2)
61 {
62 // shorten sequences as much as possible by lopping off any equal parts
63 const auto mismatch =
64 ranges::mismatch(begin1, end1, begin2, end2, pred, proj1, proj2);
65 begin1 = mismatch.in1;
66 begin2 = mismatch.in2;
67 if(begin1 == end1 || begin2 == end2)
68 {
69 return begin1 == end1 && begin2 == end2;
70 }
71 // begin1 != end1 && begin2 != end2 && *begin1 != *begin2
72 auto l1 = distance(begin1, end1);
73 auto l2 = distance(begin2, end2);
74 if(l1 != l2)
75 return false;
76
77 // For each element in [f1, l1) see if there are the same number of
78 // equal elements in [f2, l2)
79 for(I1 i = begin1; i != end1; ++i)
80 {
81 // Have we already counted the number of *i in [f1, l1)?
82 const auto should_continue = [&] {
83 for(I1 j = begin1; j != i; ++j)
84 if(invoke(pred, invoke(proj1, *j), invoke(proj1, *i)))
85 return true;
86 return false;
87 }();
88 if(should_continue)
89 {
90 continue;
91 }
92 // Count number of *i in [f2, l2)
93 iter_difference_t<I2> c2 = 0;
94 for(I2 j = begin2; j != end2; ++j)
95 if(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))
96 ++c2;
97 if(c2 == 0)
98 return false;
99 // Count number of *i in [i, l1) (we can start with 1)
100 iter_difference_t<I1> c1 = 1;
101 for(I1 j = next(i); j != end1; ++j)
102 if(invoke(pred, invoke(proj1, *i), invoke(proj1, *j)))
103 ++c1;
104 if(c1 != c2)
105 return false;
106 }
107 return true;
108 }
109 } // namespace detail
111
112 RANGES_FUNC_BEGIN(is_permutation)
113
114
115 template(typename I1,
116 typename S1,
117 typename I2,
118 typename C = equal_to,
119 typename P1 = identity,
120 typename P2 = identity)(
121 requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
122 forward_iterator<I2> AND indirectly_comparable<I1, I2, C, P1, P2>)
123 RANGES_DEPRECATED(
124 "Use the variant of ranges::is_permutation that takes an upper bound "
125 "for both sequences")
126 bool RANGES_FUNC(is_permutation)(I1 begin1,
127 S1 end1,
128 I2 begin2,
129 C pred = C{},
130 P1 proj1 = P1{},
131 P2 proj2 = P2{}) //
132 {
133 // shorten sequences as much as possible by lopping off any equal parts
134 for(; begin1 != end1; ++begin1, ++begin2)
135 if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
136 goto not_done;
137 return true;
138 not_done:
139 // begin1 != end1 && *begin1 != *begin2
140 auto l1 = distance(begin1, end1);
141 if(l1 == 1)
142 return false;
143 I2 end2 = next(begin2, l1);
144 // For each element in [f1, l1) see if there are the same number of
145 // equal elements in [f2, l2)
146 for(I1 i = begin1; i != end1; ++i)
147 {
148 // Have we already counted the number of *i in [f1, l1)?
149 for(I1 j = begin1; j != i; ++j)
150 if(invoke(pred, invoke(proj1, *j), invoke(proj1, *i)))
151 goto next_iter;
152 {
153 // Count number of *i in [f2, l2)
154 iter_difference_t<I2> c2 = 0;
155 for(I2 j = begin2; j != end2; ++j)
156 if(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))
157 ++c2;
158 if(c2 == 0)
159 return false;
160 // Count number of *i in [i, l1) (we can start with 1)
161 iter_difference_t<I1> c1 = 1;
162 for(I1 j = next(i); j != end1; ++j)
163 if(invoke(pred, invoke(proj1, *i), invoke(proj1, *j)))
164 ++c1;
165 if(c1 != c2)
166 return false;
167 }
168 next_iter:;
169 }
170 return true;
171 }
172
174 template(typename I1,
175 typename S1,
176 typename I2,
177 typename S2,
178 typename C = equal_to,
179 typename P1 = identity,
180 typename P2 = identity)(
181 requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
182 forward_iterator<I2> AND sentinel_for<S2, I2> AND
183 indirectly_comparable<I1, I2, C, P1, P2>)
184 constexpr bool RANGES_FUNC(is_permutation)(I1 begin1,
185 S1 end1,
186 I2 begin2,
187 S2 end2,
188 C pred = C{},
189 P1 proj1 = P1{},
190 P2 proj2 = P2{}) //
191 {
192 if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S1, I1> &&
193 sized_sentinel_for<S2, I2>))
194 {
195 RANGES_DIAGNOSTIC_PUSH
196 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
197 return distance(begin1, end1) == distance(begin2, end2) &&
198 (*this)(std::move(begin1),
199 std::move(end1),
200 std::move(begin2),
201 std::move(pred),
202 std::move(proj1),
203 std::move(proj2));
204 RANGES_DIAGNOSTIC_POP
205 }
206 return detail::is_permutation_impl(std::move(begin1),
207 std::move(end1),
208 std::move(begin2),
209 std::move(end2),
210 std::move(pred),
211 std::move(proj1),
212 std::move(proj2));
213 }
214
216 template(typename Rng1,
217 typename I2Ref,
218 typename C = equal_to,
219 typename P1 = identity,
220 typename P2 = identity)(
221 requires forward_range<Rng1> AND forward_iterator<uncvref_t<I2Ref>> AND
222 indirectly_comparable<iterator_t<Rng1>, uncvref_t<I2Ref>, C, P1, P2>)
223 RANGES_DEPRECATED(
224 "Use the variant of ranges::is_permutation that takes an upper bound "
225 "for both sequences")
226 bool RANGES_FUNC(is_permutation)(Rng1 && rng1,
227 I2Ref && begin2,
228 C pred = C{},
229 P1 proj1 = P1{},
230 P2 proj2 = P2{}) //
231 {
232 RANGES_DIAGNOSTIC_PUSH
233 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
234 return (*this)(begin(rng1),
235 end(rng1),
236 (I2Ref &&) begin2,
237 std::move(pred),
238 std::move(proj1),
239 std::move(proj2));
240 RANGES_DIAGNOSTIC_POP
241 }
242
244 template(typename Rng1,
245 typename Rng2,
246 typename C = equal_to,
247 typename P1 = identity,
248 typename P2 = identity)(
249 requires forward_range<Rng1> AND forward_range<Rng2> AND
250 indirectly_comparable<iterator_t<Rng1>, iterator_t<Rng2>, C, P1, P2>)
251 constexpr bool RANGES_FUNC(is_permutation)(
252 Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
253 {
254 if(RANGES_CONSTEXPR_IF(sized_range<Rng1> && sized_range<Rng2>))
255 {
256 RANGES_DIAGNOSTIC_PUSH
257 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
258 return distance(rng1) == distance(rng2) && (*this)(begin(rng1),
259 end(rng1),
260 begin(rng2),
261 std::move(pred),
262 std::move(proj1),
263 std::move(proj2));
264 RANGES_DIAGNOSTIC_POP
265 }
266 return detail::is_permutation_impl(begin(rng1),
267 end(rng1),
268 begin(rng2),
269 end(rng2),
270 std::move(pred),
271 std::move(proj1),
272 std::move(proj2));
273 }
274
275 RANGES_FUNC_END(is_permutation)
276
277 RANGES_FUNC_BEGIN(next_permutation)
278
279
280 template(typename I, typename S, typename C = less, typename P = identity)(
281 requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
282 sortable<I, C, P>)
283 constexpr bool RANGES_FUNC(next_permutation)(I first, S end_, C pred = C{}, P proj = P{}) //
284 {
285 if(first == end_)
286 return false;
287 I last = ranges::next(first, end_), i = last;
288 if(first == --i)
289 return false;
290 while(true)
291 {
292 I ip1 = i;
293 if(invoke(pred, invoke(proj, *--i), invoke(proj, *ip1)))
294 {
295 I j = last;
296 while(!invoke(pred, invoke(proj, *i), invoke(proj, *--j)))
297 ;
298 ranges::iter_swap(i, j);
299 ranges::reverse(ip1, last);
300 return true;
301 }
302 if(i == first)
303 {
304 ranges::reverse(first, last);
305 return false;
306 }
307 }
308 }
309
311 template(typename Rng, typename C = less, typename P = identity)(
312 requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
313 constexpr bool RANGES_FUNC(next_permutation)(Rng && rng, C pred = C{}, P proj = P{}) //
314 {
315 return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
316 }
317
318 RANGES_FUNC_END(next_permutation)
319
320 RANGES_FUNC_BEGIN(prev_permutation)
321
322
323 template(typename I, typename S, typename C = less, typename P = identity)(
324 requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
325 sortable<I, C, P>)
326 constexpr bool RANGES_FUNC(prev_permutation)(I first, S end_, C pred = C{}, P proj = P{}) //
327 {
328 if(first == end_)
329 return false;
330 I last = ranges::next(first, end_), i = last;
331 if(first == --i)
332 return false;
333 while(true)
334 {
335 I ip1 = i;
336 if(invoke(pred, invoke(proj, *ip1), invoke(proj, *--i)))
337 {
338 I j = last;
339 while(!invoke(pred, invoke(proj, *--j), invoke(proj, *i)))
340 ;
341 ranges::iter_swap(i, j);
342 ranges::reverse(ip1, last);
343 return true;
344 }
345 if(i == first)
346 {
347 ranges::reverse(first, last);
348 return false;
349 }
350 }
351 }
352
354 template(typename Rng, typename C = less, typename P = identity)(
355 requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
356 constexpr bool RANGES_FUNC(prev_permutation)(Rng && rng, C pred = C{}, P proj = P{}) //
357 {
358 return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
359 }
360
361 RANGES_FUNC_END(prev_permutation)
362
363 namespace cpp20
364 {
365 using ranges::is_permutation;
366 using ranges::next_permutation;
367 using ranges::prev_permutation;
368 } // namespace cpp20
370} // namespace ranges
371
372#include <range/v3/detail/epilogue.hpp>
373
374#endif
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition meta.hpp:255
bool_< T::type::value==U::type::value > equal_to
A Boolean integral constant wrapper around the result of comparing T::type::value and U::type::value ...
Definition meta.hpp:237
Tiny meta-programming library.