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_PARTIAL_SORT_COPY_H 10#define _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H 11 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/make_projected.h> 17#include <__algorithm/sift_down.h> 18#include <__algorithm/sort_heap.h> 19#include <__config> 20#include <__functional/identity.h> 21#include <__functional/invoke.h> 22#include <__iterator/iterator_traits.h> 23#include <__type_traits/is_callable.h> 24#include <__utility/move.h> 25#include <__utility/pair.h> 26 27#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 28# pragma GCC system_header 29#endif 30 31_LIBCPP_PUSH_MACROS 32#include <__undef_macros> 33 34_LIBCPP_BEGIN_NAMESPACE_STD 35 36template <class _AlgPolicy, 37 class _Compare, 38 class _InputIterator, 39 class _Sentinel1, 40 class _RandomAccessIterator, 41 class _Sentinel2, 42 class _Proj1, 43 class _Proj2> 44_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator, _RandomAccessIterator> __partial_sort_copy( 45 _InputIterator __first, 46 _Sentinel1 __last, 47 _RandomAccessIterator __result_first, 48 _Sentinel2 __result_last, 49 _Compare&& __comp, 50 _Proj1&& __proj1, 51 _Proj2&& __proj2) { 52 _RandomAccessIterator __r = __result_first; 53 auto&& __projected_comp = std::__make_projected(__comp, __proj2); 54 55 if (__r != __result_last) { 56 for (; __first != __last && __r != __result_last; ++__first, (void)++__r) 57 *__r = *__first; 58 std::__make_heap<_AlgPolicy>(__result_first, __r, __projected_comp); 59 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; 60 for (; __first != __last; ++__first) 61 if (std::__invoke(__comp, std::__invoke(__proj1, *__first), std::__invoke(__proj2, *__result_first))) { 62 *__result_first = *__first; 63 std::__sift_down<_AlgPolicy>(__result_first, __projected_comp, __len, __result_first); 64 } 65 std::__sort_heap<_AlgPolicy>(__result_first, __r, __projected_comp); 66 } 67 68 return pair<_InputIterator, _RandomAccessIterator>( 69 _IterOps<_AlgPolicy>::next(std::move(__first), std::move(__last)), std::move(__r)); 70} 71 72template <class _InputIterator, class _RandomAccessIterator, class _Compare> 73inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator partial_sort_copy( 74 _InputIterator __first, 75 _InputIterator __last, 76 _RandomAccessIterator __result_first, 77 _RandomAccessIterator __result_last, 78 _Compare __comp) { 79 static_assert( 80 __is_callable<_Compare, decltype(*__first), decltype(*__result_first)>::value, "Comparator has to be callable"); 81 82 auto __result = std::__partial_sort_copy<_ClassicAlgPolicy>( 83 __first, 84 __last, 85 __result_first, 86 __result_last, 87 static_cast<__comp_ref_type<_Compare> >(__comp), 88 __identity(), 89 __identity()); 90 return __result.second; 91} 92 93template <class _InputIterator, class _RandomAccessIterator> 94inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator partial_sort_copy( 95 _InputIterator __first, 96 _InputIterator __last, 97 _RandomAccessIterator __result_first, 98 _RandomAccessIterator __result_last) { 99 return std::partial_sort_copy(__first, __last, __result_first, __result_last, __less<>()); 100} 101 102_LIBCPP_END_NAMESPACE_STD 103 104_LIBCPP_POP_MACROS 105 106#endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H 107