Horizon
permutation.hpp
Go to the documentation of this file.
1 // 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 
26 #include <range/v3/range_fwd.hpp>
27 
39 #include <range/v3/utility/static_const.hpp>
41 
42 #include <range/v3/detail/prologue.hpp>
43 
44 namespace 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
CPP_concept indirectly_comparable
\concept indirectly_comparable
Definition: concepts.hpp:832
CPP_concept sortable
\concept sortable
Definition: concepts.hpp:865
CPP_concept forward_iterator
\concept forward_iterator
Definition: concepts.hpp:370
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
_t< detail::reverse_< L > > reverse
Return a new meta::list by reversing the elements in the list L.
Definition: meta.hpp:2996
Tiny meta-programming library.