[libc++][ranges] Implement modifying heap algorithms:
- `ranges::make_heap`;
- `ranges::push_heap`;
- `ranges::pop_heap`;
- `ranges::sort_heap`.
Differential Revision: https://reviews.llvm.org/D128115
NOKEYCHECK=True
GitOrigin-RevId: c945bd0da652cd05c0a74898ef5122c2b7a496ef
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index a5191f5..36f31c1 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -92,6 +92,7 @@
__algorithm/ranges_is_sorted_until.h
__algorithm/ranges_lexicographical_compare.h
__algorithm/ranges_lower_bound.h
+ __algorithm/ranges_make_heap.h
__algorithm/ranges_max.h
__algorithm/ranges_max_element.h
__algorithm/ranges_merge.h
@@ -104,6 +105,8 @@
__algorithm/ranges_move_backward.h
__algorithm/ranges_none_of.h
__algorithm/ranges_nth_element.h
+ __algorithm/ranges_pop_heap.h
+ __algorithm/ranges_push_heap.h
__algorithm/ranges_remove.h
__algorithm/ranges_remove_if.h
__algorithm/ranges_replace.h
@@ -111,6 +114,7 @@
__algorithm/ranges_reverse.h
__algorithm/ranges_set_difference.h
__algorithm/ranges_sort.h
+ __algorithm/ranges_sort_heap.h
__algorithm/ranges_stable_sort.h
__algorithm/ranges_swap_ranges.h
__algorithm/ranges_transform.h
diff --git a/include/__algorithm/make_heap.h b/include/__algorithm/make_heap.h
index acac0aa..bc39d82 100644
--- a/include/__algorithm/make_heap.h
+++ b/include/__algorithm/make_heap.h
@@ -14,6 +14,7 @@
#include <__algorithm/sift_down.h>
#include <__config>
#include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
@@ -22,36 +23,32 @@
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 void
-__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
- difference_type __n = __last - __first;
- if (__n > 1)
- {
- // start from the first parent, there is no need to consider children
- for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
- {
- _VSTD::__sift_down<_Compare>(__first, __comp, __n, __first + __start);
- }
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+ using _CompRef = typename __comp_ref_type<_Compare>::type;
+ _CompRef __comp_ref = __comp;
+
+ using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+ difference_type __n = __last - __first;
+ if (__n > 1) {
+ // start from the first parent, there is no need to consider children
+ for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
+ std::__sift_down<_CompRef>(__first, __comp_ref, __n, __first + __start);
}
+ }
}
template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
- typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
- _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+ std::__make_heap(std::move(__first), std::move(__last), __comp);
}
template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
- _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
+ std::make_heap(std::move(__first), std::move(__last),
+ __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/include/__algorithm/pop_heap.h b/include/__algorithm/pop_heap.h
index 2932a5e..cadda81 100644
--- a/include/__algorithm/pop_heap.h
+++ b/include/__algorithm/pop_heap.h
@@ -13,6 +13,7 @@
#include <__algorithm/comp_ref_type.h>
#include <__algorithm/push_heap.h>
#include <__algorithm/sift_down.h>
+#include <__assert>
#include <__config>
#include <__iterator/iterator_traits.h>
#include <__utility/move.h>
@@ -24,44 +25,43 @@
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _Compare, class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
- typename iterator_traits<_RandomAccessIterator>::difference_type __len)
-{
- using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp,
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
+ _LIBCPP_ASSERT(__len > 0, "The heap given to pop_heap must be non-empty");
- if (__len > 1)
- {
- value_type __top = std::move(*__first); // create a hole at __first
- _RandomAccessIterator __hole = std::__floyd_sift_down<_Compare>(__first, __comp, __len);
- --__last;
- if (__hole == __last) {
- *__hole = std::move(__top);
- } else {
- *__hole = std::move(*__last);
- ++__hole;
- *__last = std::move(__top);
- std::__sift_up<_Compare>(__first, __hole, __comp, __hole - __first);
- }
+ using _CompRef = typename __comp_ref_type<_Compare>::type;
+ _CompRef __comp_ref = __comp;
+
+ using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+ if (__len > 1) {
+ value_type __top = std::move(*__first); // create a hole at __first
+ _RandomAccessIterator __hole = std::__floyd_sift_down<_CompRef>(__first, __comp_ref, __len);
+ --__last;
+
+ if (__hole == __last) {
+ *__hole = std::move(__top);
+ } else {
+ *__hole = std::move(*__last);
+ ++__hole;
+ *__last = std::move(__top);
+ std::__sift_up<_CompRef>(__first, __hole, __comp_ref, __hole - __first);
}
+ }
}
template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
- typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
- _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
+ std::__pop_heap(std::move(__first), std::move(__last), __comp, __len);
}
template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
- _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
+ std::pop_heap(std::move(__first), std::move(__last),
+ __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/include/__algorithm/push_heap.h b/include/__algorithm/push_heap.h
index 66973e0..1e3eec3 100644
--- a/include/__algorithm/push_heap.h
+++ b/include/__algorithm/push_heap.h
@@ -22,47 +22,50 @@
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 void
-__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
- typename iterator_traits<_RandomAccessIterator>::difference_type __len)
-{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
- if (__len > 1)
- {
- __len = (__len - 2) / 2;
- _RandomAccessIterator __ptr = __first + __len;
- if (__comp(*__ptr, *--__last))
- {
- value_type __t(_VSTD::move(*__last));
- do
- {
- *__last = _VSTD::move(*__ptr);
- __last = __ptr;
- if (__len == 0)
- break;
- __len = (__len - 1) / 2;
- __ptr = __first + __len;
- } while (__comp(*__ptr, __t));
- *__last = _VSTD::move(__t);
- }
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
+ using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+
+ if (__len > 1) {
+ __len = (__len - 2) / 2;
+ _RandomAccessIterator __ptr = __first + __len;
+
+ if (__comp(*__ptr, *--__last)) {
+ value_type __t(std::move(*__last));
+ do {
+ *__last = std::move(*__ptr);
+ __last = __ptr;
+ if (__len == 0)
+ break;
+ __len = (__len - 1) / 2;
+ __ptr = __first + __len;
+ } while (__comp(*__ptr, __t));
+
+ *__last = std::move(__t);
}
+ }
}
template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
- typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
- _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+ using _CompRef = typename __comp_ref_type<_Compare>::type;
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
+ std::__sift_up<_CompRef>(std::move(__first), std::move(__last), __comp, __len);
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+ std::__push_heap(std::move(__first), std::move(__last), __comp);
}
template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
- _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
+ std::push_heap(std::move(__first), std::move(__last),
+ __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/include/__algorithm/ranges_make_heap.h b/include/__algorithm/ranges_make_heap.h
new file mode 100644
index 0000000..fd488dc
--- /dev/null
+++ b/include/__algorithm/ranges_make_heap.h
@@ -0,0 +1,79 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
+#define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
+
+#include <__algorithm/make_heap.h>
+#include <__algorithm/make_projected.h>
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __make_heap {
+
+struct __fn {
+ template <class _Iter, class _Sent, class _Comp, class _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr static
+ _Iter __make_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
+ auto __last_iter = ranges::next(__first, __last);
+
+ auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+ std::__make_heap(std::move(__first), __last_iter, __projected_comp);
+
+ return __last_iter;
+ }
+
+ template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __make_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+ }
+
+ template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __make_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+ }
+};
+
+} // namespace __make_heap
+
+inline namespace __cpo {
+ inline constexpr auto make_heap = __make_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
diff --git a/include/__algorithm/ranges_pop_heap.h b/include/__algorithm/ranges_pop_heap.h
new file mode 100644
index 0000000..d0b8314
--- /dev/null
+++ b/include/__algorithm/ranges_pop_heap.h
@@ -0,0 +1,80 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
+#define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
+
+#include <__algorithm/make_projected.h>
+#include <__algorithm/pop_heap.h>
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __pop_heap {
+
+struct __fn {
+ template <class _Iter, class _Sent, class _Comp, class _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr static
+ _Iter __pop_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
+ auto __last_iter = ranges::next(__first, __last);
+ auto __len = __last_iter - __first;
+
+ auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+ std::__pop_heap(std::move(__first), __last_iter, __projected_comp, __len);
+
+ return __last_iter;
+ }
+
+ template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __pop_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+ }
+
+ template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __pop_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+ }
+};
+
+} // namespace __pop_heap
+
+inline namespace __cpo {
+ inline constexpr auto pop_heap = __pop_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
diff --git a/include/__algorithm/ranges_push_heap.h b/include/__algorithm/ranges_push_heap.h
new file mode 100644
index 0000000..e46ad19
--- /dev/null
+++ b/include/__algorithm/ranges_push_heap.h
@@ -0,0 +1,79 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
+#define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
+
+#include <__algorithm/make_projected.h>
+#include <__algorithm/push_heap.h>
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __push_heap {
+
+struct __fn {
+ template <class _Iter, class _Sent, class _Comp, class _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr static
+ _Iter __push_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
+ auto __last_iter = ranges::next(__first, __last);
+
+ auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+ std::__push_heap(std::move(__first), __last_iter, __projected_comp);
+
+ return __last_iter;
+ }
+
+ template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __push_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+ }
+
+ template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __push_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+ }
+};
+
+} // namespace __push_heap
+
+inline namespace __cpo {
+ inline constexpr auto push_heap = __push_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
diff --git a/include/__algorithm/ranges_sort_heap.h b/include/__algorithm/ranges_sort_heap.h
new file mode 100644
index 0000000..c753e20
--- /dev/null
+++ b/include/__algorithm/ranges_sort_heap.h
@@ -0,0 +1,79 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
+#define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
+
+#include <__algorithm/make_projected.h>
+#include <__algorithm/sort_heap.h>
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __sort_heap {
+
+struct __fn {
+ template <class _Iter, class _Sent, class _Comp, class _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr static
+ _Iter __sort_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
+ auto __last_iter = ranges::next(__first, __last);
+
+ auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+ std::__sort_heap(std::move(__first), __last_iter, __projected_comp);
+
+ return __last_iter;
+ }
+
+ template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __sort_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+ }
+
+ template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr
+ borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+ return __sort_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+ }
+};
+
+} // namespace __sort_heap
+
+inline namespace __cpo {
+ inline constexpr auto sort_heap = __sort_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
diff --git a/include/__algorithm/sort_heap.h b/include/__algorithm/sort_heap.h
index 3a63d74..261aded 100644
--- a/include/__algorithm/sort_heap.h
+++ b/include/__algorithm/sort_heap.h
@@ -14,6 +14,7 @@
#include <__algorithm/pop_heap.h>
#include <__config>
#include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
#include <type_traits> // swap
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -23,29 +24,27 @@
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 void
-__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
- for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
- _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+ using _CompRef = typename __comp_ref_type<_Compare>::type;
+ _CompRef __comp_ref = __comp;
+
+ using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+ for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
+ std::__pop_heap<_CompRef>(__first, __last, __comp_ref, __n);
}
template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
- typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
- _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+ std::__sort_heap(std::move(__first), std::move(__last), __comp);
}
template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
- _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
+ std::sort_heap(std::move(__first), std::move(__last),
+ __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/include/algorithm b/include/algorithm
index 1b1dc16..785c3ef 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -287,6 +287,50 @@
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ constexpr I
+ ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ constexpr borrowed_iterator_t<R>
+ ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ constexpr I
+ ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ constexpr borrowed_iterator_t<R>
+ ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ constexpr I
+ ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ constexpr borrowed_iterator_t<R>
+ ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ constexpr I
+ ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ constexpr borrowed_iterator_t<R>
+ ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
template<bidirectional_iterator I, sentinel_for<I> S>
requires permutable<I>
constexpr I ranges::reverse(I first, S last); // since C++20
@@ -1313,6 +1357,7 @@
#include <__algorithm/ranges_is_sorted_until.h>
#include <__algorithm/ranges_lexicographical_compare.h>
#include <__algorithm/ranges_lower_bound.h>
+#include <__algorithm/ranges_make_heap.h>
#include <__algorithm/ranges_max.h>
#include <__algorithm/ranges_max_element.h>
#include <__algorithm/ranges_merge.h>
@@ -1325,6 +1370,8 @@
#include <__algorithm/ranges_move_backward.h>
#include <__algorithm/ranges_none_of.h>
#include <__algorithm/ranges_nth_element.h>
+#include <__algorithm/ranges_pop_heap.h>
+#include <__algorithm/ranges_push_heap.h>
#include <__algorithm/ranges_remove.h>
#include <__algorithm/ranges_remove_if.h>
#include <__algorithm/ranges_replace.h>
@@ -1332,6 +1379,7 @@
#include <__algorithm/ranges_reverse.h>
#include <__algorithm/ranges_set_difference.h>
#include <__algorithm/ranges_sort.h>
+#include <__algorithm/ranges_sort_heap.h>
#include <__algorithm/ranges_stable_sort.h>
#include <__algorithm/ranges_swap_ranges.h>
#include <__algorithm/ranges_transform.h>
diff --git a/include/module.modulemap.in b/include/module.modulemap.in
index 0447cf0..e90c5af 100644
--- a/include/module.modulemap.in
+++ b/include/module.modulemap.in
@@ -331,6 +331,7 @@
module ranges_is_sorted_until { private header "__algorithm/ranges_is_sorted_until.h" }
module ranges_lexicographical_compare { private header "__algorithm/ranges_lexicographical_compare.h" }
module ranges_lower_bound { private header "__algorithm/ranges_lower_bound.h" }
+ module ranges_make_heap { private header "__algorithm/ranges_make_heap.h" }
module ranges_max { private header "__algorithm/ranges_max.h" }
module ranges_max_element { private header "__algorithm/ranges_max_element.h" }
module ranges_merge { private header "__algorithm/ranges_merge.h" }
@@ -343,6 +344,8 @@
module ranges_move_backward { private header "__algorithm/ranges_move_backward.h" }
module ranges_none_of { private header "__algorithm/ranges_none_of.h" }
module ranges_nth_element { private header "__algorithm/ranges_nth_element.h" }
+ module ranges_pop_heap { private header "__algorithm/ranges_pop_heap.h" }
+ module ranges_push_heap { private header "__algorithm/ranges_push_heap.h" }
module ranges_remove { private header "__algorithm/ranges_remove.h" }
module ranges_remove_if { private header "__algorithm/ranges_remove_if.h" }
module ranges_replace { private header "__algorithm/ranges_replace.h" }
@@ -350,6 +353,7 @@
module ranges_reverse { private header "__algorithm/ranges_reverse.h" }
module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" }
module ranges_sort { private header "__algorithm/ranges_sort.h" }
+ module ranges_sort_heap { private header "__algorithm/ranges_sort_heap.h" }
module ranges_stable_sort { private header "__algorithm/ranges_stable_sort.h" }
module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" }
module ranges_transform { private header "__algorithm/ranges_transform.h" }