// Copyright 2013 The Rust Project Developers. See the COPYRIGHT | |

// file at the top-level directory of this distribution and at | |

// http://rust-lang.org/COPYRIGHT. | |

// | |

// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |

// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |

// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |

// option. This file may not be copied, modified, or distributed | |

// except according to those terms. | |

//! Generating numbers between two others. | |

// this is surprisingly complicated to be both generic & correct | |

use core::prelude::{PartialOrd}; | |

use core::num::Int; | |

use core::num::wrapping::Wrapping as w; | |

use Rng; | |

use distributions::{Sample, IndependentSample}; | |

/// Sample values uniformly between two bounds. | |

/// | |

/// This gives a uniform distribution (assuming the RNG used to sample | |

/// it is itself uniform & the `SampleRange` implementation for the | |

/// given type is correct), even for edge cases like `low = 0u8`, | |

/// `high = 170u8`, for which a naive modulo operation would return | |

/// numbers less than 85 with double the probability to those greater | |

/// than 85. | |

/// | |

/// Types should attempt to sample in `[low, high)`, i.e., not | |

/// including `high`, but this may be very difficult. All the | |

/// primitive integer types satisfy this property, and the float types | |

/// normally satisfy it, but rounding may mean `high` can occur. | |

/// | |

/// # Example | |

/// | |

/// ```rust | |

/// use rand::distributions::{IndependentSample, Range}; | |

/// | |

/// fn main() { | |

/// let between = Range::new(10, 10000); | |

/// let mut rng = rand::thread_rng(); | |

/// let mut sum = 0; | |

/// for _ in 0..1000 { | |

/// sum += between.ind_sample(&mut rng); | |

/// } | |

/// println!("{}", sum); | |

/// } | |

/// ``` | |

pub struct Range<X> { | |

low: X, | |

range: X, | |

accept_zone: X | |

} | |

impl<X: SampleRange + PartialOrd> Range<X> { | |

/// Create a new `Range` instance that samples uniformly from | |

/// `[low, high)`. Panics if `low >= high`. | |

pub fn new(low: X, high: X) -> Range<X> { | |

assert!(low < high, "Range::new called with `low >= high`"); | |

SampleRange::construct_range(low, high) | |

} | |

} | |

impl<Sup: SampleRange> Sample<Sup> for Range<Sup> { | |

#[inline] | |

fn sample<R: Rng>(&mut self, rng: &mut R) -> Sup { self.ind_sample(rng) } | |

} | |

impl<Sup: SampleRange> IndependentSample<Sup> for Range<Sup> { | |

fn ind_sample<R: Rng>(&self, rng: &mut R) -> Sup { | |

SampleRange::sample_range(self, rng) | |

} | |

} | |

/// The helper trait for types that have a sensible way to sample | |

/// uniformly between two values. This should not be used directly, | |

/// and is only to facilitate `Range`. | |

pub trait SampleRange { | |

/// Construct the `Range` object that `sample_range` | |

/// requires. This should not ever be called directly, only via | |

/// `Range::new`, which will check that `low < high`, so this | |

/// function doesn't have to repeat the check. | |

fn construct_range(low: Self, high: Self) -> Range<Self>; | |

/// Sample a value from the given `Range` with the given `Rng` as | |

/// a source of randomness. | |

fn sample_range<R: Rng>(r: &Range<Self>, rng: &mut R) -> Self; | |

} | |

