Horizon
Loading...
Searching...
No Matches
sample.hpp
Go to the documentation of this file.
1
2// 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>
30
31#include <range/v3/detail/prologue.hpp>
32
33namespace 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)(
215 convertible_to<invoke_result_t<URNG &>, range_difference_t<Rng>> AND
217 sized_sentinel_for<sentinel_t<Rng>, iterator_t<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
258 RANGES_INLINE_VARIABLE(sample_fn, sample)
259 } // namespace views
261} // namespace ranges
262
263#include <range/v3/detail/epilogue.hpp>
264#include <range/v3/detail/satisfy_boost_range.hpp>
265RANGES_SATISFY_BOOST_RANGE(::ranges::sample_view)
266
267#endif
Definition sample.hpp:84
The forward_range concept.
The input_range concept.
The sized_range concept.
The sized_sentinel_for concept.
The uniform_random_bit_generator concept.
The viewable_range concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
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