| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| |
| // <algorithm> |
| |
| // template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen> |
| // requires (forward_iterator<I> || random_access_iterator<O>) && |
| // indirectly_copyable<I, O> && |
| // uniform_random_bit_generator<remove_reference_t<Gen>> |
| // O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g); // Since C++20 |
| // |
| // template<input_range R, weakly_incrementable O, class Gen> |
| // requires (forward_range<R> || random_access_iterator<O>) && |
| // indirectly_copyable<iterator_t<R>, O> && |
| // uniform_random_bit_generator<remove_reference_t<Gen>> |
| // O sample(R&& r, O out, range_difference_t<R> n, Gen&& g); // Since C++20 |
| |
| #include <algorithm> |
| #include <array> |
| #include <concepts> |
| #include <functional> |
| #include <random> |
| #include <ranges> |
| #include <utility> |
| |
| #include "almost_satisfies_types.h" |
| #include "test_iterators.h" |
| #include "test_macros.h" |
| |
| class RandGen { |
| public: |
| constexpr static std::size_t min() { return 0; } |
| constexpr static std::size_t max() { return 255; } |
| |
| constexpr std::size_t operator()() { |
| flip = !flip; |
| return flip; |
| } |
| |
| private: |
| bool flip = false; |
| }; |
| |
| static_assert(std::uniform_random_bit_generator<RandGen>); |
| // `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<RandGen>::value); |
| |
| struct BadGen { |
| constexpr static std::size_t min() { return 255; } |
| constexpr static std::size_t max() { return 0; } |
| constexpr std::size_t operator()() const; |
| }; |
| static_assert(!std::uniform_random_bit_generator<BadGen>); |
| |
| // Test constraints of the (iterator, sentinel) overload. |
| // ====================================================== |
| |
| template <class Iter = int*, class Sent = int*, class Out = int*, class Gen = RandGen> |
| concept HasSampleIter = |
| requires(Iter&& iter, Sent&& sent, Out&& out, std::iter_difference_t<Iter> n, Gen&& gen) { |
| std::ranges::sample(std::forward<Iter>(iter), std::forward<Sent>(sent), |
| std::forward<Out>(out), n, std::forward<Gen>(gen)); |
| }; |
| |
| static_assert(HasSampleIter<int*, int*, int*, RandGen>); |
| |
| // !input_iterator<I> |
| static_assert(!HasSampleIter<InputIteratorNotDerivedFrom>); |
| static_assert(!HasSampleIter<InputIteratorNotIndirectlyReadable>); |
| static_assert(!HasSampleIter<InputIteratorNotInputOrOutputIterator>); |
| |
| // !sentinel_for<S, I> |
| static_assert(!HasSampleIter<int*, SentinelForNotSemiregular>); |
| static_assert(!HasSampleIter<int*, SentinelForNotWeaklyEqualityComparableWith>); |
| |
| // !weakly_incrementable<O> |
| static_assert(!HasSampleIter<int*, int*, WeaklyIncrementableNotMovable>); |
| |
| // (forward_iterator<I> || random_access_iterator<O>) |
| static_assert(HasSampleIter< |
| forward_iterator<int*>, forward_iterator<int*>, |
| cpp20_output_iterator<int*> |
| >); |
| static_assert(HasSampleIter< |
| cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>, |
| random_access_iterator<int*> |
| >); |
| // !(forward_iterator<I> || random_access_iterator<O>) |
| static_assert(!HasSampleIter< |
| cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>, |
| cpp20_output_iterator<int*> |
| >); |
| |
| // !indirectly_copyable<I, O> |
| static_assert(!HasSampleIter<int*, int*, int**>); |
| |
| // !uniform_random_bit_generator<remove_reference_t<Gen>> |
| static_assert(!HasSampleIter<int*, int*, int*, BadGen>); |
| |
| // Test constraints of the (range) overload. |
| // ========================================= |
| |
| template <class Range, class Out = int*, class Gen = RandGen> |
| concept HasSampleRange = |
| requires(Range&& range, Out&& out, std::ranges::range_difference_t<Range> n, Gen&& gen) { |
| std::ranges::sample(std::forward<Range>(range), std::forward<Out>(out), n, std::forward<Gen>(gen)); |
| }; |
| |
| template <class T> |
| using R = UncheckedRange<T>; |
| |
| static_assert(HasSampleRange<R<int*>, int*, RandGen>); |
| |
| // !input_range<R> |
| static_assert(!HasSampleRange<InputRangeNotDerivedFrom>); |
| static_assert(!HasSampleRange<InputRangeNotIndirectlyReadable>); |
| static_assert(!HasSampleRange<InputRangeNotInputOrOutputIterator>); |
| |
| // !weakly_incrementable<O> |
| static_assert(!HasSampleRange<R<int*>, WeaklyIncrementableNotMovable>); |
| |
| // (forward_range<R> || random_access_iterator<O>) |
| static_assert(HasSampleRange< |
| R<forward_iterator<int*>>, |
| cpp20_output_iterator<int*> |
| >); |
| static_assert(HasSampleRange< |
| R<cpp20_input_iterator<int*>>, |
| random_access_iterator<int*> |
| >); |
| // !(forward_range<R> || random_access_iterator<O>) |
| static_assert(!HasSampleRange< |
| R<cpp20_input_iterator<int*>>, |
| cpp20_output_iterator<int*> |
| >); |
| |
| // !indirectly_copyable<I, O> |
| static_assert(!HasSampleRange<R<int*>, int**>); |
| |
| // !uniform_random_bit_generator<remove_reference_t<Gen>> |
| static_assert(!HasSampleRange<R<int*>, int*, BadGen>); |
| |
| template <class Iter, class Sent, class Out, std::size_t N, class Gen> |
| void test_one(std::array<int, N> in, std::size_t n, Gen gen) { |
| assert(n <= static_cast<std::size_t>(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<int, N> output; |
| auto out = Out(output.begin()); |
| |
| std::same_as<Out> 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<int, N> output; |
| auto out = Out(output.begin()); |
| |
| std::same_as<Out> 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 <class Iter, class Sent, class Out> |
| void test_iterators_iter_sent_out() { |
| RandGen gen; |
| |
| // Empty sequence. |
| test_one<Iter, Sent, Out, 0>({}, 0, gen); |
| // 1-element sequence. |
| test_one<Iter, Sent, Out, 1>({1}, 1, gen); |
| // 2-element sequence. |
| test_one<Iter, Sent, Out, 2>({1, 2}, 1, gen); |
| test_one<Iter, Sent, Out, 2>({1, 2}, 2, gen); |
| // n == 0. |
| test_one<Iter, Sent, Out, 3>({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<int>(input.size()); ++i){ |
| test_one<Iter, Sent, Out, input.size()>(input, i, gen); |
| } |
| } |
| } |
| |
| template <class Iter, class Sent> |
| void test_iterators_iter_sent() { |
| if constexpr (std::forward_iterator<Iter>) { |
| test_iterators_iter_sent_out<Iter, Sent, cpp20_output_iterator<int*>>(); |
| test_iterators_iter_sent_out<Iter, Sent, forward_iterator<int*>>(); |
| } |
| test_iterators_iter_sent_out<Iter, Sent, random_access_iterator<int*>>(); |
| test_iterators_iter_sent_out<Iter, Sent, contiguous_iterator<int*>>(); |
| test_iterators_iter_sent_out<Iter, Sent, int*>(); |
| } |
| |
| template <class Iter> |
| void test_iterators_iter() { |
| if constexpr (std::sentinel_for<Iter, Iter>) { |
| test_iterators_iter_sent<Iter, Iter>(); |
| } |
| test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>(); |
| } |
| |
| void test_iterators() { |
| test_iterators_iter<cpp20_input_iterator<int*>>(); |
| test_iterators_iter<random_access_iterator<int*>>(); |
| test_iterators_iter<contiguous_iterator<int*>>(); |
| test_iterators_iter<int*>(); |
| test_iterators_iter<const int*>(); |
| } |
| |
| // 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 <class Gen, bool CheckConst = true> |
| void test_generator() { |
| std::array in = {1, 2, 3, 4, 5, 6, 7, 8}; |
| constexpr int N = 5; |
| std::array<int, N> 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 std::size_t min() { return 0; } |
| constexpr static std::size_t max() { return 255; } |
| }; |
| struct NonconstGen : GenBase { |
| std::size_t operator()() { return 1; } |
| }; |
| struct ConstGen : GenBase { |
| std::size_t operator()() const { return 1; } |
| }; |
| struct ConstAndNonconstGen : GenBase { |
| std::size_t operator()() { return 1; } |
| std::size_t operator()() const { return 1; } |
| }; |
| |
| test_generator<ConstGen>(); |
| test_generator<NonconstGen, /*CheckConst=*/false>(); |
| test_generator<ConstAndNonconstGen>(); |
| } |
| |
| 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<OrderedValue, 8> in = {{ |
| {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8} |
| }}; |
| |
| { // (iterator, sentinel) overload. |
| std::array<OrderedValue, in.size()> out; |
| std::ranges::sample(in.begin(), in.end(), out.begin(), in.size(), RandGen()); |
| assert(out == in); |
| } |
| |
| { // (range) overload. |
| std::array<OrderedValue, in.size()> 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; |
| } |