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
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_macros.h"
24 #include "test_iterators.h"
25 
26 // Stable if and only if PopulationIterator meets the requirements of a
27 // ForwardIterator type.
28 template <class PopulationIterator, class SampleIterator>
29 void test_stability(bool expect_stable) {
30   const unsigned kPopulationSize = 100;
31   int ia[kPopulationSize];
32   for (unsigned i = 0; i < kPopulationSize; ++i)
33     ia[i] = i;
34   PopulationIterator first(ia);
35   PopulationIterator last(ia + kPopulationSize);
36 
37   const unsigned kSampleSize = 20;
38   int oa[kPopulationSize];
39   SampleIterator out(oa);
40 
41   std::minstd_rand g;
42 
43   const int kIterations = 1000;
44   bool unstable = false;
45   for (int i = 0; i < kIterations; ++i) {
46     std::sample(first, last, out, kSampleSize, g);
47     unstable |= !std::is_sorted(oa, oa + kSampleSize);
48   }
49   assert(expect_stable == !unstable);
50 }
51 
52 int main(int, char**) {
53   test_stability<forward_iterator<int *>, output_iterator<int *> >(true);
54   test_stability<input_iterator<int *>, random_access_iterator<int *> >(false);
55 
56   return 0;
57 }
58