//! trinity John 3:16
//! 
//! A [MT19937](https://en.wikipedia.org/wiki/Mersenne_Twister) 
//! PRNG implementation for Rust.

/*
 * TODO:
 *
 *      Add more utility methods
 *
 *      Create tests for each implementation
 *
 */

use std::time::{SystemTime, UNIX_EPOCH};

// Algorithm constants

const WORD_SIZE: u64 = 32;
const RECURRENCE: usize = 624;
const MIDDLE_WORD: u64 = 397;
const SEP_POINT: u64 = 31;
const A: u64 = 0x9908B0DF;
const U: u64 = 11;
const D: u64 = 0xFFFFFFFF;
const S: u64 = 7;
const B: u64 = 0x9D2C5680;
const T: u64 = 15;
const C: u64 = 0xEFC60000;
const L: u64 = 18;
const F: u64 = 1812433253;
const LOWER_MASK: u64 = ( 1 << SEP_POINT ) - 1;
const UPPER_MASK: u64 = 0xFFFFFFFF & !LOWER_MASK;

/// Largest possible number from next()
pub const MAX: u64 = 4294967295; 

/// Contains state of PRNG
pub struct MT {
    state: [u64; RECURRENCE],
    index: usize,
}

impl MT {

    /// Create new PRNG seeded with the current timestamp
    pub fn new() -> MT {

        // Create new generator
        let mut gen = MT {
            state: [0; RECURRENCE],
            index: RECURRENCE + 1,
        };

        // Seed generator
        gen.seed( 
            SystemTime::now()
            .duration_since( UNIX_EPOCH )
            .unwrap()
            .as_nanos() as u32 as u64
        );

        gen

    }

    /// Creates a new generator seeded with the given seed
    pub fn from_seed( seed: u64 ) -> MT {

         // Create new generator
         let mut gen = MT {
            state: [0; RECURRENCE],
            index: RECURRENCE + 1,
        };

        // Seed generator
        gen.seed( 
            seed
        );

        gen

    }

    // Algorithm methods

    /// Seed the generator
    /// 
    /// Newly created MTs are seeded with the current
    /// timestamp.
    pub fn seed( &mut self, seed: u64 ) {

        self.index = RECURRENCE;
        self.state[0] = seed;

        for i in 1..RECURRENCE {
            self.state[i] = 0xFFFFFFFF & ( F * ( self.state[ i - 1 ] ^ ( self.state[i - 1] >> ( WORD_SIZE - 2 ) ) + i as u64 ) );
        }


    }

    /// Interpolate the next integer using MT19937
    /// 
    /// This method should not be used for generating
    /// random numbers within a specific range. For that
    /// use any of the methods prefixed with "rand".
    pub fn next( &mut self ) -> u64 {

        if self.index == RECURRENCE {
            self.twist();
        }

        let mut y = self.state[ self.index ];
        y ^= ( y >> U ) & D;
        y ^= ( y << S ) & B;
        y ^= ( y << T ) & C;
        y ^= y >> L;

        self.index = self.index + 1;
        0xFFFFFFFF & y

    }

    // Get new state
    fn twist( &mut self ) {

        for i in 0..RECURRENCE {

            let x = ( self.state[i] & UPPER_MASK ) + ( self.state[(i+1) % RECURRENCE] & LOWER_MASK );
            let mut x_a = x >> 1;

            if  x % 2 != 0 {
                x_a ^= A;
            }

            self.state[i] = self.state[ ( ( i as u64 + MIDDLE_WORD ) % RECURRENCE as u64 ) as usize ] ^ x_a;

        }

        self.index = 0;

    }

    // Secondary methods(Depedent on Algorithm methods)

    /// Generate an ```f32``` between 0.0 and 1.0
    /// 
    /// # Example
    /// 
    /// ```
    /// let mut gen = rustmt::MT::new();
    /// let n = gen.rand_f32();
    /// 
    /// assert!( n >= 0.0 );
    /// assert!( n <= 1.0 );
    /// ```
    pub fn rand_f32( &mut self ) -> f32 {
        self.next() as f32 / ( ( 2u64.pow( WORD_SIZE as u32 ) - 1 ) as f32 )
    }

    /// Generate an ```f64``` between 0.0 and 1.0
    /// 
    /// # Example
    /// 
    /// ```
    /// let mut gen = rustmt::MT::new();
    /// let n = gen.rand_f64();
    /// 
    /// assert!( n >= 0.0 );
    /// assert!( n <= 1.0 );
    /// ```
    pub fn rand_f64( &mut self ) -> f64 {
        self.next() as f64 / ( ( 2i64.pow( WORD_SIZE as u32 ) - 1 ) as f64 )
    }

    /// Generate an ```i32``` between start-```end-1``` inclusive
    /// 
    /// # Example
    /// 
    /// ```
    /// let mut gen = rustmt::MT::new();
    /// let n = gen.rand_i32( 1, 3 );
    /// 
    /// assert!( n >= 1 );
    /// assert!( n < 3 );
    /// ```
    /// # Panics
    /// 
    /// When ```start``` is greater than or equal to ```end```
    pub fn rand_i32( &mut self, start: i32, end: i32 ) -> i32 {
        assert!( start < end, "MT Error: start must be < end" );
        start + ( ( self.rand_f32() * ( end - start ) as f32 ) as i32 )
    }

    /// Generate an ```i64``` between start-```end-1``` inclusive
    /// 
    /// # Example
    /// 
    /// ```
    /// let mut gen = rustmt::MT::new();
    /// let n = gen.rand_i64( 1, 3 );
    /// 
    /// assert!( n >= 1 );
    /// assert!( n < 3 );
    /// ```
    /// 
    /// # Panics
    /// 
    /// When ```start``` is greater than or equal to ```end```
    pub fn rand_i64( &mut self, start: i64, end: i64 ) -> i64 {
        assert!( start < end, "MT Error: start must be < end" );
        start + ( ( self.rand_f32() * ( end - start ) as f32 ) as i64 )
    }

    /// Generate a ```usize``` less than ```end```
    /// 
    /// # Example
    /// 
    /// ```
    /// let mut gen = rustmt::MT::new();
    /// 
    /// let v = vec![ 1, 2, 3, ];
    /// let n = gen.rand_usize( v.len() );
    /// 
    /// assert!( n < v.len() );
    /// ```
    pub fn rand_usize( &mut self, end: usize ) -> usize {
        ( self.rand_f32() * end as f32 ) as usize
    }

    // Tertiary methods(Dependent upon secondary methods)

    /// Shuffle the given vector
    /// 
    /// # Example
    /// 
    /// ```
    /// let mut gen = rustmt::MT::new();
    /// 
    /// let mut people = vec![ "Logan", "Trent", "Cameron", "David", ];
    /// gen.shuffle( &mut people );
    /// 
    /// println!( "Random person = {}", people[0] );
    /// ```
    pub fn shuffle<T>( &mut self, v: &mut Vec<T> ) {

        let len = v.len();

        for _ in 0..len {
            let element = v.swap_remove( self.rand_usize( len ) as usize );
            v.push( element );
        }

    }

}

// Test

#[cfg(test)]
mod tests {

    use super::*;
    
    // Test Constants
    const RAND_I32_START: i32 = -10;
    const RAND_I32_END: i32 = 10;
    const RAND_I64_START: i64 = -10;
    const RAND_I64_END: i64 = 10;

    // Bound tests

    // Ensure next() returns results less than MAX
    #[test]
    fn next_bounds() {

        let mut gen = MT::new();

        for _ in 1..100 {
            let n = gen.next();
            assert!( n <= MAX );
        }

    }

    // Ensure rand_f32() returns results between 0.0 and 1.0
    #[test]
    fn rand_f32_bounds() {

        let mut gen = MT::new();

        for _ in 1..100 {

            let n = gen.rand_f32();
            assert!( n >= 0.0 );
            assert!( n <= 1.0 );

        }

    }

    // Ensure rand_f64() returns results between 0.0 and 1.0
    #[test]
    fn rand_f64_bounds() {

        let mut gen = MT::new();

        for _ in 1..100 {

            let n = gen.rand_f64();
            assert!( n >= 0.0 );
            assert!( n <= 1.0 );
            
        }

    }

    // Ensure rand_i32() returns results between arguments given
    #[test]
    fn rand_i32_bounds() {
        
        let mut gen = MT::new();

        for _ in 1..1000 {

            let n = gen.rand_i32( RAND_I32_START, RAND_I32_END );
            assert!( n >= RAND_I32_START );
            assert!( n < RAND_I32_END );

        }

    }

    // Ensure rand_i64() returns results between arguments given
    #[test]
    fn rand_i64_bounds() {
        
        let mut gen = MT::new();

        for _ in 1..1000 {

            let n = gen.rand_i64( RAND_I64_START, RAND_I64_END );
            assert!( n >= RAND_I64_START );
            assert!( n < RAND_I64_END );

        }

    }

    // Ensure rand_usize returns results less than the argument given
    #[test]
    fn rand_usize_bounds() {

        let mut gen = MT::new();

        for _ in 0..100 {

            let n = gen.rand_usize( 3 );
            assert!( n < 3 );

        }

    }

    // Error tests
    
    // Ensure rand_i32() errors on invalid arguments
    #[test]
    #[should_panic( expected = "MT Error: start must be < end")]
    fn rand_i32_error() {

        let mut gen = MT::new();
        gen.rand_i32( 100, 0 );

    }
    
    // Ensure rand_i64() errors on invalid arguments
    #[test]
    #[should_panic( expected = "MT Error: start must be < end" )]
    fn rand_i64_error() {

        let mut gen = MT::new();
        gen.rand_i64( 100, 0 );

    }

    // Randomness tests

    // Ensure period length is at least 20,000 (Although it is actually 2^19937 - 1)
    #[test]
    #[ignore]
    fn period_length_test() {

        let mut gen = MT::new();
        let mut nums: Vec<u64> = vec![];
        let mut dups = 0;

        for _ in 1..20000 {

            let n = gen.next();
            
            // Check for duplicate
            if !nums.contains( &n ) {
                nums.push( n );
            } else {
                dups += 1;
            }

        }

        assert!( dups == 0 );

    }

}