diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -166,7 +166,12 @@ algorithms/min_max_element.bench.cpp algorithms/pop_heap.bench.cpp algorithms/push_heap.bench.cpp + algorithms/ranges_make_heap.bench.cpp + algorithms/ranges_make_heap_then_sort_heap.bench.cpp + algorithms/ranges_pop_heap.bench.cpp + algorithms/ranges_push_heap.bench.cpp algorithms/ranges_sort.bench.cpp + algorithms/ranges_sort_heap.bench.cpp algorithms/sort.bench.cpp algorithms/sort_heap.bench.cpp algorithms/stable_sort.bench.cpp diff --git a/libcxx/benchmarks/algorithms/ranges_make_heap.bench.cpp b/libcxx/benchmarks/algorithms/ranges_make_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_make_heap.bench.cpp @@ -0,0 +1,37 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include "common.h" + +namespace { +template +struct RangesMakeHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, + [](auto& Copy) { std::ranges::make_heap(Copy); }); + } + + std::string name() const { + return "BM_RangesMakeHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/libcxx/benchmarks/algorithms/ranges_make_heap_then_sort_heap.bench.cpp b/libcxx/benchmarks/algorithms/ranges_make_heap_then_sort_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_make_heap_then_sort_heap.bench.cpp @@ -0,0 +1,39 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include "common.h" + +namespace { +template +struct RangesMakeThenSortHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies(state, Quantity, Order(), BatchSize::CountElements, + [](auto& Copy) { + std::ranges::make_heap(Copy); + std::ranges::sort_heap(Copy); + }); + } + + std::string name() const { + return "BM_RangesMakeThenSortHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/libcxx/benchmarks/algorithms/ranges_pop_heap.bench.cpp b/libcxx/benchmarks/algorithms/ranges_pop_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_pop_heap.bench.cpp @@ -0,0 +1,39 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include "common.h" + +namespace { +template +struct RangesPopHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) { + for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) { + std::ranges::pop_heap(B, I); + } + }); + } + + std::string name() const { + return "BM_RangesPopHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/libcxx/benchmarks/algorithms/ranges_push_heap.bench.cpp b/libcxx/benchmarks/algorithms/ranges_push_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_push_heap.bench.cpp @@ -0,0 +1,42 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include "common.h" + +namespace { +template +struct RangesPushHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) { + for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) { + std::ranges::push_heap(Copy.begin(), I + 1); + } + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_RangesPushHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/libcxx/benchmarks/algorithms/ranges_sort_heap.bench.cpp b/libcxx/benchmarks/algorithms/ranges_sort_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_sort_heap.bench.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include "common.h" + +namespace { +template +struct RangesSortHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order::Heap, BatchSize::CountElements, + [](auto& Copy) { std::ranges::sort_heap(Copy); }); + } + + std::string name() const { + return "BM_RangesSortHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -78,10 +78,10 @@ Permutation,partial_sort,Konstantin Varlamov,n/a,In progress Permutation,nth_element,Not assigned,n/a,Not started Permutation,inplace_merge,Not assigned,n/a,Not started -Permutation,make_heap,Not assigned,n/a,Not started -Permutation,push_heap,Not assigned,n/a,Not started -Permutation,pop_heap,Not assigned,n/a,Not started -Permutation,sort_heap,Not assigned,n/a,Not started +Permutation,make_heap,Konstantin Varlamov,`TODO `_,✅ +Permutation,push_heap,Konstantin Varlamov,`TODO `_,✅ +Permutation,pop_heap,Konstantin Varlamov,`TODO `_,✅ +Permutation,sort_heap,Konstantin Varlamov,`TODO `_,✅ Permutation,prev_permutation,Not assigned,n/a,Not started Permutation,next_permutation,Not assigned,n/a,Not started Uninitialised memory,uninitialized_copy,Konstantin Varlamov,`D116023 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/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_min.h @@ -100,10 +101,13 @@ __algorithm/ranges_minmax_element.h __algorithm/ranges_mismatch.h __algorithm/ranges_none_of.h + __algorithm/ranges_pop_heap.h + __algorithm/ranges_push_heap.h __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h __algorithm/ranges_sort.h + __algorithm/ranges_sort_heap.h __algorithm/ranges_swap_ranges.h __algorithm/ranges_transform.h __algorithm/ranges_upper_bound.h diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/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,36 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -_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); - } +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __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<_Compare>(__first, __comp, __n, __first + __start); } + } } template -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_CXX11 +void __make_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__make_heap<_Comp_ref>(std::move(__first), std::move(__last), __comp); +} + +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__make_heap_impl(std::move(__first), std::move(__last), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::make_heap(__first, __last, __less::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::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -24,44 +24,45 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -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_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; - 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); - } + 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); } + } +} + +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __pop_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__pop_heap<_Comp_ref>(std::move(__first), std::move(__last), __comp, __last - __first); } template -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) { + std::__pop_heap_impl(std::move(__first), std::move(__last), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::pop_heap(__first, __last, __less::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::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h --- a/libcxx/include/__algorithm/push_heap.h +++ b/libcxx/include/__algorithm/push_heap.h @@ -22,47 +22,48 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -_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 +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __push_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__sift_up<_Comp_ref>(std::move(__first), std::move(__last), __comp, __last - __first); } template -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_CXX17 +void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__push_heap_impl(std::move(__first), std::move(__last), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::push_heap(__first, __last, __less::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::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_make_heap.h b/libcxx/include/__algorithm/ranges_make_heap.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_make_heap.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// 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_projected.h> +#include <__algorithm/sort.h> +#include <__config> +#include <__concepts/same_as.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.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 + _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 = __make_projected_comp(__comp, __proj); + std::__make_heap_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template _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 + requires sortable, _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/libcxx/include/__algorithm/ranges_pop_heap.h b/libcxx/include/__algorithm/ranges_pop_heap.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_pop_heap.h @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__config> +#include <__concepts/same_as.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.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 + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __pop_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + _LIBCPP_ASSERT(__first != __last, "The heap given to pop_heap must be non-empty"); + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = __make_projected_comp(__comp, __proj); + std::__pop_heap_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template _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 + requires sortable, _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/libcxx/include/__algorithm/ranges_push_heap.h b/libcxx/include/__algorithm/ranges_push_heap.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_push_heap.h @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__config> +#include <__concepts/same_as.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.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 + _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 = __make_projected_comp(__comp, __proj); + std::__push_heap_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template _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 + requires sortable, _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/libcxx/include/__algorithm/ranges_sort_heap.h b/libcxx/include/__algorithm/ranges_sort_heap.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_sort_heap.h @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__config> +#include <__concepts/same_as.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.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 + _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 = __make_projected_comp(__comp, __proj); + std::__sort_heap_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template _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 + requires sortable, _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/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -15,6 +15,7 @@ #include <__config> #include <__iterator/iterator_traits.h> #include // swap +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -23,29 +24,31 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -_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); +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 + void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) + std::__pop_heap<_Compare>(__first, __last, __comp, __n); } template -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_CXX11 +void __sort_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__sort_heap<_Comp_ref>(std::move(__first), std::move(__last), __comp); +} + +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__sort_heap_impl(std::move(__first), std::move(__last), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::sort_heap(__first, __last, __less::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::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -273,6 +273,49 @@ indirect_unary_predicate, Proj>> Pred> constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20 + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr I + ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr borrowed_iterator_t + ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr I + ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr borrowed_iterator_t + ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr I + ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr borrowed_iterator_t + ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr I + ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr borrowed_iterator_t + ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 template S> requires permutable @@ -1188,6 +1231,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_min.h> @@ -1196,10 +1240,13 @@ #include <__algorithm/ranges_minmax_element.h> #include <__algorithm/ranges_mismatch.h> #include <__algorithm/ranges_none_of.h> +#include <__algorithm/ranges_pop_heap.h> +#include <__algorithm/ranges_push_heap.h> #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_sort.h> +#include <__algorithm/ranges_sort_heap.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> #include <__algorithm/ranges_upper_bound.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/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_min { private header "__algorithm/ranges_min.h" } @@ -339,10 +340,13 @@ module ranges_minmax_element { private header "__algorithm/ranges_minmax_element.h" } module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" } module ranges_none_of { private header "__algorithm/ranges_none_of.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_replace { private header "__algorithm/ranges_replace.h" } module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" } module ranges_reverse { private header "__algorithm/ranges_reverse.h" } module ranges_sort { private header "__algorithm/ranges_sort.h" } + module ranges_sort_heap { private header "__algorithm/ranges_sort_heap.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" } module ranges_transform { private header "__algorithm/ranges_transform.h" } module ranges_upper_bound { private header "__algorithm/ranges_upper_bound.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -144,8 +144,8 @@ (void)std::ranges::lexicographical_compare(a, b, Less(&copies)); assert(copies == 0); (void)std::ranges::lower_bound(first, last, value, Less(&copies)); assert(copies == 0); (void)std::ranges::lower_bound(a, value, Less(&copies)); assert(copies == 0); - //(void)std::ranges::make_heap(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::make_heap(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::make_heap(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::make_heap(a, Less(&copies)); assert(copies == 0); (void)std::ranges::max(value, value, Less(&copies)); assert(copies == 0); (void)std::ranges::max({ value, value }, Less(&copies)); assert(copies == 0); (void)std::ranges::max(a, Less(&copies)); assert(copies == 0); @@ -181,12 +181,12 @@ //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0); //(void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0); //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0); //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0); - //(void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0); //(void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0); @@ -209,8 +209,8 @@ //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0); (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0); - //(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0); //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); } //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); } //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -127,8 +127,8 @@ (void)std::ranges::lexicographical_compare(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::lower_bound(first, last, value, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::lower_bound(a, value, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::make_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::make_heap(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::make_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::make_heap(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::max(T(), T(), Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::max({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::max(a, Less(), Proj(&copies)); assert(copies == 0); @@ -164,12 +164,12 @@ //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0); @@ -200,8 +200,8 @@ //(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0); //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); } //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); } //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); } diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp @@ -0,0 +1,224 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// + +// template S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// constexpr I +// ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// constexpr borrowed_iterator_t +// ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +// SFINAE tests. + +using BadComparator = ComparatorNotCopyable; +static_assert(!std::sortable); + +template , class Comp = std::ranges::less> +concept HasMakeHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); }; + +static_assert(HasMakeHeapIt); +static_assert(!HasMakeHeapIt); +static_assert(!HasMakeHeapIt); +static_assert(!HasMakeHeapIt); +static_assert(!HasMakeHeapIt); +static_assert(!HasMakeHeapIt); +static_assert(!HasMakeHeapIt); // Doesn't satisfy `sortable`. + +template +concept HasMakeHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); }; + +static_assert(HasMakeHeapR>); +static_assert(!HasMakeHeapR); +static_assert(!HasMakeHeapR); +static_assert(!HasMakeHeapR>); +static_assert(!HasMakeHeapR>); +static_assert(!HasMakeHeapR, BadComparator>); +static_assert(!HasMakeHeapR>); // Doesn't satisfy `sortable`. + +template +constexpr void verify_heap(const std::array& heapified, Iter last, std::array expected) { + assert(heapified == expected); + assert(base(last) == heapified.data() + heapified.size()); + assert(std::is_heap(heapified.begin(), heapified.end())); +} + +template +constexpr void test_one(const std::array input, std::array expected) { + { // (iterator, sentinel) overload. + auto heapified = input; + auto b = Iter(heapified.data()); + auto e = Sent(Iter(heapified.data() + heapified.size())); + + std::same_as decltype(auto) last = std::ranges::make_heap(b, e); + verify_heap(heapified, last, expected); + } + + { // (range) overload. + auto heapified = input; + auto b = Iter(heapified.data()); + auto e = Sent(Iter(heapified.data() + heapified.size())); + auto range = std::ranges::subrange(b, e); + + std::same_as decltype(auto) last = std::ranges::make_heap(range); + verify_heap(heapified, last, expected); + } +} + +template +constexpr void test_iterators_2() { + // Empty sequence. + test_one({}, {}); + // 1-element sequence. + test_one({1}, {1}); + // 2-element sequence. + test_one({2, 1}, {2, 1}); + // 3-element sequence. + test_one({2, 1, 3}, {3, 1, 2}); + // Longer sequence. + test_one({2, 1, 3, 6, 8, 4, 11, 5}, {11, 8, 4, 6, 1, 2, 3, 5}); + // Longer sequence with duplicates. + test_one({2, 1, 3, 6, 2, 8, 6}, {8, 6, 6, 1, 2, 3, 2}); + // All elements are the same. + test_one({1, 1, 1}, {1, 1, 1}); + // Already heapified. + test_one({5, 4, 3, 1, 2}, {5, 4, 3, 1, 2}); + // Sorted. + test_one({1, 2, 3, 4, 5}, {5, 4, 3, 1, 2}); + // Reverse-sorted. + test_one({5, 4, 3, 2, 1}, {5, 4, 3, 2, 1}); +} + +template +constexpr void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +constexpr void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom comparator works. + const std::array input = {5, 4, 3, 2, 1}; + std::array expected = {1, 2, 3, 5, 4}; + { + auto in = input; + auto last = std::ranges::make_heap(in.begin(), in.end(), std::ranges::greater{}); + assert(in == expected); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::make_heap(in, std::ranges::greater{}); + assert(in == expected); + assert(last == in.end()); + } + } + + { // A custom projection works. + struct A { + int a; + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{2}, A{1}, A{3}}; + std::array expected = {A{3}, A{1}, A{2}}; + { + auto in = input; + auto last = std::ranges::make_heap(in.begin(), in.end(), {}, &A::a); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::make_heap(in, {}, &A::a); + verify_heap(in, last, expected); + } + } + + { // `std::invoke` is used in the implementation. + struct A { + int i; + constexpr A(int i_) : i(i_) {} + + constexpr bool comparator(const A& rhs) const { return i < rhs.i; } + constexpr const A& projection() const { return *this; } + + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{2}, A{1}, A{3}}; + std::array expected = {A{3}, A{1}, A{2}}; + { + auto in = input; + auto last = std::ranges::make_heap(in.begin(), in.end(), &A::comparator, &A::projection); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::make_heap(in, &A::comparator, &A::projection); + verify_heap(in, last, expected); + } + } + + { // The comparator can return any type that's convertible to `bool`. + const std::array input = {2, 1, 3}; + std::array expected = {3, 1, 2}; + { + auto in = input; + auto last = std::ranges::make_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; }); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::make_heap(in, [](int i, int j) { return BooleanTestable{i < j}; }); + verify_heap(in, last, expected); + } + } + + { // `std::ranges::dangling` is returned. + [[maybe_unused]] std::same_as decltype(auto) result = + std::ranges::make_heap(std::array{1, 2, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/ranges_pop_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/ranges_pop_heap.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/ranges_pop_heap.pass.cpp @@ -0,0 +1,223 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// + +// template S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// constexpr I +// ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// constexpr borrowed_iterator_t +// ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +// SFINAE tests. + +using BadComparator = ComparatorNotCopyable; +static_assert(!std::sortable); + +template , class Comp = std::ranges::less> +concept HasPopHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); }; + +static_assert(HasPopHeapIt); +static_assert(!HasPopHeapIt); +static_assert(!HasPopHeapIt); +static_assert(!HasPopHeapIt); +static_assert(!HasPopHeapIt); +static_assert(!HasPopHeapIt); +static_assert(!HasPopHeapIt); // Doesn't satisfy `sortable`. + +template +concept HasPopHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); }; + +static_assert(HasPopHeapR>); +static_assert(!HasPopHeapR); +static_assert(!HasPopHeapR); +static_assert(!HasPopHeapR>); +static_assert(!HasPopHeapR>); +static_assert(!HasPopHeapR, BadComparator>); +static_assert(!HasPopHeapR>); // Doesn't satisfy `sortable`. + +template +constexpr void verify_heap(const std::array& heapified, Iter last, std::array expected) { + assert(heapified == expected); + assert(base(last) == heapified.data() + heapified.size()); + assert(std::is_heap(heapified.begin(), heapified.end() - 1)); + assert(*std::max_element(heapified.begin(), heapified.end()) == heapified.back()); +} + +template +constexpr void test_one(const std::array input, std::array expected) { + assert(!input.empty()); + assert(std::is_heap(input.begin(), input.end())); + + { // (iterator, sentinel) overload. + auto heapified = input; + auto b = Iter(heapified.data()); + auto e = Sent(Iter(heapified.data() + heapified.size())); + + std::same_as decltype(auto) last = std::ranges::pop_heap(b, e); + verify_heap(heapified, last, expected); + } + + { // (range) overload. + auto heapified = input; + auto b = Iter(heapified.data()); + auto e = Sent(Iter(heapified.data() + heapified.size())); + auto range = std::ranges::subrange(b, e); + + std::same_as decltype(auto) last = std::ranges::pop_heap(range); + verify_heap(heapified, last, expected); + } +} + +template +constexpr void test_iterators_2() { + // 1-element sequence. + test_one({1}, {1}); + // 2-element sequence. + test_one({2, 1}, {1, 2}); + // 3-element sequence. + test_one({3, 1, 2}, {2, 1, 3}); + // Longer sequence. + test_one({11, 8, 5, 6, 4, 3, 2, 1}, {8, 6, 5, 1, 4, 3, 2, 11}); + // Longer sequence with duplicates. + test_one({8, 8, 6, 6, 1, 2, 2, 3}, {8, 6, 6, 3, 1, 2, 2, 8}); + // All elements are the same. + test_one({1, 1, 1, 1}, {1, 1, 1, 1}); +} + +template +constexpr void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +constexpr void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom comparator works. + const std::array input = {1, 2, 3, 5, 4}; + std::array expected = {2, 4, 3, 5, 1}; + auto comp = std::ranges::greater{}; + { + auto in = input; + auto last = std::ranges::pop_heap(in.begin(), in.end(), comp); + assert(in == expected); + assert(last == in.data() + in.size()); + assert(std::is_heap(in.begin(), in.end() - 1, comp)); + } + + { + auto in = input; + auto last = std::ranges::pop_heap(in, comp); + assert(in == expected); + assert(last == in.data() + in.size()); + assert(std::is_heap(in.begin(), in.end() - 1, comp)); + } + } + + { // A custom projection works. + struct A { + int a; + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{3}, A{1}, A{2}}; + std::array expected = {A{2}, A{1}, A{3}}; + { + auto in = input; + auto last = std::ranges::pop_heap(in.begin(), in.end(), {}, &A::a); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::pop_heap(in, {}, &A::a); + verify_heap(in, last, expected); + } + } + + { // `std::invoke` is used in the implementation. + struct A { + int i; + constexpr A(int i_) : i(i_) {} + + constexpr bool comparator(const A& rhs) const { return i < rhs.i; } + constexpr const A& projection() const { return *this; } + + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{3}, A{1}, A{2}}; + std::array expected = {A{2}, A{1}, A{3}}; + { + auto in = input; + auto last = std::ranges::pop_heap(in.begin(), in.end(), &A::comparator, &A::projection); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::pop_heap(in, &A::comparator, &A::projection); + verify_heap(in, last, expected); + } + } + + { // The comparator can return any type that's convertible to `bool`. + const std::array input = {3, 1, 2}; + std::array expected = {2, 1, 3}; + { + auto in = input; + auto last = std::ranges::pop_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; }); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::pop_heap(in, [](int i, int j) { return BooleanTestable{i < j}; }); + verify_heap(in, last, expected); + } + } + + { // `std::ranges::dangling` is returned. + [[maybe_unused]] std::same_as decltype(auto) result = + std::ranges::pop_heap(std::array{2, 1, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/ranges_push_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/ranges_push_heap.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/ranges_push_heap.pass.cpp @@ -0,0 +1,226 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// + +// template S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// constexpr I +// ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// constexpr borrowed_iterator_t +// ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +// SFINAE tests. + +using BadComparator = ComparatorNotCopyable; +static_assert(!std::sortable); + +template , class Comp = std::ranges::less> +concept HasPushHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); }; + +static_assert(HasPushHeapIt); +static_assert(!HasPushHeapIt); +static_assert(!HasPushHeapIt); +static_assert(!HasPushHeapIt); +static_assert(!HasPushHeapIt); +static_assert(!HasPushHeapIt); +static_assert(!HasPushHeapIt); // Doesn't satisfy `sortable`. + +template +concept HasPushHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); }; + +static_assert(HasPushHeapR>); +static_assert(!HasPushHeapR); +static_assert(!HasPushHeapR); +static_assert(!HasPushHeapR>); +static_assert(!HasPushHeapR>); +static_assert(!HasPushHeapR, BadComparator>); +static_assert(!HasPushHeapR>); // Doesn't satisfy `sortable`. + +template +constexpr void verify_heap(const std::array& heapified, Iter last, std::array expected) { + assert(heapified == expected); + assert(base(last) == heapified.data() + heapified.size()); + assert(std::is_heap(heapified.begin(), heapified.end())); +} + +template +constexpr void test_one(const std::array input, std::array expected) { + if (!input.empty()) { + assert(std::is_heap(input.begin(), input.end() - 1)); + } + + { // (iterator, sentinel) overload. + auto heapified = input; + auto b = Iter(heapified.data()); + auto e = Sent(Iter(heapified.data() + heapified.size())); + + std::same_as decltype(auto) last = std::ranges::push_heap(b, e); + verify_heap(heapified, last, expected); + } + + { // (range) overload. + auto heapified = input; + auto b = Iter(heapified.data()); + auto e = Sent(Iter(heapified.data() + heapified.size())); + auto range = std::ranges::subrange(b, e); + + std::same_as decltype(auto) last = std::ranges::push_heap(range); + verify_heap(heapified, last, expected); + } +} + +template +constexpr void test_iterators_2() { + // Empty sequence. + test_one({}, {}); + // 1-element sequence. + test_one({1}, {1}); + // 2-element sequence. + test_one({2, 1}, {2, 1}); + // 3-element sequence. + test_one({2, 1, 3}, {3, 1, 2}); + // Longer sequence. + test_one({11, 6, 5, 1, 4, 3, 2, 8}, {11, 8, 5, 6, 4, 3, 2, 1}); + // Longer sequence with duplicates. + test_one({8, 6, 3, 1, 2, 2, 6}, {8, 6, 6, 1, 2, 2, 3}); + // All elements are the same. + test_one({1, 1, 1, 1}, {1, 1, 1, 1}); + // Already heapified. + test_one({5, 4, 3, 1, 2}, {5, 4, 3, 1, 2}); + // Reverse-sorted. + test_one({5, 4, 3, 2, 1}, {5, 4, 3, 2, 1}); +} + +template +constexpr void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +constexpr void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom comparator works. + const std::array input = {5, 4, 3, 2, 1}; + std::array expected = {1, 5, 3, 2, 4}; + { + auto in = input; + auto last = std::ranges::push_heap(in.begin(), in.end(), std::ranges::greater{}); + assert(in == expected); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::push_heap(in, std::ranges::greater{}); + assert(in == expected); + assert(last == in.end()); + } + } + + { // A custom projection works. + struct A { + int a; + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{2}, A{1}, A{3}}; + std::array expected = {A{3}, A{1}, A{2}}; + { + auto in = input; + auto last = std::ranges::push_heap(in.begin(), in.end(), {}, &A::a); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::push_heap(in, {}, &A::a); + verify_heap(in, last, expected); + } + } + + { // `std::invoke` is used in the implementation. + struct A { + int i; + constexpr A(int i_) : i(i_) {} + + constexpr bool comparator(const A& rhs) const { return i < rhs.i; } + constexpr const A& projection() const { return *this; } + + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{2}, A{1}, A{3}}; + std::array expected = {A{3}, A{1}, A{2}}; + { + auto in = input; + auto last = std::ranges::push_heap(in.begin(), in.end(), &A::comparator, &A::projection); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::push_heap(in, &A::comparator, &A::projection); + verify_heap(in, last, expected); + } + } + + { // The comparator can return any type that's convertible to `bool`. + const std::array input = {2, 1, 3}; + std::array expected = {3, 1, 2}; + { + auto in = input; + auto last = std::ranges::push_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; }); + verify_heap(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::push_heap(in, [](int i, int j) { return BooleanTestable{i < j}; }); + verify_heap(in, last, expected); + } + } + + { // `std::ranges::dangling` is returned. + [[maybe_unused]] std::same_as decltype(auto) result = + std::ranges::push_heap(std::array{1, 2, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp @@ -0,0 +1,221 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// + +// template S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// constexpr I +// ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// constexpr borrowed_iterator_t +// ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +// SFINAE tests. + +using BadComparator = ComparatorNotCopyable; +static_assert(!std::sortable); + +template , class Comp = std::ranges::less> +concept HasSortHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); }; + +static_assert(HasSortHeapIt); +static_assert(!HasSortHeapIt); +static_assert(!HasSortHeapIt); +static_assert(!HasSortHeapIt); +static_assert(!HasSortHeapIt); +static_assert(!HasSortHeapIt); +static_assert(!HasSortHeapIt); // Doesn't satisfy `sortable`. + +template +concept HasSortHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); }; + +static_assert(HasSortHeapR>); +static_assert(!HasSortHeapR); +static_assert(!HasSortHeapR); +static_assert(!HasSortHeapR>); +static_assert(!HasSortHeapR>); +static_assert(!HasSortHeapR, BadComparator>); +static_assert(!HasSortHeapR>); // Doesn't satisfy `sortable`. + +template +constexpr void verify_sorted(const std::array& sorted, Iter last, std::array expected) { + assert(sorted == expected); + assert(base(last) == sorted.data() + sorted.size()); + assert(std::is_sorted(sorted.begin(), sorted.end())); +} + +template +constexpr void test_one(const std::array input, std::array expected) { + assert(std::is_heap(input.begin(), input.end())); + + { // (iterator, sentinel) overload. + auto sorted = input; + auto b = Iter(sorted.data()); + auto e = Sent(Iter(sorted.data() + sorted.size())); + + std::same_as decltype(auto) last = std::ranges::sort_heap(b, e); + verify_sorted(sorted, last, expected); + } + + { // (range) overload. + auto sorted = input; + auto b = Iter(sorted.data()); + auto e = Sent(Iter(sorted.data() + sorted.size())); + auto range = std::ranges::subrange(b, e); + + std::same_as decltype(auto) last = std::ranges::sort_heap(range); + verify_sorted(sorted, last, expected); + } +} + +template +constexpr void test_iterators_2() { + // 1-element sequence. + test_one({1}, {1}); + // 2-element sequence. + test_one({2, 1}, {1, 2}); + // 3-element sequence. + test_one({3, 1, 2}, {1, 2, 3}); + // Longer sequence. + test_one({11, 8, 4, 6, 1, 2, 3, 5}, {1, 2, 3, 4, 5, 6, 8, 11}); + // Longer sequence with duplicates. + test_one({8, 6, 6, 1, 2, 3, 2}, {1, 2, 2, 3, 6, 6, 8}); + // All elements are the same. + test_one({1, 1, 1, 1}, {1, 1, 1, 1}); +} + +template +constexpr void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +constexpr void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom comparator works. + const std::array input = {1, 2, 3, 5, 4}; + std::array expected = {5, 4, 3, 2, 1}; + auto comp = std::ranges::greater{}; + assert(std::is_heap(input.begin(), input.end(), comp)); + + { + auto in = input; + auto last = std::ranges::sort_heap(in.begin(), in.end(), comp); + assert(in == expected); + assert(last == in.data() + in.size()); + } + + { + auto in = input; + auto last = std::ranges::sort_heap(in, comp); + assert(in == expected); + assert(last == in.data() + in.size()); + } + } + + { // A custom projection works. + struct A { + int a; + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{3}, A{1}, A{2}}; + std::array expected = {A{1}, A{2}, A{3}}; + { + auto in = input; + auto last = std::ranges::sort_heap(in.begin(), in.end(), {}, &A::a); + verify_sorted(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::sort_heap(in, {}, &A::a); + verify_sorted(in, last, expected); + } + } + + { // `std::invoke` is used in the implementation. + struct A { + int i; + constexpr A(int i_) : i(i_) {} + + constexpr bool comparator(const A& rhs) const { return i < rhs.i; } + constexpr const A& projection() const { return *this; } + + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array input = {A{3}, A{1}, A{2}}; + std::array expected = {A{1}, A{2}, A{3}}; + { + auto in = input; + auto last = std::ranges::sort_heap(in.begin(), in.end(), &A::comparator, &A::projection); + verify_sorted(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::sort_heap(in, &A::comparator, &A::projection); + verify_sorted(in, last, expected); + } + } + + { // The comparator can return any type that's convertible to `bool`. + const std::array input = {3, 1, 2}; + std::array expected = {1, 2, 3}; + { + auto in = input; + auto last = std::ranges::sort_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; }); + verify_sorted(in, last, expected); + } + + { + auto in = input; + auto last = std::ranges::sort_heap(in, [](int i, int j) { return BooleanTestable{i < j}; }); + verify_sorted(in, last, expected); + } + } + + { // `std::ranges::dangling` is returned. + [[maybe_unused]] std::same_as decltype(auto) result = + std::ranges::sort_heap(std::array{2, 1, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -95,7 +95,7 @@ static_assert(test(std::ranges::is_sorted_until, a)); static_assert(test(std::ranges::lexicographical_compare, a, a)); static_assert(test(std::ranges::lower_bound, a, 42)); -//static_assert(test(std::ranges::make_heap, a)); +static_assert(test(std::ranges::make_heap, a)); static_assert(test(std::ranges::max, a)); static_assert(test(std::ranges::max_element, a)); //static_assert(test(std::ranges::merge, a, a, a)); @@ -114,9 +114,9 @@ //static_assert(test(std::ranges::partition, a, odd)); //static_assert(test(std::ranges::partition_copy, a, a, a, odd)); //static_assert(test(std::ranges::partition_point, a, odd)); -//static_assert(test(std::ranges::pop_heap, a)); +static_assert(test(std::ranges::pop_heap, a)); //static_assert(test(std::ranges::prev_permutation, a)); -//static_assert(test(std::ranges::push_heap, a)); +static_assert(test(std::ranges::push_heap, a)); //static_assert(test(std::ranges::remove, a, 42)); //static_assert(test(std::ranges::remove_copy, a, a, 42)); //static_assert(test(std::ranges::remove_copy_if, a, a, odd)); @@ -138,7 +138,7 @@ //static_assert(test(std::ranges::set_union, a, a, a)); //static_assert(test(std::ranges::shuffle, a, g)); static_assert(test(std::ranges::sort, a)); -//static_assert(test(std::ranges::sort_heap, a)); +static_assert(test(std::ranges::sort_heap, a)); //static_assert(test(std::ranges::stable_partition, a, odd)); //static_assert(test(std::ranges::stable_sort, a)); //static_assert(test(std::ranges::starts_with, a, a));