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<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>
14 //   requires (forward_iterator<I> || random_access_iterator<O>) &&
15 //           indirectly_copyable<I, O> &&
16 //           uniform_random_bit_generator<remove_reference_t<Gen>>
17 //   O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);                              // Since C++20
18 //
19 // template<input_range R, weakly_incrementable O, class Gen>
20 //   requires (forward_range<R> || random_access_iterator<O>) &&
21 //           indirectly_copyable<iterator_t<R>, O> &&
22 //           uniform_random_bit_generator<remove_reference_t<Gen>>
23 //   O sample(R&& r, O out, range_difference_t<R> n, Gen&& g);                                       // Since C++20
24 
25 #include <algorithm>
26 #include <array>
27 #include <concepts>
28 #include <functional>
29 #include <random>
30 #include <ranges>
31 #include <utility>
32 
33 #include "almost_satisfies_types.h"
34 #include "test_iterators.h"
35 #include "test_macros.h"
36 
37 class RandGen {
38 public:
39   constexpr static std::size_t min() { return 0; }
40   constexpr static std::size_t max() { return 255; }
41 
42   constexpr std::size_t operator()() {
43     flip = !flip;
44     return flip;
45   }
46 
47 private:
48   bool flip = false;
49 };
50 
51 static_assert(std::uniform_random_bit_generator<RandGen>);
52 // `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that
53 // a type satisfying the required minimum is still accepted by `ranges::shuffle`.
54 LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
55 
56 struct BadGen {
57   constexpr static std::size_t min() { return 255; }
58   constexpr static std::size_t max() { return 0; }
59   constexpr std::size_t operator()() const;
60 };
61 static_assert(!std::uniform_random_bit_generator<BadGen>);
62 
63 // Test constraints of the (iterator, sentinel) overload.
64 // ======================================================
65 
66 template <class Iter = int*, class Sent = int*, class Out = int*, class Gen = RandGen>
67 concept HasSampleIter =
68     requires(Iter&& iter, Sent&& sent, Out&& out, std::iter_difference_t<Iter> n, Gen&& gen) {
69       std::ranges::sample(std::forward<Iter>(iter), std::forward<Sent>(sent),
70                           std::forward<Out>(out), n, std::forward<Gen>(gen));
71     };
72 
73 static_assert(HasSampleIter<int*, int*, int*, RandGen>);
74 
75 // !input_iterator<I>
76 static_assert(!HasSampleIter<InputIteratorNotDerivedFrom>);
77 static_assert(!HasSampleIter<InputIteratorNotIndirectlyReadable>);
78 static_assert(!HasSampleIter<InputIteratorNotInputOrOutputIterator>);
79 
80 // !sentinel_for<S, I>
81 static_assert(!HasSampleIter<int*, SentinelForNotSemiregular>);
82 static_assert(!HasSampleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
83 
84 // !weakly_incrementable<O>
85 static_assert(!HasSampleIter<int*, int*, WeaklyIncrementableNotMovable>);
86 
87 // (forward_iterator<I> || random_access_iterator<O>)
88 static_assert(HasSampleIter<
89     forward_iterator<int*>, forward_iterator<int*>,
90     cpp20_output_iterator<int*>
91 >);
92 static_assert(HasSampleIter<
93     cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>,
94     random_access_iterator<int*>
95 >);
96 // !(forward_iterator<I> || random_access_iterator<O>)
97 static_assert(!HasSampleIter<
98     cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>,
99     cpp20_output_iterator<int*>
100 >);
101 
102 // !indirectly_copyable<I, O>
103 static_assert(!HasSampleIter<int*, int*, int**>);
104 
105 // !uniform_random_bit_generator<remove_reference_t<Gen>>
106 static_assert(!HasSampleIter<int*, int*, int*, BadGen>);
107 
108 // Test constraints of the (range) overload.
109 // =========================================
110 
111 template <class Range, class Out = int*, class Gen = RandGen>
112 concept HasSampleRange =
113     requires(Range&& range, Out&& out, std::ranges::range_difference_t<Range> n, Gen&& gen) {
114       std::ranges::sample(std::forward<Range>(range), std::forward<Out>(out), n, std::forward<Gen>(gen));
115     };
116 
117 template <class T>
118 using R = UncheckedRange<T>;
119 
120 static_assert(HasSampleRange<R<int*>, int*, RandGen>);
121 
122 // !input_range<R>
123 static_assert(!HasSampleRange<InputRangeNotDerivedFrom>);
124 static_assert(!HasSampleRange<InputRangeNotIndirectlyReadable>);
125 static_assert(!HasSampleRange<InputRangeNotInputOrOutputIterator>);
126 
127 // !weakly_incrementable<O>
128 static_assert(!HasSampleRange<R<int*>, WeaklyIncrementableNotMovable>);
129 
130 // (forward_range<R> || random_access_iterator<O>)
131 static_assert(HasSampleRange<
132     R<forward_iterator<int*>>,
133     cpp20_output_iterator<int*>
134 >);
135 static_assert(HasSampleRange<
136     R<cpp20_input_iterator<int*>>,
137     random_access_iterator<int*>
138 >);
139 // !(forward_range<R> || random_access_iterator<O>)
140 static_assert(!HasSampleRange<
141     R<cpp20_input_iterator<int*>>,
142     cpp20_output_iterator<int*>
143 >);
144 
145 // !indirectly_copyable<I, O>
146 static_assert(!HasSampleRange<R<int*>, int**>);
147 
148 // !uniform_random_bit_generator<remove_reference_t<Gen>>
149 static_assert(!HasSampleRange<R<int*>, int*, BadGen>);
150 
151 template <class Iter, class Sent, class Out, std::size_t N, class Gen>
152 void test_one(std::array<int, N> in, std::size_t n, Gen gen) {
153   assert(n <= static_cast<std::size_t>(N));
154 
155   auto verify_is_subsequence = [&] (auto output) {
156     auto sorted_input = in;
157     std::ranges::sort(sorted_input);
158     auto sorted_output = std::ranges::subrange(output.begin(), output.begin() + n);
159     std::ranges::sort(sorted_output);
160     assert(std::ranges::includes(sorted_input, sorted_output));
161   };
162 
163   { // (iterator, sentinel) overload.
164     auto begin = Iter(in.data());
165     auto end = Sent(Iter(in.data() + in.size()));
166     std::array<int, N> output;
167     auto out = Out(output.begin());
168 
169     std::same_as<Out> decltype(auto) result = std::ranges::sample(
170         std::move(begin), std::move(end), std::move(out), n, gen);
171     assert(base(result) == output.data() + n);
172     verify_is_subsequence(output);
173     // The output of `sample` is implementation-specific.
174   }
175 
176   { // (range) overload.
177     auto begin = Iter(in.data());
178     auto end = Sent(Iter(in.data() + in.size()));
179     std::array<int, N> output;
180     auto out = Out(output.begin());
181 
182     std::same_as<Out> decltype(auto) result = std::ranges::sample(std::ranges::subrange(
183         std::move(begin), std::move(end)), std::move(out), n, gen);
184     assert(base(result) == output.data() + n);
185     verify_is_subsequence(output);
186     // The output of `sample` is implementation-specific.
187   }
188 }
189 
190 template <class Iter, class Sent, class Out>
191 void test_iterators_iter_sent_out() {
192   RandGen gen;
193 
194   // Empty sequence.
195   test_one<Iter, Sent, Out, 0>({}, 0, gen);
196   // 1-element sequence.
197   test_one<Iter, Sent, Out, 1>({1}, 1, gen);
198   // 2-element sequence.
199   test_one<Iter, Sent, Out, 2>({1, 2}, 1, gen);
200   test_one<Iter, Sent, Out, 2>({1, 2}, 2, gen);
201   // n == 0.
202   test_one<Iter, Sent, Out, 3>({1, 2, 3}, 0, gen);
203 
204   // Longer sequence.
205   {
206     std::array input = {1, 8, 2, 3, 4, 6, 5, 7};
207     for (int i = 0; i <= static_cast<int>(input.size()); ++i){
208       test_one<Iter, Sent, Out, input.size()>(input, i, gen);
209     }
210   }
211 }
212 
213 template <class Iter, class Sent>
214 void test_iterators_iter_sent() {
215   if constexpr (std::forward_iterator<Iter>) {
216     test_iterators_iter_sent_out<Iter, Sent, cpp20_output_iterator<int*>>();
217     test_iterators_iter_sent_out<Iter, Sent, forward_iterator<int*>>();
218   }
219   test_iterators_iter_sent_out<Iter, Sent, random_access_iterator<int*>>();
220   test_iterators_iter_sent_out<Iter, Sent, contiguous_iterator<int*>>();
221   test_iterators_iter_sent_out<Iter, Sent, int*>();
222 }
223 
224 template <class Iter>
225 void test_iterators_iter() {
226   if constexpr (std::sentinel_for<Iter, Iter>) {
227     test_iterators_iter_sent<Iter, Iter>();
228   }
229   test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
230 }
231 
232 void test_iterators() {
233   test_iterators_iter<cpp20_input_iterator<int*>>();
234   test_iterators_iter<random_access_iterator<int*>>();
235   test_iterators_iter<contiguous_iterator<int*>>();
236   test_iterators_iter<int*>();
237   test_iterators_iter<const int*>();
238 }
239 
240 // Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of
241 // the given generator object.
242 template <class Gen, bool CheckConst = true>
243 void test_generator() {
244   std::array in = {1, 2, 3, 4, 5, 6, 7, 8};
245   constexpr int N = 5;
246   std::array<int, N> output;
247   auto begin = in.begin();
248   auto end = in.end();
249   auto out = output.begin();
250 
251   { // Lvalue.
252     Gen g;
253     std::ranges::sample(begin, end, out, N, g);
254     std::ranges::sample(in, out, N, g);
255   }
256 
257   if constexpr (CheckConst) { // Const lvalue.
258     const Gen g;
259     std::ranges::sample(begin, end, out, N, g);
260     std::ranges::sample(in, out, N, g);
261   }
262 
263   { // Prvalue.
264     std::ranges::sample(begin, end, out, N, Gen());
265     std::ranges::sample(in, out, N, Gen());
266   }
267 
268   { // Xvalue.
269     Gen g1, g2;
270     std::ranges::sample(begin, end, out, N, std::move(g1));
271     std::ranges::sample(in, out, N, std::move(g2));
272   }
273 }
274 
275 // Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given
276 // generator class has a const or non-const invocation operator (or both).
277 void test_generators() {
278   struct GenBase {
279     constexpr static std::size_t min() { return 0; }
280     constexpr static std::size_t max() { return 255; }
281   };
282   struct NonconstGen : GenBase {
283     std::size_t operator()() { return 1; }
284   };
285   struct ConstGen : GenBase {
286     std::size_t operator()() const { return 1; }
287   };
288   struct ConstAndNonconstGen : GenBase {
289     std::size_t operator()() { return 1; }
290     std::size_t operator()() const { return 1; }
291   };
292 
293   test_generator<ConstGen>();
294   test_generator<NonconstGen, /*CheckConst=*/false>();
295   test_generator<ConstAndNonconstGen>();
296 }
297 
298 void test() {
299   test_iterators();
300   test_generators();
301 
302   { // Stable (if `I` models `forward_iterator`).
303     struct OrderedValue {
304       int value;
305       int original_order;
306       bool operator==(const OrderedValue&) const = default;
307       auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; }
308     };
309 
310     const std::array<OrderedValue, 8> in = {{
311       {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}
312     }};
313 
314     { // (iterator, sentinel) overload.
315       std::array<OrderedValue, in.size()> out;
316       std::ranges::sample(in.begin(), in.end(), out.begin(), in.size(), RandGen());
317       assert(out == in);
318     }
319 
320     { // (range) overload.
321       std::array<OrderedValue, in.size()> out;
322       std::ranges::sample(in, out.begin(), in.size(), RandGen());
323       assert(out == in);
324     }
325   }
326 }
327 
328 int main(int, char**) {
329   test();
330   // Note: `ranges::sample` is not `constexpr`.
331 
332   return 0;
333 }
334