1fe6060f1SDimitry Andric //===----------------------------------------------------------------------===// 2fe6060f1SDimitry Andric // 3fe6060f1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4fe6060f1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5fe6060f1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6fe6060f1SDimitry Andric // 7fe6060f1SDimitry Andric //===----------------------------------------------------------------------===// 8fe6060f1SDimitry Andric 9fe6060f1SDimitry Andric #ifndef _LIBCPP___ALGORITHM_POP_HEAP_H 10fe6060f1SDimitry Andric #define _LIBCPP___ALGORITHM_POP_HEAP_H 11fe6060f1SDimitry Andric 12fe6060f1SDimitry Andric #include <__algorithm/comp.h> 13fe6060f1SDimitry Andric #include <__algorithm/comp_ref_type.h> 14fcaf7f86SDimitry Andric #include <__algorithm/iterator_operations.h> 1581ad6265SDimitry Andric #include <__algorithm/push_heap.h> 16fe6060f1SDimitry Andric #include <__algorithm/sift_down.h> 17753f127fSDimitry Andric #include <__assert> 1804eeddc0SDimitry Andric #include <__config> 19fe6060f1SDimitry Andric #include <__iterator/iterator_traits.h> 20*0fca6ea1SDimitry Andric #include <__type_traits/is_assignable.h> 21*0fca6ea1SDimitry Andric #include <__type_traits/is_constructible.h> 2281ad6265SDimitry Andric #include <__utility/move.h> 23fe6060f1SDimitry Andric 24fe6060f1SDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 25fe6060f1SDimitry Andric # pragma GCC system_header 26fe6060f1SDimitry Andric #endif 27fe6060f1SDimitry Andric 2806c3fb27SDimitry Andric _LIBCPP_PUSH_MACROS 2906c3fb27SDimitry Andric #include <__undef_macros> 3006c3fb27SDimitry Andric 31fe6060f1SDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 32fe6060f1SDimitry Andric 33fcaf7f86SDimitry Andric template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 34cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void 35cb14a3feSDimitry Andric __pop_heap(_RandomAccessIterator __first, 36cb14a3feSDimitry Andric _RandomAccessIterator __last, 37cb14a3feSDimitry Andric _Compare& __comp, 38753f127fSDimitry Andric typename iterator_traits<_RandomAccessIterator>::difference_type __len) { 391db9f3b2SDimitry Andric // Calling `pop_heap` on an empty range is undefined behavior, but in practice it will be a no-op. 401db9f3b2SDimitry Andric _LIBCPP_ASSERT_PEDANTIC(__len > 0, "The heap given to pop_heap must be non-empty"); 4181ad6265SDimitry Andric 42bdd1243dSDimitry Andric __comp_ref_type<_Compare> __comp_ref = __comp; 43753f127fSDimitry Andric 44753f127fSDimitry Andric using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 45753f127fSDimitry Andric if (__len > 1) { 46fcaf7f86SDimitry Andric value_type __top = _IterOps<_AlgPolicy>::__iter_move(__first); // create a hole at __first 4761cfbce3SDimitry Andric _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy>(__first, __comp_ref, __len); 4881ad6265SDimitry Andric --__last; 49753f127fSDimitry Andric 5081ad6265SDimitry Andric if (__hole == __last) { 5181ad6265SDimitry Andric *__hole = std::move(__top); 5281ad6265SDimitry Andric } else { 53fcaf7f86SDimitry Andric *__hole = _IterOps<_AlgPolicy>::__iter_move(__last); 5481ad6265SDimitry Andric ++__hole; 5581ad6265SDimitry Andric *__last = std::move(__top); 5661cfbce3SDimitry Andric std::__sift_up<_AlgPolicy>(__first, __hole, __comp_ref, __hole - __first); 5781ad6265SDimitry Andric } 58fe6060f1SDimitry Andric } 59fe6060f1SDimitry Andric } 60fe6060f1SDimitry Andric 61fe6060f1SDimitry Andric template <class _RandomAccessIterator, class _Compare> 62cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 63cb14a3feSDimitry Andric pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 64fcaf7f86SDimitry Andric static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible."); 65fcaf7f86SDimitry Andric static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable."); 66fcaf7f86SDimitry Andric 67753f127fSDimitry Andric typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; 68fcaf7f86SDimitry Andric std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len); 69fe6060f1SDimitry Andric } 70fe6060f1SDimitry Andric 71fe6060f1SDimitry Andric template <class _RandomAccessIterator> 72cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 73cb14a3feSDimitry Andric pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { 7406c3fb27SDimitry Andric std::pop_heap(std::move(__first), std::move(__last), __less<>()); 75fe6060f1SDimitry Andric } 76fe6060f1SDimitry Andric 77fe6060f1SDimitry Andric _LIBCPP_END_NAMESPACE_STD 78fe6060f1SDimitry Andric 7906c3fb27SDimitry Andric _LIBCPP_POP_MACROS 8006c3fb27SDimitry Andric 81fe6060f1SDimitry Andric #endif // _LIBCPP___ALGORITHM_POP_HEAP_H 82