#![deny(missing_docs)]
#![allow(non_upper_case_globals)]

//! A dead simple to use randomization library for rust.
//!
//! Functions exist to use a lazily-initialized, mutex-guarded, global
//! generator. As you can guess, this is slower than necessary, so you can also
//! make your own generator and call methods on that. The exact nature of the
//! global generator is deliberately unspecified so that it can be improved or
//! replaced in future versions if necessary.
//!
//! This library gives priority to ease of use rather than trying to cover all
//! possible uses. If you want a totally comprehensive randomization library for
//! all possible cases then this really isn't for you.
//!
//! NOT FOR CRYPTOGRAPHIC PURPOSES.

use std::borrow::Borrow;
use std::ops::Range;
use std::ptr::null_mut;
use std::sync::atomic::{AtomicPtr, Ordering};
use std::sync::Mutex;
use std::time::{SystemTime, UNIX_EPOCH};

static globalGeneratorMutex: AtomicPtr<Mutex<PCG32>> = AtomicPtr::new(null_mut());
const theOrdering: Ordering = Ordering::SeqCst;

/// A permuted congruential generator with 32-bits of output per step.
///
/// The generator has two values, `state` and `inc`, which are both a `u64`. The
/// `state` controls "where" in a number stream the generator is. The `inc`
/// controls which number stream that generator is within in the first place.
/// Any `state` value is allowed (even 0), but only odd `inc` values are
/// allowed. So there are 2^64 possible states across 2^63 different streams.
///
/// Please see [the PCG paper](http://www.pcg-random.org/paper.html) for more
/// info on the how and why of it all.
#[derive(Debug, PartialEq, Eq, Hash)]
pub struct PCG32 {
  /// the state value of the generator
  state: u64,
  /// the generator's inc value (picks the stream).
  ///
  /// must be odd!
  inc: u64,
}

impl ::std::cmp::PartialOrd<PCG32> for PCG32 {
  /// The ordering here is not meaningful, but it is consistent and total.
  fn partial_cmp(&self, other: &PCG32) -> Option<::std::cmp::Ordering> {
    Some(match self.inc.cmp(&other.inc) {
      ::std::cmp::Ordering::Equal => self.state.cmp(&other.state),
      other => other,
    })
  }
}

impl ::std::cmp::Ord for PCG32 {
  fn cmp(&self, other: &PCG32) -> ::std::cmp::Ordering {
    match self.inc.cmp(&other.inc) {
      ::std::cmp::Ordering::Equal => self.state.cmp(&other.state),
      other => other,
    }
  }
}

impl PCG32 {
  /// Makes a new PCG32 using the system time.
  ///
  /// Repeated calls to this method in close succession are likely to generate
  /// identical generators because the creation process is too fast compared to
  /// the usual resolution of a system's clock. If you need more than one
  /// generator quickly, make the first one with this method and then after that
  /// call `gen.any()` on the first generator to make all the rest.
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = PCG32::from_time();
  ///
  /// ::std::thread::sleep(::std::time::Duration::new(0,50));
  ///
  /// let gen2 = PCG32::from_time();
  ///
  /// assert_ne!(gen, gen2);
  /// ```
  pub fn from_time() -> Self {
    let the_duration = match SystemTime::now().duration_since(UNIX_EPOCH) {
      Ok(duration) => duration,
      Err(system_time_error) => system_time_error.duration(),
    };
    let base_value = if the_duration.subsec_nanos() != 0 {
      the_duration.as_secs().wrapping_mul(the_duration.subsec_nanos() as u64)
    } else {
      the_duration.as_secs()
    };
    PCG32::from_state_and_inc(base_value, base_value)
  }

  /// Makes a PCG32 using the values given.
  ///
  /// The `inc` value given is OR'd with 1, so that it is always odd in the
  /// resulting generator.
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = PCG32::from_state_and_inc(20, 505);
  /// assert_eq!(gen.state(), 20);
  /// assert_eq!(gen.inc(), 505);
  ///
  /// let gen2 = PCG32::from_state_and_inc(300, 0);
  /// assert_eq!(gen2.state(), 300);
  /// assert_eq!(gen2.inc(), 1);
  /// ```
  pub fn from_state_and_inc(state: u64, inc: u64) -> Self {
    PCG32 { state, inc: inc | 1 }
  }

  /// Gives the current `state` value. This changes from use to use.
  pub fn state(&self) -> u64 {
    self.state
  }

  /// Gives the `inc` value. This is fixed across the life of the generator.
  pub fn inc(&self) -> u64 {
    self.inc
  }

