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 <__config>
13 #include <__algorithm/comp.h>
14 #include <__algorithm/comp_ref_type.h>
15 #include <__algorithm/sort.h>
16 #include <__iterator/iterator_traits.h>
17 #include <__utility/swap.h>
18 
19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20 #pragma GCC system_header
21 #endif
22 
23 _LIBCPP_PUSH_MACROS
24 #include <__undef_macros>
25 
26 _LIBCPP_BEGIN_NAMESPACE_STD
27 
28 template<class _Compare, class _RandomAccessIterator>
29 _LIBCPP_CONSTEXPR_AFTER_CXX11 bool
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 _Compare, class _RandomAccessIterator>
45 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
46 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
47 {
48     // _Compare is known to be a reference type
49     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
50     const difference_type __limit = 7;
51     while (true)
52     {
53         if (__nth == __last)
54             return;
55         difference_type __len = __last - __first;
56         switch (__len)
57         {
58         case 0:
59         case 1:
60             return;
61         case 2:
62             if (__comp(*--__last, *__first))
63                 swap(*__first, *__last);
64             return;
65         case 3:
66             {
67             _RandomAccessIterator __m = __first;
68             _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
69             return;
70             }
71         }
72         if (__len <= __limit)
73         {
74             _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
75             return;
76         }
77         // __len > __limit >= 3
78         _RandomAccessIterator __m = __first + __len/2;
79         _RandomAccessIterator __lm1 = __last;
80         unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
81         // *__m is median
82         // partition [__first, __m) < *__m and *__m <= [__m, __last)
83         // (this inhibits tossing elements equivalent to __m around unnecessarily)
84         _RandomAccessIterator __i = __first;
85         _RandomAccessIterator __j = __lm1;
86         // j points beyond range to be tested, *__lm1 is known to be <= *__m
87         // The search going up is known to be guarded but the search coming down isn't.
88         // Prime the downward search with a guard.
89         if (!__comp(*__i, *__m))  // if *__first == *__m
90         {
91             // *__first == *__m, *__first doesn't go in first part
92             if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
93                 swap(*__i, *__j);
94                 ++__n_swaps;
95             } else {
96                 // *__first == *__m, *__m <= all other elements
97                 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
98                 ++__i;  // __first + 1
99                 __j = __last;
100                 if (!__comp(*__first, *--__j)) {  // we need a guard if *__first == *(__last-1)
101                     while (true) {
102                         if (__i == __j) {
103                             return;  // [__first, __last) all equivalent elements
104                         } else if (__comp(*__first, *__i)) {
105                             swap(*__i, *__j);
106                             ++__n_swaps;
107                             ++__i;
108                             break;
109                         }
110                         ++__i;
111                     }
112                 }
113                 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
114                 if (__i == __j) {
115                     return;
116                 }
117                 while (true) {
118                     while (!__comp(*__first, *__i))
119                         ++__i;
120                     while (__comp(*__first, *--__j))
121                         ;
122                     if (__i >= __j)
123                         break;
124                     swap(*__i, *__j);
125                     ++__n_swaps;
126                     ++__i;
127                 }
128                 // [__first, __i) == *__first and *__first < [__i, __last)
129                 // The first part is sorted,
130                 if (__nth < __i) {
131                     return;
132                 }
133                 // __nth_element the second part
134                 // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
135                 __first = __i;
136                 continue;
137             }
138         }
139         ++__i;
140         // j points beyond range to be tested, *__lm1 is known to be <= *__m
141         // if not yet partitioned...
142         if (__i < __j)
143         {
144             // known that *(__i - 1) < *__m
145             while (true)
146             {
147                 // __m still guards upward moving __i
148                 while (__comp(*__i, *__m))
149                     ++__i;
150                 // It is now known that a guard exists for downward moving __j
151                 while (!__comp(*--__j, *__m))
152                     ;
153                 if (__i >= __j)
154                     break;
155                 swap(*__i, *__j);
156                 ++__n_swaps;
157                 // It is known that __m != __j
158                 // If __m just moved, follow it
159                 if (__m == __i)
160                     __m = __j;
161                 ++__i;
162             }
163         }
164         // [__first, __i) < *__m and *__m <= [__i, __last)
165         if (__i != __m && __comp(*__m, *__i))
166         {
167             swap(*__i, *__m);
168             ++__n_swaps;
169         }
170         // [__first, __i) < *__i and *__i <= [__i+1, __last)
171         if (__nth == __i)
172             return;
173         if (__n_swaps == 0)
174         {
175             // We were given a perfectly partitioned sequence.  Coincidence?
176             if (__nth < __i)
177             {
178                 // Check for [__first, __i) already sorted
179                 __j = __m = __first;
180                 while (true) {
181                     if (++__j == __i) {
182                         // [__first, __i) sorted
183                         return;
184                     }
185                     if (__comp(*__j, *__m)) {
186                         // not yet sorted, so sort
187                         break;
188                     }
189                     __m = __j;
190                 }
191             }
192             else
193             {
194                 // Check for [__i, __last) already sorted
195                 __j = __m = __i;
196                 while (true) {
197                     if (++__j == __last) {
198                         // [__i, __last) sorted
199                         return;
200                     }
201                     if (__comp(*__j, *__m)) {
202                         // not yet sorted, so sort
203                         break;
204                     }
205                     __m = __j;
206                 }
207             }
208         }
209         // __nth_element on range containing __nth
210         if (__nth < __i)
211         {
212             // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
213             __last = __i;
214         }
215         else
216         {
217             // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
218             __first = ++__i;
219         }
220     }
221 }
222 
223 template <class _RandomAccessIterator, class _Compare>
224 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
225 void
226 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
227 {
228     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
229     _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
230 }
231 
232 template <class _RandomAccessIterator>
233 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
234 void
235 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
236 {
237     _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
238 }
239 
240 _LIBCPP_END_NAMESPACE_STD
241 
242 _LIBCPP_POP_MACROS
243 
244 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H
245