Horizon
sample.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Casey Carter 2016
5 //
6 // Use, modification and distribution is subject to the
7 // Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //
11 // Project home: https://github.com/ericniebler/range-v3
12 //
13 
14 #ifndef RANGES_V3_VIEW_SAMPLE_HPP
15 #define RANGES_V3_VIEW_SAMPLE_HPP
16 
17 #include <meta/meta.hpp>
18 
26 #include <range/v3/utility/static_const.hpp>
27 #include <range/v3/view/all.hpp>
28 #include <range/v3/view/facade.hpp>
29 #include <range/v3/view/view.hpp>
30 
31 #include <range/v3/detail/prologue.hpp>
32 
33 namespace ranges
34 {
36  namespace detail
37  {
38  template<typename Rng,
39  bool = (bool)sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>>>
40  class size_tracker
41  {
42  range_difference_t<Rng> size_;
43 
44  public:
45  CPP_assert(forward_range<Rng> || sized_range<Rng>);
46  size_tracker() = default;
47  size_tracker(Rng & rng)
48  : size_(ranges::distance(rng))
49  {}
50  void decrement()
51  {
52  --size_;
53  }
54  range_difference_t<Rng> get(Rng &, iterator_t<Rng> &) const
55  {
56  return size_;
57  }
58  };
59 
60  // Impl for sized_sentinel_for (no need to store anything)
61  template<typename Rng>
62  class size_tracker<Rng, true>
63  {
64  public:
65  size_tracker() = default;
66  size_tracker(Rng &)
67  {}
68  void decrement()
69  {}
70  range_difference_t<Rng> get(Rng & rng, iterator_t<Rng> const & it) const
71  {
72  return ranges::end(rng) - it;
73  }
74  };
75  } // namespace detail
77 
80 
81  // Take a random sampling from another view
82  template<typename Rng, typename URNG>
84  {
85  friend range_access;
86  using D = range_difference_t<Rng>;
87  Rng rng_;
88  // Mutable is OK here because sample_view is an Input view.
89  mutable range_difference_t<Rng> size_;
90  URNG * engine_;
91 
92  template<bool IsConst>
93  class cursor
94  {
95  friend cursor<!IsConst>;
96 
97  using Base = meta::const_if_c<IsConst, Rng>;
98  meta::const_if_c<IsConst, sample_view> * parent_;
99  iterator_t<Base> current_;
100  RANGES_NO_UNIQUE_ADDRESS detail::size_tracker<Base> size_;
101 
102  D pop_size()
103  {
104  return size_.get(parent_->rng_, current_);
105  }
106  void advance()
107  {
108  if(parent_->size_ > 0)
109  {
110  using Dist = std::uniform_int_distribution<D>;
111  Dist dist{};
112  URNG & engine = *parent_->engine_;
113 
114  for(;; ++current_, size_.decrement())
115  {
116  RANGES_ASSERT(current_ != ranges::end(parent_->rng_));
117  auto n = pop_size();
118  RANGES_EXPECT(n > 0);
119  typename Dist::param_type const interval{0, n - 1};
120  if(dist(engine, interval) < parent_->size_)
121  break;
122  }
123  }
124  }
125 
126  public:
127  using value_type = range_value_t<Rng>;
128  using difference_type = D;
129 
130  cursor() = default;
131  explicit cursor(meta::const_if_c<IsConst, sample_view> * rng)
132  : parent_(rng)
133  , current_(ranges::begin(rng->rng_))
134  , size_{rng->rng_}
135  {
136  auto n = pop_size();
137  if(rng->size_ > n)
138  rng->size_ = n;
139  advance();
140  }
141  template(bool Other)(
142  requires IsConst AND CPP_NOT(Other)) //
143  cursor(cursor<Other> that)
144  : parent_(that.parent_)
145  , current_(std::move(that.current_))
146  , size_(that.size_)
147  {}
148  range_reference_t<Rng> read() const
149  {
150  return *current_;
151  }
152  bool equal(default_sentinel_t) const
153  {
154  RANGES_EXPECT(parent_);
155  return parent_->size_ <= 0;
156  }
157  void next()
158  {
159  RANGES_EXPECT(parent_);
160  RANGES_EXPECT(parent_->size_ > 0);
161  --parent_->size_;
162  RANGES_ASSERT(current_ != ranges::end(parent_->rng_));
163  ++current_;
164  size_.decrement();
165  advance();
166  }
167  };
168 
169  cursor<false> begin_cursor()
170  {
171  return cursor<false>{this};
172  }
173  template(bool Const = true)(
174  requires Const AND
175  (sized_range<meta::const_if_c<Const, Rng>> ||
176  sized_sentinel_for<sentinel_t<meta::const_if_c<Const, Rng>>,
177  iterator_t<meta::const_if_c<Const, Rng>>> ||
178  forward_range<meta::const_if_c<Const, Rng>>)) //
179  cursor<Const> begin_cursor() const
180  {
181  return cursor<true>{this};
182  }
183 
184  public:
185  sample_view() = default;
186 
187  explicit sample_view(Rng rng, D sample_size, URNG & generator)
188  : rng_(std::move(rng))
189  , size_(sample_size)
190  , engine_(std::addressof(generator))
191  {
192  RANGES_EXPECT(sample_size >= 0);
193  }
194 
195  Rng base() const
196  {
197  return rng_;
198  }
199  };
200 
201 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
202  template<typename Rng, typename URNG>
203  sample_view(Rng &&, range_difference_t<Rng>, URNG &)
204  ->sample_view<views::all_t<Rng>, URNG>;
205 #endif
206 
207  namespace views
208  {
211  {
212  template(typename Rng, typename URNG = detail::default_random_engine)(
213  requires viewable_range<Rng> AND input_range<Rng> AND
214  uniform_random_bit_generator<URNG> AND
215  convertible_to<invoke_result_t<URNG &>, range_difference_t<Rng>> AND
216  (sized_range<Rng> ||
217  sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>> ||
218  forward_range<Rng>)) //
219  sample_view<all_t<Rng>, URNG> operator()(
220  Rng && rng,
221  range_difference_t<Rng> sample_size,
222  URNG & generator = detail::get_random_engine()) const
223  {
224  return sample_view<all_t<Rng>, URNG>{
225  all(static_cast<Rng &&>(rng)), sample_size, generator};
226  }
227 
229  template<typename Rng, typename URNG>
230  invoke_result_t<sample_base_fn, Rng, range_difference_t<Rng>, URNG &> //
231  operator()(
232  Rng && rng,
233  range_difference_t<Rng> sample_size,
234  detail::reference_wrapper_<URNG> r) const
235  {
236  return (*this)(static_cast<Rng &&>(rng), sample_size, r.get());
237  }
239  };
240 
242  {
243  using sample_base_fn::operator();
244 
245  template(typename Size, typename URNG = detail::default_random_engine)(
246  requires integral<Size> AND uniform_random_bit_generator<URNG>)
247  constexpr auto operator()(
248  Size n,
249  URNG & urng = detail::get_random_engine()) const //
250  {
251  return make_view_closure(bind_back(
252  sample_base_fn{}, n, detail::reference_wrapper_<URNG>(urng)));
253  }
254  };
255 
259  } // namespace views
261 } // namespace ranges
262 
263 #include <range/v3/detail/epilogue.hpp>
264 #include <range/v3/detail/satisfy_boost_range.hpp>
265 RANGES_SATISFY_BOOST_RANGE(::ranges::sample_view)
266 
267 #endif
Definition: sample.hpp:84
CPP_concept sized_sentinel_for
\concept sized_sentinel_for
Definition: concepts.hpp:332
CPP_concept sized_range
\concept sized_range
Definition: concepts.hpp:208
CPP_concept forward_range
\concept forward_range
Definition: concepts.hpp:115
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
defer< bind_back, Fn, Ts... > bind_back
Definition: meta.hpp:994
Tiny meta-programming library.
Definition: default_sentinel.hpp:26
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition: facade.hpp:66
Returns a random sample of a range of length size(range).
Definition: sample.hpp:211
Definition: sample.hpp:242