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
25 __is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp)
26 {
27     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
28     difference_type __len = __last - __first;
29     difference_type __p = 0;
30     difference_type __c = 1;
31     _RandomAccessIterator __pp = __first;
32     while (__c < __len)
33     {
34         _RandomAccessIterator __cp = __first + __c;
35         if (__comp(*__pp, *__cp))
36             return __cp;
37         ++__c;
38         ++__cp;
39         if (__c == __len)
40             return __last;
41         if (__comp(*__pp, *__cp))
42             return __cp;
43         ++__p;
44         ++__pp;
45         __c = 2 * __p + 1;
46     }
47     return __last;
48 }
49 
50 template <class _RandomAccessIterator, class _Compare>
51 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
52 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
53 {
54     return std::__is_heap_until(__first, __last, static_cast<__comp_ref_type<_Compare> >(__comp));
55 }
56 
57 template<class _RandomAccessIterator>
58 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator
59 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
60 {
61     return _VSTD::__is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
62 }
63 
64 _LIBCPP_END_NAMESPACE_STD
65 
66 #endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H
67