perchance 0.5.3

//! `perchance` is a simple random number generation library, tuned for ease of use: create an instance of [`PerchanceContext`] and go.
//!
//! Note that `perchance` is **not** cryptographically secure and ***should not*** be used in any context where security is a concern.
//!
//! When the `std` feature is enabled (by default), there's a global [`PerchanceContext`] provided, too.
//!
//! # Example
//!
//! First, create a [`PerchanceContext`]:
//!
//! ```rust
//! # let my_seed = 0;
//! let mut rng = perchance::PerchanceContext::new(my_seed);
//! ```
//!
//! Or, if you have the `std` feature enabled, obtain the global [`PerchanceContext`] object:
//!
//! ```rust
//! // Seed the global context first. You may do so manually, or, on platforms that support it,
//! // obtain a seed to pass into it by calling `perchance::gen_time_seed()`.
//! perchance::seed_global(0x5F3759DF); // ;)
//!
//! let mut rng = perchance::global();
//! ```
//!
//! Then, start letting things happen perchance!
//!
//! ```rust
//! # perchance::seed_global(0x5F3759DF);
//! # let mut rng = perchance::global();
//! let between_0_and_1 = rng.uniform_f32();
//! let dice_roll = rng.uniform_range_i32(1..=6);
//! let random_direction = rng.uniform_sphere_surface_vec3();
//! let thing_should_happen = rng.get_bool();
//!
//! enum Event {
//!     Thing1,
//!     Thing2,
//!     Thing3,
//! }
//! let which_should_happen = rng.choose(&[Event::Thing1, Event::Thing2, Event::Thing3]);
//! ```
//!
//! Some of the convenience functions exist in multiple flavors with different
//! return types.
//!
//! Perchance does NOT guarantee the same random number generator across new versions of the crate.
#![allow(clippy::disallowed_types)] // allow usage of std::sync::Mutex (instead of parking_lot) as this is typically intended for Wasm

use core::ops::Bound;
use core::ops::RangeBounds;

/// The raw random number generator.
/// As of may 2020, this is the same generator used by `rand::SmallRng`.
///
/// It is small, fast and simple. Based on the `rand_pcg` crate, but
/// without a dependency to keep the dependency tree smaller.
#[derive(Clone)]
struct Rng(u128);

const MULTIPLIER: u128 = 0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645;

impl Rng {
    #[inline]
    #[allow(unused)]
    pub const fn from_seed(seed: u128) -> Self {
        // state must be odd:
        Self((seed << 1) | 1)
    }

    #[inline]
    fn next_u32(&mut self) -> u32 {
        self.next_u64() as u32
    }

    #[inline]
    fn next_u64(&mut self) -> u64 {
        self.0 = self.0.wrapping_mul(MULTIPLIER);

        // Output function XSL RR ("xorshift low (bits), random rotation"):
        const XSHIFT: u32 = 64; // (128 - 64 + 64) / 2
        const ROTATE: u32 = 122; // 128 - 6
        let rot = (self.0 >> ROTATE) as u32;
        let xsl = ((self.0 >> XSHIFT) as u64) ^ (self.0 as u64);
        xsl.rotate_right(rot)
    }
}

macro_rules! impl_get_bounds {
    (float, $fn_name:ident, $t:ty) => {
        /// Returned start is inclusive, returned end is exclusive
        /// Ignores inclusivity of input bounds.
        /// Unbounded gets set to `$t::MIN` or `$t::MAX` respectively.
        fn $fn_name<R: RangeBounds<$t>>(bounds: R) -> ($t, $t) {
            let start = match bounds.start_bound() {
                Bound::Included(&b) | Bound::Excluded(&b) => b,
                Bound::Unbounded => <$t>::MIN,
            };
            let end = match bounds.end_bound() {
                Bound::Included(&b) | Bound::Excluded(&b) => b,
                Bound::Unbounded => <$t>::MAX,
            };
            (start, end)
        }
    };
    (int, $fn_name:ident, $t:ty) => {
        /// Returned start is inclusive, returned end is exclusive.
        /// Unbounded gets set to `$t::MIN` or `$t::MAX` respectively.
        /// Panics on overflow, if:
        /// - lower bound exclusive and = `$t::MAX`
        /// - upper bound inclusive and = `$t::MAX`
        fn $fn_name<R: RangeBounds<$t>>(bounds: R) -> ($t, $t) {
            let start = match bounds.start_bound() {
                Bound::Included(&b) => b,
                Bound::Excluded(&b) => b.checked_add(1).unwrap(),
                Bound::Unbounded => <$t>::MIN,
            };
            let end = match bounds.end_bound() {
                Bound::Included(&b) => b.checked_add(1).unwrap(),
                Bound::Excluded(&b) => b,
                Bound::Unbounded => <$t>::MAX,
            };
            (start, end)
        }
    };
}

