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 53 template <class _ForwardIterator, class _Searcher> 54 _LIBCPP_INLINE_VISIBILITY 55 _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) 56 { return __s(__f, __l); } 57 58 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 */ 121
