Horizon
Loading...
Searching...
No Matches
nth_element.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
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
29
42#include <range/v3/utility/static_const.hpp>
44
45#include <range/v3/detail/prologue.hpp>
46
47namespace 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
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