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 #include <__iterator/iterator_traits.h>
16
17 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
18 # pragma GCC system_header
19 #endif
20
21 _LIBCPP_BEGIN_NAMESPACE_STD
22
23 template <class _Compare, class _RandomAccessIterator>
24 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
__is_heap_until(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare && __comp)25 __is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp) {
26 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
27 difference_type __len = __last - __first;
28 difference_type __p = 0;
29 difference_type __c = 1;
30 _RandomAccessIterator __pp = __first;
31 while (__c < __len) {
32 _RandomAccessIterator __cp = __first + __c;
33 if (__comp(*__pp, *__cp))
34 return __cp;
35 ++__c;
36 ++__cp;
37 if (__c == __len)
38 return __last;
39 if (__comp(*__pp, *__cp))
40 return __cp;
41 ++__p;
42 ++__pp;
43 __c = 2 * __p + 1;
44 }
45 return __last;
46 }
47
48 template <class _RandomAccessIterator, class _Compare>
49 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
is_heap_until(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)50 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
51 return std::__is_heap_until(__first, __last, static_cast<__comp_ref_type<_Compare> >(__comp));
52 }
53
54 template <class _RandomAccessIterator>
55 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
is_heap_until(_RandomAccessIterator __first,_RandomAccessIterator __last)56 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) {
57 return std::__is_heap_until(__first, __last, __less<>());
58 }
59
60 _LIBCPP_END_NAMESPACE_STD
61
62 #endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H
63