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 36 template <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 72 template <class _InputIterator, class _RandomAccessIterator, class _Compare> 73 inline _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 93 template <class _InputIterator, class _RandomAccessIterator> 94 inline _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