1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef _LIBCPP___ALGORITHM_SAMPLE_H
10 #define _LIBCPP___ALGORITHM_SAMPLE_H
11
12 #include <__config>
13 #include <__algorithm/min.h>
14 #include <__random/uniform_int_distribution.h>
15 #include <iterator>
16
17 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
18 #pragma GCC system_header
19 #endif
20
21 _LIBCPP_PUSH_MACROS
22 #include <__undef_macros>
23
24 _LIBCPP_BEGIN_NAMESPACE_STD
25
26 template <class _PopulationIterator, class _SampleIterator, class _Distance,
27 class _UniformRandomNumberGenerator>
28 _LIBCPP_INLINE_VISIBILITY
__sample(_PopulationIterator __first,_PopulationIterator __last,_SampleIterator __output_iter,_Distance __n,_UniformRandomNumberGenerator & __g,input_iterator_tag)29 _SampleIterator __sample(_PopulationIterator __first,
30 _PopulationIterator __last, _SampleIterator __output_iter,
31 _Distance __n,
32 _UniformRandomNumberGenerator & __g,
33 input_iterator_tag) {
34
35 _Distance __k = 0;
36 for (; __first != __last && __k < __n; ++__first, (void) ++__k)
37 __output_iter[__k] = *__first;
38 _Distance __sz = __k;
39 for (; __first != __last; ++__first, (void) ++__k) {
40 _Distance __r = uniform_int_distribution<_Distance>(0, __k)(__g);
41 if (__r < __sz)
42 __output_iter[__r] = *__first;
43 }
44 return __output_iter + _VSTD::min(__n, __k);
45 }
46
47 template <class _PopulationIterator, class _SampleIterator, class _Distance,
48 class _UniformRandomNumberGenerator>
49 _LIBCPP_INLINE_VISIBILITY
__sample(_PopulationIterator __first,_PopulationIterator __last,_SampleIterator __output_iter,_Distance __n,_UniformRandomNumberGenerator & __g,forward_iterator_tag)50 _SampleIterator __sample(_PopulationIterator __first,
51 _PopulationIterator __last, _SampleIterator __output_iter,
52 _Distance __n,
53 _UniformRandomNumberGenerator& __g,
54 forward_iterator_tag) {
55 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
56 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
57 _Distance __r = uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
58 if (__r < __n) {
59 *__output_iter++ = *__first;
60 --__n;
61 }
62 }
63 return __output_iter;
64 }
65
66 template <class _PopulationIterator, class _SampleIterator, class _Distance,
67 class _UniformRandomNumberGenerator>
68 _LIBCPP_INLINE_VISIBILITY
__sample(_PopulationIterator __first,_PopulationIterator __last,_SampleIterator __output_iter,_Distance __n,_UniformRandomNumberGenerator & __g)69 _SampleIterator __sample(_PopulationIterator __first,
70 _PopulationIterator __last, _SampleIterator __output_iter,
71 _Distance __n, _UniformRandomNumberGenerator& __g) {
72 typedef typename iterator_traits<_PopulationIterator>::iterator_category
73 _PopCategory;
74 typedef typename iterator_traits<_PopulationIterator>::difference_type
75 _Difference;
76 static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value ||
77 __is_cpp17_random_access_iterator<_SampleIterator>::value,
78 "SampleIterator must meet the requirements of RandomAccessIterator");
79 typedef typename common_type<_Distance, _Difference>::type _CommonType;
80 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
81 return _VSTD::__sample(
82 __first, __last, __output_iter, _CommonType(__n),
83 __g, _PopCategory());
84 }
85
86 #if _LIBCPP_STD_VER > 14
87 template <class _PopulationIterator, class _SampleIterator, class _Distance,
88 class _UniformRandomNumberGenerator>
89 inline _LIBCPP_INLINE_VISIBILITY
sample(_PopulationIterator __first,_PopulationIterator __last,_SampleIterator __output_iter,_Distance __n,_UniformRandomNumberGenerator && __g)90 _SampleIterator sample(_PopulationIterator __first,
91 _PopulationIterator __last, _SampleIterator __output_iter,
92 _Distance __n, _UniformRandomNumberGenerator&& __g) {
93 return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
94 }
95 #endif // _LIBCPP_STD_VER > 14
96
97 _LIBCPP_END_NAMESPACE_STD
98
99 _LIBCPP_POP_MACROS
100
101 #endif // _LIBCPP___ALGORITHM_SAMPLE_H
102