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,n/a,In progress Permutation,partial_sort,Konstantin Varlamov,n/a,In progress -Permutation,nth_element,Not assigned,n/a,Not started +Permutation,nth_element,Konstantin Varlamov,`TODO `_,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 diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -100,6 +100,7 @@ __algorithm/ranges_minmax_element.h __algorithm/ranges_mismatch.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) @@ -28,220 +29,228 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -_LIBCPP_CONSTEXPR_AFTER_CXX11 bool -__nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j, - _RandomAccessIterator __m, _Compare __comp) -{ - // manually guard downward moving __j against __i - while (true) { - if (__i == --__j) { - return false; - } - if (__comp(*__j, *__m)) { - return true; // found guard for downward moving __j, now use unguarded partition - } +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +bool __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j, + _RandomAccessIterator __m, _Compare __comp) { + // manually guard downward moving __j against __i + while (true) { + if (__i == --__j) { + return false; } + if (__comp(*__j, *__m)) { + return true; // found guard for downward moving __j, now use unguarded partition + } + } } template -_LIBCPP_CONSTEXPR_AFTER_CXX11 void -__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) -{ - // _Compare is known to be a reference type - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - const difference_type __limit = 7; - while (true) +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare __comp) { + // _Compare is known to be a reference type + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + const difference_type __limit = 7; + + while (true) { + if (__nth == __last) + return; + + difference_type __len = __last - __first; + switch (__len) { - if (__nth == __last) - return; - difference_type __len = __last - __first; - switch (__len) + case 0: + case 1: + return; + case 2: + if (__comp(*--__last, *__first)) + swap(*__first, *__last); + return; + case 3: { - case 0: - case 1: - return; - case 2: - if (__comp(*--__last, *__first)) - swap(*__first, *__last); - return; - case 3: - { - _RandomAccessIterator __m = __first; - _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); - return; - } - } - if (__len <= __limit) - { - _VSTD::__selection_sort<_Compare>(__first, __last, __comp); - return; + _RandomAccessIterator __m = __first; + std::__sort3<_Compare>(__first, ++__m, --__last, __comp); + return; } - // __len > __limit >= 3 - _RandomAccessIterator __m = __first + __len/2; - _RandomAccessIterator __lm1 = __last; - unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); - // *__m is median - // partition [__first, __m) < *__m and *__m <= [__m, __last) - // (this inhibits tossing elements equivalent to __m around unnecessarily) - _RandomAccessIterator __i = __first; - _RandomAccessIterator __j = __lm1; - // j points beyond range to be tested, *__lm1 is known to be <= *__m - // The search going up is known to be guarded but the search coming down isn't. - // Prime the downward search with a guard. - if (!__comp(*__i, *__m)) // if *__first == *__m - { - // *__first == *__m, *__first doesn't go in first part - if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { - swap(*__i, *__j); - ++__n_swaps; - } else { - // *__first == *__m, *__m <= all other elements - // Partition instead into [__first, __i) == *__first and *__first < [__i, __last) - ++__i; // __first + 1 - __j = __last; - if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1) - while (true) { - if (__i == __j) { - return; // [__first, __last) all equivalent elements - } else if (__comp(*__first, *__i)) { - swap(*__i, *__j); - ++__n_swaps; - ++__i; - break; - } - ++__i; - } - } - // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 - if (__i == __j) { - return; - } - while (true) { - while (!__comp(*__first, *__i)) - ++__i; - while (__comp(*__first, *--__j)) - ; - if (__i >= __j) - break; - swap(*__i, *__j); - ++__n_swaps; - ++__i; - } - // [__first, __i) == *__first and *__first < [__i, __last) - // The first part is sorted, - if (__nth < __i) { - return; - } - // __nth_element the second part - // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp); - __first = __i; - continue; + } + + if (__len <= __limit) { + std::__selection_sort<_Compare>(__first, __last, __comp); + return; + } + + // __len > __limit >= 3 + _RandomAccessIterator __m = __first + __len/2; + _RandomAccessIterator __lm1 = __last; + unsigned __n_swaps = std::__sort3<_Compare>(__first, __m, --__lm1, __comp); + // *__m is median + // partition [__first, __m) < *__m and *__m <= [__m, __last) + // (this inhibits tossing elements equivalent to __m around unnecessarily) + _RandomAccessIterator __i = __first; + _RandomAccessIterator __j = __lm1; + // j points beyond range to be tested, *__lm1 is known to be <= *__m + // The search going up is known to be guarded but the search coming down isn't. + // Prime the downward search with a guard. + if (!__comp(*__i, *__m)) // if *__first == *__m + { + // *__first == *__m, *__first doesn't go in first part + if (std::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { + swap(*__i, *__j); + ++__n_swaps; + } else { + // *__first == *__m, *__m <= all other elements + // Partition instead into [__first, __i) == *__first and *__first < [__i, __last) + ++__i; // __first + 1 + __j = __last; + if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1) + while (true) { + if (__i == __j) { + return; // [__first, __last) all equivalent elements + } else if (__comp(*__first, *__i)) { + swap(*__i, *__j); + ++__n_swaps; + ++__i; + break; } + ++__i; + } } - ++__i; - // j points beyond range to be tested, *__lm1 is known to be <= *__m - // if not yet partitioned... - if (__i < __j) - { - // known that *(__i - 1) < *__m - while (true) - { - // __m still guards upward moving __i - while (__comp(*__i, *__m)) - ++__i; - // It is now known that a guard exists for downward moving __j - while (!__comp(*--__j, *__m)) - ; - if (__i >= __j) - break; - swap(*__i, *__j); - ++__n_swaps; - // It is known that __m != __j - // If __m just moved, follow it - if (__m == __i) - __m = __j; - ++__i; - } + + // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 + if (__i == __j) { + return; } - // [__first, __i) < *__m and *__m <= [__i, __last) - if (__i != __m && __comp(*__m, *__i)) - { - swap(*__i, *__m); - ++__n_swaps; + while (true) { + while (!__comp(*__first, *__i)) + ++__i; + while (__comp(*__first, *--__j)) + ; + if (__i >= __j) + break; + swap(*__i, *__j); + ++__n_swaps; + ++__i; } - // [__first, __i) < *__i and *__i <= [__i+1, __last) - if (__nth == __i) - return; - if (__n_swaps == 0) - { - // We were given a perfectly partitioned sequence. Coincidence? - if (__nth < __i) - { - // Check for [__first, __i) already sorted - __j = __m = __first; - while (true) { - if (++__j == __i) { - // [__first, __i) sorted - return; - } - if (__comp(*__j, *__m)) { - // not yet sorted, so sort - break; - } - __m = __j; - } - } - else - { - // Check for [__i, __last) already sorted - __j = __m = __i; - while (true) { - if (++__j == __last) { - // [__i, __last) sorted - return; - } - if (__comp(*__j, *__m)) { - // not yet sorted, so sort - break; - } - __m = __j; - } - } + + // [__first, __i) == *__first and *__first < [__i, __last) + // The first part is sorted, + if (__nth < __i) { + return; } - // __nth_element on range containing __nth - if (__nth < __i) - { - // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp); - __last = __i; + + // __nth_element the second part + // std::__nth_element<_Compare>(__i, __nth, __last, __comp); + __first = __i; + continue; + } + } + + ++__i; + // j points beyond range to be tested, *__lm1 is known to be <= *__m + // if not yet partitioned... + if (__i < __j) { + // known that *(__i - 1) < *__m + while (true) { + // __m still guards upward moving __i + while (__comp(*__i, *__m)) + ++__i; + + // It is now known that a guard exists for downward moving __j + while (!__comp(*--__j, *__m)) + ; + if (__i >= __j) + break; + swap(*__i, *__j); + ++__n_swaps; + + // It is known that __m != __j + // If __m just moved, follow it + if (__m == __i) + __m = __j; + ++__i; + } + } + + // [__first, __i) < *__m and *__m <= [__i, __last) + if (__i != __m && __comp(*__m, *__i)) { + swap(*__i, *__m); + ++__n_swaps; + } + + // [__first, __i) < *__i and *__i <= [__i+1, __last) + if (__nth == __i) + return; + if (__n_swaps == 0) { + // We were given a perfectly partitioned sequence. Coincidence? + if (__nth < __i) { + // Check for [__first, __i) already sorted + __j = __m = __first; + while (true) { + if (++__j == __i) { + // [__first, __i) sorted + return; + } + if (__comp(*__j, *__m)) { + // not yet sorted, so sort + break; + } + __m = __j; } - else - { - // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp); - __first = ++__i; + + } else { + // Check for [__i, __last) already sorted + __j = __m = __i; + while (true) { + if (++__j == __last) { + // [__i, __last) sorted + return; + } + if (__comp(*__j, *__m)) { + // not yet sorted, so sort + break; + } + __m = __j; } + } + } + + // __nth_element on range containing __nth + if (__nth < __i) { + // std::__nth_element<_Compare>(__first, __nth, __i, __comp); + __last = __i; + } else { + // std::__nth_element<_Compare>(__i+1, __nth, __last, __comp); + __first = ++__i; } + } } 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) { _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 = __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 @@ -356,6 +356,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 @@ -1196,6 +1207,7 @@ #include <__algorithm/ranges_minmax_element.h> #include <__algorithm/ranges_mismatch.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 @@ -339,6 +339,7 @@ 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_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 @@ -137,6 +137,7 @@ #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}} #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.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,329 @@ +//===----------------------------------------------------------------------===// +// +// 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 "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, + [[maybe_unused]] std::array expected) { + // Different implementations produce differing output that still satisfies the algorithm requirements, so we can only + // check for specific output in the libc++ implementation. + LIBCPP_ASSERT(partially_sorted == expected); + 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; + + // 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::array expected) { + { // (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); + verify_nth(partially_sorted, nth_index, last, expected); + } + + { // (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); + verify_nth(partially_sorted, nth_index, last, expected); + } +} + +template +constexpr void test_all_cases(std::array input, std::array, N> expected_array) { + for (int n = 0; n != N; ++n) { + test_one(input, n, expected_array[n]); + } + test_one(input, N, input); +} + +template +constexpr void test_all_cases(std::array input, std::array expected) { + for (int n = 0; n != N; ++n) { + test_one(input, n, expected); + } + test_one(input, N, input); +} + +template +constexpr void test_iterators_2() { + { // Empty sequence. + test_one({}, 0, {}); + } + + { // 1-element sequence. + test_one({1}, 0, {1}); + test_one({1}, 1, {1}); + } + + { // 3-element sequence. + std::array input = {2, 1}; + std::array expected = {1, 2}; + test_all_cases(input, expected); + } + + { // 3-element sequence. + std::array input = {2, 1, 3}; + std::array expected = {1, 2, 3}; + test_all_cases(input, expected); + } + + { // Longer sequence. + std::array input = {2, 1, 3, 6, 8, 4, 11, 5}; + std::array expected1 = {1, 2, 3, 4, 5, 6, 11, 8}; + std::array expected2 = {2, 1, 3, 4, 5, 6, 11, 8}; + std::array expected3 = {2, 1, 3, 4, 5, 6, 8, 11}; + + std::array expected_array = { + expected1, expected1, expected1, expected1, expected2, expected3, expected3, expected3 + }; + + test_all_cases(input, expected_array); + } + + { // Longer sequence with duplicates. + std::array input = {2, 1, 3, 6, 2, 8, 6}; + std::array expected = {1, 2, 2, 3, 6, 6, 8}; + test_all_cases(input, expected); + } + + { // All elements are the same. + std::array input = {1, 1, 1, 1}; + test_all_cases(input, input); + } + + { // nth element is in the right place. + std::array input = {6, 5, 3, 1, 4, 2}; + std::array expected = {1, 2, 3, 4, 5, 6}; + constexpr size_t N = input.size(); + + test_one(input, 2, expected); + } + + { // Already sorted. + std::array input = {1, 2, 3, 4, 5, 6}; + test_all_cases(input, input); + } + + { // Reverse sorted. + std::array input = {6, 5, 4, 3, 2, 1}; + std::array expected = {1, 2, 3, 4, 5, 6}; + test_all_cases(input, expected); + } + + { // Repeating pattern. + std::array input = {2, 1, 2, 1, 2, 1}; + std::array expected = {1, 1, 1, 2, 2, 2}; + test_all_cases(input, expected); + } +} + +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, 4, 5}; + std::array expected = {5, 4, 3, 2, 1}; + std::ranges::greater comp; + + { + auto in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), comp); + assert(in == expected); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, comp); + assert(in == expected); + 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}}; + std::array expected = {A{1}, A{2}, A{3}}; + + { + auto in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), {}, &A::a); + assert(in == expected); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, {}, &A::a); + assert(in == expected); + 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}}; + std::array expected = {S{1}, S{2}, S{3}}; + + { + auto in = input; + auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), &S::comparator, &S::projection); + assert(in == expected); + assert(last == in.end()); + } + + { + auto in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, &S::comparator, &S::projection); + assert(in == expected); + assert(last == in.end()); + } + } + + { // The comparator can return any type that's convertible to `bool`. + const std::array input = {2, 1, 3}; + std::array expected = {1, 2, 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 == expected); + assert(last == in.end()); + } + + { + std::array in = input; + auto last = std::ranges::nth_element(in, in.begin() + 1, pred); + assert(in == expected); + 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));