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