1//===----------------------------------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is dual licensed under the MIT and the University of Illinois Open
6// Source Licenses. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10// UNSUPPORTED: c++98, c++03, c++11, c++14
11
12// <algorithm>
13
14// template <class PopulationIterator, class SampleIterator, class Distance,
15//           class UniformRandomNumberGenerator>
16// SampleIterator sample(PopulationIterator first, PopulationIterator last,
17//                       SampleIterator out, Distance n,
18//                       UniformRandomNumberGenerator &&g);
19
20#include <algorithm>
21#include <random>
22#include <type_traits>
23#include <cassert>
24#include <cstddef>
25
26#include "test_iterators.h"
27#include "test_macros.h"
28
29struct ReservoirSampleExpectations {
30  enum { os = 4 };
31  static int oa1[os];
32  static int oa2[os];
33};
34
35int ReservoirSampleExpectations::oa1[] = {10, 5, 9, 4};
36int ReservoirSampleExpectations::oa2[] = {5, 2, 10, 4};
37
38struct SelectionSampleExpectations {
39  enum { os = 4 };
40  static int oa1[os];
41  static int oa2[os];
42};
43
44int SelectionSampleExpectations::oa1[] = {1, 4, 6, 7};
45int SelectionSampleExpectations::oa2[] = {1, 2, 6, 8};
46
47template <class IteratorCategory> struct TestExpectations
48    : public SelectionSampleExpectations {};
49
50template <>
51struct TestExpectations<std::input_iterator_tag>
52    : public ReservoirSampleExpectations {};
53
54template <template<class...> class PopulationIteratorType, class PopulationItem,
55          template<class...> class SampleIteratorType, class SampleItem>
56void test() {
57  typedef PopulationIteratorType<PopulationItem *> PopulationIterator;
58  typedef SampleIteratorType<SampleItem *> SampleIterator;
59  PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
60  const unsigned is = sizeof(ia) / sizeof(ia[0]);
61  typedef TestExpectations<typename std::iterator_traits<
62      PopulationIterator>::iterator_category> Expectations;
63  const unsigned os = Expectations::os;
64  SampleItem oa[os];
65  const int *oa1 = Expectations::oa1;
66  ((void)oa1); // Prevent unused warning
67  const int *oa2 = Expectations::oa2;
68  ((void)oa2); // Prevent unused warning
69  std::minstd_rand g;
70  SampleIterator end;
71  end = std::sample(PopulationIterator(ia),
72                                  PopulationIterator(ia + is),
73                                  SampleIterator(oa), os, g);
74  assert(static_cast<std::size_t>(end.base() - oa) == std::min(os, is));
75  // sample() is deterministic but non-reproducible;
76  // its results can vary between implementations.
77  LIBCPP_ASSERT(std::equal(oa, oa + os, oa1));
78  end = std::sample(PopulationIterator(ia),
79                                  PopulationIterator(ia + is),
80                                  SampleIterator(oa), os, std::move(g));
81  assert(static_cast<std::size_t>(end.base() - oa) == std::min(os, is));
82  LIBCPP_ASSERT(std::equal(oa, oa + os, oa2));
83}
84
85template <template<class...> class PopulationIteratorType, class PopulationItem,
86          template<class...> class SampleIteratorType, class SampleItem>
87void test_empty_population() {
88  typedef PopulationIteratorType<PopulationItem *> PopulationIterator;
89  typedef SampleIteratorType<SampleItem *> SampleIterator;
90  PopulationItem ia[] = {42};
91  const unsigned os = 4;
92  SampleItem oa[os];
93  std::minstd_rand g;
94  SampleIterator end =
95      std::sample(PopulationIterator(ia), PopulationIterator(ia),
96                                SampleIterator(oa), os, g);
97  assert(end.base() == oa);
98}
99
100template <template<class...> class PopulationIteratorType, class PopulationItem,
101          template<class...> class SampleIteratorType, class SampleItem>
102void test_empty_sample() {
103  typedef PopulationIteratorType<PopulationItem *> PopulationIterator;
104  typedef SampleIteratorType<SampleItem *> SampleIterator;
105  PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
106  const unsigned is = sizeof(ia) / sizeof(ia[0]);
107  SampleItem oa[1];
108  std::minstd_rand g;
109  SampleIterator end =
110      std::sample(PopulationIterator(ia), PopulationIterator(ia + is),
111                                SampleIterator(oa), 0, g);
112  assert(end.base() == oa);
113}
114
115template <template<class...> class PopulationIteratorType, class PopulationItem,
116          template<class...> class SampleIteratorType, class SampleItem>
117void test_small_population() {
118  // The population size is less than the sample size.
119  typedef PopulationIteratorType<PopulationItem *> PopulationIterator;
120  typedef SampleIteratorType<SampleItem *> SampleIterator;
121  PopulationItem ia[] = {1, 2, 3, 4, 5};
122  const unsigned is = sizeof(ia) / sizeof(ia[0]);
123  const unsigned os = 8;
124  SampleItem oa[os];
125  const SampleItem oa1[] = {1, 2, 3, 4, 5};
126  std::minstd_rand g;
127  SampleIterator end;
128  end = std::sample(PopulationIterator(ia),
129                                  PopulationIterator(ia + is),
130                                  SampleIterator(oa), os, g);
131  assert(static_cast<std::size_t>(end.base() - oa) == std::min(os, is));
132  typedef typename std::iterator_traits<PopulationIterator>::iterator_category PopulationCategory;
133  if (std::is_base_of<std::forward_iterator_tag, PopulationCategory>::value) {
134    assert(std::equal(oa, end.base(), oa1));
135  } else {
136    assert(std::is_permutation(oa, end.base(), oa1));
137  }
138}
139
140int main() {
141  test<input_iterator, int, random_access_iterator, int>();
142  test<forward_iterator, int, output_iterator, int>();
143  test<forward_iterator, int, random_access_iterator, int>();
144
145  test<input_iterator, int, random_access_iterator, double>();
146  test<forward_iterator, int, output_iterator, double>();
147  test<forward_iterator, int, random_access_iterator, double>();
148
149  test_empty_population<input_iterator, int, random_access_iterator, int>();
150  test_empty_population<forward_iterator, int, output_iterator, int>();
151  test_empty_population<forward_iterator, int, random_access_iterator, int>();
152
153  test_empty_sample<input_iterator, int, random_access_iterator, int>();
154  test_empty_sample<forward_iterator, int, output_iterator, int>();
155  test_empty_sample<forward_iterator, int, random_access_iterator, int>();
156
157  test_small_population<input_iterator, int, random_access_iterator, int>();
158  test_small_population<forward_iterator, int, output_iterator, int>();
159  test_small_population<forward_iterator, int, random_access_iterator, int>();
160}
161