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 53300770Sdimtemplate <class _ForwardIterator, class _Searcher> 54300770Sdim_LIBCPP_INLINE_VISIBILITY 55300770Sdim_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) 56300770Sdim{ return __s(__f, __l); } 57300770Sdim 58300770Sdim 59287518Sdimtemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 60287518Sdim class _UniformRandomNumberGenerator> 61287518Sdim_LIBCPP_INLINE_VISIBILITY 62287518Sdim_SampleIterator __sample(_PopulationIterator __first, 63287518Sdim _PopulationIterator __last, _SampleIterator __out, 64287518Sdim _Distance __n, 65287518Sdim _UniformRandomNumberGenerator &&__g, 66287518Sdim input_iterator_tag) { 67287518Sdim 68287518Sdim _Distance __k = 0; 69287518Sdim for (; __first != __last && __k < __n; ++__first, (void)++__k) 70287518Sdim __out[__k] = *__first; 71287518Sdim _Distance __sz = __k; 72287518Sdim for (; __first != __last; ++__first, (void)++__k) { 73287518Sdim _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); 74287518Sdim if (__r < __sz) 75287518Sdim __out[__r] = *__first; 76287518Sdim } 77287518Sdim return __out + _VSTD::min(__n, __k); 78287518Sdim} 79287518Sdim 80287518Sdimtemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 81287518Sdim class _UniformRandomNumberGenerator> 82287518Sdim_LIBCPP_INLINE_VISIBILITY 83287518Sdim_SampleIterator __sample(_PopulationIterator __first, 84287518Sdim _PopulationIterator __last, _SampleIterator __out, 85287518Sdim _Distance __n, 86287518Sdim _UniformRandomNumberGenerator &&__g, 87287518Sdim forward_iterator_tag) { 88287518Sdim _Distance __unsampled_sz = _VSTD::distance(__first, __last); 89287518Sdim for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { 90287518Sdim _Distance __r = 91287518Sdim _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 92287518Sdim if (__r < __n) { 93287518Sdim *__out++ = *__first; 94287518Sdim --__n; 95287518Sdim } 96287518Sdim } 97287518Sdim return __out; 98287518Sdim} 99287518Sdim 100287518Sdimtemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 101287518Sdim class _UniformRandomNumberGenerator> 102287518Sdim_LIBCPP_INLINE_VISIBILITY 103287518Sdim_SampleIterator sample(_PopulationIterator __first, 104287518Sdim _PopulationIterator __last, _SampleIterator __out, 105287518Sdim _Distance __n, _UniformRandomNumberGenerator &&__g) { 106287518Sdim typedef typename iterator_traits<_PopulationIterator>::iterator_category 107287518Sdim _PopCategory; 108287518Sdim typedef typename iterator_traits<_PopulationIterator>::difference_type 109287518Sdim _Difference; 110287518Sdim typedef typename common_type<_Distance, _Difference>::type _CommonType; 111287518Sdim _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 112287518Sdim return _VSTD_LFTS::__sample( 113287518Sdim __first, __last, __out, _CommonType(__n), 114287518Sdim _VSTD::forward<_UniformRandomNumberGenerator>(__g), 115287518Sdim _PopCategory()); 116287518Sdim} 117287518Sdim 118287518Sdim_LIBCPP_END_NAMESPACE_LFTS 119287518Sdim 120287518Sdim#endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ 121