Index: include/experimental/algorithm =================================================================== --- include/experimental/algorithm +++ include/experimental/algorithm @@ -0,0 +1,97 @@ +// -*- C++ -*- +//===-------------------------- algorithm ---------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM +#define _LIBCPP_EXPERIMENTAL_ALGORITHM + +/* + experimental/algorithm synopsis + +#include + +namespace std { +namespace experimental { +inline namespace fundamentals_v1 { + +template +ForwardIterator search(ForwardIterator first, ForwardIterator last, + const Searcher &searcher); +template +SampleIterator sample(PopulationIterator first, PopulationIterator last, + SampleIterator out, Distance n, + UniformRandomNumberGenerator &&g); + +} // namespace fundamentals_v1 +} // namespace experimental +} // namespace std + +*/ + +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_LFTS + +template +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, _UniformRandomNumberGenerator &&__g, + input_iterator_tag, random_access_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 +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, _UniformRandomNumberGenerator &&__g, + forward_iterator_tag, output_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 +_SampleIterator sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __out, + _Distance __n, _UniformRandomNumberGenerator &&__g) { + return _VSTD_LFTS::__sample( + __first, __last, __out, __n, + _VSTD::forward<_UniformRandomNumberGenerator>(__g), + typename iterator_traits<_PopulationIterator>::iterator_category(), + typename iterator_traits<_SampleIterator>::iterator_category()); +} + +_LIBCPP_END_NAMESPACE_LFTS + +#endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ Index: test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp =================================================================== --- test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp +++ 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>(); +} Index: test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp =================================================================== --- test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp +++ test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp @@ -0,0 +1,147 @@ +//===----------------------------------------------------------------------===// +// +// 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 { + static constexpr unsigned os = 4; + static constexpr int oa1[os] = {10, 5, 9, 4}; + static constexpr int oa2[os] = {5, 2, 10, 4}; +}; + +constexpr int ReservoirSampleExpectations::oa1[]; +constexpr int ReservoirSampleExpectations::oa2[]; + +struct SelectionSampleExpectations { + static constexpr unsigned os = 4; + static constexpr int oa1[os] = {1, 4, 6, 7}; + static constexpr int oa2[os] = {1, 2, 6, 8}; +}; + +constexpr int SelectionSampleExpectations::oa1[]; +constexpr int SelectionSampleExpectations::oa2[]; + +template struct TestExpectations; +template <> +struct TestExpectations + : public ReservoirSampleExpectations {}; +template <> +struct TestExpectations + : public SelectionSampleExpectations {}; + +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(); +} Index: test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp =================================================================== --- test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp +++ 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); +}