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