src/librand/distributions/range.rs

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