algorithm revision 288943
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 19namespace std { 20namespace experimental { 21inline namespace fundamentals_v1 { 22 23template <class ForwardIterator, class Searcher> 24ForwardIterator search(ForwardIterator first, ForwardIterator last, 25 const Searcher &searcher); 26template <class PopulationIterator, class SampleIterator, class Distance, 27 class UniformRandomNumberGenerator> 28SampleIterator 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 53template <class _PopulationIterator, class _SampleIterator, class _Distance, 54 class _UniformRandomNumberGenerator> 55_LIBCPP_INLINE_VISIBILITY 56_SampleIterator __sample(_PopulationIterator __first, 57 _PopulationIterator __last, _SampleIterator __out, 58 _Distance __n, 59 _UniformRandomNumberGenerator &&__g, 60 input_iterator_tag) { 61 62 _Distance __k = 0; 63 for (; __first != __last && __k < __n; ++__first, (void)++__k) 64 __out[__k] = *__first; 65 _Distance __sz = __k; 66 for (; __first != __last; ++__first, (void)++__k) { 67 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); 68 if (__r < __sz) 69 __out[__r] = *__first; 70 } 71 return __out + _VSTD::min(__n, __k); 72} 73 74template <class _PopulationIterator, class _SampleIterator, class _Distance, 75 class _UniformRandomNumberGenerator> 76_LIBCPP_INLINE_VISIBILITY 77_SampleIterator __sample(_PopulationIterator __first, 78 _PopulationIterator __last, _SampleIterator __out, 79 _Distance __n, 80 _UniformRandomNumberGenerator &&__g, 81 forward_iterator_tag) { 82 _Distance __unsampled_sz = _VSTD::distance(__first, __last); 83 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { 84 _Distance __r = 85 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 86 if (__r < __n) { 87 *__out++ = *__first; 88 --__n; 89 } 90 } 91 return __out; 92} 93 94template <class _PopulationIterator, class _SampleIterator, class _Distance, 95 class _UniformRandomNumberGenerator> 96_LIBCPP_INLINE_VISIBILITY 97_SampleIterator sample(_PopulationIterator __first, 98 _PopulationIterator __last, _SampleIterator __out, 99 _Distance __n, _UniformRandomNumberGenerator &&__g) { 100 typedef typename iterator_traits<_PopulationIterator>::iterator_category 101 _PopCategory; 102 typedef typename iterator_traits<_PopulationIterator>::difference_type 103 _Difference; 104 typedef typename common_type<_Distance, _Difference>::type _CommonType; 105 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 106 return _VSTD_LFTS::__sample( 107 __first, __last, __out, _CommonType(__n), 108 _VSTD::forward<_UniformRandomNumberGenerator>(__g), 109 _PopCategory()); 110} 111 112_LIBCPP_END_NAMESPACE_LFTS 113 114#endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ 115