// 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::num::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);
/// }
/// ```
#[derive(Clone, Copy, Debug)]
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 : Sized {
/// 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:ident) => {
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.
#[inline]
fn construct_range(low: $ty, high: $ty) -> Range<$ty> {
let range = (w(high as $unsigned) - w(low as $unsigned)).0;
let unsigned_max: $unsigned = ::core::$unsigned::MAX;
// 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 }
#[cfg(feature = "i128_support")]
integer_impl! { i128, u128 }
integer_impl! { isize, usize }
integer_impl! { u8, u8 }
integer_impl! { u16, u16 }
integer_impl! { u32, u32 }
integer_impl! { u64, u64 }
#[cfg(feature = "i128_support")]
integer_impl! { u128, u128 }
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::<$ty>()
}
}
}
}
float_impl! { f32 }
float_impl! { f64 }
#[cfg(test)]
mod tests {
use distributions::{Sample, IndependentSample};
use super::Range as Range;
#[should_panic]
#[test]
fn test_range_bad_limits_equal() {
Range::new(10, 10);
}
#[should_panic]
#[test]
fn test_range_bad_limits_flipped() {
Range::new(10, 5);
}
#[test]
fn test_integers() {
let mut rng = ::test::rng();
macro_rules! t {
($($ty:ident),*) => {{
$(
let v: &[($ty, $ty)] = &[(0, 10),
(10, 127),
(::core::$ty::MIN, ::core::$ty::MAX)];
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);
}
}
)*
}}
}
#[cfg(not(feature = "i128_support"))]
t!(i8, i16, i32, i64, isize,
u8, u16, u32, u64, usize);
#[cfg(feature = "i128_support")]
t!(i8, i16, i32, i64, i128, isize,
u8, u16, u32, u64, u128, 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)
}
}