libcxx/include/__algorithm/is_heap_until.h

   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<>());
  62 }
  63
  64 _LIBCPP_END_NAMESPACE_STD
  65
  66 #endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H