impl_get_bounds!(float, get_f32_bounds, f32);
impl_get_bounds!(int, get_usize_bounds, usize);
impl_get_bounds!(int, get_i32_bounds, i32);

#[derive(Clone)]
pub struct PerchanceContext(Rng);

impl PerchanceContext {
    /// Returns a new `PerchanceContext`, seeded with `seed`.
    ///
    /// Two `PerchanceContext`s seeded with the same number will generate the same
    /// sequence of outputs, given an identical sequence of calls to its member functions.
    ///
    /// Since `perchance` is not yet stabilized we reserve the right to change the
    /// random number generator algorithm, meaning the same seed may produce different
    /// numbers on different version of `perchance`.
    pub const fn new(seed: u128) -> Self {
        Self(Rng::from_seed(seed))
    }

    /// 50/50 chance
    pub fn get_bool(&mut self) -> bool {
        self.0.next_u64() & 1 == 1
    }

    /// All 32 bits of the number are random.
    pub fn get_u32(&mut self) -> u32 {
        self.0.next_u32()
    }

    /// All 64 bits of the number are random.
    pub fn get_u64(&mut self) -> u64 {
        self.0.next_u64()
    }

    /// All 128 bits of the number are random.
    pub fn get_u128(&mut self) -> u128 {
        (u128::from(self.0.next_u64()) << 64) | u128::from(self.0.next_u64())
    }

    /// Returns a number strictly less than the given max.
    /// Returns 0 if max is zero.
    pub fn u64_less_than(&mut self, max: u64) -> u64 {
        if max == 0 {
            return 0;
        }
        // We can only easily generate an integral number of bits of randomness,
        // i.e. numbers within a range [0, 2^n).
        // In particular, we can NOT do `get_u64() % max` due to the pigenhole principle.
        // We then pick the smallest power-of-two zone containing the our max.
        // So for instance, for max=6 we pick three bits of randomness, i.e. a range of [0, 8).
        // We generate numbers in this range until we get on below our max.
        // This is not the most efficient way of doing this, but it is the simplest.
        let significant_bits = 64 - max.leading_zeros();
        let mask = if significant_bits == 64 {
            u64::MAX
        } else {
            (1 << significant_bits) - 1
        };
        loop {
            let num = self.get_u64() & mask;
            if num < max {
                return num;
            }
        }
    }

    /// Returns a `usize` that is less than the given number.
    /// If the given number is zero, None is returned.
    pub fn usize_less_than(&mut self, end: usize) -> usize {
        self.u64_less_than(end as u64) as usize
    }

