Horizon
sample.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2014-present
5 // Copyright Casey Carter 2016
6 //
7 // Use, modification and distribution is subject to the
8 // Boost Software License, Version 1.0. (See accompanying
9 // file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //
12 // Project home: https://github.com/ericniebler/range-v3
13 //
14 #ifndef RANGES_V3_ALGORITHM_SAMPLE_HPP
15 #define RANGES_V3_ALGORITHM_SAMPLE_HPP
16 
17 #include <utility>
18 
19 #include <range/v3/range_fwd.hpp>
20 
30 #include <range/v3/utility/static_const.hpp>
31 
32 #include <range/v3/detail/prologue.hpp>
33 
34 namespace ranges
35 {
38  template<typename I, typename O>
39  using sample_result = detail::in_out_result<I, O>;
40 
42  namespace detail
43  {
44  template<typename I, typename S, typename O, typename Gen>
45  sample_result<I, O> sample_sized_impl(I first,
46  S last,
47  iter_difference_t<I> pop_size,
48  O out,
49  iter_difference_t<O> sample_size,
50  Gen && gen)
51  {
52  if(pop_size > 0 && sample_size > 0)
53  {
54  std::uniform_int_distribution<iter_difference_t<I>> dist;
55  using param_t = typename decltype(dist)::param_type;
56  for(; first != last; ++first)
57  {
58  if(sample_size >= pop_size)
59  return copy_n(std::move(first), pop_size, std::move(out));
60 
61  if(dist(gen, param_t{0, --pop_size}) < sample_size)
62  {
63  *out = *first;
64  ++out;
65  if(--sample_size == 0)
66  break;
67  }
68  }
69  }
70 
71  return {std::move(first), std::move(out)};
72  }
73  } // namespace detail
75 
76  RANGES_FUNC_BEGIN(sample)
77 
78 
79  template(typename I,
80  typename S,
81  typename O,
82  typename Gen = detail::default_random_engine &)(
83  requires input_iterator<I> AND sentinel_for<S, I> AND
85  uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
87  sized_sentinel_for<S, I>))
88  sample_result<I, O> RANGES_FUNC(sample)(I first,
89  S last,
90  O out,
91  iter_difference_t<O> const n,
92  Gen && gen = detail::get_random_engine())
93  {
94  if(RANGES_CONSTEXPR_IF(forward_iterator<I> || sized_sentinel_for<S, I>)) //
95  {
96  auto const k = distance(first, last);
97  return detail::sample_sized_impl(std::move(first),
98  std::move(last),
99  k,
100  std::move(out),
101  n,
102  static_cast<Gen &&>(gen));
103  }
104  else
105  {
106  // out is random-access here; calls to advance(out,n) and
107  // next(out,n) are O(1).
108  if(n > 0)
109  {
110  for(iter_difference_t<O> i = 0; i < n; (void)++i, ++first)
111  {
112  if(first == last)
113  {
114  advance(out, i);
115  goto done;
116  }
117  *next(out, i) = *first;
118  }
119 
120  std::uniform_int_distribution<iter_difference_t<O>> dist;
121  using param_t = typename decltype(dist)::param_type;
122  for(auto pop_size = n; first != last; (void)++first, ++pop_size)
123  {
124  auto const i = dist(gen, param_t{0, pop_size});
125  if(i < n)
126  *next(out, i) = *first;
127  }
128 
129  advance(out, n);
130  }
131  done:
132  return {std::move(first), std::move(out)};
133  }
134  }
135 
137  template(typename I,
138  typename S,
139  typename ORng,
140  typename Gen = detail::default_random_engine &)(
141  requires input_iterator<I> AND sentinel_for<S, I> AND
144  uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
145  (forward_range<ORng> || sized_range<ORng>) AND
146  (random_access_iterator<iterator_t<ORng>> || forward_iterator<I> ||
147  sized_sentinel_for<S, I>))
148  sample_result<I, borrowed_iterator_t<ORng>> RANGES_FUNC(sample)(
149  I first,
150  S last,
151  ORng && out,
152  Gen && gen = detail::get_random_engine()) //
153  {
154  if(RANGES_CONSTEXPR_IF(forward_iterator<I> || sized_sentinel_for<S, I>)) //
155  {
156  auto k = distance(first, last);
157  return detail::sample_sized_impl(std::move(first),
158  std::move(last),
159  k,
160  begin(out),
161  distance(out),
162  static_cast<Gen &&>(gen));
163  }
164  else
165  {
166  return (*this)(std::move(first),
167  std::move(last),
168  begin(out),
169  distance(out),
170  static_cast<Gen &&>(gen));
171  }
172  }
173 
175  template(typename Rng,
176  typename O,
177  typename Gen = detail::default_random_engine &)(
178  requires input_range<Rng> AND weakly_incrementable<O> AND
180  uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
181  (random_access_iterator<O> || forward_range<Rng> || sized_range<Rng>))
182  sample_result<borrowed_iterator_t<Rng>, O> RANGES_FUNC(sample)(
183  Rng && rng,
184  O out,
185  iter_difference_t<O> const n,
186  Gen && gen = detail::get_random_engine()) //
187  {
188  if(RANGES_CONSTEXPR_IF(forward_range<Rng> || sized_range<Rng>)) //
189  {
190  return detail::sample_sized_impl(begin(rng),
191  end(rng),
192  distance(rng),
193  std::move(out),
194  n,
195  static_cast<Gen &&>(gen));
196  }
197  else
198  {
199  return (*this)(
200  begin(rng), end(rng), std::move(out), n, static_cast<Gen &&>(gen));
201  }
202  }
203 
205  template(typename IRng,
206  typename ORng,
207  typename Gen = detail::default_random_engine &)(
208  requires input_range<IRng> AND range<ORng> AND
210  uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
211  (random_access_iterator<iterator_t<ORng>> || forward_range<IRng> ||
212  sized_range<IRng>) AND
213  (forward_range<ORng> || sized_range<ORng>))
214  sample_result<borrowed_iterator_t<IRng>, borrowed_iterator_t<ORng>> //
215  RANGES_FUNC(sample)(IRng && rng,
216  ORng && out,
217  Gen && gen = detail::get_random_engine())
218  {
219  if(RANGES_CONSTEXPR_IF(forward_range<IRng> || sized_range<IRng>)) //
220  {
221  return detail::sample_sized_impl(begin(rng),
222  end(rng),
223  distance(rng),
224  begin(out),
225  distance(out),
226  static_cast<Gen &&>(gen));
227  }
228  else
229  {
230  return (*this)(begin(rng),
231  end(rng),
232  begin(out),
233  distance(out),
234  static_cast<Gen &&>(gen));
235  }
236  }
237 
238  RANGES_FUNC_END(sample)
239 
240  namespace cpp20
241  {
242  using ranges::sample_result;
243  using ranges::sample;
244  }
246 } // namespace ranges
247 
248 #include <range/v3/detail/epilogue.hpp>
249 
250 #endif
template(typename IRng, typename ORng, typename Gen=detail::default_random_engine &)(requires input_range< IRng > AND range< ORng > AND indirectly_copyable< iterator_t< IRng >
This is an overloaded member function, provided for convenience. It differs from the above function o...
CPP_concept sentinel_for
\concept sentinel_for
Definition: concepts.hpp:306
CPP_concept input_iterator
\concept input_iterator
Definition: concepts.hpp:362
CPP_concept sized_sentinel_for
\concept sized_sentinel_for
Definition: concepts.hpp:332
CPP_concept forward_iterator
\concept forward_iterator
Definition: concepts.hpp:370
CPP_concept random_access_iterator
\concept random_access_iterator
Definition: concepts.hpp:416
CPP_concept indirectly_copyable
\concept indirectly_copyable
Definition: concepts.hpp:782
CPP_concept weakly_incrementable
\concept weakly_incrementable
Definition: concepts.hpp:268
CPP_concept uniform_random_bit_generator
\concept uniform_random_bit_generator
Definition: random.hpp:99
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251