macro_rules! integer_impl { | |

($ty:ty, $unsigned:ty) => { | |

impl SampleRange for $ty { | |

// we play free and fast with unsigned vs signed here | |

// (when $ty is signed), but that's fine, since the | |

// contract of this macro is for $ty and $unsigned to be | |

// "bit-equal", so casting between them is a no-op & a | |

// bijection. | |

fn construct_range(low: $ty, high: $ty) -> Range<$ty> { | |

let range = (w(high as $unsigned) - w(low as $unsigned)).0; | |

let unsigned_max: $unsigned = Int::max_value(); | |

// this is the largest number that fits into $unsigned | |

// that `range` divides evenly, so, if we've sampled | |

// `n` uniformly from this region, then `n % range` is | |

// uniform in [0, range) | |

let zone = unsigned_max - unsigned_max % range; | |

Range { | |

low: low, | |

range: range as $ty, | |

accept_zone: zone as $ty | |

} | |

} | |

#[inline] | |

fn sample_range<R: Rng>(r: &Range<$ty>, rng: &mut R) -> $ty { | |

loop { | |

// rejection sample | |

let v = rng.gen::<$unsigned>(); | |

// until we find something that fits into the | |

// region which r.range evenly divides (this will | |

// be uniformly distributed) | |

if v < r.accept_zone as $unsigned { | |

// and return it, with some adjustments | |

return (w(r.low) + w((v % r.range as $unsigned) as $ty)).0; | |

} | |

} | |

} | |

} | |

} | |

} | |

integer_impl! { i8, u8 } | |

integer_impl! { i16, u16 } | |

integer_impl! { i32, u32 } | |

integer_impl! { i64, u64 } | |

integer_impl! { isize, usize } | |

integer_impl! { u8, u8 } | |

integer_impl! { u16, u16 } | |

integer_impl! { u32, u32 } | |

integer_impl! { u64, u64 } | |

integer_impl! { usize, usize } | |

macro_rules! float_impl { | |

($ty:ty) => { | |

impl SampleRange for $ty { | |

fn construct_range(low: $ty, high: $ty) -> Range<$ty> { | |

Range { | |

low: low, | |

range: high - low, | |

accept_zone: 0.0 // unused | |

} | |

} | |

fn sample_range<R: Rng>(r: &Range<$ty>, rng: &mut R) -> $ty { | |

r.low + r.range * rng.gen() | |

} | |

} | |

} | |

} | |

float_impl! { f32 } | |

float_impl! { f64 } | |

#[cfg(test)] | |

mod tests { | |

use std::num::Int; | |

use std::prelude::v1::*; | |

use distributions::{Sample, IndependentSample}; | |

use super::Range as Range; | |

#[should_fail] | |

#[test] | |

fn test_range_bad_limits_equal() { | |

Range::new(10, 10); | |

} | |

#[should_fail] | |

#[test] | |

fn test_range_bad_limits_flipped() { | |

Range::new(10, 5); | |

} | |

#[test] | |

fn test_integers() { | |

let mut rng = ::test::rng(); | |

macro_rules! t { | |

($($ty:ty),*) => {{ | |

$( | |

let v: &[($ty, $ty)] = &[(0, 10), | |

(10, 127), | |

(Int::min_value(), Int::max_value())]; | |

for &(low, high) in v.iter() { | |

let mut sampler: Range<$ty> = Range::new(low, high); | |

for _ in 0..1000 { | |

let v = sampler.sample(&mut rng); | |

assert!(low <= v && v < high); | |

let v = sampler.ind_sample(&mut rng); | |

assert!(low <= v && v < high); | |

} | |

} | |

)* | |

}} | |

} | |

t!(i8, i16, i32, i64, isize, | |

u8, u16, u32, u64, usize) | |

} | |

#[test] | |

fn test_floats() { | |

let mut rng = ::test::rng(); | |

macro_rules! t { | |

($($ty:ty),*) => {{ | |

$( | |

let v: &[($ty, $ty)] = &[(0.0, 100.0), | |

(-1e35, -1e25), | |

(1e-35, 1e-25), | |

(-1e35, 1e35)]; | |

for &(low, high) in v.iter() { | |

let mut sampler: Range<$ty> = Range::new(low, high); | |

for _ in 0..1000 { | |

let v = sampler.sample(&mut rng); | |

assert!(low <= v && v < high); | |

let v = sampler.ind_sample(&mut rng); | |

assert!(low <= v && v < high); | |

} | |

} | |

)* | |

}} | |

} | |

t!(f32, f64) | |

} | |

} |