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