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> 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 const int *oa2 = Expectations::oa2; 62 std::minstd_rand g; 63 SampleIterator end; 64 end = std::experimental::sample(PopulationIterator(ia), 65 PopulationIterator(ia + is), 66 SampleIterator(oa), os, g); 67 assert(&*end - oa == std::min(os, is)); 68 assert(std::equal(oa, oa + os, oa1)); 69 end = std::experimental::sample(PopulationIterator(ia), 70 PopulationIterator(ia + is), 71 SampleIterator(oa), os, g); 72 assert(&*end - oa == std::min(os, is)); 73 assert(std::equal(oa, oa + os, oa2)); 74 } 75 76 template <template<class> class PopulationIteratorType, class PopulationItem, 77 template<class> class SampleIteratorType, class SampleItem> 78 void test_empty_population() { 79 typedef PopulationIteratorType<PopulationItem *> PopulationIterator; 80 typedef SampleIteratorType<SampleItem *> SampleIterator; 81 PopulationItem ia[] = {42}; 82 const unsigned os = 4; 83 SampleItem oa[os]; 84 std::minstd_rand g; 85 SampleIterator end = 86 std::experimental::sample(PopulationIterator(ia), PopulationIterator(ia), 87 SampleIterator(oa), os, g); 88 assert(&*end == oa); 89 } 90 91 template <template<class> class PopulationIteratorType, class PopulationItem, 92 template<class> class SampleIteratorType, class SampleItem> 93 void test_empty_sample() { 94 typedef PopulationIteratorType<PopulationItem *> PopulationIterator; 95 typedef SampleIteratorType<SampleItem *> SampleIterator; 96 PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 97 const unsigned is = sizeof(ia) / sizeof(ia[0]); 98 SampleItem oa[1]; 99 std::minstd_rand g; 100 SampleIterator end = 101 std::experimental::sample(PopulationIterator(ia), PopulationIterator(ia + is), 102 SampleIterator(oa), 0, g); 103 assert(&*end == oa); 104 } 105 106 template <template<class> class PopulationIteratorType, class PopulationItem, 107 template<class> class SampleIteratorType, class SampleItem> 108 void test_small_population() { 109 // The population size is less than the sample size. 110 typedef PopulationIteratorType<PopulationItem *> PopulationIterator; 111 typedef SampleIteratorType<SampleItem *> SampleIterator; 112 PopulationItem ia[] = {1, 2, 3, 4, 5}; 113 const unsigned is = sizeof(ia) / sizeof(ia[0]); 114 const unsigned os = 8; 115 SampleItem oa[os]; 116 const SampleItem oa1[] = {1, 2, 3, 4, 5}; 117 std::minstd_rand g; 118 SampleIterator end; 119 end = std::experimental::sample(PopulationIterator(ia), 120 PopulationIterator(ia + is), 121 SampleIterator(oa), os, g); 122 assert(&*end - oa == std::min(os, is)); 123 assert(std::equal(oa, &*end, oa1)); 124 } 125 126 int main() { 127 test<input_iterator, int, random_access_iterator, int>(); 128 test<forward_iterator, int, output_iterator, int>(); 129 test<forward_iterator, int, random_access_iterator, int>(); 130 131 test<input_iterator, int, random_access_iterator, double>(); 132 test<forward_iterator, int, output_iterator, double>(); 133 test<forward_iterator, int, random_access_iterator, double>(); 134 135 test_empty_population<input_iterator, int, random_access_iterator, int>(); 136 test_empty_population<forward_iterator, int, output_iterator, int>(); 137 test_empty_population<forward_iterator, int, random_access_iterator, int>(); 138 139 test_empty_sample<input_iterator, int, random_access_iterator, int>(); 140 test_empty_sample<forward_iterator, int, output_iterator, int>(); 141 test_empty_sample<forward_iterator, int, random_access_iterator, int>(); 142 143 test_small_population<input_iterator, int, random_access_iterator, int>(); 144 test_small_population<forward_iterator, int, output_iterator, int>(); 145 test_small_population<forward_iterator, int, random_access_iterator, int>(); 146 } 147
