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++98, c++03, c++11, c++14
10 
11 // <algorithm>
12 
13 // template <class PopulationIterator, class SampleIterator, class Distance,
14 //           class UniformRandomNumberGenerator>
15 // SampleIterator sample(PopulationIterator first, PopulationIterator last,
16 //                       SampleIterator out, Distance n,
17 //                       UniformRandomNumberGenerator &&g);
18 
19 #include <algorithm>
20 #include <random>
21 #include <cassert>
22 
23 #include "test_iterators.h"
24 
25 // Stable if and only if PopulationIterator meets the requirements of a
26 // ForwardIterator type.
27 template <class PopulationIterator, class SampleIterator>
28 void test_stability(bool expect_stable) {
29   const unsigned kPopulationSize = 100;
30   int ia[kPopulationSize];
31   for (unsigned i = 0; i < kPopulationSize; ++i)
32     ia[i] = i;
33   PopulationIterator first(ia);
34   PopulationIterator last(ia + kPopulationSize);
35 
36   const unsigned kSampleSize = 20;
37   int oa[kPopulationSize];
38   SampleIterator out(oa);
39 
40   std::minstd_rand g;
41 
42   const int kIterations = 1000;
43   bool unstable = false;
44   for (int i = 0; i < kIterations; ++i) {
45     std::sample(first, last, out, kSampleSize, g);
46     unstable |= !std::is_sorted(oa, oa + kSampleSize);
47   }
48   assert(expect_stable == !unstable);
49 }
50 
51 int main() {
52   test_stability<forward_iterator<int *>, output_iterator<int *> >(true);
53   test_stability<input_iterator<int *>, random_access_iterator<int *> >(false);
54 }
55