use {Random, RandomGen};

use std::num::Wrapping;

/// A Permuted Congruential Generator.
///
/// [Permuted congruential generators][0] (PCGs) are [linear congruential
/// generators][1] that, instead of using their state as the random number,
/// permute their state.
/// This improves their statistical quality significantly, while maintaining
/// quite fast performance; they are however not cryptographically secure.
///
/// The main interface for this struct are its [`Rng`] and [`SeedableRng`]
/// implementations.
/// In addition, `Pcg` also provides functions for [advancing] and [reversing]
/// itself by an arbitrary amount of steps quickly.
///
/// `Pcg` provides for 2<sup>63</sup> different sequences, these are specified
/// by the second field of the seed (see [`reseed`]'s documentation).
/// It implements the "xsh-rr-64-32" scheme.
///
/// For more information on PCGs, see [pcgrandom.org][0].
///
/// [0]: http://www.pcg-random.org/
/// [1]: https://en.wikipedia.org/wiki/Linear_congruential_generator
/// [`Rng`]: trait.Rng.html
/// [`SeedableRng`]: trait.SeedableRng.html
/// [advancing]: #method.advance
/// [reversing]: #method.revert
/// [`reseed`]: #method.reseed
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Pcg {
    state: Wrapping<u64>,
    increment: Wrapping<u64>,
}

const PCG64_MULTIPLIER: Wrapping<u64> = Wrapping(6_364_136_223_846_793_005);

impl Pcg {
    /// Creates the `Pcg` with a given seed and sequence.
    ///
    /// The highest bit of `sequence` is ignored.
    pub fn new(seed: u64, sequence: u64) -> Pcg {
        let mut result = Pcg {
            state: Wrapping(0),
            increment: Wrapping((sequence << 1) + 1), // increment must be odd
        };

        result.step();
        result.state += Wrapping(seed);

        result
    }

    /// Steps the `Pcg`'s state.
    fn step(&mut self) {
        self.state = self.state * PCG64_MULTIPLIER + self.increment;
    }

    /// Advances the `Pcg` by `delta` steps.
    ///
    /// This uses a method similar to fast exponentiation and thus runs in
    /// O(log(`delta`)) time.
    pub fn advance(&mut self, mut delta: u64) {
        let mut cur_mult = PCG64_MULTIPLIER;
        let mut cur_plus = self.increment;
        let mut acc_mult = Wrapping(1);
        let mut acc_plus = Wrapping(0);
        while delta > 0 {
            if delta & 1 != 0 {
                acc_mult *= cur_mult;
                acc_plus = acc_plus * cur_mult + cur_plus;
            }
            cur_plus *= cur_mult + Wrapping(1);
            cur_mult *= cur_mult;
            delta /= 2;
        }
        self.state = self.state * acc_mult + acc_plus;
    }

    /// Reverses the `Pcg` by `delta` steps.
    ///
    /// This is a convenience method, reversing by `delta` steps is the same as
    /// [advancing] by 2<sup>64</sup>-`delta` steps.
    ///
    /// [advancing]: #method.advance
    pub fn revert(&mut self, delta: u64) {
        self.advance(-(delta as i64) as u64);
    }

    /// Calculates the distance between `Pcg`s of the same sequence.
    ///
    /// # Errors
    ///
    /// If `self` and `other` are on different streams, this method returns
    /// `None`.
    pub fn steps_since(&self, other: &Pcg) -> Option<u64> {
        if self.increment != other.increment {
            return None;
        }

        let mut old_state = other.state;
        let new_state = self.state;
        let mut cur_mult = PCG64_MULTIPLIER;
        let mut cur_plus = self.increment;
        let mut test_bit = Wrapping(1);
        let mut distance = Wrapping(0);

        while old_state != new_state {
            if (old_state & test_bit) != (new_state & test_bit) {
                old_state = old_state * cur_mult + cur_plus;
                distance |= test_bit;
            }
            debug_assert_eq!(old_state & test_bit, new_state & test_bit);
            test_bit <<= 1;
            cur_plus *= cur_mult + Wrapping(1);
            cur_mult *= cur_mult;
        }
        Some(distance.0)
    }
}

impl RandomGen for Pcg {
    fn gen_u32(&mut self) -> u32 {
        self.step();

        let Wrapping(state) = self.state;
        (((state ^ (state >> 18)) >> 27) as u32).rotate_right((state >> 59) as u32)
    }
}

impl Random for Pcg {
    fn random<G: RandomGen>(rng: &mut G) -> Pcg {
        Pcg::new(rng.gen(), rng.gen())
    }
}

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

    #[test]
    fn gen_u32_changes_state() {
        let seed = 0xBAD1DEA;
        let sequence = 0xBEEFBEEF;

        let rng_one = Pcg::new(seed, sequence);
        let mut rng_two = Pcg::new(seed, sequence);
        assert_eq!(rng_one, rng_two);

        let _ = rng_two.gen_u32();
        assert_ne!(rng_one, rng_two);
    }

    #[test]
    fn advance() {
        let mut rng_one = Pcg::new(0xDEADBEEF, 0xD15EA5E);
        let mut rng_two = rng_one.clone();

        let iterations = 12345;
        for _ in 0..iterations {
            rng_one.step();
        }

        rng_two.advance(iterations);

        assert_eq!(rng_one, rng_two);
    }

    #[test]
    fn revert() {
        let rng_one = Pcg::new(0xDEADDEADBEEF, 0xBADBAD1DEA5);
        let mut rng_two = rng_one.clone();

        let iterations = 14321;
        for _ in 0..iterations {
            rng_two.step();
        }

        rng_two.revert(iterations);

        assert_eq!(rng_one, rng_two);
    }

    #[test]
    fn steps_since_success() {
        let rng_one = Pcg::new(0x0123456789ABCDEF, 0x1FFFFFFF_C0000000);
        let mut rng_two = rng_one.clone();

        assert_eq!(rng_two.steps_since(&rng_one), Some(0));

        let steps = 123456789;
        rng_two.advance(steps);

        assert_eq!(rng_two.steps_since(&rng_one), Some(steps));
    }

    #[test]
    fn steps_since_failure() {
        let rng_one = Pcg::new(0, 0);
        let rng_two = Pcg::new(0, 1);

        assert_eq!(rng_two.steps_since(&rng_one), None);
    }
}