120 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_SIFT_DOWN_H10#define _LIBCPP___ALGORITHM_SIFT_DOWN_H11 12#include <__algorithm/iterator_operations.h>13#include <__assert>14#include <__config>15#include <__iterator/iterator_traits.h>16#include <__utility/move.h>17 18#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)19# pragma GCC system_header20#endif21 22_LIBCPP_PUSH_MACROS23#include <__undef_macros>24 25_LIBCPP_BEGIN_NAMESPACE_STD26 27template <class _AlgPolicy, bool __assume_both_children, class _Compare, class _RandomAccessIterator>28_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void29__sift_down(_RandomAccessIterator __first,30 _Compare&& __comp,31 __iterator_difference_type<_RandomAccessIterator> __len,32 __iterator_difference_type<_RandomAccessIterator> __start) {33 using _Ops = _IterOps<_AlgPolicy>;34 35 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;36 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;37 // left-child of __start is at 2 * __start + 138 // right-child of __start is at 2 * __start + 239 difference_type __child = __start;40 41 if (__len < 2 || (__len - 2) / 2 < __child)42 return;43 44 __child = 2 * __child + 1;45 46 if _LIBCPP_CONSTEXPR (__assume_both_children) {47 // right-child exists and is greater than left-child48 __child += __comp(__first[__child], __first[__child + 1]);49 } else if ((__child + 1) < __len && __comp(__first[__child], __first[__child + 1])) {50 // right-child exists and is greater than left-child51 ++__child;52 }53 54 // check if we are in heap-order55 if (__comp(__first[__child], __first[__start]))56 // we are, __start is larger than its largest child57 return;58 59 value_type __top(_Ops::__iter_move(__first + __start));60 do {61 // we are not in heap-order, swap the parent with its largest child62 __first[__start] = _Ops::__iter_move(__first + __child);63 __start = __child;64 65 if ((__len - 2) / 2 < __child)66 break;67 68 // recompute the child based off of the updated parent69 __child = 2 * __child + 1;70 71 if _LIBCPP_CONSTEXPR (__assume_both_children) {72 __child += __comp(__first[__child], __first[__child + 1]);73 } else if ((__child + 1) < __len && __comp(__first[__child], __first[__child + 1])) {74 // right-child exists and is greater than left-child75 ++__child;76 }77 78 // check if we are in heap-order79 } while (!__comp(__first[__child], __top));80 __first[__start] = std::move(__top);81}82 83template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>84_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __floyd_sift_down(85 _RandomAccessIterator __first,86 _Compare&& __comp,87 typename iterator_traits<_RandomAccessIterator>::difference_type __len) {88 using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;89 _LIBCPP_ASSERT_INTERNAL(__len >= 2, "shouldn't be called unless __len >= 2");90 91 _RandomAccessIterator __hole = __first;92 _RandomAccessIterator __child_i = __first;93 difference_type __child = 0;94 95 while (true) {96 __child_i += difference_type(__child + 1);97 __child = 2 * __child + 1;98 99 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {100 // right-child exists and is greater than left-child101 ++__child_i;102 ++__child;103 }104 105 // swap __hole with its largest child106 *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i);107 __hole = __child_i;108 109 // if __hole is now a leaf, we're done110 if (__child > (__len - 2) / 2)111 return __hole;112 }113}114 115_LIBCPP_END_NAMESPACE_STD116 117_LIBCPP_POP_MACROS118 119#endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H120