diff options
Diffstat (limited to 'libcxx/test/std/algorithms')
3 files changed, 244 insertions, 0 deletions
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 + +// <algorithm> + +// template <class PopulationIterator, class SampleIterator, class Distance, +// class UniformRandomNumberGenerator> +// SampleIterator sample(PopulationIterator first, PopulationIterator last, +// SampleIterator out, Distance n, +// UniformRandomNumberGenerator &&g); + +#include <algorithm> +#include <random> +#include <cassert> + +#include "test_iterators.h" + +template <class PopulationIterator, class SampleIterator> 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<input_iterator<int *>, output_iterator<int *> >(); +} 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 + +// <algorithm> + +// template <class PopulationIterator, class SampleIterator, class Distance, +// class UniformRandomNumberGenerator> +// SampleIterator sample(PopulationIterator first, PopulationIterator last, +// SampleIterator out, Distance n, +// UniformRandomNumberGenerator &&g); + +#include <algorithm> +#include <random> +#include <cassert> + +#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 <class IteratorCategory> struct TestExpectations + : public SelectionSampleExpectations {}; + +template <> +struct TestExpectations<std::input_iterator_tag> + : public ReservoirSampleExpectations {}; + +template <template<class...> class PopulationIteratorType, class PopulationItem, + template<class...> class SampleIteratorType, class SampleItem> +void test() { + typedef PopulationIteratorType<PopulationItem *> PopulationIterator; + typedef SampleIteratorType<SampleItem *> SampleIterator; + PopulationItem ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + const unsigned is = sizeof(ia) / sizeof(ia[0]); + typedef TestExpectations<typename std::iterator_traits< + PopulationIterator>::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 <template<class...> class PopulationIteratorType, class PopulationItem, + template<class...> class SampleIteratorType, class SampleItem> +void test_empty_population() { + typedef PopulationIteratorType<PopulationItem *> PopulationIterator; + typedef SampleIteratorType<SampleItem *> 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 <template<class...> class PopulationIteratorType, class PopulationItem, + template<class...> class SampleIteratorType, class SampleItem> +void test_empty_sample() { + typedef PopulationIteratorType<PopulationItem *> PopulationIterator; + typedef SampleIteratorType<SampleItem *> 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 <template<class...> class PopulationIteratorType, class PopulationItem, + template<class...> class SampleIteratorType, class SampleItem> +void test_small_population() { + // The population size is less than the sample size. + typedef PopulationIteratorType<PopulationItem *> PopulationIterator; + typedef SampleIteratorType<SampleItem *> 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<input_iterator, int, random_access_iterator, int>(); + test<forward_iterator, int, output_iterator, int>(); + test<forward_iterator, int, random_access_iterator, int>(); + + test<input_iterator, int, random_access_iterator, double>(); + test<forward_iterator, int, output_iterator, double>(); + test<forward_iterator, int, random_access_iterator, double>(); + + test_empty_population<input_iterator, int, random_access_iterator, int>(); + test_empty_population<forward_iterator, int, output_iterator, int>(); + test_empty_population<forward_iterator, int, random_access_iterator, int>(); + + test_empty_sample<input_iterator, int, random_access_iterator, int>(); + test_empty_sample<forward_iterator, int, output_iterator, int>(); + test_empty_sample<forward_iterator, int, random_access_iterator, int>(); + + test_small_population<input_iterator, int, random_access_iterator, int>(); + test_small_population<forward_iterator, int, output_iterator, int>(); + test_small_population<forward_iterator, int, random_access_iterator, int>(); +} 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 + +// <algorithm> + +// template <class PopulationIterator, class SampleIterator, class Distance, +// class UniformRandomNumberGenerator> +// SampleIterator sample(PopulationIterator first, PopulationIterator last, +// SampleIterator out, Distance n, +// UniformRandomNumberGenerator &&g); + +#include <algorithm> +#include <random> +#include <cassert> + +#include "test_iterators.h" + +// Stable if and only if PopulationIterator meets the requirements of a +// ForwardIterator type. +template <class PopulationIterator, class SampleIterator> +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<forward_iterator<int *>, output_iterator<int *> >(true); + test_stability<input_iterator<int *>, random_access_iterator<int *> >(false); +} |
