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