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_PUSH_MACROS 27 #include <__undef_macros> 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 template <class _Compare, class _RandomAccessIterator> 32 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __nth_element_find_guard( 33 _RandomAccessIterator& __i, _RandomAccessIterator& __j, _RandomAccessIterator __m, _Compare __comp) { 34 // manually guard downward moving __j against __i 35 while (true) { 36 if (__i == --__j) { 37 return false; 38 } 39 if (__comp(*__j, *__m)) { 40 return true; // found guard for downward moving __j, now use unguarded partition 41 } 42 } 43 } 44 45 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 46 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void 47 // NOLINTNEXTLINE(readability-function-cognitive-complexity) 48 __nth_element( 49 _RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { 50 using _Ops = _IterOps<_AlgPolicy>; 51 52 // _Compare is known to be a reference type 53 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 54 const difference_type __limit = 7; 55 while (true) { 56 if (__nth == __last) 57 return; 58 difference_type __len = __last - __first; 59 switch (__len) { 60 case 0: 61 case 1: 62 return; 63 case 2: 64 if (__comp(*--__last, *__first)) 65 _Ops::iter_swap(__first, __last); 66 return; 67 case 3: { 68 _RandomAccessIterator __m = __first; 69 std::__sort3<_AlgPolicy, _Compare>(__first, ++__m, --__last, __comp); 70 return; 71 } 72 } 73 if (__len <= __limit) { 74 std::__selection_sort<_AlgPolicy, _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 = std::__sort3<_AlgPolicy, _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 (std::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { 93 _Ops::iter_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 _Ops::iter_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 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 121 __i != __last, 122 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 123 } 124 do { 125 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 126 __j != __first, 127 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 128 --__j; 129 } while (__comp(*__first, *__j)); 130 if (__i >= __j) 131 break; 132 _Ops::iter_swap(__i, __j); 133 ++__n_swaps; 134 ++__i; 135 } 136 // [__first, __i) == *__first and *__first < [__i, __last) 137 // The first part is sorted, 138 if (__nth < __i) { 139 return; 140 } 141 // __nth_element the second part 142 // std::__nth_element<_Compare>(__i, __nth, __last, __comp); 143 __first = __i; 144 continue; 145 } 146 } 147 ++__i; 148 // j points beyond range to be tested, *__lm1 is known to be <= *__m 149 // if not yet partitioned... 150 if (__i < __j) { 151 // known that *(__i - 1) < *__m 152 while (true) { 153 // __m still guards upward moving __i 154 while (__comp(*__i, *__m)) { 155 ++__i; 156 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 157 __i != __last, 158 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 159 } 160 // It is now known that a guard exists for downward moving __j 161 do { 162 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 163 __j != __first, 164 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 165 --__j; 166 } while (!__comp(*__j, *__m)); 167 if (__i >= __j) 168 break; 169 _Ops::iter_swap(__i, __j); 170 ++__n_swaps; 171 // It is known that __m != __j 172 // If __m just moved, follow it 173 if (__m == __i) 174 __m = __j; 175 ++__i; 176 } 177 } 178 // [__first, __i) < *__m and *__m <= [__i, __last) 179 if (__i != __m && __comp(*__m, *__i)) { 180 _Ops::iter_swap(__i, __m); 181 ++__n_swaps; 182 } 183 // [__first, __i) < *__i and *__i <= [__i+1, __last) 184 if (__nth == __i) 185 return; 186 if (__n_swaps == 0) { 187 // We were given a perfectly partitioned sequence. Coincidence? 188 if (__nth < __i) { 189 // Check for [__first, __i) already sorted 190 __j = __m = __first; 191 while (true) { 192 if (++__j == __i) { 193 // [__first, __i) sorted 194 return; 195 } 196 if (__comp(*__j, *__m)) { 197 // not yet sorted, so sort 198 break; 199 } 200 __m = __j; 201 } 202 } else { 203 // Check for [__i, __last) already sorted 204 __j = __m = __i; 205 while (true) { 206 if (++__j == __last) { 207 // [__i, __last) sorted 208 return; 209 } 210 if (__comp(*__j, *__m)) { 211 // not yet sorted, so sort 212 break; 213 } 214 __m = __j; 215 } 216 } 217 } 218 // __nth_element on range containing __nth 219 if (__nth < __i) { 220 // std::__nth_element<_Compare>(__first, __nth, __i, __comp); 221 __last = __i; 222 } else { 223 // std::__nth_element<_Compare>(__i+1, __nth, __last, __comp); 224 __first = ++__i; 225 } 226 } 227 } 228 229 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare> 230 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __nth_element_impl( 231 _RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare& __comp) { 232 if (__nth == __last) 233 return; 234 235 std::__debug_randomize_range<_AlgPolicy>(__first, __last); 236 237 std::__nth_element<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __nth, __last, __comp); 238 239 std::__debug_randomize_range<_AlgPolicy>(__first, __nth); 240 if (__nth != __last) { 241 std::__debug_randomize_range<_AlgPolicy>(++__nth, __last); 242 } 243 } 244 245 template <class _RandomAccessIterator, class _Compare> 246 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 247 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { 248 std::__nth_element_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__nth), std::move(__last), __comp); 249 } 250 251 template <class _RandomAccessIterator> 252 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 253 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { 254 std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<>()); 255 } 256 257 _LIBCPP_END_NAMESPACE_STD 258 259 _LIBCPP_POP_MACROS 260 261 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H 262