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> 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> 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> 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> 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 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
