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:
min()40 constexpr static size_t min() { return 0; }
max()41 constexpr static size_t max() { return 255; }
42
operator ()()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 {
minBadGen58 constexpr static size_t min() { return 255; }
maxBadGen59 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>
test_one(std::array<int,N> in,size_t n,Gen 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>
test_iterators_iter_sent_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>
test_iterators_iter_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>
test_iterators_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
test_iterators()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>
test_generator()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).
test_generators()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
test()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
main(int,char **)329 int main(int, char**) {
330 test();
331 // Note: `ranges::sample` is not `constexpr`.
332
333 return 0;
334 }
335