v1/__algorithm/nth_element.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_NTH_ELEMENT_H
0010 #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H
0011
0012 #include <__algorithm/comp.h>
0013 #include <__algorithm/comp_ref_type.h>
0014 #include <__algorithm/iterator_operations.h>
0015 #include <__algorithm/sort.h>
0016 #include <__assert>
0017 #include <__config>
0018 #include <__debug_utils/randomize_range.h>
0019 #include <__iterator/iterator_traits.h>
0020 #include <__utility/move.h>
0021
0022 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0023 #  pragma GCC system_header
0024 #endif
0025
0026 _LIBCPP_PUSH_MACROS
0027 #include <__undef_macros>
0028
0029 _LIBCPP_BEGIN_NAMESPACE_STD
0030
0031 template <class _Compare, class _RandomAccessIterator>
0032 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __nth_element_find_guard(
0033     _RandomAccessIterator& __i, _RandomAccessIterator& __j, _RandomAccessIterator __m, _Compare __comp) {
0034   // manually guard downward moving __j against __i
0035   while (true) {
0036     if (__i == --__j) {
0037       return false;
0038     }
0039     if (__comp(*__j, *__m)) {
0040       return true; // found guard for downward moving __j, now use unguarded partition
0041     }
0042   }
0043 }
0044
0045 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0046 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
0047 // NOLINTNEXTLINE(readability-function-cognitive-complexity)
0048 __nth_element(
0049     _RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) {
0050   using _Ops = _IterOps<_AlgPolicy>;
0051
0052   // _Compare is known to be a reference type
0053   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
0054   const difference_type __limit = 7;
0055   while (true) {
0056     if (__nth == __last)
0057       return;
0058     difference_type __len = __last - __first;
0059     switch (__len) {
0060     case 0:
0061     case 1:
0062       return;
0063     case 2:
0064       if (__comp(*--__last, *__first))
0065         _Ops::iter_swap(__first, __last);
0066       return;
0067     case 3: {
0068       _RandomAccessIterator __m = __first;
0069       std::__sort3<_AlgPolicy, _Compare>(__first, ++__m, --__last, __comp);
0070       return;
0071     }
0072     }
0073     if (__len <= __limit) {
0074       std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
0075       return;
0076     }
0077     // __len > __limit >= 3
0078     _RandomAccessIterator __m   = __first + __len / 2;
0079     _RandomAccessIterator __lm1 = __last;
0080     unsigned __n_swaps          = std::__sort3<_AlgPolicy, _Compare>(__first, __m, --__lm1, __comp);
0081     // *__m is median
0082     // partition [__first, __m) < *__m and *__m <= [__m, __last)
0083     // (this inhibits tossing elements equivalent to __m around unnecessarily)
0084     _RandomAccessIterator __i = __first;
0085     _RandomAccessIterator __j = __lm1;
0086     // j points beyond range to be tested, *__lm1 is known to be <= *__m
0087     // The search going up is known to be guarded but the search coming down isn't.
0088     // Prime the downward search with a guard.
0089     if (!__comp(*__i, *__m)) // if *__first == *__m
0090     {
0091       // *__first == *__m, *__first doesn't go in first part
0092       if (std::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
0093         _Ops::iter_swap(__i, __j);
0094         ++__n_swaps;
0095       } else {
0096         // *__first == *__m, *__m <= all other elements
0097         // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
0098         ++__i; // __first + 1
0099         __j = __last;
0100         if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1)
0101           while (true) {
0102             if (__i == __j) {
0103               return; // [__first, __last) all equivalent elements
0104             } else if (__comp(*__first, *__i)) {
0105               _Ops::iter_swap(__i, __j);
0106               ++__n_swaps;
0107               ++__i;
0108               break;
0109             }
0110             ++__i;
0111           }
0112         }
0113         // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
0114         if (__i == __j) {
0115           return;
0116         }
0117         while (true) {
0118           while (!__comp(*__first, *__i)) {
0119             ++__i;
0120             _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0121                 __i != __last,
0122                 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
0123           }
0124           do {
0125             _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0126                 __j != __first,
0127                 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
0128             --__j;
0129           } while (__comp(*__first, *__j));
0130           if (__i >= __j)
0131             break;
0132           _Ops::iter_swap(__i, __j);
0133           ++__n_swaps;
0134           ++__i;
0135         }
0136         // [__first, __i) == *__first and *__first < [__i, __last)
0137         // The first part is sorted,
0138         if (__nth < __i) {
0139           return;
0140         }
0141         // __nth_element the second part
0142         // std::__nth_element<_Compare>(__i, __nth, __last, __comp);
0143         __first = __i;
0144         continue;
0145       }
0146     }
0147     ++__i;
0148     // j points beyond range to be tested, *__lm1 is known to be <= *__m
0149     // if not yet partitioned...
0150     if (__i < __j) {
0151       // known that *(__i - 1) < *__m
0152       while (true) {
0153         // __m still guards upward moving __i
0154         while (__comp(*__i, *__m)) {
0155           ++__i;
0156           _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0157               __i != __last,
0158               "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
0159         }
0160         // It is now known that a guard exists for downward moving __j
0161         do {
0162           _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0163               __j != __first,
0164               "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
0165           --__j;
0166         } while (!__comp(*__j, *__m));
0167         if (__i >= __j)
0168           break;
0169         _Ops::iter_swap(__i, __j);
0170         ++__n_swaps;
0171         // It is known that __m != __j
0172         // If __m just moved, follow it
0173         if (__m == __i)
0174           __m = __j;
0175         ++__i;
0176       }
0177     }
0178     // [__first, __i) < *__m and *__m <= [__i, __last)
0179     if (__i != __m && __comp(*__m, *__i)) {
0180       _Ops::iter_swap(__i, __m);
0181       ++__n_swaps;
0182     }
0183     // [__first, __i) < *__i and *__i <= [__i+1, __last)
0184     if (__nth == __i)
0185       return;
0186     if (__n_swaps == 0) {
0187       // We were given a perfectly partitioned sequence.  Coincidence?
0188       if (__nth < __i) {
0189         // Check for [__first, __i) already sorted
0190         __j = __m = __first;
0191         while (true) {
0192           if (++__j == __i) {
0193             // [__first, __i) sorted
0194             return;
0195           }
0196           if (__comp(*__j, *__m)) {
0197             // not yet sorted, so sort
0198             break;
0199           }
0200           __m = __j;
0201         }
0202       } else {
0203         // Check for [__i, __last) already sorted
0204         __j = __m = __i;
0205         while (true) {
0206           if (++__j == __last) {
0207             // [__i, __last) sorted
0208             return;
0209           }
0210           if (__comp(*__j, *__m)) {
0211             // not yet sorted, so sort
0212             break;
0213           }
0214           __m = __j;
0215         }
0216       }
0217     }
0218     // __nth_element on range containing __nth
0219     if (__nth < __i) {
0220       // std::__nth_element<_Compare>(__first, __nth, __i, __comp);
0221       __last = __i;
0222     } else {
0223       // std::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
0224       __first = ++__i;
0225     }
0226   }
0227 }
0228
0229 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
0230 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __nth_element_impl(
0231     _RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare& __comp) {
0232   if (__nth == __last)
0233     return;
0234
0235   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
0236
0237   std::__nth_element<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __nth, __last, __comp);
0238
0239   std::__debug_randomize_range<_AlgPolicy>(__first, __nth);
0240   if (__nth != __last) {
0241     std::__debug_randomize_range<_AlgPolicy>(++__nth, __last);
0242   }
0243 }
0244
0245 template <class _RandomAccessIterator, class _Compare>
0246 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0247 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) {
0248   std::__nth_element_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__nth), std::move(__last), __comp);
0249 }
0250
0251 template <class _RandomAccessIterator>
0252 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0253 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) {
0254   std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<>());
0255 }
0256
0257 _LIBCPP_END_NAMESPACE_STD
0258
0259 _LIBCPP_POP_MACROS
0260
0261 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H