21#ifndef RANGES_V3_ALGORITHM_PERMUTATION_HPP
22#define RANGES_V3_ALGORITHM_PERMUTATION_HPP
39#include <range/v3/utility/static_const.hpp>
42#include <range/v3/detail/prologue.hpp>
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,
64 ranges::mismatch(begin1, end1, begin2, end2, pred, proj1, proj2);
65 begin1 = mismatch.in1;
66 begin2 = mismatch.in2;
67 if(begin1 == end1 || begin2 == end2)
69 return begin1 == end1 && begin2 == end2;
72 auto l1 = distance(begin1, end1);
73 auto l2 = distance(begin2, end2);
79 for(I1 i = begin1; i != end1; ++i)
82 const auto should_continue = [&] {
83 for(I1 j = begin1; j != i; ++j)
93 iter_difference_t<I2> c2 = 0;
94 for(I2 j = begin2; j != end2; ++j)
100 iter_difference_t<I1> c1 = 1;
101 for(I1 j = next(i); j != end1; ++j)
112 RANGES_FUNC_BEGIN(is_permutation)
115 template(
typename I1,
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>)
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,
134 for(; begin1 != end1; ++begin1, ++begin2)
140 auto l1 = distance(begin1, end1);
143 I2 end2 = next(begin2, l1);
146 for(I1 i = begin1; i != end1; ++i)
149 for(I1 j = begin1; j != i; ++j)
154 iter_difference_t<I2> c2 = 0;
155 for(I2 j = begin2; j != end2; ++j)
161 iter_difference_t<I1> c1 = 1;
162 for(I1 j = next(i); j != end1; ++j)
174 template(
typename I1,
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,
192 if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S1, I1> &&
193 sized_sentinel_for<S2, I2>))
195 RANGES_DIAGNOSTIC_PUSH
196 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
197 return distance(begin1, end1) == distance(begin2, end2) &&
198 (*this)(std::move(begin1),
204 RANGES_DIAGNOSTIC_POP
206 return detail::is_permutation_impl(std::move(begin1),
216 template(
typename Rng1,
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>)
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,
232 RANGES_DIAGNOSTIC_PUSH
233 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
234 return (*
this)(begin(rng1),
240 RANGES_DIAGNOSTIC_POP
244 template(
typename Rng1,
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{})
254 if(RANGES_CONSTEXPR_IF(sized_range<Rng1> && sized_range<Rng2>))
256 RANGES_DIAGNOSTIC_PUSH
257 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
258 return distance(rng1) == distance(rng2) && (*this)(begin(rng1),
264 RANGES_DIAGNOSTIC_POP
266 return detail::is_permutation_impl(begin(rng1),
275 RANGES_FUNC_END(is_permutation)
277 RANGES_FUNC_BEGIN(next_permutation)
280 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
281 requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
283 constexpr bool RANGES_FUNC(next_permutation)(I
first, S end_, C pred = C{}, P proj = P{})
287 I last = ranges::next(first, end_), i = last;
298 ranges::iter_swap(i, j);
299 ranges::reverse(ip1, last);
304 ranges::reverse(first, last);
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{})
315 return (*
this)(begin(rng), end(rng), std::move(pred), std::move(proj));
318 RANGES_FUNC_END(next_permutation)
320 RANGES_FUNC_BEGIN(prev_permutation)
323 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
324 requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
326 constexpr bool RANGES_FUNC(prev_permutation)(I
first, S end_, C pred = C{}, P proj = P{})
330 I last = ranges::next(first, end_), i = last;
341 ranges::iter_swap(i, j);
342 ranges::reverse(ip1, last);
347 ranges::reverse(first, last);
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{})
358 return (*
this)(begin(rng), end(rng), std::move(pred), std::move(proj));
361 RANGES_FUNC_END(prev_permutation)
365 using ranges::is_permutation;
366 using ranges::next_permutation;
367 using ranges::prev_permutation;
372#include <range/v3/detail/epilogue.hpp>
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