  /// Obtains the next 32-bits of output from the generator.
  ///
  /// This is the "actual" function that all the other functions end up calling.
  pub fn next_u32(&mut self) -> u32 {
    const magic_LCG_mult: u64 = 6364136223846793005;
    let new_state: u64 = self.state.wrapping_mul(magic_LCG_mult).wrapping_add(self.inc);
    let xor_shifted: u32 = (((self.state >> 18) ^ self.state) >> 27) as u32;
    let rot: u32 = (self.state >> 59) as u32;
    let output = xor_shifted.rotate_right(rot);
    self.state = new_state;
    output
  }

  /// Generates a value using the `AnyRandom` instance for the type desired.
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = &mut PCG32::from_time();
  /// if gen.any() {
  ///   let x: u32 = gen.any();
  ///   println!("x as a u32: {}",x);
  /// } else {
  ///   let x: [char;3] = gen.any();
  ///   println!("x as an array of 3 chars: {:?}",x);
  /// }
  /// ```
  pub fn any<A: AnyRandom>(&mut self) -> A {
    AnyRandom::from_pcg32(self)
  }

  /// Returns a `char` value in the ASCII range (0-127).
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = &mut PCG32::from_time();
  /// for _ in 0 .. 5_000 {
  ///   assert!((gen.any_ascii() as u8) <= 127);
  /// }
  /// ```
  pub fn any_ascii(&mut self) -> char {
    // we keep the highest 7 bits, since those are the best quality.
    const ASCII_SHIFT: u32 = 32 - 7;
    (self.next_u32() >> ASCII_SHIFT) as u8 as char
  }

  /// Returns an `f32` value in the inclusive range 0.0 to 1.0.
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = &mut PCG32::from_time();
  /// for _ in 0 .. 5_000 {
  ///   let f = gen.any_f32_zero_to_one();
  ///   assert!(f >= 0.0 && f <= 1.0);
  /// }
  /// ```
  pub fn any_f32_zero_to_one(&mut self) -> f32 {
    const reciprocal_u32_max_float: f32 = 1.0 / ::std::u32::MAX as f32;
    self.next_u32() as f32 * reciprocal_u32_max_float
  }

  /// Returns `true` a percentage of the time (eg: 0.3 for 30%).
  ///
  /// With how many different floating point values there are in that range,
  /// this is "close enough" to the correct chances for most people. If you want
  /// exact odds you'll have to do some integral math, call `next_u32`, and
  /// potentially do re-rolls and stuff (which is what `in_range` does).
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = &mut PCG32::from_time();
  /// let mut hits = 0i32;
  /// for _ in 0 .. 100_000 {
  ///   if gen.percent_chance(0.3) {
  ///     hits += 1;
  ///   }
  /// }
  /// // the exact number is random, so we can only say it'll be "close enough"
  /// assert!((hits - 30_000).abs() < 1_000);
  ///
  /// // inputs that are "out of range" will always be `true` or `false`.
  /// assert!(gen.percent_chance(1.0));
  /// assert!(gen.percent_chance(1.1));
  /// assert!(!gen.percent_chance(0.0));
  /// assert!(!gen.percent_chance(-8.5));
  /// ```
  pub fn percent_chance(&mut self, chance: f32) -> bool {
    self.any_f32_zero_to_one() <= chance
  }

  /// Gives a value in the `Range` specified (inclusive of the bottom but
  /// exclusive of the top).
  ///
  /// Every position within an inhabited range will have an equal chance of
  /// being the result. This is a somewhat more expensive than a single mod
  /// operation, so if you want speed over precision you can also do something
  /// like `gen.any() % thing.len()`.
  ///
  /// Gives `None` if the range is empty.
  ///
  /// ```rust
  /// use randomize::PCG32;
  /// let gen = &mut PCG32::from_time();
  /// for &base in [0, 456, 93498383].iter() {
  ///   for &width in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 40, 50].iter() {
  ///     let range = base .. (base+width);
  ///     let out = gen.in_range(range.clone()).unwrap();
  ///     assert!(out >= range.start && out < range.end);
  ///   }
  /// }
  /// assert_eq!(gen.in_range(7..4), None);
  /// ```
  pub fn in_range<R: Borrow<Range<usize>>>(&mut self, r: R) -> Option<usize> {
    let r = r.borrow();
    if r.start < r.end {
      let range_width = r.end - r.start;
      let range_leftover = ::std::usize::MAX % range_width;
      let output_cap = ::std::usize::MAX - range_leftover;
      loop {
        let out = self.any::<usize>();
        if out >= output_cap {
          continue;
        } else {
          return Some(r.start + out % range_width);
        }
      }
    } else {
      None
    }
  }
}

