From 732e2681c710147e95b390db06bf72ded13efb1e Mon Sep 17 00:00:00 2001 From: Evgeniy Stepanov Date: Wed, 13 May 2015 16:55:41 +0000 Subject: Implement std::experimental::sample. Following specification in "C++ Extensions for Library Fundamentals": http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4480.html#alg.random.sample llvm-svn: 237264 --- .../algorithms/alg.random.sample/sample.fail.cpp | 36 +++++ .../algorithms/alg.random.sample/sample.pass.cpp | 146 +++++++++++++++++++++ .../alg.random.sample/sample.stable.pass.cpp | 53 ++++++++ 3 files changed, 235 insertions(+) create mode 100644 libcxx/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp create mode 100644 libcxx/test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp create mode 100644 libcxx/test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp (limited to 'libcxx/test/std/experimental/algorithms/alg.random.sample') diff --git a/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp new file mode 100644 index 00000000000..eeb43737932 --- /dev/null +++ b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// + +// 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::experimental::sample(PopulationIterator(ia), PopulationIterator(ia + is), + SampleIterator(oa), os, g); +} + +int main() { + test, output_iterator >(); +} diff --git a/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp new file mode 100644 index 00000000000..0f0784d6ee9 --- /dev/null +++ b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp @@ -0,0 +1,146 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// + +// 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::experimental::sample(PopulationIterator(ia), + PopulationIterator(ia + is), + SampleIterator(oa), os, g); + assert(&*end - oa == std::min(os, is)); + assert(std::equal(oa, oa + os, oa1)); + end = std::experimental::sample(PopulationIterator(ia), + PopulationIterator(ia + is), + SampleIterator(oa), os, g); + assert(&*end - 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::experimental::sample(PopulationIterator(ia), PopulationIterator(ia), + SampleIterator(oa), os, g); + assert(&*end == 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::experimental::sample(PopulationIterator(ia), PopulationIterator(ia + is), + SampleIterator(oa), 0, g); + assert(&*end == 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::experimental::sample(PopulationIterator(ia), + PopulationIterator(ia + is), + SampleIterator(oa), os, g); + assert(&*end - oa == std::min(os, is)); + assert(std::equal(oa, &*end, 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/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp new file mode 100644 index 00000000000..c805c66fa5e --- /dev/null +++ b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp @@ -0,0 +1,53 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// + +// 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::experimental::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