// -*- C++ -*- //===-------------------------- algorithm ---------------------------------===// // // The LLVM Compiler Infrastructure // // This file is dual licensed under the MIT and the University of Illinois Open // Source Licenses. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM #define _LIBCPP_EXPERIMENTAL_ALGORITHM /* experimental/algorithm synopsis #include <algorithm> namespace std { namespace experimental { inline namespace fundamentals_v1 { template <class ForwardIterator, class Searcher> ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher &searcher); template <class PopulationIterator, class SampleIterator, class Distance, class UniformRandomNumberGenerator> SampleIterator sample(PopulationIterator first, PopulationIterator last, SampleIterator out, Distance n, UniformRandomNumberGenerator &&g); } // namespace fundamentals_v1 } // namespace experimental } // namespace std */ #include <experimental/__config> #include <algorithm> #include <type_traits> #include <__undef_min_max> #include <__debug> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_LFTS template <class _ForwardIterator, class _Searcher> _LIBCPP_INLINE_VISIBILITY _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) { return __s(__f, __l); } template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator> _LIBCPP_INLINE_VISIBILITY _SampleIterator __sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomNumberGenerator &&__g, input_iterator_tag) { _Distance __k = 0; for (; __first != __last && __k < __n; ++__first, (void)++__k) __out[__k] = *__first; _Distance __sz = __k; for (; __first != __last; ++__first, (void)++__k) { _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); if (__r < __sz) __out[__r] = *__first; } return __out + _VSTD::min(__n, __k); } template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator> _LIBCPP_INLINE_VISIBILITY _SampleIterator __sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomNumberGenerator &&__g, forward_iterator_tag) { _Distance __unsampled_sz = _VSTD::distance(__first, __last); for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); if (__r < __n) { *__out++ = *__first; --__n; } } return __out; } template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator> _LIBCPP_INLINE_VISIBILITY _SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomNumberGenerator &&__g) { typedef typename iterator_traits<_PopulationIterator>::iterator_category _PopCategory; typedef typename iterator_traits<_PopulationIterator>::difference_type _Difference; typedef typename common_type<_Distance, _Difference>::type _CommonType; _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); return _VSTD_LFTS::__sample( __first, __last, __out, _CommonType(__n), _VSTD::forward<_UniformRandomNumberGenerator>(__g), _PopCategory()); } _LIBCPP_END_NAMESPACE_LFTS #endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */