1*0a6a1f1dSLionel Sambuc// -*- C++ -*- 2*0a6a1f1dSLionel Sambuc//===-------------------------- algorithm ---------------------------------===// 3*0a6a1f1dSLionel Sambuc// 4*0a6a1f1dSLionel Sambuc// The LLVM Compiler Infrastructure 5*0a6a1f1dSLionel Sambuc// 6*0a6a1f1dSLionel Sambuc// This file is dual licensed under the MIT and the University of Illinois Open 7*0a6a1f1dSLionel Sambuc// Source Licenses. See LICENSE.TXT for details. 8*0a6a1f1dSLionel Sambuc// 9*0a6a1f1dSLionel Sambuc//===----------------------------------------------------------------------===// 10*0a6a1f1dSLionel Sambuc 11*0a6a1f1dSLionel Sambuc#ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM 12*0a6a1f1dSLionel Sambuc#define _LIBCPP_EXPERIMENTAL_ALGORITHM 13*0a6a1f1dSLionel Sambuc 14*0a6a1f1dSLionel Sambuc/* 15*0a6a1f1dSLionel Sambuc experimental/algorithm synopsis 16*0a6a1f1dSLionel Sambuc 17*0a6a1f1dSLionel Sambuc#include <algorithm> 18*0a6a1f1dSLionel Sambuc 19*0a6a1f1dSLionel Sambucnamespace std { 20*0a6a1f1dSLionel Sambucnamespace experimental { 21*0a6a1f1dSLionel Sambucinline namespace fundamentals_v1 { 22*0a6a1f1dSLionel Sambuc 23*0a6a1f1dSLionel Sambuctemplate <class ForwardIterator, class Searcher> 24*0a6a1f1dSLionel SambucForwardIterator search(ForwardIterator first, ForwardIterator last, 25*0a6a1f1dSLionel Sambuc const Searcher &searcher); 26*0a6a1f1dSLionel Sambuctemplate <class PopulationIterator, class SampleIterator, class Distance, 27*0a6a1f1dSLionel Sambuc class UniformRandomNumberGenerator> 28*0a6a1f1dSLionel SambucSampleIterator sample(PopulationIterator first, PopulationIterator last, 29*0a6a1f1dSLionel Sambuc SampleIterator out, Distance n, 30*0a6a1f1dSLionel Sambuc UniformRandomNumberGenerator &&g); 31*0a6a1f1dSLionel Sambuc 32*0a6a1f1dSLionel Sambuc} // namespace fundamentals_v1 33*0a6a1f1dSLionel Sambuc} // namespace experimental 34*0a6a1f1dSLionel Sambuc} // namespace std 35*0a6a1f1dSLionel Sambuc 36*0a6a1f1dSLionel Sambuc*/ 37*0a6a1f1dSLionel Sambuc 38*0a6a1f1dSLionel Sambuc#include <experimental/__config> 39*0a6a1f1dSLionel Sambuc#include <algorithm> 40*0a6a1f1dSLionel Sambuc#include <type_traits> 41*0a6a1f1dSLionel Sambuc 42*0a6a1f1dSLionel Sambuc#include <__undef_min_max> 43*0a6a1f1dSLionel Sambuc 44*0a6a1f1dSLionel Sambuc#include <__debug> 45*0a6a1f1dSLionel Sambuc 46*0a6a1f1dSLionel Sambuc#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 47*0a6a1f1dSLionel Sambuc#pragma GCC system_header 48*0a6a1f1dSLionel Sambuc#endif 49*0a6a1f1dSLionel Sambuc 50*0a6a1f1dSLionel Sambuc_LIBCPP_BEGIN_NAMESPACE_LFTS 51*0a6a1f1dSLionel Sambuc 52*0a6a1f1dSLionel Sambuc 53*0a6a1f1dSLionel Sambuctemplate <class _ForwardIterator, class _Searcher> 54*0a6a1f1dSLionel Sambuc_LIBCPP_INLINE_VISIBILITY 55*0a6a1f1dSLionel Sambuc_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) 56*0a6a1f1dSLionel Sambuc{ return __s(__f, __l); } 57*0a6a1f1dSLionel Sambuc 58*0a6a1f1dSLionel Sambuc 59*0a6a1f1dSLionel Sambuctemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 60*0a6a1f1dSLionel Sambuc class _UniformRandomNumberGenerator> 61*0a6a1f1dSLionel Sambuc_LIBCPP_INLINE_VISIBILITY 62*0a6a1f1dSLionel Sambuc_SampleIterator __sample(_PopulationIterator __first, 63*0a6a1f1dSLionel Sambuc _PopulationIterator __last, _SampleIterator __out, 64*0a6a1f1dSLionel Sambuc _Distance __n, 65*0a6a1f1dSLionel Sambuc _UniformRandomNumberGenerator &&__g, 66*0a6a1f1dSLionel Sambuc input_iterator_tag) { 67*0a6a1f1dSLionel Sambuc 68*0a6a1f1dSLionel Sambuc _Distance __k = 0; 69*0a6a1f1dSLionel Sambuc for (; __first != __last && __k < __n; ++__first, (void)++__k) 70*0a6a1f1dSLionel Sambuc __out[__k] = *__first; 71*0a6a1f1dSLionel Sambuc _Distance __sz = __k; 72*0a6a1f1dSLionel Sambuc for (; __first != __last; ++__first, (void)++__k) { 73*0a6a1f1dSLionel Sambuc _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); 74*0a6a1f1dSLionel Sambuc if (__r < __sz) 75*0a6a1f1dSLionel Sambuc __out[__r] = *__first; 76*0a6a1f1dSLionel Sambuc } 77*0a6a1f1dSLionel Sambuc return __out + _VSTD::min(__n, __k); 78*0a6a1f1dSLionel Sambuc} 79*0a6a1f1dSLionel Sambuc 80*0a6a1f1dSLionel Sambuctemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 81*0a6a1f1dSLionel Sambuc class _UniformRandomNumberGenerator> 82*0a6a1f1dSLionel Sambuc_LIBCPP_INLINE_VISIBILITY 83*0a6a1f1dSLionel Sambuc_SampleIterator __sample(_PopulationIterator __first, 84*0a6a1f1dSLionel Sambuc _PopulationIterator __last, _SampleIterator __out, 85*0a6a1f1dSLionel Sambuc _Distance __n, 86*0a6a1f1dSLionel Sambuc _UniformRandomNumberGenerator &&__g, 87*0a6a1f1dSLionel Sambuc forward_iterator_tag) { 88*0a6a1f1dSLionel Sambuc _Distance __unsampled_sz = _VSTD::distance(__first, __last); 89*0a6a1f1dSLionel Sambuc for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { 90*0a6a1f1dSLionel Sambuc _Distance __r = 91*0a6a1f1dSLionel Sambuc _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 92*0a6a1f1dSLionel Sambuc if (__r < __n) { 93*0a6a1f1dSLionel Sambuc *__out++ = *__first; 94*0a6a1f1dSLionel Sambuc --__n; 95*0a6a1f1dSLionel Sambuc } 96*0a6a1f1dSLionel Sambuc } 97*0a6a1f1dSLionel Sambuc return __out; 98*0a6a1f1dSLionel Sambuc} 99*0a6a1f1dSLionel Sambuc 100*0a6a1f1dSLionel Sambuctemplate <class _PopulationIterator, class _SampleIterator, class _Distance, 101*0a6a1f1dSLionel Sambuc class _UniformRandomNumberGenerator> 102*0a6a1f1dSLionel Sambuc_LIBCPP_INLINE_VISIBILITY 103*0a6a1f1dSLionel Sambuc_SampleIterator sample(_PopulationIterator __first, 104*0a6a1f1dSLionel Sambuc _PopulationIterator __last, _SampleIterator __out, 105*0a6a1f1dSLionel Sambuc _Distance __n, _UniformRandomNumberGenerator &&__g) { 106*0a6a1f1dSLionel Sambuc typedef typename iterator_traits<_PopulationIterator>::iterator_category 107*0a6a1f1dSLionel Sambuc _PopCategory; 108*0a6a1f1dSLionel Sambuc typedef typename iterator_traits<_PopulationIterator>::difference_type 109*0a6a1f1dSLionel Sambuc _Difference; 110*0a6a1f1dSLionel Sambuc typedef typename common_type<_Distance, _Difference>::type _CommonType; 111*0a6a1f1dSLionel Sambuc _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 112*0a6a1f1dSLionel Sambuc return _VSTD_LFTS::__sample( 113*0a6a1f1dSLionel Sambuc __first, __last, __out, _CommonType(__n), 114*0a6a1f1dSLionel Sambuc _VSTD::forward<_UniformRandomNumberGenerator>(__g), 115*0a6a1f1dSLionel Sambuc _PopCategory()); 116*0a6a1f1dSLionel Sambuc} 117*0a6a1f1dSLionel Sambuc 118*0a6a1f1dSLionel Sambuc_LIBCPP_END_NAMESPACE_LFTS 119*0a6a1f1dSLionel Sambuc 120*0a6a1f1dSLionel Sambuc#endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */ 121