| //===----------------------------------------------------------------------===// |
| // |
| // 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<random_access_iterator I, sentinel_for<I> S, class Gen> |
| // requires permutable<I> && |
| // uniform_random_bit_generator<remove_reference_t<Gen>> |
| // I shuffle(I first, S last, Gen&& g); // Since C++20 |
| // |
| // template<random_access_range R, class Gen> |
| // requires permutable<iterator_t<R>> && |
| // uniform_random_bit_generator<remove_reference_t<Gen>> |
| // borrowed_iterator_t<R> shuffle(R&& r, 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 Gen = RandGen> |
| concept HasShuffleIter = |
| requires(Iter&& iter, Sent&& sent, Gen&& gen) { |
| std::ranges::shuffle(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen)); |
| }; |
| |
| static_assert(HasShuffleIter<int*, int*, RandGen>); |
| |
| // !random_access_iterator<I> |
| static_assert(!HasShuffleIter<RandomAccessIteratorNotDerivedFrom>); |
| static_assert(!HasShuffleIter<RandomAccessIteratorBadIndex>); |
| |
| // !sentinel_for<S, I> |
| static_assert(!HasShuffleIter<int*, SentinelForNotSemiregular>); |
| static_assert(!HasShuffleIter<int*, SentinelForNotWeaklyEqualityComparableWith>); |
| |
| // !permutable<I> |
| static_assert(!HasShuffleIter<PermutableNotForwardIterator>); |
| static_assert(!HasShuffleIter<PermutableNotSwappable>); |
| |
| // !uniform_random_bit_generator<remove_reference_t<Gen>> |
| static_assert(!HasShuffleIter<int*, int*, BadGen>); |
| |
| // Test constraints of the (range) overload. |
| // ========================================= |
| |
| template <class Range, class Gen = RandGen> |
| concept HasShuffleRange = |
| requires(Range&& range, Gen&& gen) { |
| std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen)); |
| }; |
| |
| template <class T> |
| using R = UncheckedRange<T>; |
| |
| static_assert(HasShuffleRange<R<int*>, RandGen>); |
| |
| // !random_access_range<R> |
| static_assert(!HasShuffleRange<RandomAccessRangeNotDerivedFrom>); |
| static_assert(!HasShuffleRange<RandomAccessRangeBadIndex>); |
| |
| // !permutable<iterator_t<R>> |
| static_assert(!HasShuffleRange<PermutableNotForwardIterator>); |
| static_assert(!HasShuffleRange<PermutableNotSwappable>); |
| |
| // !uniform_random_bit_generator<remove_reference_t<Gen>> |
| static_assert(!HasShuffleRange<R<int*>, BadGen>); |
| |
| template <class Iter, class Sent, std::size_t N, class Gen> |
| void test_one(const std::array<int, N> input, Gen gen) { |
| { // (iterator, sentinel) overload. |
| auto shuffled = input; |
| auto begin = Iter(shuffled.data()); |
| auto end = Sent(Iter(shuffled.data() + shuffled.size())); |
| |
| std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(begin, end, gen); |
| |
| assert(result == Iter(shuffled.data() + shuffled.size())); |
| // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting. |
| //assert(std::ranges::is_permutation(shuffled, input); |
| { |
| auto shuffled_sorted = shuffled; |
| std::ranges::sort(shuffled_sorted); |
| auto original_sorted = input; |
| std::ranges::sort(original_sorted); |
| assert(shuffled_sorted == original_sorted); |
| } |
| } |
| |
| { // (range) overload. |
| auto shuffled = input; |
| auto begin = Iter(shuffled.data()); |
| auto end = Sent(Iter(shuffled.data() + shuffled.size())); |
| auto range = std::ranges::subrange(begin, end); |
| |
| std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(range, gen); |
| |
| assert(result == Iter(shuffled.data() + shuffled.size())); |
| // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting. |
| //assert(std::ranges::is_permutation(shuffled, input); |
| { |
| auto shuffled_sorted = shuffled; |
| std::ranges::sort(shuffled_sorted); |
| auto original_sorted = input; |
| std::ranges::sort(original_sorted); |
| assert(shuffled_sorted == original_sorted); |
| } |
| } |
| } |
| |
| template <class Iter, class Sent> |
| void test_iterators_iter_sent() { |
| RandGen gen; |
| |
| // Empty sequence. |
| test_one<Iter, Sent, 0>({}, gen); |
| // 1-element sequence. |
| test_one<Iter, Sent, 1>({1}, gen); |
| // 2-element sequence. |
| test_one<Iter, Sent, 2>({2, 1}, gen); |
| // 3-element sequence. |
| test_one<Iter, Sent, 3>({2, 1, 3}, gen); |
| // Longer sequence. |
| test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, gen); |
| // Longer sequence with duplicates. |
| test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, gen); |
| // All elements are the same. |
| test_one<Iter, Sent, 3>({1, 1, 1}, gen); |
| } |
| |
| template <class Iter> |
| void test_iterators_iter() { |
| test_iterators_iter_sent<Iter, Iter>(); |
| test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>(); |
| } |
| |
| void test_iterators() { |
| test_iterators_iter<random_access_iterator<int*>>(); |
| test_iterators_iter<contiguous_iterator<int*>>(); |
| test_iterators_iter<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}; |
| auto begin = in.begin(); |
| auto end = in.end(); |
| |
| { // Lvalue. |
| Gen g; |
| std::ranges::shuffle(begin, end, g); |
| std::ranges::shuffle(in, g); |
| } |
| |
| if constexpr (CheckConst) { // Const lvalue. |
| const Gen g; |
| std::ranges::shuffle(begin, end, g); |
| std::ranges::shuffle(in, g); |
| } |
| |
| { // Prvalue. |
| std::ranges::shuffle(begin, end, Gen()); |
| std::ranges::shuffle(in, Gen()); |
| } |
| |
| { // Xvalue. |
| Gen g1, g2; |
| std::ranges::shuffle(begin, end, std::move(g1)); |
| std::ranges::shuffle(in, 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(); |
| |
| { // Complexity: Exactly `(last - first) - 1` swaps. |
| { |
| std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; //14 |
| |
| int swaps = 0; |
| auto begin = adl::Iterator::TrackSwaps(in.data(), swaps); |
| auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps); |
| |
| std::ranges::shuffle(begin, end, RandGen()); |
| int expected = in.size() - 1; |
| // Note: our implementation doesn't perform a swap when the distribution returns 0, so the actual number of swaps |
| // might be less than specified in the standard. |
| assert(swaps <= expected); |
| swaps = 0; |
| } |
| } |
| } |
| |
| int main(int, char**) { |
| test(); |
| // Note: `ranges::shuffle` is not `constexpr`. |
| |
| return 0; |
| } |