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
29 struct ReservoirSampleExpectations {
30 enum { os = 4 };
31 static int oa1[os];
32 static int oa2[os];
33 };
34
35 int ReservoirSampleExpectations::oa1[] = {10, 5, 9, 4};
36 int ReservoirSampleExpectations::oa2[] = {5, 2, 10, 4};
37
38 struct SelectionSampleExpectations {
39 enum { os = 4 };
40 static int oa1[os];
41 static int oa2[os];
42 };
43
44 int SelectionSampleExpectations::oa1[] = {1, 4, 6, 7};
45 int SelectionSampleExpectations::oa2[] = {1, 2, 6, 8};
46
47 template <class IteratorCategory> struct TestExpectations
48 : public SelectionSampleExpectations {};
49
50 template <>
51 struct TestExpectations<std::input_iterator_tag>
52 : public ReservoirSampleExpectations {};
53
54 template <template<class...> class PopulationIteratorType, class PopulationItem,
55 template<class...> class SampleIteratorType, class SampleItem>
test()56 void 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
85 template <template<class...> class PopulationIteratorType, class PopulationItem,
86 template<class...> class SampleIteratorType, class SampleItem>
test_empty_population()87 void 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
100 template <template<class...> class PopulationIteratorType, class PopulationItem,
101 template<class...> class SampleIteratorType, class SampleItem>
test_empty_sample()102 void 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
115 template <template<class...> class PopulationIteratorType, class PopulationItem,
116 template<class...> class SampleIteratorType, class SampleItem>
test_small_population()117 void 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
main()140 int 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