//! Definition of the `BuildRandom` trait and implementations of it for built-in
//! (etc.) types.

use {Random, RandomGen};

use std::num::Wrapping;
use std::ops::{Range, RangeInclusive};

/// A type defining some distribution for generating (pseudo-)random values.
///
/// If a type `B` implements `BuildRandom<R>`, then `B` can be used to generate
/// values of `R` in some distribution.
pub trait BuildRandom<R> {
    /// Randomly generates a value according to some distribution.
    ///
    /// `self` specifies a distribution for generating an `R` using a
    /// [`RandomGen`].
    ///
    /// [`RandomGen`] provides the wrapper method [`build`], which may (or may
    /// not) be more convenient.
    ///
    /// # Panics
    ///
    /// Depending on the instance, this method might panic, e.g. if the
    /// parameters are invalid. See the particular instance's documentation for
    /// details.
    ///
    /// [`build`]: trait.RandomGen.html#method.build
    /// [`RandomGen`]: trait.RandomGen.html
    fn build<G: RandomGen>(&self, rng: &mut G) -> R;
}

// TODO @Feature weighted selection from a list (might need wrapper)
// TODO @Feature normal distribution
// TODO @Feature poisson distribution
// TODO @Feature binomial distribution
// TODO @Feature `BuildRandom` impl corresponding with `choose_from`

/// Macro for generating `BuildRandom<{integer}>` instances for
/// `Range<{integer}>`.
///
/// The first parameter is the integer type the instance is generated for, the
/// second paramter must be the unsigned integer type of the same size.
// TODO: @Completeness this wants to use RangeArgument when that's stable
// this would also allow for the maximum value to be included in a
// range, since right now, the end of the range is exclusive.
macro_rules! impl_build_random_for_integer_ranges {
    ($ty:ident, $unsigned:ident) => {
        impl BuildRandom<$ty> for Range<$ty> {
            /// Generates a uniformly distributed integer in the range.
            ///
            /// # Panics
            ///
            /// Panics if `self.start >= self.end`.
            fn build<G: RandomGen>(&self, rng: &mut G) -> $ty {
                assert!(self.end > self.start,
                        "End of range must be greater than start of range.");

                let range: $unsigned =
                    (Wrapping(self.end as $unsigned)
                   - Wrapping(self.start as $unsigned)).0;
                let max_accept: $unsigned =
                    ::std::$unsigned::MAX - ::std::$unsigned::MAX % range;

                loop {
                    let offset: $unsigned = rng.gen::<$unsigned>();

                    if offset < max_accept {
                        return (Wrapping(self.start) +
                                Wrapping((offset % range) as $ty)).0;
                    }
                }
            }
        }

        impl BuildRandom<$ty> for RangeInclusive<$ty> {
            /// Generates a uniformly distributed integer in the inclusive range.
            ///
            /// # Panics
            ///
            /// Panics if `self.start > self.end`.
            fn build<G: RandomGen>(&self, rng: &mut G) -> $ty {
                assert!(self.end() >= self.start(),
                        "End of inclusive range mustn't be less than start of range.");

                if *self.end() != ::std::$ty::MAX {
                    (*self.start()..*self.end() + 1).build(rng)
                } else if *self.start() != ::std::$ty::MIN {
                    ((*self.start() - 1)..*self.end()).build(rng) + 1
                } else {
                    rng.gen::<$ty>()
                }
            }
        }
    }
}

impl_build_random_for_integer_ranges!(   u8,    u8);
impl_build_random_for_integer_ranges!(  u16,   u16);
impl_build_random_for_integer_ranges!(  u32,   u32);
impl_build_random_for_integer_ranges!(  u64,   u64);
impl_build_random_for_integer_ranges!( u128,  u128);
impl_build_random_for_integer_ranges!(usize, usize);
impl_build_random_for_integer_ranges!(   i8,    u8);
impl_build_random_for_integer_ranges!(  i16,   u16);
impl_build_random_for_integer_ranges!(  i32,   u32);
impl_build_random_for_integer_ranges!(  i64,   u64);
impl_build_random_for_integer_ranges!( i128,  u128);
impl_build_random_for_integer_ranges!(isize, usize);

/// Wrapper type for generating floating point numbers in [0.0, 1.0).
// right now this is private as it's mainly a helper for ourselves.
struct Halfopen01<F>(pub F);

macro_rules! impl_random_for_halfopen {
    ($ty:ty) => {
        impl Random for Halfopen01<$ty> {
            /// Generates uniformly distributed values in [0.0, 1.0).
            #[cfg_attr(feature = "cargo-clippy", allow(float_cmp))]
            fn random<G: RandomGen>(rng: &mut G) -> Halfopen01<$ty> {
                loop {
                    let f = rng.gen::<$ty>();
                    if f != 1.0 {
                        return Halfopen01(f);
                    }
                }
            }
        }
    }
}

impl_random_for_halfopen!(f32);
impl_random_for_halfopen!(f64);

