1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef _LIBCPP___ALGORITHM_NTH_ELEMENT_H
10 #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H
11
12 #include <__algorithm/comp.h>
13 #include <__algorithm/comp_ref_type.h>
14 #include <__algorithm/iterator_operations.h>
15 #include <__algorithm/sort.h>
16 #include <__assert>
17 #include <__config>
18 #include <__debug_utils/randomize_range.h>
19 #include <__iterator/iterator_traits.h>
20 #include <__utility/move.h>
21
22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23 # pragma GCC system_header
24 #endif
25
26 _LIBCPP_BEGIN_NAMESPACE_STD
27
28 template<class _Compare, class _RandomAccessIterator>
29 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool
__nth_element_find_guard(_RandomAccessIterator & __i,_RandomAccessIterator & __j,_RandomAccessIterator __m,_Compare __comp)30 __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
31 _RandomAccessIterator __m, _Compare __comp)
32 {
33 // manually guard downward moving __j against __i
34 while (true) {
35 if (__i == --__j) {
36 return false;
37 }
38 if (__comp(*__j, *__m)) {
39 return true; // found guard for downward moving __j, now use unguarded partition
40 }
41 }
42 }
43
44 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
45 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
46 // NOLINTNEXTLINE(readability-function-cognitive-complexity)
__nth_element(_RandomAccessIterator __first,_RandomAccessIterator __nth,_RandomAccessIterator __last,_Compare __comp)47 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
48 {
49 using _Ops = _IterOps<_AlgPolicy>;
50
51 // _Compare is known to be a reference type
52 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
53 const difference_type __limit = 7;
54 while (true)
55 {
56 if (__nth == __last)
57 return;
58 difference_type __len = __last - __first;
59 switch (__len)
60 {
61 case 0:
62 case 1:
63 return;
64 case 2:
65 if (__comp(*--__last, *__first))
66 _Ops::iter_swap(__first, __last);
67 return;
68 case 3:
69 {
70 _RandomAccessIterator __m = __first;
71 std::__sort3<_AlgPolicy, _Compare>(__first, ++__m, --__last, __comp);
72 return;
73 }
74 }
75 if (__len <= __limit)
76 {
77 std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
78 return;
79 }
80 // __len > __limit >= 3
81 _RandomAccessIterator __m = __first + __len/2;
82 _RandomAccessIterator __lm1 = __last;
83 unsigned __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, --__lm1, __comp);
84 // *__m is median
85 // partition [__first, __m) < *__m and *__m <= [__m, __last)
86 // (this inhibits tossing elements equivalent to __m around unnecessarily)
87 _RandomAccessIterator __i = __first;
88 _RandomAccessIterator __j = __lm1;
89 // j points beyond range to be tested, *__lm1 is known to be <= *__m
90 // The search going up is known to be guarded but the search coming down isn't.
91 // Prime the downward search with a guard.
92 if (!__comp(*__i, *__m)) // if *__first == *__m
93 {
94 // *__first == *__m, *__first doesn't go in first part
95 if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
96 _Ops::iter_swap(__i, __j);
97 ++__n_swaps;
98 } else {
99 // *__first == *__m, *__m <= all other elements
100 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
101 ++__i; // __first + 1
102 __j = __last;
103 if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1)
104 while (true) {
105 if (__i == __j) {
106 return; // [__first, __last) all equivalent elements
107 } else if (__comp(*__first, *__i)) {
108 _Ops::iter_swap(__i, __j);
109 ++__n_swaps;
110 ++__i;
111 break;
112 }
113 ++__i;
114 }
115 }
116 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
117 if (__i == __j) {
118 return;
119 }
120 while (true) {
121 while (!__comp(*__first, *__i)) {
122 ++__i;
123 _LIBCPP_ASSERT_UNCATEGORIZED(
124 __i != __last,
125 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
126 }
127 do {
128 _LIBCPP_ASSERT_UNCATEGORIZED(
129 __j != __first,
130 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
131 --__j;
132 } while (__comp(*__first, *__j));
133 if (__i >= __j)
134 break;
135 _Ops::iter_swap(__i, __j);
136 ++__n_swaps;
137 ++__i;
138 }
139 // [__first, __i) == *__first and *__first < [__i, __last)
140 // The first part is sorted,
141 if (__nth < __i) {
142 return;
143 }
144 // __nth_element the second part
145 // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
146 __first = __i;
147 continue;
148 }
149 }
150 ++__i;
151 // j points beyond range to be tested, *__lm1 is known to be <= *__m
152 // if not yet partitioned...
153 if (__i < __j)
154 {
155 // known that *(__i - 1) < *__m
156 while (true)
157 {
158 // __m still guards upward moving __i
159 while (__comp(*__i, *__m)) {
160 ++__i;
161 _LIBCPP_ASSERT_UNCATEGORIZED(
162 __i != __last,
163 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
164 }
165 // It is now known that a guard exists for downward moving __j
166 do {
167 _LIBCPP_ASSERT_UNCATEGORIZED(
168 __j != __first,
169 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
170 --__j;
171 } while (!__comp(*__j, *__m));
172 if (__i >= __j)
173 break;
174 _Ops::iter_swap(__i, __j);
175 ++__n_swaps;
176 // It is known that __m != __j
177 // If __m just moved, follow it
178 if (__m == __i)
179 __m = __j;
180 ++__i;
181 }
182 }
183 // [__first, __i) < *__m and *__m <= [__i, __last)
184 if (__i != __m && __comp(*__m, *__i))
185 {
186 _Ops::iter_swap(__i, __m);
187 ++__n_swaps;
188 }
189 // [__first, __i) < *__i and *__i <= [__i+1, __last)
190 if (__nth == __i)
191 return;
192 if (__n_swaps == 0)
193 {
194 // We were given a perfectly partitioned sequence. Coincidence?
195 if (__nth < __i)
196 {
197 // Check for [__first, __i) already sorted
198 __j = __m = __first;
199 while (true) {
200 if (++__j == __i) {
201 // [__first, __i) sorted
202 return;
203 }
204 if (__comp(*__j, *__m)) {
205 // not yet sorted, so sort
206 break;
207 }
208 __m = __j;
209 }
210 }
211 else
212 {
213 // Check for [__i, __last) already sorted
214 __j = __m = __i;
215 while (true) {
216 if (++__j == __last) {
217 // [__i, __last) sorted
218 return;
219 }
220 if (__comp(*__j, *__m)) {
221 // not yet sorted, so sort
222 break;
223 }
224 __m = __j;
225 }
226 }
227 }
228 // __nth_element on range containing __nth
229 if (__nth < __i)
230 {
231 // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
232 __last = __i;
233 }
234 else
235 {
236 // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
237 __first = ++__i;
238 }
239 }
240 }
241
242 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
243 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
__nth_element_impl(_RandomAccessIterator __first,_RandomAccessIterator __nth,_RandomAccessIterator __last,_Compare & __comp)244 void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
245 _Compare& __comp) {
246 if (__nth == __last)
247 return;
248
249 std::__debug_randomize_range<_AlgPolicy>(__first, __last);
250
251 std::__nth_element<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __nth, __last, __comp);
252
253 std::__debug_randomize_range<_AlgPolicy>(__first, __nth);
254 if (__nth != __last) {
255 std::__debug_randomize_range<_AlgPolicy>(++__nth, __last);
256 }
257 }
258
259 template <class _RandomAccessIterator, class _Compare>
260 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
nth_element(_RandomAccessIterator __first,_RandomAccessIterator __nth,_RandomAccessIterator __last,_Compare __comp)261 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
262 _Compare __comp) {
263 std::__nth_element_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__nth), std::move(__last), __comp);
264 }
265
266 template <class _RandomAccessIterator>
267 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
nth_element(_RandomAccessIterator __first,_RandomAccessIterator __nth,_RandomAccessIterator __last)268 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) {
269 std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<>());
270 }
271
272 _LIBCPP_END_NAMESPACE_STD
273
274 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H
275