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 29struct ReservoirSampleExpectations { 30 enum { os = 4 }; 31 static int oa1[os]; 32 static int oa2[os]; 33}; 34 35int ReservoirSampleExpectations::oa1[] = {10, 5, 9, 4}; 36int ReservoirSampleExpectations::oa2[] = {5, 2, 10, 4}; 37 38struct SelectionSampleExpectations { 39 enum { os = 4 }; 40 static int oa1[os]; 41 static int oa2[os]; 42}; 43 44int SelectionSampleExpectations::oa1[] = {1, 4, 6, 7}; 45int SelectionSampleExpectations::oa2[] = {1, 2, 6, 8}; 46 47template <class IteratorCategory> struct TestExpectations 48 : public SelectionSampleExpectations {}; 49 50template <> 51struct TestExpectations<std::input_iterator_tag> 52 : public ReservoirSampleExpectations {}; 53 54template <template<class...> class PopulationIteratorType, class PopulationItem, 55 template<class...> class SampleIteratorType, class SampleItem> 56void 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 85template <template<class...> class PopulationIteratorType, class PopulationItem, 86 template<class...> class SampleIteratorType, class SampleItem> 87void 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 100template <template<class...> class PopulationIteratorType, class PopulationItem, 101 template<class...> class SampleIteratorType, class SampleItem> 102void 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 115template <template<class...> class PopulationIteratorType, class PopulationItem, 116 template<class...> class SampleIteratorType, class SampleItem> 117void 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 140int 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