v1/__algorithm/push_heap.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_PUSH_HEAP_H
0010 #define _LIBCPP___ALGORITHM_PUSH_HEAP_H
0011
0012 #include <__algorithm/comp.h>
0013 #include <__algorithm/comp_ref_type.h>
0014 #include <__algorithm/iterator_operations.h>
0015 #include <__config>
0016 #include <__iterator/iterator_traits.h>
0017 #include <__type_traits/is_assignable.h>
0018 #include <__type_traits/is_constructible.h>
0019 #include <__utility/move.h>
0020
0021 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0022 #  pragma GCC system_header
0023 #endif
0024
0025 _LIBCPP_PUSH_MACROS
0026 #include <__undef_macros>
0027
0028 _LIBCPP_BEGIN_NAMESPACE_STD
0029
0030 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0031 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
0032 __sift_up(_RandomAccessIterator __first,
0033           _RandomAccessIterator __last,
0034           _Compare&& __comp,
0035           typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
0036   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
0037
0038   if (__len > 1) {
0039     __len                       = (__len - 2) / 2;
0040     _RandomAccessIterator __ptr = __first + __len;
0041
0042     if (__comp(*__ptr, *--__last)) {
0043       value_type __t(_IterOps<_AlgPolicy>::__iter_move(__last));
0044       do {
0045         *__last = _IterOps<_AlgPolicy>::__iter_move(__ptr);
0046         __last  = __ptr;
0047         if (__len == 0)
0048           break;
0049         __len = (__len - 1) / 2;
0050         __ptr = __first + __len;
0051       } while (__comp(*__ptr, __t));
0052
0053       *__last = std::move(__t);
0054     }
0055   }
0056 }
0057
0058 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
0059 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
0060 __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
0061   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
0062   std::__sift_up<_AlgPolicy, __comp_ref_type<_Compare> >(std::move(__first), std::move(__last), __comp, __len);
0063 }
0064
0065 template <class _RandomAccessIterator, class _Compare>
0066 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0067 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
0068   static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
0069   static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
0070
0071   std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
0072 }
0073
0074 template <class _RandomAccessIterator>
0075 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0076 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
0077   std::push_heap(std::move(__first), std::move(__last), __less<>());
0078 }
0079
0080 _LIBCPP_END_NAMESPACE_STD
0081
0082 _LIBCPP_POP_MACROS
0083
0084 #endif // _LIBCPP___ALGORITHM_PUSH_HEAP_H