Last active
August 29, 2015 14:20
-
-
Save EricWF/c62b0979202cfd2cc6af to your computer and use it in GitHub Desktop.
Misc additions to sample patch
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
diff --git a/include/experimental/algorithm b/include/experimental/algorithm | |
new file mode 100644 | |
index 0000000..a2e956f | |
--- /dev/null | |
+++ b/include/experimental/algorithm | |
@@ -0,0 +1,114 @@ | |
+// -*- 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> | |
+#include <type_traits> | |
+ | |
+#include <__undef_min_max> | |
+ | |
+#include <__debug> | |
+ | |
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) | |
+#pragma GCC system_header | |
+#endif | |
+ | |
+_LIBCPP_BEGIN_NAMESPACE_LFTS | |
+ | |
+ | |
+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; | |
+ 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()); | |
+} | |
+ | |
+_LIBCPP_END_NAMESPACE_LFTS | |
+ | |
+#endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ | |
diff --git a/test/libcxx/double_include.sh.cpp b/test/libcxx/double_include.sh.cpp | |
index fd08128..5620e5b 100644 | |
--- a/test/libcxx/double_include.sh.cpp | |
+++ b/test/libcxx/double_include.sh.cpp | |
@@ -49,6 +49,7 @@ | |
#include <cwctype> | |
#include <deque> | |
#include <exception> | |
+#include <experimental/algorithm> | |
#include <experimental/chrono> | |
#include <experimental/dynarray> | |
#include <experimental/optional> | |
diff --git a/test/libcxx/experimental/algorithms/header.algorithm.synop/includes.pass.cpp b/test/libcxx/experimental/algorithms/header.algorithm.synop/includes.pass.cpp | |
new file mode 100644 | |
index 0000000..accdd69 | |
--- /dev/null | |
+++ b/test/libcxx/experimental/algorithms/header.algorithm.synop/includes.pass.cpp | |
@@ -0,0 +1,20 @@ | |
+//===----------------------------------------------------------------------===// | |
+// | |
+// 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. | |
+// | |
+//===----------------------------------------------------------------------===// | |
+ | |
+// <experimental/algorithm> | |
+ | |
+#include <experimental/algorithm> | |
+ | |
+#ifndef _LIBCPP_ALGORITHM | |
+# error "<experimental/algorithm> must include <algorithm>" | |
+#endif | |
+ | |
+int main() | |
+{ | |
+} | |
diff --git a/test/libcxx/experimental/algorithms/version.pass.cpp b/test/libcxx/experimental/algorithms/version.pass.cpp | |
new file mode 100644 | |
index 0000000..6d9d0c6 | |
--- /dev/null | |
+++ b/test/libcxx/experimental/algorithms/version.pass.cpp | |
@@ -0,0 +1,20 @@ | |
+//===----------------------------------------------------------------------===// | |
+// | |
+// 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. | |
+// | |
+//===----------------------------------------------------------------------===// | |
+ | |
+// <experimental/algorithm> | |
+ | |
+#include <experimental/algorithm> | |
+ | |
+#ifndef _LIBCPP_VERSION | |
+# error _LIBCPP_VERSION not defined | |
+#endif | |
+ | |
+int main() | |
+{ | |
+} | |
diff --git a/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp b/test/std/experimental/algorithms/alg.random.sample/sample.fail.cpp | |
new file mode 100644 | |
index 0000000..eeb4373 | |
--- /dev/null | |
+++ b/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 *> >(); | |
+} | |
diff --git a/test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp b/test/std/experimental/algorithms/alg.random.sample/sample.pass.cpp | |
new file mode 100644 | |
index 0000000..0f0784d | |
--- /dev/null | |
+++ b/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. | |
+// | |
+//===----------------------------------------------------------------------===// | |
+ | |
+// <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 { | |
+ 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::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>(); | |
+} | |
diff --git a/test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp b/test/std/experimental/algorithms/alg.random.sample/sample.stable.pass.cpp | |
new file mode 100644 | |
index 0000000..c805c66 | |
--- /dev/null | |
+++ b/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); | |
+} | |
diff --git a/www/ts1z_status.html b/www/ts1z_status.html | |
index 59cfe5e..6cca195 100644 | |
--- a/www/ts1z_status.html | |
+++ b/www/ts1z_status.html | |
@@ -78,7 +78,7 @@ | |
<tr><td>class any</td><td>Implementation in progress</td></tr> | |
<tr><td>string_view</td><td>Implementation in progress</td></tr> | |
<tr><td>memory</td><td>Implementation in progress</td></tr> | |
- <tr><td>Algorithms library</td><td>Not started</td></tr> | |
+ <tr><td>Algorithms library</td><td>Implementation in progress</td></tr> | |
</table> | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment