From e7154709e02a388db2d8dce91860f2452f4145e0 Mon Sep 17 00:00:00 2001 From: Eric Fiselier Date: Sun, 28 Aug 2016 22:14:37 +0000 Subject: Implement C++17 std::sample. This patch implements the std::sample function added to C++17 from LFTS. It also removes the std::experimental::sample implementation which now forwards to std::sample. llvm-svn: 279948 --- .../alg.random.sample/sample.fail.cpp | 41 ++++++ .../alg.random.sample/sample.pass.cpp | 148 +++++++++++++++++++++ .../alg.random.sample/sample.stable.pass.cpp | 55 ++++++++ 3 files changed, 244 insertions(+) create mode 100644 libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.fail.cpp create mode 100644 libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.pass.cpp create mode 100644 libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.stable.pass.cpp (limited to 'libcxx/test/std/algorithms') diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.fail.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.fail.cpp new file mode 100644 index 00000000000..d769ad850c3 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.fail.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// template +// SampleIterator sample(PopulationIterator first, PopulationIterator last, +// SampleIterator out, Distance n, +// UniformRandomNumberGenerator &&g); + +#include +#include +#include + +#include "test_iterators.h" + +template void test() { + int ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + const unsigned is = sizeof(ia) / sizeof(ia[0]); + const unsigned os = 4; + int oa[os]; + std::minstd_rand g; + std::sample(PopulationIterator(ia), PopulationIterator(ia + is), + SampleIterator(oa), os, g); +} + +int main() { + // expected-error@algorithm:* {{static_assert failed "SampleIterator must meet the requirements of RandomAccessIterator"}} + // expected-error@algorithm:* 2 {{does not provide a subscript operator}} + // expected-error@algorithm:* {{invalid operands}} + test, output_iterator >(); +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.pass.cpp new file mode 100644 index 00000000000..ed23d690c8f --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.pass.cpp @@ -0,0 +1,148 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// template +// SampleIterator sample(PopulationIterator first, PopulationIterator last, +// SampleIterator out, Distance n, +// UniformRandomNumberGenerator &&g); + +#include +#include +#include + +#include "test_iterators.h" + +struct ReservoirSampleExpectations { + enum { os = 4 }; + static int oa1[os]; + static int oa2[os]; +}; + +int ReservoirSampleExpectations::oa1[] = {10, 5, 9, 4}; +int ReservoirSampleExpectations::oa2[] = {5, 2, 10, 4}; + +struct SelectionSampleExpectations { + enum { os = 4 }; + static int oa1[os]; + static int oa2[os]; +}; + +int SelectionSampleExpectations::oa1[] = {1, 4, 6, 7}; +int SelectionSampleExpectations::oa2[] = {1, 2, 6, 8}; + +template struct TestExpectations + : public SelectionSampleExpectations {}; + +template <> +struct TestExpectations + : public ReservoirSampleExpectations {}; + +template class PopulationIteratorType, class PopulationItem, + template class SampleIteratorType, class SampleItem> +void test() { + typedef PopulationIteratorType PopulationIterator; + typedef SampleIteratorType SampleIterator; + PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + const unsigned is = sizeof(ia) / sizeof(ia[0]); + typedef TestExpectations::iterator_category> Expectations; + const unsigned os = Expectations::os; + SampleItem oa[os]; + const int *oa1 = Expectations::oa1; + const int *oa2 = Expectations::oa2; + std::minstd_rand g; + SampleIterator end; + end = std::sample(PopulationIterator(ia), + PopulationIterator(ia + is), + SampleIterator(oa), os, g); + assert(end.base() - oa == std::min(os, is)); + assert(std::equal(oa, oa + os, oa1)); + end = std::sample(PopulationIterator(ia), + PopulationIterator(ia + is), + SampleIterator(oa), os, std::move(g)); + assert(end.base() - oa == std::min(os, is)); + assert(std::equal(oa, oa + os, oa2)); +} + +template class PopulationIteratorType, class PopulationItem, + template class SampleIteratorType, class SampleItem> +void test_empty_population() { + typedef PopulationIteratorType PopulationIterator; + typedef SampleIteratorType SampleIterator; + PopulationItem ia[] = {42}; + const unsigned os = 4; + SampleItem oa[os]; + std::minstd_rand g; + SampleIterator end = + std::sample(PopulationIterator(ia), PopulationIterator(ia), + SampleIterator(oa), os, g); + assert(end.base() == oa); +} + +template class PopulationIteratorType, class PopulationItem, + template class SampleIteratorType, class SampleItem> +void test_empty_sample() { + typedef PopulationIteratorType PopulationIterator; + typedef SampleIteratorType SampleIterator; + PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + const unsigned is = sizeof(ia) / sizeof(ia[0]); + SampleItem oa[1]; + std::minstd_rand g; + SampleIterator end = + std::sample(PopulationIterator(ia), PopulationIterator(ia + is), + SampleIterator(oa), 0, g); + assert(end.base() == oa); +} + +template class PopulationIteratorType, class PopulationItem, + template class SampleIteratorType, class SampleItem> +void test_small_population() { + // The population size is less than the sample size. + typedef PopulationIteratorType PopulationIterator; + typedef SampleIteratorType SampleIterator; + PopulationItem ia[] = {1, 2, 3, 4, 5}; + const unsigned is = sizeof(ia) / sizeof(ia[0]); + const unsigned os = 8; + SampleItem oa[os]; + const SampleItem oa1[] = {1, 2, 3, 4, 5}; + std::minstd_rand g; + SampleIterator end; + end = std::sample(PopulationIterator(ia), + PopulationIterator(ia + is), + SampleIterator(oa), os, g); + assert(end.base() - oa == std::min(os, is)); + assert(std::equal(oa, end.base(), oa1)); +} + +int main() { + test(); + test(); + test(); + + test(); + test(); + test(); + + test_empty_population(); + test_empty_population(); + test_empty_population(); + + test_empty_sample(); + test_empty_sample(); + test_empty_sample(); + + test_small_population(); + test_small_population(); + test_small_population(); +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.stable.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.stable.pass.cpp new file mode 100644 index 00000000000..db484238c95 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.stable.pass.cpp @@ -0,0 +1,55 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// template +// SampleIterator sample(PopulationIterator first, PopulationIterator last, +// SampleIterator out, Distance n, +// UniformRandomNumberGenerator &&g); + +#include +#include +#include + +#include "test_iterators.h" + +// Stable if and only if PopulationIterator meets the requirements of a +// ForwardIterator type. +template +void test_stability(bool expect_stable) { + const unsigned kPopulationSize = 100; + int ia[kPopulationSize]; + for (unsigned i = 0; i < kPopulationSize; ++i) + ia[i] = i; + PopulationIterator first(ia); + PopulationIterator last(ia + kPopulationSize); + + const unsigned kSampleSize = 20; + int oa[kPopulationSize]; + SampleIterator out(oa); + + std::minstd_rand g; + + const int kIterations = 1000; + bool unstable = false; + for (int i = 0; i < kIterations; ++i) { + std::sample(first, last, out, kSampleSize, g); + unstable |= !std::is_sorted(oa, oa + kSampleSize); + } + assert(expect_stable == !unstable); +} + +int main() { + test_stability, output_iterator >(true); + test_stability, random_access_iterator >(false); +} -- cgit v1.2.3