v1/__algorithm/sift_down.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H
0010 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
0011
0012 #include <__algorithm/iterator_operations.h>
0013 #include <__assert>
0014 #include <__config>
0015 #include <__iterator/iterator_traits.h>
0016 #include <__utility/move.h>
0017
0018 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0019 #  pragma GCC system_header
0020 #endif
0021
0022 _LIBCPP_PUSH_MACROS
0023 #include <__undef_macros>
0024
0025 _LIBCPP_BEGIN_NAMESPACE_STD
0026
0027 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0028 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
0029 __sift_down(_RandomAccessIterator __first,
0030             _Compare&& __comp,
0031             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
0032             _RandomAccessIterator __start) {
0033   using _Ops = _IterOps<_AlgPolicy>;
0034
0035   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
0036   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
0037   // left-child of __start is at 2 * __start + 1
0038   // right-child of __start is at 2 * __start + 2
0039   difference_type __child = __start - __first;
0040
0041   if (__len < 2 || (__len - 2) / 2 < __child)
0042     return;
0043
0044   __child                         = 2 * __child + 1;
0045   _RandomAccessIterator __child_i = __first + __child;
0046
0047   if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
0048     // right-child exists and is greater than left-child
0049     ++__child_i;
0050     ++__child;
0051   }
0052
0053   // check if we are in heap-order
0054   if (__comp(*__child_i, *__start))
0055     // we are, __start is larger than its largest child
0056     return;
0057
0058   value_type __top(_Ops::__iter_move(__start));
0059   do {
0060     // we are not in heap-order, swap the parent with its largest child
0061     *__start = _Ops::__iter_move(__child_i);
0062     __start  = __child_i;
0063
0064     if ((__len - 2) / 2 < __child)
0065       break;
0066
0067     // recompute the child based off of the updated parent
0068     __child   = 2 * __child + 1;
0069     __child_i = __first + __child;
0070
0071     if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
0072       // right-child exists and is greater than left-child
0073       ++__child_i;
0074       ++__child;
0075     }
0076
0077     // check if we are in heap-order
0078   } while (!__comp(*__child_i, __top));
0079   *__start = std::move(__top);
0080 }
0081
0082 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0083 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __floyd_sift_down(
0084     _RandomAccessIterator __first,
0085     _Compare&& __comp,
0086     typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
0087   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
0088   _LIBCPP_ASSERT_INTERNAL(__len >= 2, "shouldn't be called unless __len >= 2");
0089
0090   _RandomAccessIterator __hole    = __first;
0091   _RandomAccessIterator __child_i = __first;
0092   difference_type __child         = 0;
0093
0094   while (true) {
0095     __child_i += difference_type(__child + 1);
0096     __child = 2 * __child + 1;
0097
0098     if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
0099       // right-child exists and is greater than left-child
0100       ++__child_i;
0101       ++__child;
0102     }
0103
0104     // swap __hole with its largest child
0105     *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i);
0106     __hole  = __child_i;
0107
0108     // if __hole is now a leaf, we're done
0109     if (__child > (__len - 2) / 2)
0110       return __hole;
0111   }
0112 }
0113
0114 _LIBCPP_END_NAMESPACE_STD
0115
0116 _LIBCPP_POP_MACROS
0117
0118 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H