Horizon
nth_element.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 
14 //===----------------------------------------------------------------------===//
15 //
16 // The LLVM Compiler Infrastructure
17 //
18 // This file is dual licensed under the MIT and the University of Illinois Open
19 // Source Licenses. See LICENSE.TXT for details.
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef RANGES_V3_ALGORITHM_NTH_ELEMENT_HPP
24 #define RANGES_V3_ALGORITHM_NTH_ELEMENT_HPP
25 
26 #include <utility>
27 
28 #include <range/v3/range_fwd.hpp>
29 
42 #include <range/v3/utility/static_const.hpp>
44 
45 #include <range/v3/detail/prologue.hpp>
46 
47 namespace ranges
48 {
50  namespace detail
51  {
52  // stable, 2-3 compares, 0-2 swaps
53 
54  template(typename I, typename C, typename P)(
55  requires forward_iterator<I> AND indirect_relation<C, projected<I, P>>)
56  unsigned sort3(I x, I y, I z, C & pred, P & proj)
57  {
58  unsigned r = 0;
59  if(!invoke(pred, invoke(proj, *y), invoke(proj, *x))) // if x <= y
60  {
61  if(!invoke(pred, invoke(proj, *z), invoke(proj, *y))) // if y <= z
62  return r; // x <= y && y <= z
63  // x <= y && y > z
64  ranges::iter_swap(y, z); // x <= z && y < z
65  r = 1;
66  if(invoke(pred, invoke(proj, *y), invoke(proj, *x))) // if x > y
67  {
68  ranges::iter_swap(x, y); // x < y && y <= z
69  r = 2;
70  }
71  return r; // x <= y && y < z
72  }
73  if(invoke(pred, invoke(proj, *z), invoke(proj, *y))) // x > y, if y > z
74  {
75  ranges::iter_swap(x, z); // x < y && y < z
76  r = 1;
77  return r;
78  }
79  ranges::iter_swap(x, y); // x > y && y <= z
80  r = 1; // x < y && x <= z
81  if(invoke(pred, invoke(proj, *z), invoke(proj, *y))) // if y > z
82  {
83  ranges::iter_swap(y, z); // x <= y && y < z
84  r = 2;
85  }
86  return r;
87  } // x <= y && y <= z
88 
89  template(typename I, typename C, typename P)(
90  requires bidirectional_iterator<I> AND indirect_relation<C, projected<I, P>>)
91  void selection_sort(I first, I last, C & pred, P & proj)
92  {
93  RANGES_EXPECT(first != last);
94  for(I lm1 = ranges::prev(last); first != lm1; ++first)
95  {
96  I i = ranges::min_element(first, last, std::ref(pred), std::ref(proj));
97  if(i != first)
98  ranges::iter_swap(first, i);
99  }
100  }
101  } // namespace detail
103 
106  RANGES_FUNC_BEGIN(nth_element)
107 
108 
109  template(typename I, typename S, typename C = less, typename P = identity)(
110  requires random_access_iterator<I> AND sortable<I, C, P>)
111  constexpr I RANGES_FUNC(nth_element)(
112  I first, I nth, S end_, C pred = C{}, P proj = P{}) //
113  {
114  I last = ranges::next(nth, end_), end_orig = last;
115  // C is known to be a reference type
116  using difference_type = iter_difference_t<I>;
117  difference_type const limit = 7;
118  while(true)
119  {
120  if(nth == last)
121  return end_orig;
122  difference_type len = last - first;
123  switch(len)
124  {
125  case 0:
126  case 1:
127  return end_orig;
128  case 2:
129  if(invoke(pred, invoke(proj, *--last), invoke(proj, *first)))
130  ranges::iter_swap(first, last);
131  return end_orig;
132  case 3:
133  {
134  I m = first;
135  detail::sort3(first, ++m, --last, pred, proj);
136  return end_orig;
137  }
138  }
139  if(len <= limit)
140  {
141  detail::selection_sort(first, last, pred, proj);
142  return end_orig;
143  }
144  // len > limit >= 3
145  I m = first + len / 2;
146  I lm1 = last;
147  unsigned n_swaps = detail::sort3(first, m, --lm1, pred, proj);
148  // *m is median
149  // partition [first, m) < *m and *m <= [m, last)
150  //(this inhibits tossing elements equivalent to m around unnecessarily)
151  I i = first;
152  I j = lm1;
153  // j points beyond range to be tested, *lm1 is known to be <= *m
154  // The search going up is known to be guarded but the search coming down
155  // isn't. Prime the downward search with a guard.
156  if(!invoke(pred, invoke(proj, *i), invoke(proj, *m))) // if *first == *m
157  {
158  // *first == *m, *first doesn't go in first part
159  // manually guard downward moving j against i
160  while(true)
161  {
162  if(i == --j)
163  {
164  // *first == *m, *m <= all other elements
165  // Parition instead into [first, i) == *first and *first < [i,
166  // last)
167  ++i; // first + 1
168  j = last;
169  if(!invoke(
170  pred,
171  invoke(proj, *first),
172  invoke(
173  proj,
174  *--j))) // we need a guard if *first == *(last-1)
175  {
176  while(true)
177  {
178  if(i == j)
179  return end_orig; // [first, last) all equivalent
180  // elements
181  if(invoke(
182  pred, invoke(proj, *first), invoke(proj, *i)))
183  {
184  ranges::iter_swap(i, j);
185  ++n_swaps;
186  ++i;
187  break;
188  }
189  ++i;
190  }
191  }
192  // [first, i) == *first and *first < [j, last) and j == last -
193  // 1
194  if(i == j)
195  return end_orig;
196  while(true)
197  {
198  while(
199  !invoke(pred, invoke(proj, *first), invoke(proj, *i)))
200  ++i;
201  while(invoke(
202  pred, invoke(proj, *first), invoke(proj, *--j)))
203  ;
204  if(i >= j)
205  break;
206  ranges::iter_swap(i, j);
207  ++n_swaps;
208  ++i;
209  }
210  // [first, i) == *first and *first < [i, last)
211  // The first part is sorted,
212  if(nth < i)
213  return end_orig;
214  // nth_element the second part
215  // nth_element<C>(i, nth, last, pred);
216  first = i;
217  continue;
218  }
219  if(invoke(pred, invoke(proj, *j), invoke(proj, *m)))
220  {
221  ranges::iter_swap(i, j);
222  ++n_swaps;
223  break; // found guard for downward moving j, now use unguarded
224  // partition
225  }
226  }
227  }
228  ++i;
229  // j points beyond range to be tested, *lm1 is known to be <= *m
230  // if not yet partitioned...
231  if(i < j)
232  {
233  // known that *(i - 1) < *m
234  while(true)
235  {
236  // m still guards upward moving i
237  while(invoke(pred, invoke(proj, *i), invoke(proj, *m)))
238  ++i;
239  // It is now known that a guard exists for downward moving j
240  while(!invoke(pred, invoke(proj, *--j), invoke(proj, *m)))
241  ;
242  if(i >= j)
243  break;
244  ranges::iter_swap(i, j);
245  ++n_swaps;
246  // It is known that m != j
247  // If m just moved, follow it
248  if(m == i)
249  m = j;
250  ++i;
251  }
252  }
253  // [first, i) < *m and *m <= [i, last)
254  if(i != m && invoke(pred, invoke(proj, *m), invoke(proj, *i)))
255  {
256  ranges::iter_swap(i, m);
257  ++n_swaps;
258  }
259  // [first, i) < *i and *i <= [i+1, last)
260  if(nth == i)
261  return end_orig;
262  const auto optional_return = [&]() -> ranges::optional<I> {
263  if(n_swaps == 0)
264  {
265  // We were given a perfectly partitioned sequence. Coincidence?
266  if(nth < i)
267  {
268  // Check for [first, i) already sorted
269  j = m = first;
270  while(++j != i)
271  {
272  if(invoke(pred, invoke(proj, *j), invoke(proj, *m)))
273  // not yet sorted, so sort
274  return ranges::nullopt;
275  m = j;
276  }
277  // [first, i) sorted
278  return end_orig;
279  }
280  else
281  {
282  // Check for [i, last) already sorted
283  j = m = i;
284  while(++j != last)
285  {
286  if(invoke(pred, invoke(proj, *j), invoke(proj, *m)))
287  // not yet sorted, so sort
288  return ranges::nullopt;
289  m = j;
290  }
291  // [i, last) sorted
292  return end_orig;
293  }
294  }
295  return ranges::nullopt;
296  }();
297  if(optional_return)
298  {
299  return *optional_return;
300  }
301  // nth_element on range containing nth
302  if(nth < i)
303  {
304  // nth_element<C>(first, nth, i, pred);
305  last = i;
306  }
307  else
308  {
309  // nth_element<C>(i+1, nth, last, pred);
310  first = ++i;
311  }
312  }
313  return end_orig;
314  }
315 
317  template(typename Rng, typename C = less, typename P = identity)(
318  requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
319  constexpr borrowed_iterator_t<Rng> RANGES_FUNC(nth_element)(
320  Rng && rng, iterator_t<Rng> nth, C pred = C{}, P proj = P{}) //
321  {
322  return (*this)(
323  begin(rng), std::move(nth), end(rng), std::move(pred), std::move(proj));
324  }
325 
326  RANGES_FUNC_END(nth_element)
327 
328  namespace cpp20
329  {
330  using ranges::nth_element;
331  }
333 } // namespace ranges
334 
335 #include <range/v3/detail/epilogue.hpp>
336 
337 #endif
CPP_concept indirect_relation
\concept indirect_relation
Definition: concepts.hpp:670
CPP_concept sortable
\concept sortable
Definition: concepts.hpp:865
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
Definition: optional.hpp:501