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 @@ -76,7 +76,7 @@ Permutation,sort,Konstantin Varlamov,`D127557 `_,✅ Permutation,stable_sort,Konstantin Varlamov,`D127834 `_,✅ Permutation,partial_sort,Konstantin Varlamov,n/a,In progress -Permutation,nth_element,Not assigned,n/a,Not started +Permutation,nth_element,Konstantin Varlamov,`D128149 `_,✅ 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 diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -102,6 +102,7 @@ __algorithm/ranges_move.h __algorithm/ranges_move_backward.h __algorithm/ranges_none_of.h + __algorithm/ranges_nth_element.h __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h --- a/libcxx/include/__algorithm/nth_element.h +++ b/libcxx/include/__algorithm/nth_element.h @@ -15,6 +15,7 @@ #include <__config> #include <__debug> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <__utility/swap.h> #if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) @@ -223,25 +224,35 @@ } template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) -{ +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare& __comp) { + if (__nth == __last) + return; + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth); if (__nth != __last) { _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last); } } +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare __comp) { + std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp); +} + template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) -{ - _VSTD::nth_element(__first, __nth, __last, __less::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { + std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_nth_element.h b/libcxx/include/__algorithm/ranges_nth_element.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_nth_element.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_NTH_ELEMENT_H +#define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/nth_element.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 __nth_element { + +struct __fn { + template + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__nth_element_impl(std::move(__first), std::move(__nth), __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, _Iter __nth, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __nth_element_fn_impl(std::move(__first), std::move(__nth), std::move(__last), __comp, __proj); + } + + template + requires sortable, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, iterator_t<_Range> __nth, _Comp __comp = {}, + _Proj __proj = {}) const { + return __nth_element_fn_impl(ranges::begin(__r), std::move(__nth), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __nth_element + +inline namespace __cpo { + inline constexpr auto nth_element = __nth_element::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -379,6 +379,17 @@ constexpr borrowed_iterator_t ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr I + ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr borrowed_iterator_t + ranges::nth_element(R&& r, iterator_t nth, Comp comp = {}, Proj proj = {}); // since C++20 + template S, class T, class Proj = identity, indirect_strict_weak_order> Comp = ranges::less> constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 @@ -1257,6 +1268,7 @@ #include <__algorithm/ranges_move.h> #include <__algorithm/ranges_move_backward.h> #include <__algorithm/ranges_none_of.h> +#include <__algorithm/ranges_nth_element.h> #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.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 @@ -341,6 +341,7 @@ module ranges_move { private header "__algorithm/ranges_move.h" } 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_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" } 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 @@ -169,8 +169,8 @@ //(void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0); (void)std::ranges::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::none_of(a, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0); + (void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0); //(void)std::ranges::partial_sort(first, mid, last, Less(&copies)); assert(copies == 0); //(void)std::ranges::partial_sort(a, mid, Less(&copies)); assert(copies == 0); //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, 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 @@ -152,8 +152,8 @@ //(void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::none_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::none_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::partial_sort(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::partial_sort(a, mid, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -139,6 +139,7 @@ #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}} #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}} #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}} +#include <__algorithm/ranges_nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_nth_element.h'}} #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}} #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}} #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp @@ -0,0 +1,293 @@ +//===----------------------------------------------------------------------===// +// +// 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::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// constexpr borrowed_iterator_t +// ranges::nth_element(R&& r, iterator_t nth, Comp comp = {}, Proj proj = {}); // since C++20 + +#include +#include +#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 HasNthElementIt = requires(Iter first, Iter nth, Sent last, Comp comp) { + std::ranges::nth_element(first, nth, last, comp); +}; + +static_assert(HasNthElementIt); +static_assert(!HasNthElementIt); +static_assert(!HasNthElementIt); +static_assert(!HasNthElementIt); +static_assert(!HasNthElementIt); +static_assert(!HasNthElementIt); +static_assert(!HasNthElementIt); // Doesn't satisfy `sortable`. + +template +concept HasNthElementR = requires(Range range, std::ranges::iterator_t nth, Comp comp) { + std::ranges::nth_element(range, nth, comp); +}; + +static_assert(HasNthElementR>); +static_assert(!HasNthElementR); +static_assert(!HasNthElementR); +static_assert(!HasNthElementR>); +static_assert(!HasNthElementR>); +static_assert(!HasNthElementR, BadComparator>); +static_assert(!HasNthElementR>); // Doesn't satisfy `sortable`. + +template +constexpr void verify_nth(const std::array& partially_sorted, size_t nth_index, Iter last, T expected_nth) { + // Note that the exact output of `nth_element` is unspecified and may vary between implementations. + + assert(base(last) == partially_sorted.end()); + + auto b = partially_sorted.begin(); + auto nth = b + nth_index; + auto e = partially_sorted.end(); + if (nth == e) + return; + + assert(*nth == expected_nth); + + // All elements on the left are <= nth. + assert(std::all_of(b, nth, [&](const auto& v) { return v <= *nth; })); + // All elements on the right are >= nth. + assert(std::all_of(nth, e, [&](const auto& v) { return v >= *nth; })); + + { + auto sorted = partially_sorted; + std::ranges::sort(sorted); + + // The element at index `n` is the same as if the range were fully sorted. + assert(sorted[nth_index] == *nth); + } +} + +template +constexpr void test_one(std::array input, size_t nth_index, std::optional expected_nth = {}) { + assert(expected_nth || nth_index == N); + + { // (iterator, sentinel) overload. + auto partially_sorted = input; + auto b = Iter(partially_sorted.data()); + auto nth = b + nth_index; + auto e = Sent(Iter(partially_sorted.data() + partially_sorted.size())); + + std::same_as decltype(auto) last = std::ranges::nth_element(b, nth, e); + if (nth_index != N) { + verify_nth(partially_sorted, nth_index, last, *expected_nth); + } else { + assert(partially_sorted == input); + } + } + + { // (range) overload. + auto partially_sorted = input; + auto b = Iter(partially_sorted.data()); + auto nth = b + nth_index; + auto e = Sent(Iter(partially_sorted.data() + partially_sorted.size())); + auto range = std::ranges::subrange(b, e); + + std::same_as decltype(auto) last = std::ranges::nth_element(range, nth); + if (nth_index != N) { + verify_nth(partially_sorted, nth_index, last, *expected_nth); + } else { + assert(partially_sorted == input); + } + } +} + +template +constexpr void test_all_cases(std::array input) { + auto sorted = input; + std::sort(sorted.begin(), sorted.end()); + + for (int n = 0; n != N; ++n) { + test_one(input, n, sorted[n]); + } + test_one(input, N); +} + +constexpr void test_iterators() { + auto check = [] { + // Empty sequence. + test_one({}, 0); + + // 1-element sequence. + test_all_cases(std::array{1}); + + // 2-element sequence. + test_all_cases(std::array{2, 1}); + + // 3-element sequence. + test_all_cases(std::array{2, 1, 3}); + + // Longer sequence. + test_all_cases(std::array{2, 1, 3, 6, 8, 4, 11, 5}); + + // Longer sequence with duplicates. + test_all_cases(std::array{2, 1, 3, 6, 2, 8, 6}); + + // All elements are the same. + test_all_cases(std::array{1, 1, 1, 1}); + + { // nth element is in the right place. + std::array input = {6, 5, 3, 1, 4, 2}; + constexpr size_t N = input.size(); + test_one(input, 2, /*expected_nth=*/3); + } + + // Already sorted. + test_all_cases(std::array{1, 2, 3, 4, 5, 6}); + + // Descending. + test_all_cases(std::array{6, 5, 4, 3, 2, 1}); + + // Repeating pattern. + test_all_cases(std::array{2, 1, 2, 1, 2, 1}); + }; + + check.operator(), random_access_iterator>(); + check.operator(), sentinel_wrapper>>(); + check.operator(), contiguous_iterator>(); + check.operator(), sentinel_wrapper>>(); + check.operator()(); + check.operator()>(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom comparator works. + const std::array input = {1, 2, 3, 4, 5}; + std::ranges::greater comp; + + { + auto in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), comp); + assert(in[1] == 4); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, comp); + assert(in[1] == 4); + assert(last == in.end()); + } + } + + { // A custom projection works. + struct A { + int a; + constexpr bool operator==(const A&) const = default; + }; + + const std::array input = {A{2}, A{1}, A{3}}; + + { + auto in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), {}, &A::a); + assert(in[1] == A{2}); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, {}, &A::a); + assert(in[1] == A{2}); + assert(last == in.end()); + } + } + + { // `std::invoke` is used in the implementation. + struct S { + int i; + constexpr S(int i_) : i(i_) {} + + constexpr bool comparator(const S& rhs) const { return i < rhs.i; } + constexpr const S& projection() const { return *this; } + + constexpr bool operator==(const S&) const = default; + }; + + const std::array input = {S{2}, S{1}, S{3}}; + + { + auto in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), &S::comparator, &S::projection); + assert(in[1] == S{2}); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, &S::comparator, &S::projection); + assert(in[1] == S{2}); + assert(last == in.end()); + } + } + + { // The comparator can return any type that's convertible to `bool`. + const std::array input = {2, 1, 3}; + auto pred = [](int i, int j) { return BooleanTestable{i < j}; }; + + { + std::array in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), pred); + assert(in[1] == 2); + assert(last == in.end()); + } + + { + std::array in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, pred); + assert(in[1] == 2); + assert(last == in.end()); + } + } + + { // `std::ranges::dangling` is returned. + [[maybe_unused]] std::same_as decltype(auto) result = + std::ranges::nth_element(std::array{1, 2, 3}, 0); + } + + 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 @@ -108,7 +108,7 @@ static_assert(test(std::ranges::move_backward, a, a)); //static_assert(test(std::ranges::next_permutation, a)); static_assert(test(std::ranges::none_of, a, odd)); -//static_assert(test(std::ranges::nth_element, a, a+5)); +static_assert(test(std::ranges::nth_element, a, a+5)); //static_assert(test(std::ranges::partial_sort, a, a+5)); //static_assert(test(std::ranges::partial_sort_copy, a, a)); //static_assert(test(std::ranges::partition, a, odd));