algorithm revision 287518
1287518Sdim// -*- C++ -*- 2287518Sdim//===-------------------------- algorithm ---------------------------------===// 3287518Sdim// 4287518Sdim// The LLVM Compiler Infrastructure 5287518Sdim// 6287518Sdim// This file is dual licensed under the MIT and the University of Illinois Open 7287518Sdim// Source Licenses. See LICENSE.TXT for details. 8287518Sdim// 9287518Sdim//===----------------------------------------------------------------------===// 10287518Sdim 11287518Sdim#ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM 12287518Sdim#define _LIBCPP_EXPERIMENTAL_ALGORITHM 13287518Sdim 14287518Sdim/* 15287518Sdim experimental/algorithm synopsis 16287518Sdim 17287518Sdim#include <algorithm> 18287518Sdim 19287518Sdimnamespace std { 20287518Sdimnamespace experimental { 21287518Sdiminline namespace fundamentals_v1 { 22287518Sdim 23287518Sdimtemplate <class ForwardIterator, class Searcher> 24287518SdimForwardIterator search(ForwardIterator first, ForwardIterator last, 25287518Sdim const Searcher &searcher); 26287518Sdimtemplate <class PopulationIterator, class SampleIterator, class Distance, 27287518Sdim class UniformRandomNumberGenerator> 28287518SdimSampleIterator sample(PopulationIterator first, PopulationIterator last, 29287518Sdim SampleIterator out, Distance n, 30287518Sdim UniformRandomNumberGenerator &&g); 31287518Sdim 32287518Sdim} // namespace fundamentals_v1 33287518Sdim} // namespace experimental 34287518Sdim} // namespace std 35287518Sdim 36287518Sdim*/ 37287518Sdim 38287518Sdim#include <experimental/__config> 39287518Sdim#include <algorithm> 40287518Sdim#include <type_traits> 41287518Sdim 42287518Sdim#include <__undef_min_max> 43287518Sdim 44287518Sdim#include <__debug> 45287518Sdim 46287518Sdim#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 47287518Sdim#pragma GCC system_header 48287518Sdim#endif 49287518Sdim 50287518Sdim_LIBCPP_BEGIN_NAMESPACE_LFTS 51287518Sdim 52287518Sdim 53287518Sdimtemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 54287518Sdim class _UniformRandomNumberGenerator> 55287518Sdim_LIBCPP_INLINE_VISIBILITY 56287518Sdim_SampleIterator __sample(_PopulationIterator __first, 57287518Sdim _PopulationIterator __last, _SampleIterator __out, 58287518Sdim _Distance __n, 59287518Sdim _UniformRandomNumberGenerator &&__g, 60287518Sdim input_iterator_tag) { 61287518Sdim 62287518Sdim _Distance __k = 0; 63287518Sdim for (; __first != __last && __k < __n; ++__first, (void)++__k) 64287518Sdim __out[__k] = *__first; 65287518Sdim _Distance __sz = __k; 66287518Sdim for (; __first != __last; ++__first, (void)++__k) { 67287518Sdim _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); 68287518Sdim if (__r < __sz) 69287518Sdim __out[__r] = *__first; 70287518Sdim } 71287518Sdim return __out + _VSTD::min(__n, __k); 72287518Sdim} 73287518Sdim 74287518Sdimtemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 75287518Sdim class _UniformRandomNumberGenerator> 76287518Sdim_LIBCPP_INLINE_VISIBILITY 77287518Sdim_SampleIterator __sample(_PopulationIterator __first, 78287518Sdim _PopulationIterator __last, _SampleIterator __out, 79287518Sdim _Distance __n, 80287518Sdim _UniformRandomNumberGenerator &&__g, 81287518Sdim forward_iterator_tag) { 82287518Sdim _Distance __unsampled_sz = _VSTD::distance(__first, __last); 83287518Sdim for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { 84287518Sdim _Distance __r = 85287518Sdim _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 86287518Sdim if (__r < __n) { 87287518Sdim *__out++ = *__first; 88287518Sdim --__n; 89287518Sdim } 90287518Sdim } 91287518Sdim return __out; 92287518Sdim} 93287518Sdim 94287518Sdimtemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 95287518Sdim class _UniformRandomNumberGenerator> 96287518Sdim_LIBCPP_INLINE_VISIBILITY 97287518Sdim_SampleIterator sample(_PopulationIterator __first, 98287518Sdim _PopulationIterator __last, _SampleIterator __out, 99287518Sdim _Distance __n, _UniformRandomNumberGenerator &&__g) { 100287518Sdim typedef typename iterator_traits<_PopulationIterator>::iterator_category 101287518Sdim _PopCategory; 102287518Sdim typedef typename iterator_traits<_PopulationIterator>::difference_type 103287518Sdim _Difference; 104287518Sdim typedef typename common_type<_Distance, _Difference>::type _CommonType; 105287518Sdim _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 106287518Sdim return _VSTD_LFTS::__sample( 107287518Sdim __first, __last, __out, _CommonType(__n), 108287518Sdim _VSTD::forward<_UniformRandomNumberGenerator>(__g), 109287518Sdim _PopCategory()); 110287518Sdim} 111287518Sdim 112287518Sdim_LIBCPP_END_NAMESPACE_LFTS 113287518Sdim 114287518Sdim#endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ 115