random_sequence 0.1.1

//!Generate a random shuffle of the numbers between start (inclusive) and end (exclusive) in O(1) space.
//!
//! No repeats will be generated. No number in the range won't be generated.
//!

use rand::Rng;
use primes::is_prime;
use num::Integer;

fn first_prime_above(mut value: u64) -> u64 {
    while !is_prime(value) {
        value += 1;
    }
    value
}

pub struct RandomSequence {
    curr: u64,
    modulus: u64,
    offset: u64,
    range_size: u64,
    a: u64,
    c: u64,
    num_generated: u64,
}

impl RandomSequence {

    /// Generate a random shuffle of the numbers between start (inclusive) and end (exclusive)
    ///
    /// No repeats will be generated. No number in the range won't be generated.
    ///
    /// The space complexity of this system is O(1), and time complexity O(n) (obviously)
    fn new(start: u64, end: u64) -> Self {
        assert!(end >= start);
        let length = end - start;

        // first value (seed)
        let seed: u64 = rand::thread_rng().gen();

        // modulus
        let m = first_prime_above(length);

        // multiplier (2m + 1) to make sure (a-1) % m == 0
        let a: u64 = (m * 2) + 1;

        // offset
        let c: u64 = rand::thread_rng().gen();

        let mut c = c % m;
        // Make sure c is never 0
        if c == 0 {
            c += 1;
        }

        // m prime
        assert!(is_prime(m));
        // c not 0
        assert_ne!(c, 0);
        // c and m relatively prime
        assert!(m.gcd(&c) == 1 && c.gcd(&m) == 1);
        // a - 1 divisible by m (which is the only prime factor of m, m is prime)
        assert_eq!((a - 1) % m, 0);

        // if m is divisible by 4, then a-1 is
        if m % 4 == 0 {
            assert_eq!((a - 1) % 4, 0);
        }

        Self {
            curr: seed % m,
            modulus: m,
            offset: start,
            range_size: length,
            a,
            c,
            num_generated: 0,
        }
    }
}

impl Iterator for RandomSequence {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.num_generated > self.range_size {
            return None
        }

        loop {
            self.curr = ((self.a as u128 * self.curr as u128 + self.c as u128) % self.modulus as u128) as u64;

            if self.curr <= self.range_size {
                self.num_generated += 1;
                break;
            }
        }


        Some(self.curr + self.offset)
    }
}


#[cfg(test)]
mod tests {
    extern crate std;

    use std::collections::HashMap;
    use crate::RandomSequence;

    #[test]
    fn test() {

        let start = 1000;
        let end = 100000;
        let mut seen = HashMap::new();

        for i in RandomSequence::new(start, end) {
            *seen.entry(i).or_insert(0) += 1;
        }


        for i in start..end {
            assert_eq!(seen.get(&i), Some(&1));
        }
    }

}