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
37class RandGen {
38public:
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
47private:
48 bool flip = false;
49};
50
51static_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`.
54LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
55
56struct 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};
61static_assert(!std::uniform_random_bit_generator<BadGen>);
62
63// Test constraints of the (iterator, sentinel) overload.
64// ======================================================
65
66template <class Iter = int*, class Sent = int*, class Out = int*, class Gen = RandGen>
67concept 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
73static_assert(HasSampleIter<int*, int*, int*, RandGen>);
74
75// !input_iterator<I>
76static_assert(!HasSampleIter<InputIteratorNotDerivedFrom>);
77static_assert(!HasSampleIter<InputIteratorNotIndirectlyReadable>);
78static_assert(!HasSampleIter<InputIteratorNotInputOrOutputIterator>);
79
80// !sentinel_for<S, I>
81static_assert(!HasSampleIter<int*, SentinelForNotSemiregular>);
82static_assert(!HasSampleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
83
84// !weakly_incrementable<O>
85static_assert(!HasSampleIter<int*, int*, WeaklyIncrementableNotMovable>);
86
87// (forward_iterator<I> || random_access_iterator<O>)
88static_assert(HasSampleIter<
89 forward_iterator<int*>, forward_iterator<int*>,
90 cpp20_output_iterator<int*>
91>);
92static_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>)
97static_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>
103static_assert(!HasSampleIter<int*, int*, int**>);
104
105// !uniform_random_bit_generator<remove_reference_t<Gen>>
106static_assert(!HasSampleIter<int*, int*, int*, BadGen>);
107
108// Test constraints of the (range) overload.
109// =========================================
110
111template <class Range, class Out = int*, class Gen = RandGen>
112concept 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
117template <class T>
118using R = UncheckedRange<T>;
119
120static_assert(HasSampleRange<R<int*>, int*, RandGen>);
121
122// !input_range<R>
123static_assert(!HasSampleRange<InputRangeNotDerivedFrom>);
124static_assert(!HasSampleRange<InputRangeNotIndirectlyReadable>);
125static_assert(!HasSampleRange<InputRangeNotInputOrOutputIterator>);
126
127// !weakly_incrementable<O>
128static_assert(!HasSampleRange<R<int*>, WeaklyIncrementableNotMovable>);
129
130// (forward_range<R> || random_access_iterator<O>)
131static_assert(HasSampleRange<
132 R<forward_iterator<int*>>,
133 cpp20_output_iterator<int*>
134>);
135static_assert(HasSampleRange<
136 R<cpp20_input_iterator<int*>>,
137 random_access_iterator<int*>
138>);
139// !(forward_range<R> || random_access_iterator<O>)
140static_assert(!HasSampleRange<
141 R<cpp20_input_iterator<int*>>,
142 cpp20_output_iterator<int*>
143>);
144
145// !indirectly_copyable<I, O>
146static_assert(!HasSampleRange<R<int*>, int**>);
147
148// !uniform_random_bit_generator<remove_reference_t<Gen>>
149static_assert(!HasSampleRange<R<int*>, int*, BadGen>);
150
151template <class Iter, class Sent, class Out, std::size_t N, class Gen>
152void 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.data());
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.data());
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
190template <class Iter, class Sent, class Out>
191void 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
213template <class Iter, class Sent>
214void 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
224template <class Iter>
225void 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
232void 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.
242template <class Gen, bool CheckConst = true>
243void 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).
277void 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
298void 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 = {._M_elems: {
311 {.value: 1, .original_order: 1}, {.value: 1, .original_order: 2}, {.value: 1, .original_order: 3}, {.value: 1, .original_order: 4}, {.value: 1, .original_order: 5}, {.value: 1, .original_order: 6}, {.value: 1, .original_order: 7}, {.value: 1, .original_order: 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
328int main(int, char**) {
329 test();
330 // Note: `ranges::sample` is not `constexpr`.
331
332 return 0;
333}
334

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp