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_SIFT_DOWN_H
10 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
11 
12 #include <__config>
13 #include <__iterator/iterator_traits.h>
14 #include <__utility/move.h>
15 
16 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
17 #pragma GCC system_header
18 #endif
19 
20 _LIBCPP_BEGIN_NAMESPACE_STD
21 
22 template <class _Compare, class _RandomAccessIterator>
23 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
24 __sift_down(_RandomAccessIterator __first, _Compare __comp,
25             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
26             _RandomAccessIterator __start)
27 {
28     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
29     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
30     // left-child of __start is at 2 * __start + 1
31     // right-child of __start is at 2 * __start + 2
32     difference_type __child = __start - __first;
33 
34     if (__len < 2 || (__len - 2) / 2 < __child)
35         return;
36 
37     __child = 2 * __child + 1;
38     _RandomAccessIterator __child_i = __first + __child;
39 
40     if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
41         // right-child exists and is greater than left-child
42         ++__child_i;
43         ++__child;
44     }
45 
46     // check if we are in heap-order
47     if (__comp(*__child_i, *__start))
48         // we are, __start is larger than its largest child
49         return;
50 
51     value_type __top(_VSTD::move(*__start));
52     do
53     {
54         // we are not in heap-order, swap the parent with its largest child
55         *__start = _VSTD::move(*__child_i);
56         __start = __child_i;
57 
58         if ((__len - 2) / 2 < __child)
59             break;
60 
61         // recompute the child based off of the updated parent
62         __child = 2 * __child + 1;
63         __child_i = __first + __child;
64 
65         if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
66             // right-child exists and is greater than left-child
67             ++__child_i;
68             ++__child;
69         }
70 
71         // check if we are in heap-order
72     } while (!__comp(*__child_i, __top));
73     *__start = _VSTD::move(__top);
74 }
75 
76 _LIBCPP_END_NAMESPACE_STD
77 
78 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H
79