diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__algorithm/sift_down.h')
-rw-r--r-- | contrib/llvm-project/libcxx/include/__algorithm/sift_down.h | 141 |
1 files changed, 70 insertions, 71 deletions
diff --git a/contrib/llvm-project/libcxx/include/__algorithm/sift_down.h b/contrib/llvm-project/libcxx/include/__algorithm/sift_down.h index 3a222f7c7f1b..7f152e4dbd7f 100644 --- a/contrib/llvm-project/libcxx/include/__algorithm/sift_down.h +++ b/contrib/llvm-project/libcxx/include/__algorithm/sift_down.h @@ -26,90 +26,89 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void -__sift_down(_RandomAccessIterator __first, _Compare&& __comp, +__sift_down(_RandomAccessIterator __first, + _Compare&& __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, - _RandomAccessIterator __start) -{ - using _Ops = _IterOps<_AlgPolicy>; + _RandomAccessIterator __start) { + using _Ops = _IterOps<_AlgPolicy>; - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - // left-child of __start is at 2 * __start + 1 - // right-child of __start is at 2 * __start + 2 - difference_type __child = __start - __first; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + // left-child of __start is at 2 * __start + 1 + // right-child of __start is at 2 * __start + 2 + difference_type __child = __start - __first; - if (__len < 2 || (__len - 2) / 2 < __child) - return; + if (__len < 2 || (__len - 2) / 2 < __child) + return; - __child = 2 * __child + 1; - _RandomAccessIterator __child_i = __first + __child; + __child = 2 * __child + 1; + _RandomAccessIterator __child_i = __first + __child; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; + } + + // check if we are in heap-order + if (__comp(*__child_i, *__start)) + // we are, __start is larger than its largest child + return; + + value_type __top(_Ops::__iter_move(__start)); + do { + // we are not in heap-order, swap the parent with its largest child + *__start = _Ops::__iter_move(__child_i); + __start = __child_i; + + if ((__len - 2) / 2 < __child) + break; + + // recompute the child based off of the updated parent + __child = 2 * __child + 1; + __child_i = __first + __child; if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { - // right-child exists and is greater than left-child - ++__child_i; - ++__child; + // right-child exists and is greater than left-child + ++__child_i; + ++__child; } // check if we are in heap-order - if (__comp(*__child_i, *__start)) - // we are, __start is larger than its largest child - return; - - value_type __top(_Ops::__iter_move(__start)); - do - { - // we are not in heap-order, swap the parent with its largest child - *__start = _Ops::__iter_move(__child_i); - __start = __child_i; - - if ((__len - 2) / 2 < __child) - break; - - // recompute the child based off of the updated parent - __child = 2 * __child + 1; - __child_i = __first + __child; - - if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { - // right-child exists and is greater than left-child - ++__child_i; - ++__child; - } - - // check if we are in heap-order - } while (!__comp(*__child_i, __top)); - *__start = std::move(__top); + } while (!__comp(*__child_i, __top)); + *__start = std::move(__top); } template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator -__floyd_sift_down(_RandomAccessIterator __first, _Compare&& __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) -{ - using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; - _LIBCPP_ASSERT_UNCATEGORIZED(__len >= 2, "shouldn't be called unless __len >= 2"); - - _RandomAccessIterator __hole = __first; - _RandomAccessIterator __child_i = __first; - difference_type __child = 0; - - while (true) { - __child_i += difference_type(__child + 1); - __child = 2 * __child + 1; - - if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { - // right-child exists and is greater than left-child - ++__child_i; - ++__child; - } - - // swap __hole with its largest child - *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i); - __hole = __child_i; - - // if __hole is now a leaf, we're done - if (__child > (__len - 2) / 2) - return __hole; +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __floyd_sift_down( + _RandomAccessIterator __first, + _Compare&& __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) { + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + _LIBCPP_ASSERT_UNCATEGORIZED(__len >= 2, "shouldn't be called unless __len >= 2"); + + _RandomAccessIterator __hole = __first; + _RandomAccessIterator __child_i = __first; + difference_type __child = 0; + + while (true) { + __child_i += difference_type(__child + 1); + __child = 2 * __child + 1; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; } + + // swap __hole with its largest child + *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i); + __hole = __child_i; + + // if __hole is now a leaf, we're done + if (__child > (__len - 2) / 2) + return __hole; + } } _LIBCPP_END_NAMESPACE_STD |