/// These numbers all come from https://github.com/Lokathor/pcgen-hs/issues/3
#[test]
fn pcg32_basic_correctness_test() {
  let gen = &mut PCG32 { state: 505, inc: 505 };
  assert_eq!(gen.state, 505);
  assert_eq!(gen.inc, 505);

  let out = gen.next_u32();
  assert_eq!(out, 0);
  assert_eq!(gen.state, 4155324217168486846);
  assert_eq!(gen.inc, 505);

  let out = gen.next_u32();
  assert_eq!(out, 2926225613);
  assert_eq!(gen.state, 2179395809720005215);
  assert_eq!(gen.inc, 505);

  let out = gen.next_u32();
  assert_eq!(out, 1492848122);
  assert_eq!(gen.state, 15704844188202024364);
  assert_eq!(gen.inc, 505);
}

/// Obtains the global generator. If the generator is not currently initialized
/// then this will initialize it from the system time.
fn get_global_generator_mutex() -> &'static Mutex<PCG32> {
  unsafe {
    match globalGeneratorMutex.load(theOrdering).as_ref() {
      Some(mutex_ref) => mutex_ref,
      None => {
        let mutex_box_raw = Box::into_raw(Box::new(Mutex::new(PCG32::from_time())));
        match globalGeneratorMutex.compare_and_swap(null_mut(), mutex_box_raw, theOrdering).as_ref() {
          Some(mutex_ref) => {
            let _mutex_box_reconstructed = Box::from_raw(mutex_box_raw);
            mutex_ref
          }
          None => mutex_box_raw.as_ref().unwrap(),
        }
      }
    }
  }
}

/// Returns a `u32` from the global generator.
///
/// ```rust
/// use randomize;
/// let a = randomize::next_u32();
/// let b = randomize::next_u32();
/// assert_ne!(a,b);
/// ```
pub fn next_u32() -> u32 {
  let mutex_ref = get_global_generator_mutex();
  let mut guard = match mutex_ref.lock() {
    Ok(guard) => guard,
    Err(poison_error_guard) => poison_error_guard.into_inner(),
  };
  guard.next_u32()
}

/// Gives a random value of the desired type from the global RNG.
pub fn any<A: AnyRandom>() -> A {
  let mutex_ref = get_global_generator_mutex();
  let mut guard = match mutex_ref.lock() {
    Ok(guard) => guard,
    Err(poison_error_guard) => poison_error_guard.into_inner(),
  };
  guard.any()
}

/// Gives an ASCII value from the global RNG.
pub fn any_ascii() -> char {
  let mutex_ref = get_global_generator_mutex();
  let mut guard = match mutex_ref.lock() {
    Ok(guard) => guard,
    Err(poison_error_guard) => poison_error_guard.into_inner(),
  };
  guard.any_ascii()
}

/// An `f32` value from 0.0 to 1.0 (inclusive at both ends) from the global RNG.
pub fn any_f32_zero_to_one() -> f32 {
  let mutex_ref = get_global_generator_mutex();
  let mut guard = match mutex_ref.lock() {
    Ok(guard) => guard,
    Err(poison_error_guard) => poison_error_guard.into_inner(),
  };
  guard.any_f32_zero_to_one()
}

/// Returns `true` a percentage of the time (eg: 0.3 = 30%) from the global RNG.
pub fn percent_chance(chance: f32) -> bool {
  let mutex_ref = get_global_generator_mutex();
  let mut guard = match mutex_ref.lock() {
    Ok(guard) => guard,
    Err(poison_error_guard) => poison_error_guard.into_inner(),
  };
  guard.percent_chance(chance)
}

/// Returns a value out of the `Range` specified using the global RNG.
///
/// You get a `None` back if the range specified is empty.
pub fn in_range<R: Borrow<Range<usize>>>(r: R) -> Option<usize> {
  let mutex_ref = get_global_generator_mutex();
  let mut guard = match mutex_ref.lock() {
    Ok(guard) => guard,
    Err(poison_error_guard) => poison_error_guard.into_inner(),
  };
  guard.in_range(r)
}

/// A trait for types can can be generated in "any" state.
///
/// The precise definition of this is intentionally fuzzy.
pub trait AnyRandom {
  /// Makes a value of the type from the given RNG.
  fn from_pcg32(&mut PCG32) -> Self;
}

impl AnyRandom for u8 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.next_u32() as u8
  }
}

impl AnyRandom for i8 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.next_u32() as i8
  }
}

impl AnyRandom for u16 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.next_u32() as u16
  }
}

impl AnyRandom for i16 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.next_u32() as i16
  }
}

impl AnyRandom for u32 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.next_u32()
  }
}

impl AnyRandom for i32 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.next_u32() as i32
  }
}

impl AnyRandom for u64 {
  /// This uses two calls to the generator.
  fn from_pcg32(gen: &mut PCG32) -> Self {
    let low = gen.next_u32() as u64;
    let high = gen.next_u32() as u64;
    (high << 32) | low
  }
}

impl AnyRandom for i64 {
  /// This uses two calls to the generator.
  fn from_pcg32(gen: &mut PCG32) -> Self {
    let low = gen.next_u32() as u64;
    let high = gen.next_u32() as u64;
    ((high << 32) | low) as i64
  }
}

impl AnyRandom for usize {
  #[cfg(target_pointer_width = "32")]
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.any::<u32>() as usize
  }

  #[cfg(target_pointer_width = "64")]
  /// This uses two calls to the generator.
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.any::<u64>() as usize
  }
}

impl AnyRandom for isize {
  #[cfg(target_pointer_width = "32")]
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.any::<i32>() as isize
  }

  #[cfg(target_pointer_width = "64")]
  /// This uses two calls to the generator.
  fn from_pcg32(gen: &mut PCG32) -> Self {
    gen.any::<i64>() as isize
  }
}

impl AnyRandom for bool {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.next_u32() as i32) < 0
  }
}

impl AnyRandom for char {
  /// This calls the generator one or more times, until the `u32` obtained is a
  /// valid `char` value.
  fn from_pcg32(gen: &mut PCG32) -> Self {
    loop {
      match ::std::char::from_u32(gen.any()) {
        Some(ch) => return ch,
        None => continue,
      }
    }
  }
}

impl AnyRandom for f32 {
  /// This converts a `u32` into an `f32` using `from_bits`, so the distribution
  /// is _absolutely terrible_. Still, you get exactly what the `AnyRandom`
  /// trait says, "potentially any f32 at all".
  fn from_pcg32(gen: &mut PCG32) -> Self {
    f32::from_bits(gen.any())
  }
}

impl AnyRandom for f64 {
  /// This converts a `u64` into an `f64` using `from_bits`, so the distribution
  /// is _absolutely terrible_. Still, you get exactly what the `AnyRandom`
  /// trait says, "potentially any f64 at all".
  fn from_pcg32(gen: &mut PCG32) -> Self {
    f64::from_bits(gen.any())
  }
}

impl AnyRandom for PCG32 {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    Self::from_state_and_inc(gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom> AnyRandom for (A, B) {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom, C: AnyRandom> AnyRandom for (A, B, C) {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom, C: AnyRandom, D: AnyRandom> AnyRandom for (A, B, C, D) {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any(), gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom, C: AnyRandom, D: AnyRandom, E: AnyRandom> AnyRandom for (A, B, C, D, E) {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any(), gen.any(), gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom, C: AnyRandom, D: AnyRandom, E: AnyRandom, F: AnyRandom> AnyRandom for (A, B, C, D, E, F) {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any(), gen.any(), gen.any(), gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom, C: AnyRandom, D: AnyRandom, E: AnyRandom, F: AnyRandom, G: AnyRandom> AnyRandom for (A, B, C, D, E, F, G) {
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any(), gen.any(), gen.any(), gen.any(), gen.any(), gen.any())
  }
}

impl<A: AnyRandom, B: AnyRandom, C: AnyRandom, D: AnyRandom, E: AnyRandom, F: AnyRandom, G: AnyRandom, H: AnyRandom> AnyRandom
  for (A, B, C, D, E, F, G, H)
{
  fn from_pcg32(gen: &mut PCG32) -> Self {
    (gen.any(), gen.any(), gen.any(), gen.any(), gen.any(), gen.any(), gen.any(), gen.any())
  }
}

macro_rules! impl_for_array {
  ($n:expr) => {
    impl<A: AnyRandom + Default> AnyRandom for [A; $n] {
      fn from_pcg32(gen: &mut PCG32) -> Self {
        let mut arr: [A; $n] = Default::default();
        for arr_val_mut_ref in arr.iter_mut() {
          *arr_val_mut_ref = gen.any();
        }
        arr
      }
    }
  };
}

impl_for_array!(0);
impl_for_array!(1);
impl_for_array!(2);
impl_for_array!(3);
impl_for_array!(4);
impl_for_array!(5);
impl_for_array!(6);
impl_for_array!(7);
impl_for_array!(8);
impl_for_array!(9);
impl_for_array!(10);
impl_for_array!(11);
impl_for_array!(12);
impl_for_array!(13);
impl_for_array!(14);
impl_for_array!(15);
impl_for_array!(16);
impl_for_array!(17);
impl_for_array!(18);
impl_for_array!(19);
impl_for_array!(20);
impl_for_array!(21);
impl_for_array!(22);
impl_for_array!(23);
impl_for_array!(24);
impl_for_array!(25);
impl_for_array!(26);
impl_for_array!(27);
impl_for_array!(28);
impl_for_array!(29);
impl_for_array!(30);
impl_for_array!(31);
impl_for_array!(32);