diff options
7 files changed, 333 insertions, 62 deletions
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 867383c37ef..3bafd3df79d 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -288,6 +288,12 @@ template <class RandomAccessIterator, class RandomNumberGenerator> random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); // deprecated in C++14 +template<class PopulationIterator, class SampleIterator, + class Distance, class UniformRandomBitGenerator> + SampleIterator sample(PopulationIterator first, PopulationIterator last, + SampleIterator out, Distance n, + UniformRandomBitGenerator&& g); // C++17 + template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g); @@ -3142,6 +3148,78 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, } } +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +_LIBCPP_INLINE_VISIBILITY +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, + _UniformRandomNumberGenerator & __g, + input_iterator_tag) { + + _Distance __k = 0; + for (; __first != __last && __k < __n; ++__first, (void)++__k) + __out[__k] = *__first; + _Distance __sz = __k; + for (; __first != __last; ++__first, (void)++__k) { + _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); + if (__r < __sz) + __out[__r] = *__first; + } + return __out + _VSTD::min(__n, __k); +} + +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +_LIBCPP_INLINE_VISIBILITY +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, + _UniformRandomNumberGenerator& __g, + forward_iterator_tag) { + _Distance __unsampled_sz = _VSTD::distance(__first, __last); + for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { + _Distance __r = + _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); + if (__r < __n) { + *__out++ = *__first; + --__n; + } + } + return __out; +} + +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +_LIBCPP_INLINE_VISIBILITY +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, _UniformRandomNumberGenerator& __g) { + typedef typename iterator_traits<_PopulationIterator>::iterator_category + _PopCategory; + typedef typename iterator_traits<_PopulationIterator>::difference_type + _Difference; + static_assert(__is_forward_iterator<_PopulationIterator>::value || + __is_random_access_iterator<_SampleIterator>::value, + "SampleIterator must meet the requirements of RandomAccessIterator"); + typedef typename common_type<_Distance, _Difference>::type _CommonType; + _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); + return _VSTD::__sample( + __first, __last, __out, _CommonType(__n), + __g, _PopCategory()); +} + +#if _LIBCPP_STD_VER > 14 +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +inline _LIBCPP_INLINE_VISIBILITY +_SampleIterator sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, _UniformRandomNumberGenerator&& __g) { + return _VSTD::__sample(__first, __last, __out, __n, __g); +} +#endif // _LIBCPP_STD_VER > 14 + template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES diff --git a/libcxx/include/experimental/algorithm b/libcxx/include/experimental/algorithm index 10eafbdbabe..392ca1fa41c 100644 --- a/libcxx/include/experimental/algorithm +++ b/libcxx/include/experimental/algorithm @@ -58,64 +58,11 @@ _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searc template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator> -_LIBCPP_INLINE_VISIBILITY -_SampleIterator __sample(_PopulationIterator __first, - _PopulationIterator __last, _SampleIterator __out, - _Distance __n, - _UniformRandomNumberGenerator &&__g, - input_iterator_tag) { - - _Distance __k = 0; - for (; __first != __last && __k < __n; ++__first, (void)++__k) - __out[__k] = *__first; - _Distance __sz = __k; - for (; __first != __last; ++__first, (void)++__k) { - _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); - if (__r < __sz) - __out[__r] = *__first; - } - return __out + _VSTD::min(__n, __k); -} - -template <class _PopulationIterator, class _SampleIterator, class _Distance, - class _UniformRandomNumberGenerator> -_LIBCPP_INLINE_VISIBILITY -_SampleIterator __sample(_PopulationIterator __first, - _PopulationIterator __last, _SampleIterator __out, - _Distance __n, - _UniformRandomNumberGenerator &&__g, - forward_iterator_tag) { - _Distance __unsampled_sz = _VSTD::distance(__first, __last); - for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { - _Distance __r = - _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); - if (__r < __n) { - *__out++ = *__first; - --__n; - } - } - return __out; -} - -template <class _PopulationIterator, class _SampleIterator, class _Distance, - class _UniformRandomNumberGenerator> -_LIBCPP_INLINE_VISIBILITY -_SampleIterator sample(_PopulationIterator __first, - _PopulationIterator __last, _SampleIterator __out, - _Distance __n, _UniformRandomNumberGenerator &&__g) { - typedef typename iterator_traits<_PopulationIterator>::iterator_category - _PopCategory; - typedef typename iterator_traits<_PopulationIterator>::difference_type - _Difference; - static_assert(__is_forward_iterator<_PopulationIterator>::value || - __is_random_access_iterator<_SampleIterator>::value, - "SampleIterator must meet the requirements of RandomAccessIterator"); - typedef typename common_type<_Distance, _Difference>::type _CommonType; - _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); - return _VSTD_LFTS::__sample( - __first, __last, __out, _CommonType(__n), - _VSTD::forward<_UniformRandomNumberGenerator>(__g), - _PopCategory()); +inline _LIBCPP_INLINE_VISIBILITY +_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, + _SampleIterator __out, _Distance __n, + _UniformRandomNumberGenerator &&__g) { + return _VSTD::__sample(__first, __last, __out, __n, __g); } _LIBCPP_END_NAMESPACE_LFTS 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); +} 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 index b27135ac7c0..85ff8e15d16 100644 --- a/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp +++ b/libcxx/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +// UNSUPPORTED: c++98, c++03 + // <algorithm> // template <class PopulationIterator, class SampleIterator, class Distance, @@ -32,8 +34,8 @@ template <class PopulationIterator, class SampleIterator> void test() { } int main() { - // expected-error@experimental/algorithm:* {{static_assert failed "SampleIterator must meet the requirements of RandomAccessIterator"}} - // expected-error@experimental/algorithm:* 2 {{does not provide a subscript operator}} - // expected-error@experimental/algorithm:* {{invalid operands}} + // 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/support/test_iterators.h b/libcxx/test/support/test_iterators.h index fb5c06ad943..379933eb51b 100644 --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -57,7 +57,7 @@ template <class It, class ItTraits = It> class input_iterator { - using Traits = std::iterator_traits<ItTraits>; + typedef std::iterator_traits<ItTraits> Traits; It it_; template <class U, class T> friend class input_iterator; |
