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_IS_HEAP_UNTIL_H
10#define _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H
11
12#include <__algorithm/comp.h>
13#include <__algorithm/comp_ref_type.h>
14#include <__config>
15
16#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
17# pragma GCC system_header
18#endif
19
20_LIBCPP_BEGIN_NAMESPACE_STD
21
22template <class _Compare, class _Iter>
23_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter
24__is_heap_until(_Iter __first, _Iter __last, _Compare&& __comp) {
25 auto __count = __last - __first;
26
27 if (__count < 2)
28 return __last;
29
30 // This points to one past the last parent that has two children.
31 // Integer division handles the case where the last parent has a single child.
32 auto __parent_last = __first + (__count - 1) / 2;
33 auto __child = __first;
34 ++__child;
35 for (; __first != __parent_last; ++__first) {
36 if (__comp(*__first, *__child))
37 return __child;
38 ++__child;
39
40 if (__comp(*__first, *__child))
41 return __child;
42 ++__child;
43 }
44
45 // If the heap is even-sized, the last parent has a single child, handled here.
46 if (__count % 2 == 0) {
47 if (__comp(*__first, *__child))
48 return __child;
49 ++__child;
50 }
51
52 return __child;
53}
54
55template <class _RandomAccessIterator, class _Compare>
56[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
57is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
58 return std::__is_heap_until(__first, __last, static_cast<__comp_ref_type<_Compare> >(__comp));
59}
60
61template <class _RandomAccessIterator>
62[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
63is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) {
64 return std::__is_heap_until(__first, __last, __less<>());
65}
66
67_LIBCPP_END_NAMESPACE_STD
68
69#endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H
70