85 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_PUSH_HEAP_H10#define _LIBCPP___ALGORITHM_PUSH_HEAP_H11 12#include <__algorithm/comp.h>13#include <__algorithm/comp_ref_type.h>14#include <__algorithm/iterator_operations.h>15#include <__config>16#include <__iterator/iterator_traits.h>17#include <__type_traits/is_assignable.h>18#include <__type_traits/is_constructible.h>19#include <__utility/move.h>20 21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)22# pragma GCC system_header23#endif24 25_LIBCPP_PUSH_MACROS26#include <__undef_macros>27 28_LIBCPP_BEGIN_NAMESPACE_STD29 30template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>31_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void32__sift_up(_RandomAccessIterator __first,33 _RandomAccessIterator __last,34 _Compare&& __comp,35 typename iterator_traits<_RandomAccessIterator>::difference_type __len) {36 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;37 38 if (__len > 1) {39 __len = (__len - 2) / 2;40 _RandomAccessIterator __ptr = __first + __len;41 42 if (__comp(*__ptr, *--__last)) {43 value_type __t(_IterOps<_AlgPolicy>::__iter_move(__last));44 do {45 *__last = _IterOps<_AlgPolicy>::__iter_move(__ptr);46 __last = __ptr;47 if (__len == 0)48 break;49 __len = (__len - 1) / 2;50 __ptr = __first + __len;51 } while (__comp(*__ptr, __t));52 53 *__last = std::move(__t);54 }55 }56}57 58template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>59inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void60__push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {61 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;62 std::__sift_up<_AlgPolicy, __comp_ref_type<_Compare> >(std::move(__first), std::move(__last), __comp, __len);63}64 65template <class _RandomAccessIterator, class _Compare>66inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void67push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {68 static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");69 static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");70 71 std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);72}73 74template <class _RandomAccessIterator>75inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void76push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {77 std::push_heap(std::move(__first), std::move(__last), __less<>());78}79 80_LIBCPP_END_NAMESPACE_STD81 82_LIBCPP_POP_MACROS83 84#endif // _LIBCPP___ALGORITHM_PUSH_HEAP_H85