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 @@ -56,7 +56,7 @@ Write,swap_ranges,Nikolas Klauser,`D116303 `_,✅ Write,reverse_copy,Nikolas Klauser,`D127211 `_,✅ Write,rotate_copy,Nikolas Klauser,`D127211 `_,✅ -Write,sample,Not assigned,n/a,Not started +Write,sample,Konstantin Varlamov,`D130865 `_,✅ Write,unique_copy,Hui Xie,`D130404 `_,✅ Write,partition_copy,Konstantin Varlamov,`D130070 `_,✅ Write,partial_sort_copy,Konstantin Varlamov,`D130532 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -133,6 +133,7 @@ __algorithm/ranges_reverse.h __algorithm/ranges_reverse_copy.h __algorithm/ranges_rotate_copy.h + __algorithm/ranges_sample.h __algorithm/ranges_search.h __algorithm/ranges_search_n.h __algorithm/ranges_set_difference.h @@ -178,6 +179,7 @@ __algorithm/stable_sort.h __algorithm/swap_ranges.h __algorithm/transform.h + __algorithm/uniform_random_bit_generator_adaptor.h __algorithm/unique.h __algorithm/unique_copy.h __algorithm/unwrap_iter.h diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -10,9 +10,11 @@ #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H #include <__algorithm/iter_swap.h> +#include <__algorithm/ranges_iterator_concept.h> #include <__config> #include <__iterator/advance.h> #include <__iterator/distance.h> +#include <__iterator/incrementable_traits.h> #include <__iterator/iter_move.h> #include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> @@ -40,6 +42,12 @@ template using __value_type = iter_value_t<_Iter>; + template + using __iterator_category = ranges::__iterator_concept<_Iter>; + + template + using __difference_type = iter_difference_t<_Iter>; + static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; static constexpr auto __iter_move = ranges::iter_move; @@ -58,6 +66,12 @@ template using __value_type = typename iterator_traits<_Iter>::value_type; + template + using __iterator_category = typename iterator_traits<_Iter>::iterator_category; + + template + using __difference_type = typename iterator_traits<_Iter>::difference_type; + // advance template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 diff --git a/libcxx/include/__algorithm/ranges_sample.h b/libcxx/include/__algorithm/ranges_sample.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_sample.h @@ -0,0 +1,74 @@ +//===----------------------------------------------------------------------===// +// +// 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_SAMPLE_H +#define _LIBCPP___ALGORITHM_RANGES_SAMPLE_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/sample.h> +#include <__algorithm/uniform_random_bit_generator_adaptor.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iterator_traits.h> +#include <__random/uniform_random_bit_generator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/forward.h> +#include <__utility/move.h> +#include + +#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 __sample { + +struct __fn { + + template _Sent, weakly_incrementable _OutIter, class _Gen> + requires (forward_iterator<_Iter> || random_access_iterator<_OutIter>) && + indirectly_copyable<_Iter, _OutIter> && + uniform_random_bit_generator> + _LIBCPP_HIDE_FROM_ABI + _OutIter operator()(_Iter __first, _Sent __last, + _OutIter __out_first, iter_difference_t<_Iter> __n, _Gen&& __gen) const { + _ClassicGenAdaptor<_Gen> __adapted_gen(__gen); + return std::__sample<_RangeAlgPolicy>( + std::move(__first), std::move(__last), std::move(__out_first), __n, __adapted_gen); + } + + template + requires (forward_range<_Range> || random_access_iterator<_OutIter>) && + indirectly_copyable, _OutIter> && + uniform_random_bit_generator> + _LIBCPP_HIDE_FROM_ABI + _OutIter operator()(_Range&& __range, _OutIter __out_first, range_difference_t<_Range> __n, _Gen&& __gen) const { + return (*this)(ranges::begin(__range), ranges::end(__range), + std::move(__out_first), __n, std::forward<_Gen>(__gen)); + } + +}; + +} // namespace __sample + +inline namespace __cpo { + inline constexpr auto sample = __sample::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SAMPLE_H diff --git a/libcxx/include/__algorithm/ranges_shuffle.h b/libcxx/include/__algorithm/ranges_shuffle.h --- a/libcxx/include/__algorithm/ranges_shuffle.h +++ b/libcxx/include/__algorithm/ranges_shuffle.h @@ -11,6 +11,7 @@ #include <__algorithm/iterator_operations.h> #include <__algorithm/shuffle.h> +#include <__algorithm/uniform_random_bit_generator_adaptor.h> #include <__config> #include <__functional/invoke.h> #include <__functional/ranges_operations.h> @@ -32,43 +33,12 @@ #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD namespace ranges { namespace __shuffle { struct __fn { - // `std::shuffle` is more constrained than `std::ranges::shuffle`. `std::ranges::shuffle` only requires the given - // generator to satisfy the `std::uniform_random_bit_generator` concept. `std::shuffle` requires the given - // generator to meet the uniform random bit generator requirements; these requirements include satisfying - // `std::uniform_random_bit_generator` and add a requirement for the generator to provide a nested `result_type` - // typedef (see `[rand.req.urng]`). - // - // To reuse the implementation from `std::shuffle`, make the given generator meet the classic requirements by wrapping - // it into an adaptor type that forwards all of its interface and adds the required typedef. - template - class _ClassicGenAdaptor { - private: - // The generator is not required to be copyable or movable, so it has to be stored as a reference. - _Gen& __gen; - - public: - using result_type = invoke_result_t<_Gen&>; - - _LIBCPP_HIDE_FROM_ABI - static constexpr auto min() { return __uncvref_t<_Gen>::min(); } - _LIBCPP_HIDE_FROM_ABI - static constexpr auto max() { return __uncvref_t<_Gen>::max(); } - - _LIBCPP_HIDE_FROM_ABI - constexpr explicit _ClassicGenAdaptor(_Gen& __g) : __gen(__g) {} - - _LIBCPP_HIDE_FROM_ABI - constexpr auto operator()() const { return __gen(); } - }; template _Sent, class _Gen> requires permutable<_Iter> && uniform_random_bit_generator> @@ -96,8 +66,6 @@ _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) #endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H diff --git a/libcxx/include/__algorithm/sample.h b/libcxx/include/__algorithm/sample.h --- a/libcxx/include/__algorithm/sample.h +++ b/libcxx/include/__algorithm/sample.h @@ -9,12 +9,14 @@ #ifndef _LIBCPP___ALGORITHM_SAMPLE_H #define _LIBCPP___ALGORITHM_SAMPLE_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/min.h> #include <__assert> #include <__config> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__random/uniform_int_distribution.h> +#include <__utility/move.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -26,13 +28,14 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template _LIBCPP_INLINE_VISIBILITY _SampleIterator __sample(_PopulationIterator __first, - _PopulationIterator __last, _SampleIterator __output_iter, + _PopulationSentinel __last, _SampleIterator __output_iter, _Distance __n, - _UniformRandomNumberGenerator & __g, + _UniformRandomNumberGenerator& __g, input_iterator_tag) { _Distance __k = 0; @@ -47,15 +50,16 @@ return __output_iter + _VSTD::min(__n, __k); } -template _LIBCPP_INLINE_VISIBILITY _SampleIterator __sample(_PopulationIterator __first, - _PopulationIterator __last, _SampleIterator __output_iter, + _PopulationSentinel __last, _SampleIterator __output_iter, _Distance __n, _UniformRandomNumberGenerator& __g, forward_iterator_tag) { - _Distance __unsampled_sz = _VSTD::distance(__first, __last); + _Distance __unsampled_sz = _IterOps<_AlgPolicy>::distance(__first, __last); for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { _Distance __r = uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); if (__r < __n) { @@ -66,24 +70,22 @@ return __output_iter; } -template _LIBCPP_INLINE_VISIBILITY _SampleIterator __sample(_PopulationIterator __first, - _PopulationIterator __last, _SampleIterator __output_iter, + _PopulationSentinel __last, _SampleIterator __output_iter, _Distance __n, _UniformRandomNumberGenerator& __g) { - typedef typename iterator_traits<_PopulationIterator>::iterator_category - _PopCategory; - typedef typename iterator_traits<_PopulationIterator>::difference_type - _Difference; - static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value || - __is_cpp17_random_access_iterator<_SampleIterator>::value, - "SampleIterator must meet the requirements of RandomAccessIterator"); - typedef typename common_type<_Distance, _Difference>::type _CommonType; _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); - return _VSTD::__sample( - __first, __last, __output_iter, _CommonType(__n), - __g, _PopCategory()); + + using _PopIterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_PopulationIterator>; + using _Difference = typename _IterOps<_AlgPolicy>::template __difference_type<_PopulationIterator>; + using _CommonType = typename common_type<_Distance, _Difference>::type; + + return std::__sample<_AlgPolicy>( + std::move(__first), std::move(__last), std::move(__output_iter), _CommonType(__n), + __g, _PopIterCategory()); } #if _LIBCPP_STD_VER > 14 @@ -93,8 +95,14 @@ _SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __output_iter, _Distance __n, _UniformRandomNumberGenerator&& __g) { - return _VSTD::__sample(__first, __last, __output_iter, __n, __g); + static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value || + __is_cpp17_random_access_iterator<_SampleIterator>::value, + "SampleIterator must meet the requirements of RandomAccessIterator"); + + return std::__sample<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__output_iter), __n, __g); } + #endif // _LIBCPP_STD_VER > 14 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h b/libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h @@ -0,0 +1,62 @@ +//===----------------------------------------------------------------------===// +// +// 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_UNIFORM_RANDOM_BIT_GENERATOR_ADAPTOR_H +#define _LIBCPP___ALGORITHM_RANGES_UNIFORM_RANDOM_BIT_GENERATOR_ADAPTOR_H + +#include <__config> +#include <__functional/invoke.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +// Range versions of random algorithms (e.g. `std::shuffle`) are less constrained than their classic counterparts. +// Range algorithms only require the given generator to satisfy the `std::uniform_random_bit_generator` concept. +// Classic algorithms require the given generator to meet the uniform random bit generator requirements; these +// requirements include satisfying `std::uniform_random_bit_generator` and add a requirement for the generator to +// provide a nested `result_type` typedef (see `[rand.req.urng]`). +// +// To be able to reuse classic implementations, make the given generator meet the classic requirements by wrapping +// it into an adaptor type that forwards all of its interface and adds the required typedef. +template +class _ClassicGenAdaptor { +private: + // The generator is not required to be copyable or movable, so it has to be stored as a reference. + _Gen& __gen; + +public: + using result_type = invoke_result_t<_Gen&>; + + _LIBCPP_HIDE_FROM_ABI + static constexpr auto min() { return __uncvref_t<_Gen>::min(); } + _LIBCPP_HIDE_FROM_ABI + static constexpr auto max() { return __uncvref_t<_Gen>::max(); } + + _LIBCPP_HIDE_FROM_ABI + constexpr explicit _ClassicGenAdaptor(_Gen& __g) : __gen(__g) {} + + _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()() const { return __gen(); } +}; + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP_STD_VER > 17 + +#endif // _LIBCPP___ALGORITHM_RANGES_UNIFORM_RANDOM_BIT_GENERATOR_ADAPTOR_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -758,6 +758,18 @@ constexpr ranges::rotate_copy_result, O> ranges::rotate_copy(R&& r, iterator_t middle, O result); // since C++20 + template S, weakly_incrementable O, class Gen> + requires (forward_iterator || random_access_iterator) && + indirectly_copyable && + uniform_random_bit_generator> + O sample(I first, S last, O out, iter_difference_t n, Gen&& g); // Since C++20 + + template + requires (forward_range || random_access_iterator) && + indirectly_copyable, O> && + uniform_random_bit_generator> + O sample(R&& r, O out, range_difference_t n, Gen&& g); // Since C++20 + template S, class Gen> requires permutable && uniform_random_bit_generator> @@ -1773,6 +1785,7 @@ #include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_reverse_copy.h> #include <__algorithm/ranges_rotate_copy.h> +#include <__algorithm/ranges_sample.h> #include <__algorithm/ranges_search.h> #include <__algorithm/ranges_search_n.h> #include <__algorithm/ranges_set_difference.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 @@ -372,6 +372,7 @@ module ranges_reverse { private header "__algorithm/ranges_reverse.h" } module ranges_reverse_copy { private header "__algorithm/ranges_reverse_copy.h" } module ranges_rotate_copy { private header "__algorithm/ranges_rotate_copy.h" } + module ranges_sample { private header "__algorithm/ranges_sample.h" } module ranges_search { private header "__algorithm/ranges_search.h" } module ranges_search_n { private header "__algorithm/ranges_search_n.h" } module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" } @@ -385,6 +386,9 @@ module ranges_stable_sort { private header "__algorithm/ranges_stable_sort.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" } module ranges_transform { private header "__algorithm/ranges_transform.h" } + module uniform_random_bit_generator_adaptor { + private header "__algorithm/uniform_random_bit_generator_adaptor.h" + } module ranges_unique { private header "__algorithm/ranges_unique.h" } module ranges_unique_copy { private header "__algorithm/ranges_unique_copy.h" } module ranges_upper_bound { private header "__algorithm/ranges_upper_bound.h" } 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 @@ -170,6 +170,7 @@ #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} #include <__algorithm/ranges_reverse_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse_copy.h'}} #include <__algorithm/ranges_rotate_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.h'}} +#include <__algorithm/ranges_sample.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sample.h'}} #include <__algorithm/ranges_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search.h'}} #include <__algorithm/ranges_search_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search_n.h'}} #include <__algorithm/ranges_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.h'}} @@ -215,6 +216,7 @@ #include <__algorithm/stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/stable_sort.h'}} #include <__algorithm/swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/swap_ranges.h'}} #include <__algorithm/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/transform.h'}} +#include <__algorithm/uniform_random_bit_generator_adaptor.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/uniform_random_bit_generator_adaptor.h'}} #include <__algorithm/unique.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique.h'}} #include <__algorithm/unique_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique_copy.h'}} #include <__algorithm/unwrap_iter.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unwrap_iter.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp @@ -0,0 +1,334 @@ +//===----------------------------------------------------------------------===// +// +// 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, weakly_incrementable O, class Gen> +// requires (forward_iterator || random_access_iterator) && +// indirectly_copyable && +// uniform_random_bit_generator> +// O sample(I first, S last, O out, iter_difference_t n, Gen&& g); // Since C++20 +// +// template +// requires (forward_range || random_access_iterator) && +// indirectly_copyable, O> && +// uniform_random_bit_generator> +// O sample(R&& r, O out, range_difference_t n, Gen&& g); // Since C++20 + +#include +#include +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" +#include "test_macros.h" + +class RandGen { +public: + constexpr static size_t min() { return 0; } + constexpr static size_t max() { return 255; } + + constexpr size_t operator()() { + flip = !flip; + return flip; + } + +private: + bool flip = false; +}; + +static_assert(std::uniform_random_bit_generator); +// `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that +// a type satisfying the required minimum is still accepted by `ranges::shuffle`. +LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng::value); + +struct BadGen { + constexpr static size_t min() { return 255; } + constexpr static size_t max() { return 0; } + constexpr size_t operator()() const; +}; +static_assert(!std::uniform_random_bit_generator); + +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasSampleIter = + requires(Iter&& iter, Sent&& sent, Out&& out, std::iter_difference_t n, Gen&& gen) { + std::ranges::sample(std::forward(iter), std::forward(sent), + std::forward(out), n, std::forward(gen)); + }; + +static_assert(HasSampleIter); + +// !input_iterator +static_assert(!HasSampleIter); +static_assert(!HasSampleIter); +static_assert(!HasSampleIter); + +// !sentinel_for +static_assert(!HasSampleIter); +static_assert(!HasSampleIter); + +// !weakly_incrementable +static_assert(!HasSampleIter); + +// (forward_iterator || random_access_iterator) +static_assert(HasSampleIter< + forward_iterator, forward_iterator, + cpp20_output_iterator +>); +static_assert(HasSampleIter< + cpp20_input_iterator, sentinel_wrapper>, + random_access_iterator +>); +// !(forward_iterator || random_access_iterator) +static_assert(!HasSampleIter< + cpp20_input_iterator, sentinel_wrapper>, + cpp20_output_iterator +>); + +// !indirectly_copyable +static_assert(!HasSampleIter); + +// !uniform_random_bit_generator> +static_assert(!HasSampleIter); + +// Test constraints of the (range) overload. +// ========================================= + +template +concept HasSampleRange = + requires(Range&& range, Out&& out, std::ranges::range_difference_t n, Gen&& gen) { + std::ranges::sample(std::forward(range), std::forward(out), n, std::forward(gen)); + }; + +template +using R = UncheckedRange; + +static_assert(HasSampleRange, int*, RandGen>); + +// !input_range +static_assert(!HasSampleRange); +static_assert(!HasSampleRange); +static_assert(!HasSampleRange); + +// !weakly_incrementable +static_assert(!HasSampleRange, WeaklyIncrementableNotMovable>); + +// (forward_range || random_access_iterator) +static_assert(HasSampleRange< + R>, + cpp20_output_iterator +>); +static_assert(HasSampleRange< + R>, + random_access_iterator +>); +// !(forward_range || random_access_iterator) +static_assert(!HasSampleRange< + R>, + cpp20_output_iterator +>); + +// !indirectly_copyable +static_assert(!HasSampleRange, int**>); + +// !uniform_random_bit_generator> +static_assert(!HasSampleRange, int*, BadGen>); + +template +void test_one(std::array in, size_t n, Gen gen) { + assert(n <= static_cast(N)); + + auto verify_is_subsequence = [&] (auto output) { + auto sorted_input = in; + std::ranges::sort(sorted_input); + auto sorted_output = std::ranges::subrange(output.begin(), output.begin() + n); + std::ranges::sort(sorted_output); + assert(std::ranges::includes(sorted_input, sorted_output)); + }; + + { // (iterator, sentinel) overload. + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + std::array output; + auto out = Out(output.begin()); + + std::same_as decltype(auto) result = std::ranges::sample( + std::move(begin), std::move(end), std::move(out), n, gen); + assert(base(result) == output.data() + n); + verify_is_subsequence(output); + // The output of `sample` is implementation-specific. + } + + { // (range) overload. + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + std::array output; + auto out = Out(output.begin()); + + std::same_as decltype(auto) result = std::ranges::sample(std::ranges::subrange( + std::move(begin), std::move(end)), std::move(out), n, gen); + assert(base(result) == output.data() + n); + verify_is_subsequence(output); + // The output of `sample` is implementation-specific. + } +} + +template +void test_iterators_iter_sent_out() { + RandGen gen; + + // Empty sequence. + test_one({}, 0, gen); + // 1-element sequence. + test_one({1}, 1, gen); + // 2-element sequence. + test_one({1, 2}, 1, gen); + test_one({1, 2}, 2, gen); + // n == 0. + test_one({1, 2, 3}, 0, gen); + + // Longer sequence. + { + std::array input = {1, 8, 2, 3, 4, 6, 5, 7}; + for (int i = 0; i <= static_cast(input.size()); ++i){ + test_one(input, i, gen); + } + } +} + +template +void test_iterators_iter_sent() { + if constexpr (std::forward_iterator) { + test_iterators_iter_sent_out>(); + test_iterators_iter_sent_out>(); + } + test_iterators_iter_sent_out>(); + test_iterators_iter_sent_out>(); + test_iterators_iter_sent_out(); +} + +template +void test_iterators_iter() { + if constexpr (std::sentinel_for) { + test_iterators_iter_sent(); + } + test_iterators_iter_sent>(); +} + +void test_iterators() { + test_iterators_iter>(); + test_iterators_iter>(); + test_iterators_iter>(); + test_iterators_iter(); + test_iterators_iter(); +} + +// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of +// the given generator object. +template +void test_generator() { + std::array in = {1, 2, 3, 4, 5, 6, 7, 8}; + constexpr int N = 5; + std::array output; + auto begin = in.begin(); + auto end = in.end(); + auto out = output.begin(); + + { // Lvalue. + Gen g; + std::ranges::sample(begin, end, out, N, g); + std::ranges::sample(in, out, N, g); + } + + if constexpr (CheckConst) { // Const lvalue. + const Gen g; + std::ranges::sample(begin, end, out, N, g); + std::ranges::sample(in, out, N, g); + } + + { // Prvalue. + std::ranges::sample(begin, end, out, N, Gen()); + std::ranges::sample(in, out, N, Gen()); + } + + { // Xvalue. + Gen g1, g2; + std::ranges::sample(begin, end, out, N, std::move(g1)); + std::ranges::sample(in, out, N, std::move(g2)); + } +} + +// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given +// generator class has a const or non-const invocation operator (or both). +void test_generators() { + struct GenBase { + constexpr static size_t min() { return 0; } + constexpr static size_t max() { return 255; } + }; + struct NonconstGen : GenBase { + size_t operator()() { return 1; } + }; + struct ConstGen : GenBase { + size_t operator()() const { return 1; } + }; + struct ConstAndNonconstGen : GenBase { + size_t operator()() { return 1; } + size_t operator()() const { return 1; } + }; + + test_generator(); + test_generator(); + test_generator(); +} + +void test() { + test_iterators(); + test_generators(); + + { // Stable (if `I` models `forward_iterator`). + struct OrderedValue { + int value; + int original_order; + bool operator==(const OrderedValue&) const = default; + auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; } + }; + + const std::array in = {{ + {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8} + }}; + + { // (iterator, sentinel) overload. + std::array out; + std::ranges::sample(in.begin(), in.end(), out.begin(), in.size(), RandGen()); + assert(out == in); + } + + { // (range) overload. + std::array out; + std::ranges::sample(in, out.begin(), in.size(), RandGen()); + assert(out == in); + } + } +} + +int main(int, char**) { + test(); + // Note: `ranges::sample` is not `constexpr`. + + return 0; +} diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -139,7 +139,7 @@ // `swap_ranges` has neither a projection nor a predicate. // `reverse_copy` has neither a projection nor a predicate. // `rotate_copy` has neither a projection nor a predicate. - // `sample` has no requirement that the given generator be invoked via `std::invoke`. + // For `sample`, whether the given generator is invoked via `std::invoke` is not observable. test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val); test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val); test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); @@ -152,7 +152,7 @@ test(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val); // `reverse` has neither a projection nor a predicate. // `rotate` has neither a projection nor a predicate. - // `shuffle` has neither a projection nor a predicate. + // For `shuffle`, whether the given generator is invoked via `std::invoke` is not observable. test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val); test(std::ranges::partition, in, &Foo::unary_pred, &Bar::val); if (!std::is_constant_evaluated()) diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -150,8 +150,10 @@ //test_mid(std::ranges::rotate, in, mid); if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. test(std::ranges::shuffle, in, rand_gen()); - //if (!std::is_constant_evaluated()) - // test(std::ranges::sample, in, out, count, rand_gen()); + if (!std::is_constant_evaluated()) { + if constexpr (std::copyable) + test(std::ranges::sample, in, out, count, rand_gen()); + } test(std::ranges::unique, in); test(std::ranges::partition, in, unary_pred); // TODO(ranges): `stable_partition` requires `ranges::rotate` to be implemented. 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 @@ -130,7 +130,7 @@ static_assert(test(std::ranges::reverse_copy, a, a)); //static_assert(test(std::ranges::rotate, a, a+5)); static_assert(test(std::ranges::rotate_copy, a, a+5, a)); -//static_assert(test(std::ranges::sample, a, a, 5)); +static_assert(test(std::ranges::sample, a, a, 5, g)); static_assert(test(std::ranges::search, a, a)); static_assert(test(std::ranges::search_n, a, 10, 42)); static_assert(test(std::ranges::set_difference, a, a, a));