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:
38   constexpr static size_t min() { return 0; }
39   constexpr static size_t max() { return 255; }
40 
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 {
56   constexpr static size_t min() { return 255; }
57   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>
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>
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>
176 void test_iterators_iter() {
177   test_iterators_iter_sent<Iter, Iter>();
178   test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
179 }
180 
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>
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).
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 
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 
264 int main(int, char**) {
265   test();
266   // Note: `ranges::shuffle` is not `constexpr`.
267 
268   return 0;
269 }
270