    /// Chose one of the given values at random.
    /// panics if the given slice is empty
    pub fn choose<'slice, T>(&mut self, slice: &'slice [T]) -> &'slice T {
        &slice[self.usize_less_than(slice.len())]
    }

    /// Chose one of the given values at random.
    /// panics if the given slice is empty
    pub fn choose_mut<'slice, T>(&mut self, slice: &'slice mut [T]) -> &'slice mut T {
        &mut slice[self.usize_less_than(slice.len())]
    }

    /// Chose one of the given values at random.
    /// Returns `None` if the given iterator is empty.
    pub fn choose_it<T>(&mut self, it: impl Iterator<Item = T>) -> Option<T> {
        // reservoir sampling
        let mut chosen = None;
        for (i, value) in it.enumerate() {
            if self.usize_less_than(i + 1) == 0 {
                chosen = Some(value);
            }
        }
        chosen
    }

    /// Shuffle the order of entities within the slice.
    /// The shuffle is performed in place and resembles a reversed Fisher-Yates shuffle.
    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
        for i in 0..slice.len().saturating_sub(1) {
            let j = self.uniform_range_usize(i..slice.len());
            slice.swap(i, j);
        }
    }

    /// Returns a random integer uniformly distributed over `range`.
    /// Panics if the range is invalid (end < start) or if the range bounds would overflow an i32.
    /// Example: `let dice = rng.uniform_range_i32(0..6);`
    pub fn uniform_range_i32<R: RangeBounds<i32>>(&mut self, range: R) -> i32 {
        // Switch to i64 to prevent overflows
        let (start, end) = get_i32_bounds(range);
        let start = i64::from(start);
        let end = i64::from(end);
        let range_size = end - start;
        assert!(range_size >= 0);
        let value = start + self.u64_less_than(range_size as u64) as i64;
        value as i32
    }

    /// Returns a random usize uniformly distributed over `range`.
    /// Panics if the range is invalid (end < start) or if the range bounds would overflow a usize.
    /// Example: `let array_index = rng.uniform_range_usize(0..array.len());`
    pub fn uniform_range_usize<R: RangeBounds<usize>>(&mut self, range: R) -> usize {
        let (start, end) = get_usize_bounds(range);
        assert!(end >= start);
        start + self.usize_less_than(end - start)
    }

    /// Returns a random floating point number in the range [0.0, 1.0).
    pub fn uniform_f32(&mut self) -> f32 {
        // Construct a floating point number between 1.0 and 2.0 directly from the bits for maximally uniform coverage.
        // Subtract 1.0 to get to the 0..1 range.
        f32::from_bits(0x3F80_0000 | (self.get_u32() >> 9)) - 1.0
    }

    /// Returns a random floating point number in the range [0.0, 1.0).
    pub fn uniform_f64(&mut self) -> f64 {
        // Construct a floating point number between 1.0 and 2.0 directly from the bits for maximally uniform coverage.
        // Subtract 1.0 to get to the 0..1 range.
        let exponent = 1023; // 0
        let mantissa = self.get_u64() >> 12;
        f64::from_bits((exponent << 52) | mantissa) - 1.0
    }

    /// Returns a random floating point number uniformly distributed over `range`.
    ///
    /// Note that this ignores the inclusivity of the range (always assumes an inclusive
    /// lower bound and an exclusive upper bound). An unbonded lower and upper bound will be set to
    /// `f32::MIN` and `f32::MAX` respectively.
    pub fn uniform_range_f32<R: RangeBounds<f32>>(&mut self, range: R) -> f32 {
        self.uniform_range_f32_raw(get_f32_bounds(range))
    }

    #[inline]
    fn uniform_range_f32_raw(&mut self, (start, end): (f32, f32)) -> f32 {
        self.uniform_f32() * (end - start) + start
    }

    /// A normally distributed value with standard deviation=1
    pub fn normal_f32(&mut self) -> f32 {
        // Basic Box-Muller transform
        let mut r;
        #[allow(clippy::blocks_in_conditions)]
        while {
            r = (-2.0 * self.uniform_f64().ln()).sqrt();
            !r.is_finite()
        } {}
        let angle = 2.0 * core::f64::consts::PI * self.uniform_f64();
        let s = angle.sin();
        (r * s) as f32
    }

    /// Two independent normally distributed values
    #[cfg(feature = "macaw")]
    pub fn normal_vec2(&mut self) -> macaw::Vec2 {
        // Basic Box-Muller transform
        let mut r;
        #[allow(clippy::blocks_in_conditions)]
        while {
            r = (-2.0 * self.uniform_f64().ln()).sqrt();
            !r.is_finite()
        } {}
        let angle = 2.0 * core::f64::consts::PI * self.uniform_f64();
        let (s, c) = angle.sin_cos();
        macaw::Vec2::new((r * s) as f32, (r * c) as f32)
    }

    /// Three independent normally distributed values
    #[cfg(feature = "macaw")]
    pub fn normal_vec3(&mut self) -> macaw::Vec3 {
        self.normal_vec2().extend(self.normal_f32())
    }

    /// Returns a Vec2 where both components are uniformly distributed over `range`.
    #[cfg(feature = "macaw")]
    pub fn uniform_square_vec2<R: RangeBounds<f32>>(&mut self, range: R) -> macaw::Vec2 {
        let bounds = get_f32_bounds(range);
        macaw::Vec2::new(
            self.uniform_range_f32_raw(bounds),
            self.uniform_range_f32_raw(bounds),
        )
    }

    /// Returns a Vec3 where all three components are uniformly distributed over `range`.
    #[cfg(feature = "macaw")]
    pub fn uniform_cube_vec3<R: RangeBounds<f32>>(&mut self, range: R) -> macaw::Vec3 {
        let bounds = get_f32_bounds(range);
        macaw::Vec3::new(
            self.uniform_range_f32_raw(bounds),
            self.uniform_range_f32_raw(bounds),
            self.uniform_range_f32_raw(bounds),
        )
    }

    /// Returns a uniformly random point that lies inside the bounding box.
    #[cfg(feature = "macaw")]
    pub fn uniform_bounds_vec3(&mut self, bounds: macaw::BoundingBox) -> macaw::Vec3 {
        macaw::Vec3::new(
            self.uniform_range_f32_raw((bounds.min.x, bounds.max.x)),
            self.uniform_range_f32_raw((bounds.min.y, bounds.max.y)),
            self.uniform_range_f32_raw((bounds.min.z, bounds.max.z)),
        )
    }

    /// Returns a uniformly random point that lies inside the rectangle.
    #[cfg(feature = "macaw")]
    pub fn uniform_rectangle_vec2(&mut self, min: macaw::Vec2, max: macaw::Vec2) -> macaw::Vec2 {
        macaw::Vec2::new(
            self.uniform_range_f32_raw((min.x, max.x)),
            self.uniform_range_f32_raw((min.y, max.y)),
        )
    }

    /// Returns a random Vec2 on the edge of a circle with radius 1.0.
    #[cfg(feature = "macaw")]
    pub fn uniform_circle_edge_vec2(&mut self) -> macaw::Vec2 {
        let angle = self.uniform_f32() * core::f32::consts::TAU;
        let x = angle.cos();
        let y = angle.sin();
        macaw::Vec2::new(x, y)
    }

    /// Returns a random Vec2 within the area of a circle with radius 1.0.
    #[cfg(feature = "macaw")]
    pub fn uniform_circle_area_vec2(&mut self) -> macaw::Vec2 {
        let radius = self.uniform_f32();
        let edge_point = self.uniform_circle_edge_vec2();
        edge_point * radius
    }

    /// Returns a random Vec2 within a circular disc.
    #[cfg(feature = "macaw")]
    #[deprecated = "Deprecated in favor of the equivalent `uniform_circle_area_vec2()`"]
    pub fn uniform_disc_vec2(&mut self) -> macaw::Vec2 {
        self.uniform_circle_area_vec2()
    }

    /// Returns a random Vec3 on the surface of a sphere with radius 1.0.
    #[cfg(feature = "macaw")]
    pub fn uniform_sphere_surface_vec3(&mut self) -> macaw::Vec3 {
        let x = self.uniform_f32();
        let y = self.uniform_f32();
        let z = 1.0f32 - 2.0f32 * x;
        let xy = ((0.0f32).max(1.0f32 - z * z)).sqrt();
        let sn = (core::f32::consts::TAU * y).sin();
        let cs = (core::f32::consts::TAU * y).cos();
        macaw::Vec3::new(sn * xy, cs * xy, z)
    }

    /// Returns a random Vec3 within the volume of a sphere.
    #[cfg(feature = "macaw")]
    pub fn uniform_sphere_volume_vec3(&mut self) -> macaw::Vec3 {
        let radius = self.uniform_f32();
        let surface_point = self.uniform_sphere_surface_vec3();
        surface_point * radius
    }

    /// Return a an integer index, weighted by the given weights.
    /// For instance, `rng.weighted_choice_f32(&[1.0, 3.0, 2.0])` will return
    /// `0` with a  `1/6` probability,
    /// `1` with a  `3/6` probability,
    /// `2` with a  `2/6` probability.
    ///
    /// If the weights sum to zero, a fair choice is returned.
    ///
    /// The function panics if the given weight list is empty, or contain non-finite or negative numbers.
    pub fn weighted_choice_f32(&mut self, weights: &[f32]) -> usize {
        assert!(!weights.is_empty());
        let sum: f64 = weights.iter().map(|&w| f64::from(w)).sum();
        assert!(sum.is_finite());
        if sum == 0.0 {
            self.usize_less_than(weights.len())
        } else {
            let pos = self.uniform_f64() * sum;

            let mut cumulative_sum = 0.0;
            for (i, w) in weights.iter().take(weights.len() - 1).enumerate() {
                cumulative_sum += f64::from(*w);
                if pos < cumulative_sum {
                    return i;
                }
            }
            weights.len() - 1
        }
    }

    /// Like [`Self::weighted_choice_f32`], but returns a sampler that allows you to much more efficiently sample multiple choices with the same weights.
    ///
    /// Complexity for `N` samples with `C` weights is `C + N*log(C)` instead of `C + N*C` when using `weighted_choice_f32`.
    ///
    /// Panics if given a NaN weight.
    pub fn weighted_choices_f32(&mut self, weights: &[f32]) -> WeightedSampler<'_> {
        use ordered_float::NotNan;
        assert!(!weights.is_empty());
        let zero = NotNan::<f64>::default();
        let mut sum = zero;
        let mut cum = Vec::with_capacity(weights.len());
        cum.resize(weights.len(), zero);
        for (c, v) in cum.iter_mut().zip(weights) {
            sum += NotNan::new(f64::from(*v)).expect("weighted_choices_f32 was given a NaN weight");
            *c = sum;
        }

        WeightedSampler {
            context: self,
            cumulative_weights: cum,
        }
    }
}

