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
35 class RandGen {
36 public:
min()37 constexpr static std::size_t min() { return 0; }
max()38 constexpr static std::size_t max() { return 255; }
39
operator ()()40 constexpr std::size_t operator()() {
41 flip = !flip;
42 return flip;
43 }
44
45 private:
46 bool flip = false;
47 };
48
49 static_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`.
52 LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
53
54 struct BadGen {
minBadGen55 constexpr static std::size_t min() { return 255; }
maxBadGen56 constexpr static std::size_t max() { return 0; }
57 constexpr std::size_t operator()() const;
58 };
59 static_assert(!std::uniform_random_bit_generator<BadGen>);
60
61 // Test constraints of the (iterator, sentinel) overload.
62 // ======================================================
63
64 template <class Iter = int*, class Sent = int*, class Gen = RandGen>
65 concept 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
70 static_assert(HasShuffleIter<int*, int*, RandGen>);
71
72 // !random_access_iterator<I>
73 static_assert(!HasShuffleIter<RandomAccessIteratorNotDerivedFrom>);
74 static_assert(!HasShuffleIter<RandomAccessIteratorBadIndex>);
75
76 // !sentinel_for<S, I>
77 static_assert(!HasShuffleIter<int*, SentinelForNotSemiregular>);
78 static_assert(!HasShuffleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
79
80 // !permutable<I>
81 static_assert(!HasShuffleIter<PermutableNotForwardIterator>);
82 static_assert(!HasShuffleIter<PermutableNotSwappable>);
83
84 // !uniform_random_bit_generator<remove_reference_t<Gen>>
85 static_assert(!HasShuffleIter<int*, int*, BadGen>);
86
87 // Test constraints of the (range) overload.
88 // =========================================
89
90 template <class Range, class Gen = RandGen>
91 concept HasShuffleRange =
92 requires(Range&& range, Gen&& gen) {
93 std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen));
94 };
95
96 template <class T>
97 using R = UncheckedRange<T>;
98
99 static_assert(HasShuffleRange<R<int*>, RandGen>);
100
101 // !random_access_range<R>
102 static_assert(!HasShuffleRange<RandomAccessRangeNotDerivedFrom>);
103 static_assert(!HasShuffleRange<RandomAccessRangeBadIndex>);
104
105 // !permutable<iterator_t<R>>
106 static_assert(!HasShuffleRange<PermutableNotForwardIterator>);
107 static_assert(!HasShuffleRange<PermutableNotSwappable>);
108
109 // !uniform_random_bit_generator<remove_reference_t<Gen>>
110 static_assert(!HasShuffleRange<R<int*>, BadGen>);
111
112 template <class Iter, class Sent, std::size_t N, class Gen>
test_one(const std::array<int,N> input,Gen gen)113 void 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
154 template <class Iter, class Sent>
test_iterators_iter_sent()155 void 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
174 template <class Iter>
test_iterators_iter()175 void test_iterators_iter() {
176 test_iterators_iter_sent<Iter, Iter>();
177 test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
178 }
179
test_iterators()180 void 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.
188 template <class Gen, bool CheckConst = true>
test_generator()189 void 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).
test_generators()220 void 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
test()241 void 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
main(int,char **)263 int main(int, char**) {
264 test();
265 // Note: `ranges::shuffle` is not `constexpr`.
266
267 return 0;
268 }
269