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 
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>
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(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(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>
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>
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>
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(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 
139 int main() {
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