pub struct WeightedSampler<'a> {
    context: &'a mut PerchanceContext,
    cumulative_weights: Vec<ordered_float::NotNan<f64>>,
}

impl<'a> WeightedSampler<'a> {
    /// Returns an index sampled according to the given weights.
    ///
    /// See [`PerchanceContext::weighted_choice_f32`] for more details.
    pub fn sample(&mut self) -> usize {
        // Note: guaranteed to contain at least one element
        let weight_sum = *self.cumulative_weights.last().unwrap();
        let value = ordered_float::NotNan::new(self.context.uniform_f64()).unwrap() * weight_sum;
        match self.cumulative_weights.binary_search(&value) {
            Ok(index) | Err(index) => index,
        }
    }
}

mod global_ctx {
    use super::*;
    use once_cell::sync::Lazy;
    use std::sync::Mutex;
    #[cfg(not(target_family = "wasm"))]
    use std::time::SystemTime;
    #[cfg(not(target_family = "wasm"))]
    use std::time::UNIX_EPOCH;

    #[cfg(not(target_family = "wasm"))]
    const TWO_POW_64: u128 = 2u128.pow(64);
    #[cfg(not(target_family = "wasm"))]
    const TWO_POW_96: u128 = 2u128.pow(96);

    static GLOBAL_RNG: Lazy<Mutex<PerchanceContext>> =
        Lazy::new(|| Mutex::new(PerchanceContext::new(0)));
    static HAS_BEEN_SEEDED: std::sync::atomic::AtomicBool =
        std::sync::atomic::AtomicBool::new(false);

