92 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_PARTIAL_SORT_H10#define _LIBCPP___ALGORITHM_PARTIAL_SORT_H11 12#include <__algorithm/comp.h>13#include <__algorithm/comp_ref_type.h>14#include <__algorithm/iterator_operations.h>15#include <__algorithm/make_heap.h>16#include <__algorithm/sift_down.h>17#include <__algorithm/sort_heap.h>18#include <__config>19#include <__debug_utils/randomize_range.h>20#include <__iterator/iterator_traits.h>21#include <__type_traits/is_assignable.h>22#include <__type_traits/is_constructible.h>23#include <__utility/move.h>24 25#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)26# pragma GCC system_header27#endif28 29_LIBCPP_PUSH_MACROS30#include <__undef_macros>31 32_LIBCPP_BEGIN_NAMESPACE_STD33 34template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>35_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator __partial_sort_impl(36 _RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare&& __comp) {37 if (__first == __middle) {38 return _IterOps<_AlgPolicy>::next(__middle, __last);39 }40 41 std::__make_heap<_AlgPolicy>(__first, __middle, __comp);42 43 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;44 _RandomAccessIterator __i = __middle;45 for (; __i != __last; ++__i) {46 if (__comp(*__i, *__first)) {47 _IterOps<_AlgPolicy>::iter_swap(__i, __first);48 std::__sift_down<_AlgPolicy, false>(__first, __comp, __len, 0);49 }50 }51 std::__sort_heap<_AlgPolicy>(std::move(__first), std::move(__middle), __comp);52 53 return __i;54}55 56template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>57_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator58__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare& __comp) {59 if (__first == __middle)60 return _IterOps<_AlgPolicy>::next(__middle, __last);61 62 std::__debug_randomize_range<_AlgPolicy>(__first, __last);63 64 auto __last_iter =65 std::__partial_sort_impl<_AlgPolicy>(__first, __middle, __last, static_cast<__comp_ref_type<_Compare> >(__comp));66 67 std::__debug_randomize_range<_AlgPolicy>(__middle, __last);68 69 return __last_iter;70}71 72template <class _RandomAccessIterator, class _Compare>73inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void partial_sort(74 _RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) {75 static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");76 static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");77 78 (void)std::__partial_sort<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __comp);79}80 81template <class _RandomAccessIterator>82inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void83partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) {84 std::partial_sort(__first, __middle, __last, __less<>());85}86 87_LIBCPP_END_NAMESPACE_STD88 89_LIBCPP_POP_MACROS90 91#endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_H92