Evgeniy Stepanov | 56a8c64 | 2015-05-13 16:55:41 +0000 | [diff] [blame] | 1 | // -*- C++ -*- |
| 2 | //===-------------------------- algorithm ---------------------------------===// |
| 3 | // |
| 4 | // The LLVM Compiler Infrastructure |
| 5 | // |
| 6 | // This file is dual licensed under the MIT and the University of Illinois Open |
| 7 | // Source Licenses. See LICENSE.TXT for details. |
| 8 | // |
| 9 | //===----------------------------------------------------------------------===// |
| 10 | |
| 11 | #ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM |
| 12 | #define _LIBCPP_EXPERIMENTAL_ALGORITHM |
| 13 | |
| 14 | /* |
| 15 | experimental/algorithm synopsis |
| 16 | |
| 17 | #include <algorithm> |
| 18 | |
| 19 | namespace std { |
| 20 | namespace experimental { |
| 21 | inline namespace fundamentals_v1 { |
| 22 | |
| 23 | template <class ForwardIterator, class Searcher> |
| 24 | ForwardIterator search(ForwardIterator first, ForwardIterator last, |
| 25 | const Searcher &searcher); |
| 26 | template <class PopulationIterator, class SampleIterator, class Distance, |
| 27 | class UniformRandomNumberGenerator> |
| 28 | SampleIterator sample(PopulationIterator first, PopulationIterator last, |
| 29 | SampleIterator out, Distance n, |
| 30 | UniformRandomNumberGenerator &&g); |
| 31 | |
| 32 | } // namespace fundamentals_v1 |
| 33 | } // namespace experimental |
| 34 | } // namespace std |
| 35 | |
| 36 | */ |
| 37 | |
| 38 | #include <experimental/__config> |
| 39 | #include <algorithm> |
| 40 | #include <type_traits> |
| 41 | |
| 42 | #include <__undef_min_max> |
| 43 | |
| 44 | #include <__debug> |
| 45 | |
| 46 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 47 | #pragma GCC system_header |
| 48 | #endif |
| 49 | |
| 50 | _LIBCPP_BEGIN_NAMESPACE_LFTS |
| 51 | |
| 52 | |
Marshall Clow | 166dadb | 2015-07-20 15:40:27 +0000 | [diff] [blame] | 53 | template <class _ForwardIterator, class _Searcher> |
| 54 | _LIBCPP_INLINE_VISIBILITY |
| 55 | _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) |
Marshall Clow | f6d6b51 | 2016-03-08 15:12:52 +0000 | [diff] [blame] | 56 | { return __s(__f, __l).first; } |
Marshall Clow | 166dadb | 2015-07-20 15:40:27 +0000 | [diff] [blame] | 57 | |
| 58 | |
Evgeniy Stepanov | 56a8c64 | 2015-05-13 16:55:41 +0000 | [diff] [blame] | 59 | template <class _PopulationIterator, class _SampleIterator, class _Distance, |
| 60 | class _UniformRandomNumberGenerator> |
| 61 | _LIBCPP_INLINE_VISIBILITY |
| 62 | _SampleIterator __sample(_PopulationIterator __first, |
| 63 | _PopulationIterator __last, _SampleIterator __out, |
| 64 | _Distance __n, |
| 65 | _UniformRandomNumberGenerator &&__g, |
| 66 | input_iterator_tag) { |
| 67 | |
| 68 | _Distance __k = 0; |
| 69 | for (; __first != __last && __k < __n; ++__first, (void)++__k) |
| 70 | __out[__k] = *__first; |
| 71 | _Distance __sz = __k; |
| 72 | for (; __first != __last; ++__first, (void)++__k) { |
| 73 | _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); |
| 74 | if (__r < __sz) |
| 75 | __out[__r] = *__first; |
| 76 | } |
| 77 | return __out + _VSTD::min(__n, __k); |
| 78 | } |
| 79 | |
| 80 | template <class _PopulationIterator, class _SampleIterator, class _Distance, |
| 81 | class _UniformRandomNumberGenerator> |
| 82 | _LIBCPP_INLINE_VISIBILITY |
| 83 | _SampleIterator __sample(_PopulationIterator __first, |
| 84 | _PopulationIterator __last, _SampleIterator __out, |
| 85 | _Distance __n, |
| 86 | _UniformRandomNumberGenerator &&__g, |
| 87 | forward_iterator_tag) { |
| 88 | _Distance __unsampled_sz = _VSTD::distance(__first, __last); |
| 89 | for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { |
| 90 | _Distance __r = |
| 91 | _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); |
| 92 | if (__r < __n) { |
| 93 | *__out++ = *__first; |
| 94 | --__n; |
| 95 | } |
| 96 | } |
| 97 | return __out; |
| 98 | } |
| 99 | |
| 100 | template <class _PopulationIterator, class _SampleIterator, class _Distance, |
| 101 | class _UniformRandomNumberGenerator> |
| 102 | _LIBCPP_INLINE_VISIBILITY |
| 103 | _SampleIterator sample(_PopulationIterator __first, |
| 104 | _PopulationIterator __last, _SampleIterator __out, |
| 105 | _Distance __n, _UniformRandomNumberGenerator &&__g) { |
| 106 | typedef typename iterator_traits<_PopulationIterator>::iterator_category |
| 107 | _PopCategory; |
| 108 | typedef typename iterator_traits<_PopulationIterator>::difference_type |
| 109 | _Difference; |
| 110 | typedef typename common_type<_Distance, _Difference>::type _CommonType; |
| 111 | _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); |
| 112 | return _VSTD_LFTS::__sample( |
| 113 | __first, __last, __out, _CommonType(__n), |
| 114 | _VSTD::forward<_UniformRandomNumberGenerator>(__g), |
| 115 | _PopCategory()); |
| 116 | } |
| 117 | |
| 118 | _LIBCPP_END_NAMESPACE_LFTS |
| 119 | |
| 120 | #endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ |