libcxx/include/__algorithm/nth_element.h

   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
  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)
  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
 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
 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
 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