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