/// Macro for generating `BuildRandom<{float}>` instances for `Range<{float}>`.
///
/// The parameter is the type the instance is generated for.
// TODO @Feature generate the number directly, instead of just scaling [0.0,1.0].
// the number of bits we'd want to sample might be significantly larger than
// just for a number in [0, 1]. generating the number directly from a stream of
// bits would also ensure all possible values are generatable.
//                                                     -- lukaramu, 2017-07-21
macro_rules! impl_build_random_for_float_ranges {
    ($ty:ty) => {
        impl BuildRandom<$ty> for Range<$ty> {
            /// Generates a uniformly distributed floating point value in the
            /// range.
            ///
            /// Note that as of 2017-07-22,
            /// not all possibble values in the range are generated; the number
            /// of possible values is currently bound by the number of values
            /// generatable by the float types' `Random` instance.
            ///
            /// # Panics
            ///
            /// Panics if `self.start >= self.end`.
            fn build<G: RandomGen>(&self, rng: &mut G) -> $ty {
                assert!(self.end > self.start,
                        "End of range must be greater than start of range.");

                (self.end - self.start).mul_add(rng.gen::<Halfopen01<$ty>>().0, self.start)
            }
        }

        impl BuildRandom<$ty> for RangeInclusive<$ty> {
            /// Generates a uniformly distributed floating point value in the
            /// range.
            ///
            /// Note that as of 2017-07-22,
            /// not all possibble values in the range are generated; the number
            /// of possible values is currently bound by the number of values
            /// generatable by the float types' `Random` instance.
            ///
            /// # Panics
            ///
            /// Panics if `self.start > self.end`.
            fn build<G: RandomGen>(&self, rng: &mut G) -> $ty {
                assert!(self.end() >= self.start(),
                        "End of range mustn't be less than start of range.");

                (*self.end() - *self.start()).mul_add(rng.gen::<$ty>(), *self.start())
            }
        }
    }
}

impl_build_random_for_float_ranges!(f32);
impl_build_random_for_float_ranges!(f64);

/// Macro for generating `BuildRandom<bool>` instances for floating point
/// types.
///
/// The parameter is the floating point type that is used for generation.
macro_rules! impl_build_random_for_weighted_bool {
    ($ty:ty) => {
        impl BuildRandom<bool> for $ty {
            /// Returns `true` with a given probability.
            ///
            /// `self` is the probability with which `true` is returned.
            ///
            /// # Panics
            ///
            /// Panics if `self` is not in [0.0, 1.0], i.e. if `self` is not a
            /// probability.
            fn build<G: RandomGen>(&self, rng: &mut G) -> bool {
                let prob = *self;

                assert!(prob >= 0.0, "Probability must be >= 0.0");
                assert!(prob <= 1.0, "Probability must be <= 1.0");

                rng.gen::<$ty>() < prob
            }
        }
    }
}

impl_build_random_for_weighted_bool!(f32);
impl_build_random_for_weighted_bool!(f64);

/// This instance creates `BuildRandom<Option<R>>` instances for types that
/// have `BuildRandom<bool>` instances.
impl<B: BuildRandom<bool>, R: Random> BuildRandom<Option<R>> for B {
    /// Returns `Some` random value, or `None`.
    ///
    /// If the corresponding `BuildRandom<bool>` instance generates `true`, then
    /// `Some` random value is generated; else `None` is returned.
    fn build<G: RandomGen>(&self, rng: &mut G) -> Option<R> {
        if self.build(rng) {
            Some(rng.gen())
        } else {
            None
        }
    }
}

/// Wrapper struct for the constant distribution.
pub struct Const<T>(pub T);

impl<T: Clone> BuildRandom<T> for Const<T> {
    /// Returns `self.0`.
    fn build<G: RandomGen>(&self, _rng: &mut G) -> T {
        self.0.clone()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use Pcg;

    #[test]
    fn build_random_from_unsigned_integer_range() {
        let mut rng = Pcg::new(0x1337BEEF, 0);

        for x in 0..1000 {
            let sample = (x..x + 100).build(&mut rng);

            assert!(sample >= x);
            assert!(sample < x + 100);
        }

        for x in 0..1000 {
            let sample = (x..=x + 100).build(&mut rng);

            assert!(sample >= x);
            assert!(sample <= x + 100);
        }
    }

    #[test]
    fn build_random_from_signed_integer_range() {
        let mut rng = Pcg::new(0x1337BEEF, 0);

        for x in (-500i16)..500 {
            let sample = (x..x + 100).build(&mut rng);

            assert!(sample >= x);
            assert!(sample < x + 100);
        }

        for x in (-500i16)..500 {
            let sample = (x..=x + 100).build(&mut rng);

            assert!(sample >= x);
            assert!(sample <= x + 100);
        }
    }

    #[test]
    fn build_random_inclusive_integer_range_special_cases() {
        let mut rng = Pcg::new(49849898165, 0);

        let _ = (::std::u64::MIN..=::std::u64::MAX).build(&mut rng);

        for _ in 0..1000 {
            let sample = (::std::u64::MAX - 1..=::std::u64::MAX).build(&mut rng);

            assert!(sample >= ::std::u64::MAX - 1);
            assert!(sample <= ::std::u64::MAX);
        }

        for x in ::std::u64::MAX - 1000..=::std::u64::MAX {
            let sample = (x..=x).build(&mut rng);

            assert!(sample == x);
        }
    }

    #[test]
    fn build_random_from_integer_range_with_single_element() {
        let mut rng = Pcg::new(123456789, 1234);

        for x in 0..1000 {
            assert_eq!(x, (x..x + 1).build(&mut rng));
        }

        for x in 0..1000 {
            assert_eq!(x, (x..=x).build(&mut rng));
        }
    }

    #[test]
    fn build_random_from_float_range() {
        let mut rng = Pcg::new(777888999, 444555666);

        for x in (-500)..500 {
            let y = x as f64;
            let sample: f64 = (y..y + 87.0).build(&mut rng);

            assert!(sample >= y);
            assert!(sample < y + 87.0);
        }

        for x in (-500)..500 {
            let y = x as f64;
            let sample: f64 = (y..=y + 87.0).build(&mut rng);

            assert!(sample >= y);
            assert!(sample <= y + 87.0);
        }
    }
}