160 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++1410 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 28struct ReservoirSampleExpectations {29 enum { os = 4 };30 static int oa1[os];31 static int oa2[os];32};33 34int ReservoirSampleExpectations::oa1[] = {10, 5, 9, 4};35int ReservoirSampleExpectations::oa2[] = {5, 2, 10, 4};36 37struct SelectionSampleExpectations {38 enum { os = 4 };39 static int oa1[os];40 static int oa2[os];41};42 43int SelectionSampleExpectations::oa1[] = {1, 4, 6, 7};44int SelectionSampleExpectations::oa2[] = {1, 2, 6, 8};45 46template <class IteratorCategory> struct TestExpectations47 : public SelectionSampleExpectations {};48 49template <>50struct TestExpectations<std::input_iterator_tag>51 : public ReservoirSampleExpectations {};52 53template <template<class...> class PopulationIteratorType, class PopulationItem,54 template<class...> class SampleIteratorType, class SampleItem>55void 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 warning66 const int *oa2 = Expectations::oa2;67 ((void)oa2); // Prevent unused warning68 std::minstd_rand g;69 SampleIterator end = std::sample(PopulationIterator(ia),70 PopulationIterator(ia + is),71 SampleIterator(oa), os, g);72 assert(static_cast<std::size_t>(base(end) - oa) == std::min(os, is));73 // sample() is deterministic but non-reproducible;74 // its results can vary between implementations.75 LIBCPP_ASSERT(std::equal(oa, oa + os, oa1));76 end = std::sample(PopulationIterator(ia),77 PopulationIterator(ia + is),78 SampleIterator(oa), os, std::move(g));79 assert(static_cast<std::size_t>(base(end) - oa) == std::min(os, is));80 LIBCPP_ASSERT(std::equal(oa, oa + os, oa2));81}82 83template <template<class...> class PopulationIteratorType, class PopulationItem,84 template<class...> class SampleIteratorType, class SampleItem>85void test_empty_population() {86 typedef PopulationIteratorType<PopulationItem *> PopulationIterator;87 typedef SampleIteratorType<SampleItem *> SampleIterator;88 PopulationItem ia[] = {42};89 const unsigned os = 4;90 SampleItem oa[os];91 std::minstd_rand g;92 SampleIterator end =93 std::sample(PopulationIterator(ia), PopulationIterator(ia),94 SampleIterator(oa), os, g);95 assert(base(end) == oa);96}97 98template <template<class...> class PopulationIteratorType, class PopulationItem,99 template<class...> class SampleIteratorType, class SampleItem>100void test_empty_sample() {101 typedef PopulationIteratorType<PopulationItem *> PopulationIterator;102 typedef SampleIteratorType<SampleItem *> SampleIterator;103 PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};104 const unsigned is = sizeof(ia) / sizeof(ia[0]);105 SampleItem oa[1];106 std::minstd_rand g;107 SampleIterator end =108 std::sample(PopulationIterator(ia), PopulationIterator(ia + is),109 SampleIterator(oa), 0, g);110 assert(base(end) == oa);111}112 113template <template<class...> class PopulationIteratorType, class PopulationItem,114 template<class...> class SampleIteratorType, class SampleItem>115void test_small_population() {116 // The population size is less than the sample size.117 typedef PopulationIteratorType<PopulationItem *> PopulationIterator;118 typedef SampleIteratorType<SampleItem *> SampleIterator;119 PopulationItem ia[] = {1, 2, 3, 4, 5};120 const unsigned is = sizeof(ia) / sizeof(ia[0]);121 const unsigned os = 8;122 SampleItem oa[os];123 const SampleItem oa1[] = {1, 2, 3, 4, 5};124 std::minstd_rand g;125 SampleIterator end = std::sample(PopulationIterator(ia),126 PopulationIterator(ia + is),127 SampleIterator(oa), os, g);128 assert(static_cast<std::size_t>(base(end) - oa) == std::min(os, is));129 typedef typename std::iterator_traits<PopulationIterator>::iterator_category PopulationCategory;130 if (std::is_base_of<std::forward_iterator_tag, PopulationCategory>::value) {131 assert(std::equal(oa, base(end), oa1));132 } else {133 assert(std::is_permutation(oa, base(end), oa1));134 }135}136 137int main(int, char**) {138 test<cpp17_input_iterator, int, random_access_iterator, int>();139 test<forward_iterator, int, cpp17_output_iterator, int>();140 test<forward_iterator, int, random_access_iterator, int>();141 142 test<cpp17_input_iterator, int, random_access_iterator, double>();143 test<forward_iterator, int, cpp17_output_iterator, double>();144 test<forward_iterator, int, random_access_iterator, double>();145 146 test_empty_population<cpp17_input_iterator, int, random_access_iterator, int>();147 test_empty_population<forward_iterator, int, cpp17_output_iterator, int>();148 test_empty_population<forward_iterator, int, random_access_iterator, int>();149 150 test_empty_sample<cpp17_input_iterator, int, random_access_iterator, int>();151 test_empty_sample<forward_iterator, int, cpp17_output_iterator, int>();152 test_empty_sample<forward_iterator, int, random_access_iterator, int>();153 154 test_small_population<cpp17_input_iterator, int, random_access_iterator, int>();155 test_small_population<forward_iterator, int, cpp17_output_iterator, int>();156 test_small_population<forward_iterator, int, random_access_iterator, int>();157 158 return 0;159}160