http://reviews.llvm.org/D9044
Files:
include/experimental/algorithm
test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp
test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp
test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp
EMAIL PREFERENCES
http://reviews.llvm.org/settings/panel/emailpreferences/
Index: include/experimental/algorithm
===================================================================
--- include/experimental/algorithm
+++ include/experimental/algorithm
@@ -0,0 +1,93 @@
+// -*- 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 <algorithm>
+
+namespace std {
+namespace experimental {
+inline namespace fundamentals_v1 {
+
+template <class ForwardIterator, class Searcher>
+ForwardIterator search(ForwardIterator first, ForwardIterator last,
+ const Searcher &searcher);
+template <class PopulationIterator, class SampleIterator, class Distance,
+ class UniformRandomNumberGenerator>
+SampleIterator sample(PopulationIterator first, PopulationIterator last,
+ SampleIterator out, Distance n,
+ UniformRandomNumberGenerator &&g);
+
+} // namespace fundamentals_v1
+} // namespace experimental
+} // namespace std
+
+*/
+
+#include <experimental/__config>
+#include <algorithm>
+
+_LIBCPP_BEGIN_NAMESPACE_LFTS
+
+template <class _PopulationIterator, class _SampleIterator, class _Distance,
+ class _UniformRandomNumberGenerator>
+_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 <class _PopulationIterator, class _SampleIterator, class _Distance,
+ class _UniformRandomNumberGenerator>
+_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 <class _PopulationIterator, class _SampleIterator, class _Distance,
+ class _UniformRandomNumberGenerator>
+_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.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template <class PopulationIterator, class SampleIterator, class Distance,
+// class UniformRandomNumberGenerator>
+// SampleIterator sample(PopulationIterator first, PopulationIterator last,
+// SampleIterator out, Distance n,
+// UniformRandomNumberGenerator &&g);
+
+#include <experimental/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::experimental::sample(PopulationIterator(ia), PopulationIterator(ia + is),
+ SampleIterator(oa), os, g);
+}
+
+int main() {
+ test<input_iterator<int *>, output_iterator<int *>>();
+}
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.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template <class PopulationIterator, class SampleIterator, class Distance,
+// class UniformRandomNumberGenerator>
+// SampleIterator sample(PopulationIterator first, PopulationIterator last,
+// SampleIterator out, Distance n,
+// UniformRandomNumberGenerator &&g);
+
+#include <experimental/algorithm>
+#include <random>
+#include <cassert>
+
+#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 <class IteratorCategory> struct TestExpectations;
+template <>
+struct TestExpectations<std::random_access_iterator_tag>
+ : public ReservoirSampleExpectations {};
+template <>
+struct TestExpectations<std::output_iterator_tag>
+ : public SelectionSampleExpectations {};
+
+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<
+ SampleIterator>::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 <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::experimental::sample(PopulationIterator(ia), PopulationIterator(ia),
+ SampleIterator(oa), os, g);
+ assert(&*end == 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::experimental::sample(PopulationIterator(ia), PopulationIterator(ia + is),
+ SampleIterator(oa), 0, g);
+ assert(&*end == 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::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<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>();
+}
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.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template <class PopulationIterator, class SampleIterator, class Distance,
+// class UniformRandomNumberGenerator>
+// SampleIterator sample(PopulationIterator first, PopulationIterator last,
+// SampleIterator out, Distance n,
+// UniformRandomNumberGenerator &&g);
+
+#include <experimental/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::experimental::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);
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
