1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Generating numbers between two others.
12
13 // this is surprisingly complicated to be both generic & correct
14
15 use std::num::Bounded;
16 use Rng;
17 use distributions::{Sample, IndependentSample};
18
19 /// Sample values uniformly between two bounds.
20 ///
21 /// This gives a uniform distribution (assuming the RNG used to sample
22 /// it is itself uniform & the `SampleRange` implementation for the
23 /// given type is correct), even for edge cases like `low = 0u8`,
24 /// `high = 170u8`, for which a naive modulo operation would return
25 /// numbers less than 85 with double the probability to those greater
26 /// than 85.
27 ///
28 /// Types should attempt to sample in `[low, high)`, i.e., not
29 /// including `high`, but this may be very difficult. All the
30 /// primitive integer types satisfy this property, and the float types
31 /// normally satisfy it, but rounding may mean `high` can occur.
32 ///
33 /// # Example
34 ///
35 /// ```rust
36 /// use rand::distributions::{IndependentSample, Range};
37 ///
38 /// fn main() {
39 /// let between = Range::new(10u, 10000u);
40 /// let mut rng = rand::task_rng();
41 /// let mut sum = 0;
42 /// for _ in range(0, 1000) {
43 /// sum += between.ind_sample(&mut rng);
44 /// }
45 /// println!("{}", sum);
46 /// }
47 /// ```
48 pub struct Range<X> {
49 low: X,
50 range: X,
51 accept_zone: X
52 }
53
54 impl<X: SampleRange + Ord> Range<X> {
55 /// Create a new `Range` instance that samples uniformly from
56 /// `[low, high)`. Fails if `low >= high`.
57 pub fn new(low: X, high: X) -> Range<X> {
58 assert!(low < high, "Range::new called with `low >= high`");
59 SampleRange::construct_range(low, high)
60 }
61 }
62
63 impl<Sup: SampleRange> Sample<Sup> for Range<Sup> {
64 #[inline]
65 fn sample<R: Rng>(&mut self, rng: &mut R) -> Sup { self.ind_sample(rng) }
66 }
67 impl<Sup: SampleRange> IndependentSample<Sup> for Range<Sup> {
68 fn ind_sample<R: Rng>(&self, rng: &mut R) -> Sup {
69 SampleRange::sample_range(self, rng)
70 }
71 }
72
73 /// The helper trait for types that have a sensible way to sample
74 /// uniformly between two values. This should not be used directly,
75 /// and is only to facilitate `Range`.
76 pub trait SampleRange {
77 /// Construct the `Range` object that `sample_range`
78 /// requires. This should not ever be called directly, only via
79 /// `Range::new`, which will check that `low < high`, so this
80 /// function doesn't have to repeat the check.
81 fn construct_range(low: Self, high: Self) -> Range<Self>;
82
83 /// Sample a value from the given `Range` with the given `Rng` as
84 /// a source of randomness.
85 fn sample_range<R: Rng>(r: &Range<Self>, rng: &mut R) -> Self;
86 }
87
88 macro_rules! integer_impl {
89 ($ty:ty, $unsigned:ty) => {
90 impl SampleRange for $ty {
91 // we play free and fast with unsigned vs signed here
92 // (when $ty is signed), but that's fine, since the
93 // contract of this macro is for $ty and $unsigned to be
94 // "bit-equal", so casting between them is a no-op & a
95 // bijection.
96
97 fn construct_range(low: $ty, high: $ty) -> Range<$ty> {
98 let range = high as $unsigned - low as $unsigned;
99 let unsigned_max: $unsigned = Bounded::max_value();
100
101 // this is the largest number that fits into $unsigned
102 // that `range` divides evenly, so, if we've sampled
103 // `n` uniformly from this region, then `n % range` is
104 // uniform in [0, range)
105 let zone = unsigned_max - unsigned_max % range;
106
107 Range {
108 low: low,
109 range: range as $ty,
110 accept_zone: zone as $ty
111 }
112 }
113 #[inline]
114 fn sample_range<R: Rng>(r: &Range<$ty>, rng: &mut R) -> $ty {
115 loop {
116 // rejection sample
117 let v = rng.gen::<$unsigned>();
118 // until we find something that fits into the
119 // region which r.range evenly divides (this will
120 // be uniformly distributed)
121 if v < r.accept_zone as $unsigned {
122 // and return it, with some adjustments
123 return r.low + (v % r.range as $unsigned) as $ty;
124 }
125 }
126 }
127 }
128 }
129 }
130
131 integer_impl! { i8, u8 }
132 integer_impl! { i16, u16 }
133 integer_impl! { i32, u32 }
134 integer_impl! { i64, u64 }
135 integer_impl! { int, uint }
136 integer_impl! { u8, u8 }
137 integer_impl! { u16, u16 }
138 integer_impl! { u32, u32 }
139 integer_impl! { u64, u64 }
140 integer_impl! { uint, uint }
141
142 macro_rules! float_impl {
143 ($ty:ty) => {
144 impl SampleRange for $ty {
145 fn construct_range(low: $ty, high: $ty) -> Range<$ty> {
146 Range {
147 low: low,
148 range: high - low,
149 accept_zone: 0.0 // unused
150 }
151 }
152 fn sample_range<R: Rng>(r: &Range<$ty>, rng: &mut R) -> $ty {
153 r.low + r.range * rng.gen()
154 }
155 }
156 }
157 }
158
159 float_impl! { f32 }
160 float_impl! { f64 }
161
162 #[cfg(test)]
163 mod tests {
164 use distributions::{Sample, IndependentSample};
165 use {Rng, task_rng};
166 use super::Range;
167 use std::num::Bounded;
168
169 #[should_fail]
170 #[test]
171 fn test_range_bad_limits_equal() {
172 Range::new(10, 10);
173 }
174 #[should_fail]
175 #[test]
176 fn test_range_bad_limits_flipped() {
177 Range::new(10, 5);
178 }
179
180 #[test]
181 fn test_integers() {
182 let mut rng = task_rng();
183 macro_rules! t (
184 ($($ty:ty),*) => {{
185 $(
186 let v: &[($ty, $ty)] = [(0, 10),
187 (10, 127),
188 (Bounded::min_value(), Bounded::max_value())];
189 for &(low, high) in v.iter() {
190 let mut sampler: Range<$ty> = Range::new(low, high);
191 for _ in range(0, 1000) {
192 let v = sampler.sample(&mut rng);
193 assert!(low <= v && v < high);
194 let v = sampler.ind_sample(&mut rng);
195 assert!(low <= v && v < high);
196 }
197 }
198 )*
199 }}
200 );
201 t!(i8, i16, i32, i64, int,
202 u8, u16, u32, u64, uint)
203 }
204
205 #[test]
206 fn test_floats() {
207 let mut rng = task_rng();
208 macro_rules! t (
209 ($($ty:ty),*) => {{
210 $(
211 let v: &[($ty, $ty)] = [(0.0, 100.0),
212 (-1e35, -1e25),
213 (1e-35, 1e-25),
214 (-1e35, 1e35)];
215 for &(low, high) in v.iter() {
216 let mut sampler: Range<$ty> = Range::new(low, high);
217 for _ in range(0, 1000) {
218 let v = sampler.sample(&mut rng);
219 assert!(low <= v && v < high);
220 let v = sampler.ind_sample(&mut rng);
221 assert!(low <= v && v < high);
222 }
223 }
224 )*
225 }}
226 );
227
228 t!(f32, f64)
229 }
230
231 }