use std::cell::Cell;
use std::time::SystemTime;
use std::time::UNIX_EPOCH;
const MULTIPLIER: u64 = 6364136223846793005;
const INCREMENT: u64 = 1442695040888963407;
#[derive(Debug)]
pub(crate) struct Rng {
state: Cell<u64>,
}
impl Rng {
pub(crate) fn new() -> Self {
let seed = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap()
.as_nanos() as u64;
Self::with_seed(seed)
}
pub(crate) fn with_seed(seed: u64) -> Self {
let state = seed.wrapping_add(INCREMENT);
Self {
state: Cell::new(state),
}
}
pub(crate) fn rand_u32(&self) -> u32 {
fn rotr32(x: u32, r: usize) -> u32 {
x >> r | x << (!r & 31)
}
let mut x = self.state.get();
let count = (x >> 59) as usize;
let () = self
.state
.set(x.wrapping_mul(MULTIPLIER).wrapping_add(INCREMENT));
x ^= x >> 18;
rotr32((x >> 27) as u32, count)
}
}
impl private::Sealed for Rng {}
mod private {
pub trait Sealed {}
}
pub(crate) trait RandExt: private::Sealed {
fn shuffle<T>(&self, slice: &mut [T]);
}
impl RandExt for Rng {
fn shuffle<T>(&self, slice: &mut [T]) {
let len = slice.len();
for _ in 0..len {
let idx1 = self.rand_u32() as usize % len;
let idx2 = self.rand_u32() as usize % len;
let () = slice.swap(idx1, idx2);
}
}
}
#[cfg(test)]
mod tests {
use std::collections::HashSet;
use super::*;
#[test]
fn rng_randomness() {
let rng = Rng::new();
let set = (0..10).map(|_| rng.rand_u32()).collect::<HashSet<u32>>();
assert!(set.len() > 5, "{set:#?}");
}
#[test]
fn rng_seed_dependence() {
let rng1 = Rng::with_seed(42);
let rng2 = Rng::with_seed(42);
(0..10).for_each(|_| {
assert_eq!(rng1.rand_u32(), rng2.rand_u32());
})
}
#[test]
fn slice_shuffling() {
let vec1 = (0usize..20).collect::<Vec<_>>();
let mut vec2 = vec1.clone();
let rng = Rng::new();
let () = rng.shuffle(&mut vec2);
assert_ne!(vec2, vec1);
}
}