2 //===-------------------------- algorithm ---------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM
12 #define _LIBCPP_EXPERIMENTAL_ALGORITHM
15 experimental/algorithm synopsis
20 namespace experimental {
21 inline namespace fundamentals_v1 {
23 template <class ForwardIterator, class Searcher>
24 ForwardIterator search(ForwardIterator first, ForwardIterator last,
25 const Searcher &searcher);
26 template <class PopulationIterator, class SampleIterator, class Distance,
27 class UniformRandomNumberGenerator>
28 SampleIterator sample(PopulationIterator first, PopulationIterator last,
29 SampleIterator out, Distance n,
30 UniformRandomNumberGenerator &&g);
32 } // namespace fundamentals_v1
33 } // namespace experimental
38 #include <experimental/__config>
40 #include <type_traits>
42 #include <__undef_min_max>
46 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
47 #pragma GCC system_header
50 _LIBCPP_BEGIN_NAMESPACE_LFTS
53 template <class _PopulationIterator, class _SampleIterator, class _Distance,
54 class _UniformRandomNumberGenerator>
55 _LIBCPP_INLINE_VISIBILITY
56 _SampleIterator __sample(_PopulationIterator __first,
57 _PopulationIterator __last, _SampleIterator __out,
59 _UniformRandomNumberGenerator &&__g,
63 for (; __first != __last && __k < __n; ++__first, (void)++__k)
64 __out[__k] = *__first;
66 for (; __first != __last; ++__first, (void)++__k) {
67 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
69 __out[__r] = *__first;
71 return __out + _VSTD::min(__n, __k);
74 template <class _PopulationIterator, class _SampleIterator, class _Distance,
75 class _UniformRandomNumberGenerator>
76 _LIBCPP_INLINE_VISIBILITY
77 _SampleIterator __sample(_PopulationIterator __first,
78 _PopulationIterator __last, _SampleIterator __out,
80 _UniformRandomNumberGenerator &&__g,
81 forward_iterator_tag) {
82 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
83 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
85 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
94 template <class _PopulationIterator, class _SampleIterator, class _Distance,
95 class _UniformRandomNumberGenerator>
96 _LIBCPP_INLINE_VISIBILITY
97 _SampleIterator sample(_PopulationIterator __first,
98 _PopulationIterator __last, _SampleIterator __out,
99 _Distance __n, _UniformRandomNumberGenerator &&__g) {
100 typedef typename iterator_traits<_PopulationIterator>::iterator_category
102 typedef typename iterator_traits<_PopulationIterator>::difference_type
104 typedef typename common_type<_Distance, _Difference>::type _CommonType;
105 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
106 return _VSTD_LFTS::__sample(
107 __first, __last, __out, _CommonType(__n),
108 _VSTD::forward<_UniformRandomNumberGenerator>(__g),
112 _LIBCPP_END_NAMESPACE_LFTS
114 #endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */