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