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