algorithm revision 300770
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 _ForwardIterator, class _Searcher> 54_LIBCPP_INLINE_VISIBILITY 55_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) 56{ return __s(__f, __l); } 57 58 59template <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 80template <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 100template <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