use {Rng, Rand};
pub use self::range::Range;
#[cfg(feature="std")]
pub use self::gamma::{Gamma, ChiSquared, FisherF, StudentT};
#[cfg(feature="std")]
pub use self::normal::{Normal, LogNormal};
#[cfg(feature="std")]
pub use self::exponential::Exp;
pub mod range;
#[cfg(feature="std")]
pub mod gamma;
#[cfg(feature="std")]
pub mod normal;
#[cfg(feature="std")]
pub mod exponential;
#[cfg(feature="std")]
mod ziggurat_tables;
#[deprecated(since="0.5.0", note="use Distribution instead")]
pub trait Sample<Support> {
fn sample<R: Rng>(&mut self, rng: &mut R) -> Support;
}
#[allow(deprecated)]
#[deprecated(since="0.5.0", note="use Distribution instead")]
pub trait IndependentSample<Support>: Sample<Support> {
fn ind_sample<R: Rng>(&self, &mut R) -> Support;
}
#[allow(deprecated)]
mod impls {
use Rng;
use distributions::{Distribution, Sample, IndependentSample,
Default, WeightedChoice};
use distributions::exponential::Exp;
use distributions::gamma::{Gamma, ChiSquared, FisherF, StudentT};
use distributions::normal::{Normal, LogNormal};
use distributions::range::{Range, SampleRange};
impl<T> Sample<T> for Default where Default: Distribution<T> {
fn sample<R: Rng>(&mut self, rng: &mut R) -> T {
Default.sample(rng)
}
}
impl<T: Rand> IndependentSample<T> for Default where Default: Distribution<T> {
fn ind_sample<R: Rng>(&self, rng: &mut R) -> T {
Default.sample(rng)
}
}
impl<'a, T: Clone> Sample<T> for WeightedChoice<'a, T> {
fn sample<R: Rng>(&mut self, rng: &mut R) -> T {
Distribution::sample(self, rng)
}
}
impl<'a, T: Clone> IndependentSample<T> for WeightedChoice<'a, T> {
fn ind_sample<R: Rng>(&self, rng: &mut R) -> T {
Distribution::sample(self, rng)
}
}
impl<Sup: SampleRange> Sample<Sup> for Range<Sup> {
fn sample<R: Rng>(&mut self, rng: &mut R) -> Sup {
Distribution::sample(self, rng)
}
}
impl<Sup: SampleRange> IndependentSample<Sup> for Range<Sup> {
fn ind_sample<R: Rng>(&self, rng: &mut R) -> Sup {
Distribution::sample(self, rng)
}
}
macro_rules! impl_f64 {
($($name: ident), *) => {
$(
impl Sample<f64> for $name {
fn sample<R: Rng>(&mut self, rng: &mut R) -> f64 {
Distribution::sample(self, rng)
}
}
impl IndependentSample<f64> for $name {
fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 {
Distribution::sample(self, rng)
}
}
)*
}
}
impl_f64!(Exp, Gamma, ChiSquared, FisherF, StudentT, Normal, LogNormal);
}
pub trait Distribution<T> {
fn sample<R: Rng>(&self, rng: &mut R) -> T;
}
impl<'a, T, D: Distribution<T>> Distribution<T> for &'a D {
fn sample<R: Rng>(&self, rng: &mut R) -> T {
(*self).sample(rng)
}
}
#[derive(Copy, Clone, Debug)]
pub struct Default;
pub trait Rand : Sized {
fn rand<R: Rng+?Sized>(rng: &mut R) -> Self;
}
impl<T> Rand for T where Default: Distribution<T> {
fn rand<R: Rng+?Sized>(rng: &mut R) -> Self {
Default.sample(rng)
}
}
#[derive(Copy, Clone, Debug)]
pub struct Weighted<T> {
pub weight: u32,
pub item: T,
}
#[derive(Debug)]
pub struct WeightedChoice<'a, T:'a> {
items: &'a mut [Weighted<T>],
weight_range: Range<u32>
}
impl<'a, T: Clone> WeightedChoice<'a, T> {
pub fn new(items: &'a mut [Weighted<T>]) -> WeightedChoice<'a, T> {
assert!(!items.is_empty(), "WeightedChoice::new called with no items");
let mut running_total: u32 = 0;
for item in items.iter_mut() {
running_total = match running_total.checked_add(item.weight) {
Some(n) => n,
None => panic!("WeightedChoice::new called with a total weight \
larger than a u32 can contain")
};
item.weight = running_total;
}
assert!(running_total != 0, "WeightedChoice::new called with a total weight of 0");
WeightedChoice {
items: items,
weight_range: Range::new(0, running_total)
}
}
}
impl<'a, T: Clone> Distribution<T> for WeightedChoice<'a, T> {
fn sample<R: Rng>(&self, rng: &mut R) -> T {
let sample_weight = self.weight_range.sample(rng);
if sample_weight < self.items[0].weight {
return self.items[0].item.clone();
}
let mut idx = 0;
let mut modifier = self.items.len();
while modifier > 1 {
let i = idx + modifier / 2;
if self.items[i].weight <= sample_weight {
idx = i;
modifier += 1;
} else {
}
modifier /= 2;
}
return self.items[idx + 1].item.clone();
}
}
#[cfg(feature="std")]
#[inline(always)]
fn ziggurat<R: Rng, P, Z>(
rng: &mut R,
symmetric: bool,
x_tab: ziggurat_tables::ZigTable,
f_tab: ziggurat_tables::ZigTable,
mut pdf: P,
mut zero_case: Z)
-> f64 where P: FnMut(f64) -> f64, Z: FnMut(&mut R, f64) -> f64
{
use Sample;
const SCALE: f64 = (1u64 << 53) as f64;
loop {
let bits: u64 = rng.gen();
let i = (bits & 0xff) as usize;
let f = (bits >> 11) as f64 / SCALE;
let u = if symmetric {2.0 * f - 1.0} else {f};
let x = u * x_tab[i];
let test_x = if symmetric { x.abs() } else {x};
if test_x < x_tab[i + 1] {
return x;
}
if i == 0 {
return zero_case(rng, u);
}
if f_tab[i + 1] + (f_tab[i] - f_tab[i + 1]) * rng.gen::<f64>() < pdf(x) {
return x;
}
}
}
#[cfg(test)]
mod tests {
use Rng;
use impls;
use super::{WeightedChoice, Weighted, Distribution};
struct CountingRng { i: u32 }
impl Rng for CountingRng {
fn next_u32(&mut self) -> u32 {
self.i += 1;
self.i - 1
}
fn next_u64(&mut self) -> u64 {
self.next_u32() as u64
}
fn fill_bytes(&mut self, dest: &mut [u8]) {
impls::fill_bytes_via_u32(self, dest)
}
}
#[test]
fn test_weighted_choice() {
macro_rules! t {
($items:expr, $expected:expr) => {{
let mut items = $items;
let wc = WeightedChoice::new(&mut items);
let expected = $expected;
let mut rng = CountingRng { i: 0 };
for &val in expected.iter() {
assert_eq!(wc.sample(&mut rng), val)
}
}}
}
t!(vec!(Weighted { weight: 1, item: 10}), [10]);
t!(vec!(Weighted { weight: 0, item: 20},
Weighted { weight: 2, item: 21},
Weighted { weight: 0, item: 22},
Weighted { weight: 1, item: 23}),
[21,21, 23]);
t!(vec!(Weighted { weight: 4, item: 30},
Weighted { weight: 3, item: 31}),
[30,30,30,30, 31,31,31]);
t!(vec!(Weighted { weight: 1, item: 40},
Weighted { weight: 1, item: 41},
Weighted { weight: 1, item: 42},
Weighted { weight: 1, item: 43},
Weighted { weight: 1, item: 44}),
[40, 41, 42, 43, 44]);
t!(vec!(Weighted { weight: 1, item: 50},
Weighted { weight: 1, item: 51},
Weighted { weight: 1, item: 52},
Weighted { weight: 1, item: 53},
Weighted { weight: 1, item: 54},
Weighted { weight: 1, item: 55},
Weighted { weight: 1, item: 56}),
[50, 51, 52, 53, 54, 55, 56]);
}
#[test]
fn test_weighted_clone_initialization() {
let initial : Weighted<u32> = Weighted {weight: 1, item: 1};
let clone = initial.clone();
assert_eq!(initial.weight, clone.weight);
assert_eq!(initial.item, clone.item);
}
#[test] #[should_panic]
fn test_weighted_clone_change_weight() {
let initial : Weighted<u32> = Weighted {weight: 1, item: 1};
let mut clone = initial.clone();
clone.weight = 5;
assert_eq!(initial.weight, clone.weight);
}
#[test] #[should_panic]
fn test_weighted_clone_change_item() {
let initial : Weighted<u32> = Weighted {weight: 1, item: 1};
let mut clone = initial.clone();
clone.item = 5;
assert_eq!(initial.item, clone.item);
}
#[test] #[should_panic]
fn test_weighted_choice_no_items() {
WeightedChoice::<isize>::new(&mut []);
}
#[test] #[should_panic]
fn test_weighted_choice_zero_weight() {
WeightedChoice::new(&mut [Weighted { weight: 0, item: 0},
Weighted { weight: 0, item: 1}]);
}
#[test] #[should_panic]
fn test_weighted_choice_weight_overflows() {
let x = ::std::u32::MAX / 2; WeightedChoice::new(&mut [Weighted { weight: x, item: 0 },
Weighted { weight: 1, item: 1 },
Weighted { weight: x, item: 2 },
Weighted { weight: 1, item: 3 }]);
}
#[test] #[allow(deprecated)]
fn test_backwards_compat_sample() {
use distributions::{Sample, IndependentSample};
struct Constant<T> { val: T }
impl<T: Copy> Sample<T> for Constant<T> {
fn sample<R: Rng>(&mut self, _: &mut R) -> T { self.val }
}
impl<T: Copy> IndependentSample<T> for Constant<T> {
fn ind_sample<R: Rng>(&self, _: &mut R) -> T { self.val }
}
let mut sampler = Constant{ val: 293 };
assert_eq!(sampler.sample(&mut ::test::rng()), 293);
assert_eq!(sampler.ind_sample(&mut ::test::rng()), 293);
}
#[test] #[allow(deprecated)]
fn test_backwards_compat_exp() {
use distributions::{IndependentSample, Exp};
let sampler = Exp::new(1.0);
sampler.ind_sample(&mut ::test::rng());
}
}