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