1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // UNSUPPORTED: c++98, c++03, c++11, c++14 10 11 // <algorithm> 12 13 // template <class PopulationIterator, class SampleIterator, class Distance, 14 // class UniformRandomNumberGenerator> 15 // SampleIterator sample(PopulationIterator first, PopulationIterator last, 16 // SampleIterator out, Distance n, 17 // UniformRandomNumberGenerator &&g); 18 19 #include <algorithm> 20 #include <random> 21 #include <type_traits> 22 #include <cassert> 23 #include <cstddef> 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(static_cast<std::size_t>(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(static_cast<std::size_t>(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(static_cast<std::size_t>(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