    /// Returns the global [`PerchanceContext`]. You **must** seed it by calling
    /// [`perchance::seed_global`](self::seed_global) at least once before calling this function or else
    /// it will panic.
    ///
    /// Call methods on it like [`PerchanceContext::get_u32`] to get random numbers from anywhere in your module.
    pub fn global<'a>() -> std::sync::MutexGuard<'a, PerchanceContext> {
        assert!(
            global_has_been_seeded(),
            "You must call `perchance::seed_global` before using the global perchance instance."
        );
        GLOBAL_RNG.lock().unwrap()
    }

    /// Seed (or reseed) the global [`PerchanceContext`] returned by [`perchance::global`](self::global).
    ///
    /// After calling this at least once, [`perchance::global_has_been_seeded`](self::global_has_been_seeded) will return true.
    pub fn seed_global(seed: u128) {
        HAS_BEEN_SEEDED.store(true, std::sync::atomic::Ordering::SeqCst);
        *global() = PerchanceContext::new(seed);
    }

    /// Generates a seed that may be passed to [`perchance::seed_global`](self::seed_global) based on the
    /// system clock.
    #[cfg(not(target_family = "wasm"))]
    pub fn gen_time_seed() -> u128 {
        SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .map(|duration| {
                u128::from(duration.as_secs()) // u64 as bits 0..64 of u128
                    | (u128::from(duration.subsec_millis()) * TWO_POW_64) // put u32 into bits 64..96 of u128
                    | (u128::from(duration.subsec_micros()) * TWO_POW_96) // put u32 into bits 96..128 of u128
            })
            .unwrap()
    }

    /// Returns `true` if [`perchance::seed_global`](self::seed_global) has been called at least once.
    pub fn global_has_been_seeded() -> bool {
        HAS_BEEN_SEEDED.load(std::sync::atomic::Ordering::SeqCst)
    }
}

pub use global_ctx::*;