1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<random_access_iterator I, sentinel_for<I> S, class Gen>
14// requires permutable<I> &&
15// uniform_random_bit_generator<remove_reference_t<Gen>>
16// I shuffle(I first, S last, Gen&& g); // Since C++20
17//
18// template<random_access_range R, class Gen>
19// requires permutable<iterator_t<R>> &&
20// uniform_random_bit_generator<remove_reference_t<Gen>>
21// borrowed_iterator_t<R> shuffle(R&& r, Gen&& g); // Since C++20
22
23#include <algorithm>
24#include <array>
25#include <concepts>
26#include <functional>
27#include <random>
28#include <ranges>
29#include <utility>
30
31#include "almost_satisfies_types.h"
32#include "test_iterators.h"
33#include "test_macros.h"
34
35class RandGen {
36public:
37 constexpr static std::size_t min() { return 0; }
38 constexpr static std::size_t max() { return 255; }
39
40 constexpr std::size_t operator()() {
41 flip = !flip;
42 return flip;
43 }
44
45private:
46 bool flip = false;
47};
48
49static_assert(std::uniform_random_bit_generator<RandGen>);
50// `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that
51// a type satisfying the required minimum is still accepted by `ranges::shuffle`.
52LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
53
54struct BadGen {
55 constexpr static std::size_t min() { return 255; }
56 constexpr static std::size_t max() { return 0; }
57 constexpr std::size_t operator()() const;
58};
59static_assert(!std::uniform_random_bit_generator<BadGen>);
60
61// Test constraints of the (iterator, sentinel) overload.
62// ======================================================
63
64template <class Iter = int*, class Sent = int*, class Gen = RandGen>
65concept HasShuffleIter =
66 requires(Iter&& iter, Sent&& sent, Gen&& gen) {
67 std::ranges::shuffle(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen));
68 };
69
70static_assert(HasShuffleIter<int*, int*, RandGen>);
71
72// !random_access_iterator<I>
73static_assert(!HasShuffleIter<RandomAccessIteratorNotDerivedFrom>);
74static_assert(!HasShuffleIter<RandomAccessIteratorBadIndex>);
75
76// !sentinel_for<S, I>
77static_assert(!HasShuffleIter<int*, SentinelForNotSemiregular>);
78static_assert(!HasShuffleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
79
80// !permutable<I>
81static_assert(!HasShuffleIter<PermutableNotForwardIterator>);
82static_assert(!HasShuffleIter<PermutableNotSwappable>);
83
84// !uniform_random_bit_generator<remove_reference_t<Gen>>
85static_assert(!HasShuffleIter<int*, int*, BadGen>);
86
87// Test constraints of the (range) overload.
88// =========================================
89
90template <class Range, class Gen = RandGen>
91concept HasShuffleRange =
92 requires(Range&& range, Gen&& gen) {
93 std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen));
94 };
95
96template <class T>
97using R = UncheckedRange<T>;
98
99static_assert(HasShuffleRange<R<int*>, RandGen>);
100
101// !random_access_range<R>
102static_assert(!HasShuffleRange<RandomAccessRangeNotDerivedFrom>);
103static_assert(!HasShuffleRange<RandomAccessRangeBadIndex>);
104
105// !permutable<iterator_t<R>>
106static_assert(!HasShuffleRange<PermutableNotForwardIterator>);
107static_assert(!HasShuffleRange<PermutableNotSwappable>);
108
109// !uniform_random_bit_generator<remove_reference_t<Gen>>
110static_assert(!HasShuffleRange<R<int*>, BadGen>);
111
112template <class Iter, class Sent, std::size_t N, class Gen>
113void test_one(const std::array<int, N> input, Gen gen) {
114 { // (iterator, sentinel) overload.
115 auto shuffled = input;
116 auto begin = Iter(shuffled.data());
117 auto end = Sent(Iter(shuffled.data() + shuffled.size()));
118
119 std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(begin, end, gen);
120
121 assert(result == Iter(shuffled.data() + shuffled.size()));
122 // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
123 //assert(std::ranges::is_permutation(shuffled, input);
124 {
125 auto shuffled_sorted = shuffled;
126 std::ranges::sort(shuffled_sorted);
127 auto original_sorted = input;
128 std::ranges::sort(original_sorted);
129 assert(shuffled_sorted == original_sorted);
130 }
131 }
132
133 { // (range) overload.
134 auto shuffled = input;
135 auto begin = Iter(shuffled.data());
136 auto end = Sent(Iter(shuffled.data() + shuffled.size()));
137 auto range = std::ranges::subrange(begin, end);
138
139 std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(range, gen);
140
141 assert(result == Iter(shuffled.data() + shuffled.size()));
142 // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
143 //assert(std::ranges::is_permutation(shuffled, input);
144 {
145 auto shuffled_sorted = shuffled;
146 std::ranges::sort(shuffled_sorted);
147 auto original_sorted = input;
148 std::ranges::sort(original_sorted);
149 assert(shuffled_sorted == original_sorted);
150 }
151 }
152}
153
154template <class Iter, class Sent>
155void test_iterators_iter_sent() {
156 RandGen gen;
157
158 // Empty sequence.
159 test_one<Iter, Sent, 0>({}, gen);
160 // 1-element sequence.
161 test_one<Iter, Sent, 1>({1}, gen);
162 // 2-element sequence.
163 test_one<Iter, Sent, 2>({2, 1}, gen);
164 // 3-element sequence.
165 test_one<Iter, Sent, 3>({2, 1, 3}, gen);
166 // Longer sequence.
167 test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, gen);
168 // Longer sequence with duplicates.
169 test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, gen);
170 // All elements are the same.
171 test_one<Iter, Sent, 3>({1, 1, 1}, gen);
172}
173
174template <class Iter>
175void test_iterators_iter() {
176 test_iterators_iter_sent<Iter, Iter>();
177 test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
178}
179
180void test_iterators() {
181 test_iterators_iter<random_access_iterator<int*>>();
182 test_iterators_iter<contiguous_iterator<int*>>();
183 test_iterators_iter<int*>();
184}
185
186// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of
187// the given generator object.
188template <class Gen, bool CheckConst = true>
189void test_generator() {
190 std::array in = {1, 2, 3, 4, 5, 6, 7, 8};
191 auto begin = in.begin();
192 auto end = in.end();
193
194 { // Lvalue.
195 Gen g;
196 std::ranges::shuffle(begin, end, g);
197 std::ranges::shuffle(in, g);
198 }
199
200 if constexpr (CheckConst) { // Const lvalue.
201 const Gen g;
202 std::ranges::shuffle(begin, end, g);
203 std::ranges::shuffle(in, g);
204 }
205
206 { // Prvalue.
207 std::ranges::shuffle(begin, end, Gen());
208 std::ranges::shuffle(in, Gen());
209 }
210
211 { // Xvalue.
212 Gen g1, g2;
213 std::ranges::shuffle(begin, end, std::move(g1));
214 std::ranges::shuffle(in, std::move(g2));
215 }
216}
217
218// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given
219// generator class has a const or non-const invocation operator (or both).
220void test_generators() {
221 struct GenBase {
222 constexpr static std::size_t min() { return 0; }
223 constexpr static std::size_t max() { return 255; }
224 };
225 struct NonconstGen : GenBase {
226 std::size_t operator()() { return 1; }
227 };
228 struct ConstGen : GenBase {
229 std::size_t operator()() const { return 1; }
230 };
231 struct ConstAndNonconstGen : GenBase {
232 std::size_t operator()() { return 1; }
233 std::size_t operator()() const { return 1; }
234 };
235
236 test_generator<ConstGen>();
237 test_generator<NonconstGen, /*CheckConst=*/false>();
238 test_generator<ConstAndNonconstGen>();
239}
240
241void test() {
242 test_iterators();
243 test_generators();
244
245 { // Complexity: Exactly `(last - first) - 1` swaps.
246 {
247 std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; //14
248
249 int swaps = 0;
250 auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
251 auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
252
253 std::ranges::shuffle(begin, end, RandGen());
254 int expected = in.size() - 1;
255 // Note: our implementation doesn't perform a swap when the distribution returns 0, so the actual number of swaps
256 // might be less than specified in the standard.
257 assert(swaps <= expected);
258 swaps = 0;
259 }
260 }
261}
262
263int main(int, char**) {
264 test();
265 // Note: `ranges::shuffle` is not `constexpr`.
266
267 return 0;
268}
269

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp