Skip to main content

tpt_math_prob_sampler/
lib.rs

1#![no_std]
2//! Sampling strategies for the `tpt-math-prob-*` family.
3//!
4//! This crate consolidates reusable sampling *strategies* on top of the shared
5//! [`tpt_math_prob_core`] traits ([`Distribution`], [`Rng`], [`Sampler`]). It is
6//! `no_std`-compatible; the bulk of the API is allocation-free and works with
7//! any slice-backed storage, while the convenience constructors that own a
8//! [`alloc::vec::Vec`] are gated behind the `std` (default) or `alloc`
9//! features.
10//!
11//! The crate provides:
12//!
13//! * [`InverseCdfSampler`] — inverse-transform (alias) sampling over a weighted
14//!   categorical distribution, generic over any CDF storage.
15//! * [`SystematicResampler`] (with multinomial, systematic and stratified
16//!   resampling schemes) — resample `n` particles from weighted possibilities,
17//!   writing into a caller-provided index buffer.
18//! * [`ReservoirSampler`] — streaming `n`-from-`k` (with `k` unknown) uniform
19//!   reservoir sampling.
20//! * [`RejectionSampler`] — standard rejection sampling that wraps a target
21//!   density and a proposal [`Distribution`] + [`Density`] with a bounding
22//!   constant `m`.
23//! * Free helpers: [`categorical`], [`sample_categorical`], [`uniform_index`],
24//!   [`shuffle`], and the small [`Uniform`] / [`Bernoulli`] building blocks.
25//!
26//! # Examples
27//!
28//! ```
29//! use tpt_math_prob_sampler::{categorical, SystematicResampler, ResampleScheme};
30//! use tpt_math_prob_core::{Distribution, Rng, Standard, SplitMix64};
31//!
32//! let mut rng = SplitMix64::seed_from_u64(0);
33//! let cat = categorical(&[1.0, 2.0, 3.0]).unwrap();
34//! let x = cat.sample(&mut rng);
35//! assert!(x < 3);
36//!
37//! let resampler = SystematicResampler::new(cat.cdf().to_vec()).unwrap();
38//! let mut out = [0usize; 5];
39//! resampler.sample_indices(&mut rng, ResampleScheme::Systematic, &mut out);
40//! assert_eq!(out.len(), 5);
41//! ```
42
43extern crate alloc;
44
45#[cfg(feature = "std")]
46extern crate std;
47
48// Re-export the core traits/types so consumers only depend on this crate.
49pub use tpt_math_prob_core::{Distribution, Rng, Sampler, SplitMix64, Standard};
50
51use core::fmt;
52
53#[cfg(any(feature = "std", feature = "alloc"))]
54use alloc::vec::Vec;
55
56/// Absolute value without relying on `f64::abs` (kept `no_std`-portable).
57#[inline]
58fn fabs(x: f64) -> f64 {
59    if x < 0.0 {
60        -x
61    } else {
62        x
63    }
64}
65
66/// Draw a single `f64` from [`Standard`] (avoids ambiguous-trait inference).
67#[inline]
68fn uniform_f64<R: Rng + ?Sized>(rng: &mut R) -> f64 {
69    Distribution::<f64>::sample(&Standard, rng)
70}
71
72/// Errors produced while constructing or validating a sampler.
73#[derive(Clone, Copy, Debug, PartialEq, Eq)]
74#[non_exhaustive]
75pub enum SamplerError {
76    /// No weights / empty distribution.
77    Empty,
78    /// A weight was negative.
79    NegativeWeight,
80    /// A weight was not finite (`NaN` or `inf`).
81    NonFiniteWeight,
82    /// The total weight was zero.
83    ZeroTotal,
84    /// A `from_cdf` CDF was not monotone non-decreasing or did not end in `1`.
85    InvalidCdf,
86    /// A probability parameter was outside `[0, 1]`.
87    InvalidProbability,
88    /// A rejection-sampling envelope constant `m` was not strictly positive.
89    InvalidBound,
90    /// A uniform interval was empty or invalid (`lo >= hi`).
91    InvalidInterval,
92    /// Requested `n` exceeds the number of distinct items.
93    TooManySamples,
94}
95
96impl fmt::Display for SamplerError {
97    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
98        let s = match self {
99            SamplerError::Empty => "empty distribution (no weights)",
100            SamplerError::NegativeWeight => "negative weight encountered",
101            SamplerError::NonFiniteWeight => "non-finite (NaN/inf) weight encountered",
102            SamplerError::ZeroTotal => "total weight is zero",
103            SamplerError::InvalidCdf => "CDF is not monotone non-decreasing ending in 1",
104            SamplerError::InvalidProbability => "probability not in [0, 1]",
105            SamplerError::InvalidBound => "envelope constant m must be strictly positive",
106            SamplerError::InvalidInterval => "uniform interval lo >= hi",
107            SamplerError::TooManySamples => "requested sample count exceeds the population",
108        };
109        f.write_str(s)
110    }
111}
112
113#[cfg(feature = "std")]
114impl std::error::Error for SamplerError {}
115
116/// Validate a slice of unnormalised weights and return their (positive) sum.
117fn validate_weights(weights: &[f64]) -> Result<f64, SamplerError> {
118    if weights.is_empty() {
119        return Err(SamplerError::Empty);
120    }
121    let mut total = 0.0;
122    for &w in weights {
123        if !w.is_finite() {
124            return Err(SamplerError::NonFiniteWeight);
125        }
126        if w < 0.0 {
127            return Err(SamplerError::NegativeWeight);
128        }
129        total += w;
130    }
131    if total <= 0.0 || !total.is_finite() {
132        return Err(SamplerError::ZeroTotal);
133    }
134    Ok(total)
135}
136
137/// Locate the first index `i` with `cdf[i] > u` (inverse-transform lookup).
138///
139/// `cdf` is assumed normalised so that `cdf.last() == 1` and is non-decreasing.
140/// `u` must be in `[0, 1)`.
141#[inline]
142fn inverse_cdf_index(cdf: &[f64], u: f64) -> usize {
143    let mut idx = cdf.partition_point(|&c| c <= u);
144    if idx >= cdf.len() {
145        // Defensive: u could be exactly 1.0 due to rounding; clamp into the
146        // last bin that actually has positive probability.
147        idx = cdf.len() - 1;
148        while idx > 0 && cdf[idx] == cdf[idx - 1] {
149            idx -= 1;
150        }
151    }
152    idx
153}
154
155// =====================================================================
156// Inverse-transform (alias) sampler
157// =====================================================================
158
159/// Inverse-transform sampler for a categorical (discrete) distribution.
160///
161/// Given a cumulative distribution function `cdf` (non-decreasing, ending in
162/// `1.0`) stored in any type implementing [`AsRef<[f64]>`][core::convert::AsRef],
163/// it draws an `usize` index by the alias / inverse-CDF method. The storage is
164/// generic so the same type works with a borrowed `&[f64]`, an array, or an
165/// owned [`alloc::vec::Vec`].
166///
167/// # Examples
168///
169/// ```
170/// use tpt_math_prob_sampler::{InverseCdfSampler, categorical};
171/// use tpt_math_prob_core::{Distribution, Rng, SplitMix64};
172///
173/// let cdf = categorical(&[1.0, 1.0, 2.0]).unwrap();
174/// let s = InverseCdfSampler::from_cdf(cdf.cdf().to_vec()).unwrap();
175/// let mut rng = SplitMix64::seed_from_u64(3);
176/// let i = s.sample(&mut rng);
177/// assert!(i < 3);
178/// ```
179pub struct InverseCdfSampler<S> {
180    cdf: S,
181}
182
183impl<S: AsRef<[f64]>> Clone for InverseCdfSampler<S>
184where
185    S: Clone,
186{
187    fn clone(&self) -> Self {
188        InverseCdfSampler {
189            cdf: self.cdf.clone(),
190        }
191    }
192}
193impl<S: AsRef<[f64]>> Copy for InverseCdfSampler<S> where S: Copy {}
194impl<S: AsRef<[f64]>> fmt::Debug for InverseCdfSampler<S>
195where
196    S: fmt::Debug,
197{
198    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
199        f.debug_struct("InverseCdfSampler")
200            .field("cdf", &self.cdf)
201            .finish()
202    }
203}
204impl<S: AsRef<[f64]>> PartialEq for InverseCdfSampler<S>
205where
206    S: PartialEq,
207{
208    fn eq(&self, other: &Self) -> bool {
209        self.cdf == other.cdf
210    }
211}
212
213/// Convenience alias for the owned, [`alloc`] backed inverse-CDF sampler.
214#[cfg(any(feature = "std", feature = "alloc"))]
215pub type WeightedIndex = InverseCdfSampler<Vec<f64>>;
216
217impl<S: AsRef<[f64]>> InverseCdfSampler<S> {
218    /// Build a sampler from an existing, already-normalised cumulative
219    /// distribution function.
220    ///
221    /// The CDF must be non-decreasing, all entries in `[0, 1]`, and end in
222    /// exactly `1.0` (within `1e-12`). Returns [`SamplerError::InvalidCdf`]
223    /// otherwise.
224    pub fn from_cdf(cdf: S) -> Result<Self, SamplerError> {
225        let slice = cdf.as_ref();
226        if slice.is_empty() {
227            return Err(SamplerError::Empty);
228        }
229        let mut prev = 0.0;
230        for &c in slice {
231            if !c.is_finite() || !(0.0..=1.0).contains(&c) {
232                return Err(SamplerError::InvalidCdf);
233            }
234            if c < prev {
235                return Err(SamplerError::InvalidCdf);
236            }
237            prev = c;
238        }
239        if fabs(prev - 1.0) > 1e-12 {
240            return Err(SamplerError::InvalidCdf);
241        }
242        Ok(InverseCdfSampler { cdf })
243    }
244
245    /// The number of categories.
246    pub fn len(&self) -> usize {
247        self.cdf.as_ref().len()
248    }
249
250    /// True when there are no categories (constructed from an empty CDF).
251    pub fn is_empty(&self) -> bool {
252        self.cdf.as_ref().is_empty()
253    }
254
255    /// Borrow the underlying cumulative distribution function.
256    pub fn cdf(&self) -> &[f64] {
257        self.cdf.as_ref()
258    }
259
260    /// Probability of category `i` (difference of adjacent CDF entries).
261    ///
262    /// Returns `0.0` for out-of-range `i`.
263    pub fn probability(&self, i: usize) -> f64 {
264        let cdf = self.cdf.as_ref();
265        if i >= cdf.len() {
266            return 0.0;
267        }
268        if i == 0 {
269            cdf[0]
270        } else {
271            cdf[i] - cdf[i - 1]
272        }
273    }
274
275    /// Draw an index given a uniform variate `u in [0, 1)`.
276    ///
277    /// Useful for deterministic / systematic resampling.
278    pub fn sample_index_from_uniform(&self, u: f64) -> usize {
279        inverse_cdf_index(self.cdf.as_ref(), u)
280    }
281}
282
283#[cfg(any(feature = "std", feature = "alloc"))]
284impl InverseCdfSampler<Vec<f64>> {
285    /// Build a sampler from a slice of non-negative unnormalised `weights`.
286    ///
287    /// The weights are normalised and turned into a cumulative distribution
288    /// function. Returns an error if the slice is empty, any weight is
289    /// negative / non-finite, or the total weight is zero.
290    pub fn from_weights(weights: &[f64]) -> Result<Self, SamplerError> {
291        let total = validate_weights(weights)?;
292        let mut cdf = Vec::with_capacity(weights.len());
293        let mut acc = 0.0;
294        for &w in weights {
295            acc += w / total;
296            cdf.push(acc);
297        }
298        // Guard against floating-point drift: force the final entry to 1.
299        if let Some(last) = cdf.last_mut() {
300            *last = 1.0;
301        }
302        Ok(InverseCdfSampler { cdf })
303    }
304}
305
306impl<S: AsRef<[f64]>> Distribution<usize> for InverseCdfSampler<S> {
307    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize {
308        let u: f64 = Standard.sample(rng);
309        self.sample_index_from_uniform(u)
310    }
311}
312
313/// Build a [`WeightedIndex`] (owned, [`alloc`]-backed inverse-CDF sampler) from
314/// unnormalised `weights`.
315///
316/// # Examples
317///
318/// ```
319/// use tpt_math_prob_sampler::categorical;
320/// let cat = categorical(&[0.2, 0.8]).unwrap();
321/// assert_eq!(cat.len(), 2);
322/// ```
323#[cfg(any(feature = "std", feature = "alloc"))]
324pub fn categorical(weights: &[f64]) -> Result<WeightedIndex, SamplerError> {
325    WeightedIndex::from_weights(weights)
326}
327
328/// Draw a categorical index from `weights` using allocation-free linear scan
329/// (inverse-transform without a normalised CDF table).
330///
331/// `weights` are non-negative unnormalised probabilities. Returns `None` if the
332/// weights are invalid (empty, negative, non-finite or summing to zero).
333///
334/// # Examples
335///
336/// ```
337/// use tpt_math_prob_sampler::sample_categorical;
338/// use tpt_math_prob_core::{Rng, SplitMix64};
339/// let mut rng = SplitMix64::seed_from_u64(1);
340/// let i = sample_categorical(&[1.0, 1.0, 1.0], &mut rng).unwrap();
341/// assert!(i < 3);
342/// ```
343pub fn sample_categorical<R: Rng + ?Sized>(weights: &[f64], rng: &mut R) -> Option<usize> {
344    let total = validate_weights(weights).ok()?;
345    let mut u = uniform_f64(rng) * total;
346    for (i, &w) in weights.iter().enumerate() {
347        if u < w {
348            return Some(i);
349        }
350        u -= w;
351    }
352    // Rounding can land exactly on the total; return the last index.
353    Some(weights.len() - 1)
354}
355
356// =====================================================================
357// Systematic / multinomial / stratified resampling
358// =====================================================================
359
360/// The resampling scheme used by [`SystematicResampler::sample_indices`].
361#[derive(Clone, Copy, Debug, PartialEq, Eq)]
362pub enum ResampleScheme {
363    /// Independent inverse-CDF draws (a plain multinomial resample).
364    Multinomial,
365    /// One random offset; evenly spaced "ladders" through the CDF
366    /// (low variance, deterministic given the seed).
367    Systematic,
368    /// One random offset per slot, jittered inside its own stratum.
369    Stratified,
370}
371
372/// Resamples `n` particle *indices* from a weighted categorical distribution.
373///
374/// Unlike [`InverseCdfSampler`] this writes `n` indices into a caller-provided
375/// buffer ([`sample_indices`](SystematicResampler::sample_indices)) and supports
376/// the low-variance [systematic](ResampleScheme::Systematic) and
377/// [stratified](ResampleScheme::Stratified) schemes in addition to a plain
378/// [multinomial](ResampleScheme::Multinomial) resample.
379///
380/// # Examples
381///
382/// ```
383/// use tpt_math_prob_sampler::{categorical, SystematicResampler, ResampleScheme};
384/// use tpt_math_prob_core::{Rng, SplitMix64};
385/// let cat = categorical(&[1.0, 2.0, 3.0]).unwrap();
386/// let resampler = SystematicResampler::new(cat.cdf().to_vec()).unwrap();
387/// let mut rng = SplitMix64::seed_from_u64(0);
388/// let mut out = [0usize; 4];
389/// resampler.sample_indices(&mut rng, ResampleScheme::Systematic, &mut out);
390/// assert!(out.iter().all(|&i| i < 3));
391/// ```
392pub struct SystematicResampler<S> {
393    sampler: InverseCdfSampler<S>,
394}
395
396impl<S: AsRef<[f64]>> Clone for SystematicResampler<S>
397where
398    S: Clone,
399{
400    fn clone(&self) -> Self {
401        SystematicResampler {
402            sampler: self.sampler.clone(),
403        }
404    }
405}
406impl<S: AsRef<[f64]>> Copy for SystematicResampler<S> where S: Copy {}
407impl<S: AsRef<[f64]>> fmt::Debug for SystematicResampler<S>
408where
409    S: fmt::Debug,
410{
411    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
412        f.debug_struct("SystematicResampler")
413            .field("sampler", &self.sampler)
414            .finish()
415    }
416}
417impl<S: AsRef<[f64]>> PartialEq for SystematicResampler<S>
418where
419    S: PartialEq,
420{
421    fn eq(&self, other: &Self) -> bool {
422        self.sampler == other.sampler
423    }
424}
425
426#[cfg(any(feature = "std", feature = "alloc"))]
427impl SystematicResampler<Vec<f64>> {
428    /// Build from unnormalised `weights`.
429    pub fn from_weights(weights: &[f64]) -> Result<Self, SamplerError> {
430        Ok(SystematicResampler {
431            sampler: InverseCdfSampler::from_weights(weights)?,
432        })
433    }
434}
435
436impl<S: AsRef<[f64]>> SystematicResampler<S> {
437    /// Build from an existing normalised CDF (`InverseCdfSampler::from_cdf`).
438    pub fn new(cdf: S) -> Result<Self, SamplerError> {
439        Ok(SystematicResampler {
440            sampler: InverseCdfSampler::from_cdf(cdf)?,
441        })
442    }
443
444    /// Number of source categories.
445    pub fn len(&self) -> usize {
446        self.sampler.len()
447    }
448
449    /// True when there are no categories.
450    pub fn is_empty(&self) -> bool {
451        self.sampler.is_empty()
452    }
453
454    /// Borrow the underlying cumulative distribution function.
455    pub fn cdf(&self) -> &[f64] {
456        self.sampler.cdf()
457    }
458
459    /// Resample `n` indices into `out` using the chosen [`ResampleScheme`].
460    ///
461    /// `out.len()` determines `n`; the resampled indices are in `0..len()`.
462    pub fn sample_indices<R: Rng + ?Sized>(
463        &self,
464        rng: &mut R,
465        scheme: ResampleScheme,
466        out: &mut [usize],
467    ) {
468        let cdf = self.sampler.cdf();
469        let n = out.len();
470        if n == 0 {
471            return;
472        }
473        match scheme {
474            ResampleScheme::Multinomial => {
475                for slot in out.iter_mut() {
476                    let u = uniform_f64(rng);
477                    *slot = inverse_cdf_index(cdf, u);
478                }
479            }
480            ResampleScheme::Systematic => {
481                let u0: f64 = uniform_f64(rng) / (n as f64);
482                let mut cursor = 0usize;
483                for (j, slot) in out.iter_mut().enumerate() {
484                    let u = u0 + (j as f64) / (n as f64);
485                    while cursor + 1 < cdf.len() && cdf[cursor] <= u {
486                        cursor += 1;
487                    }
488                    *slot = cursor;
489                }
490            }
491            ResampleScheme::Stratified => {
492                for (j, slot) in out.iter_mut().enumerate() {
493                    let u: f64 = (uniform_f64(rng) + j as f64) / (n as f64);
494                    *slot = inverse_cdf_index(cdf, u);
495                }
496            }
497        }
498    }
499}
500
501// =====================================================================
502// Reservoir sampling (streaming n-of-k, k unknown)
503// =====================================================================
504
505/// Streaming reservoir sampler: keep a uniformly random sample of size `cap`
506/// from a stream of `k` items of unknown length.
507///
508/// Fill it with [`offer`](ReservoirSampler::offer) for every incoming item.
509/// Once `cap` items have been seen, each subsequent item replaces a uniformly
510/// chosen reservoir slot with probability `cap / seen`, so every item seen so
511/// far is equally likely to be in the reservoir.
512///
513/// The sampler borrows a caller-owned buffer `buf` of length `cap`; it never
514/// allocates.
515///
516/// # Examples
517///
518/// ```
519/// use tpt_math_prob_sampler::ReservoirSampler;
520/// use tpt_math_prob_core::{Rng, SplitMix64};
521/// let mut rng = SplitMix64::seed_from_u64(0);
522/// let mut slots = [0u32; 3];
523/// let mut rs = ReservoirSampler::new(&mut slots);
524/// for x in 0u32..100 { rs.offer(x, &mut rng); }
525/// // every value 0..100 was equally likely to survive
526/// assert!(slots.iter().all(|&v| v < 100));
527/// ```
528pub struct ReservoirSampler<'a, T> {
529    buf: &'a mut [T],
530    seen: u64,
531}
532
533impl<'a, T> ReservoirSampler<'a, T> {
534    /// Create a reservoir backed by `buf` (length = capacity `cap`).
535    pub fn new(buf: &'a mut [T]) -> Self {
536        ReservoirSampler { buf, seen: 0 }
537    }
538
539    /// Capacity `cap` of the reservoir.
540    pub fn capacity(&self) -> usize {
541        self.buf.len()
542    }
543
544    /// How many items have been offered so far.
545    pub fn seen(&self) -> u64 {
546        self.seen
547    }
548
549    /// Current contents (the first `min(seen, cap)` slots are live).
550    pub fn sample(&self) -> &[T] {
551        let live = self.seen as usize;
552        let n = if live < self.buf.len() {
553            live
554        } else {
555            self.buf.len()
556        };
557        &self.buf[..n]
558    }
559
560    /// Number of live (filled) slots.
561    pub fn len(&self) -> usize {
562        self.sample().len()
563    }
564
565    /// True when no items have been offered yet.
566    pub fn is_empty(&self) -> bool {
567        self.seen == 0
568    }
569
570    /// True when the reservoir is full (at capacity).
571    pub fn is_full(&self) -> bool {
572        self.seen as usize >= self.buf.len()
573    }
574
575    /// Reset the stream (drop all offered items) without clearing values.
576    pub fn reset(&mut self) {
577        self.seen = 0;
578    }
579
580    /// Offer one `item` from the stream.
581    ///
582    /// While the reservoir is filling, `item` is appended. Once full, `item`
583    /// replaces a uniformly chosen slot with probability `cap / seen`; the
584    /// displaced item is returned (or `None` if `item` was itself rejected).
585    pub fn offer<R: Rng + ?Sized>(&mut self, item: T, rng: &mut R) -> Option<T> {
586        let cap = self.buf.len();
587        let idx = self.seen as usize;
588        self.seen = self.seen.wrapping_add(1);
589        if idx < cap {
590            // Filling phase: append, displacing the placeholder.
591            let _ = core::mem::replace(&mut self.buf[idx], item);
592            return None;
593        }
594        // Full phase: accept with probability cap / seen. Pick a slot in
595        // `0..seen`; if it falls in the reservoir (cap slots) we replace it.
596        let j = uniform_index(rng, self.seen as usize).expect("seen > 0");
597        if j < cap {
598            Some(core::mem::replace(&mut self.buf[j], item))
599        } else {
600            Some(item)
601        }
602    }
603}
604
605/// Draw a uniform `usize` in `0..n` (unbiased, rejection-based).
606///
607/// Returns `None` if `n == 0`. Operates only on the `Rng` interface (no
608/// allocation), and is the building block for [`shuffle`] and
609/// [`ReservoirSampler`].
610///
611/// # Examples
612///
613/// ```
614/// use tpt_math_prob_sampler::uniform_index;
615/// use tpt_math_prob_core::{Rng, SplitMix64};
616/// let mut rng = SplitMix64::seed_from_u64(0);
617/// let i = uniform_index(&mut rng, 6).unwrap();
618/// assert!(i < 6);
619/// ```
620pub fn uniform_index<R: Rng + ?Sized>(rng: &mut R, n: usize) -> Option<usize> {
621    if n == 0 {
622        return None;
623    }
624    if n == 1 {
625        return Some(0);
626    }
627    let span = n as u64;
628    let limit = if span.is_power_of_two() {
629        u64::MAX
630    } else {
631        // Largest multiple of `n` <= u64::MAX; values >= limit are rejected.
632        (u64::MAX / span) * span
633    };
634    loop {
635        let x = rng.next_u64();
636        if x < limit {
637            return Some((x % span) as usize);
638        }
639    }
640}
641
642/// In-place Fisher–Yates shuffle of `slice`.
643///
644/// # Examples
645///
646/// ```
647/// use tpt_math_prob_sampler::shuffle;
648/// use tpt_math_prob_core::{Rng, SplitMix64};
649/// let mut v = [1, 2, 3, 4, 5];
650/// let mut rng = SplitMix64::seed_from_u64(0);
651/// shuffle(&mut v, &mut rng);
652/// v.sort_unstable();
653/// assert_eq!(v, [1, 2, 3, 4, 5]);
654/// ```
655pub fn shuffle<R: Rng + ?Sized, T>(slice: &mut [T], rng: &mut R) {
656    let n = slice.len();
657    for i in (1..n).rev() {
658        let j = uniform_index(rng, i + 1).expect("i + 1 > 0");
659        slice.swap(i, j);
660    }
661}
662
663// =====================================================================
664// Densities and rejection sampling
665// =====================================================================
666
667/// A probability density (evaluated on the real line) for rejection sampling.
668///
669/// A [`Distribution<f64>`] only knows how to *draw*; a `Density` additionally
670/// knows the value of its probability density function, which is required for
671/// the acceptance test of [`RejectionSampler`].
672pub trait Density {
673    /// Density at `x`. Must be `>= 0` everywhere and finite at `x`.
674    fn density(&self, x: f64) -> f64;
675}
676
677/// Adapter turning a closure `Fn(f64) -> f64` into a [`Density`].
678///
679/// # Examples
680///
681/// ```
682/// use tpt_math_prob_sampler::{DensityFn, Density};
683/// let d = DensityFn(|x: f64| if x >= 0.0 && x <= 1.0 { 1.0 } else { 0.0 });
684/// assert_eq!(d.density(0.5), 1.0);
685/// ```
686pub struct DensityFn<F>(pub F);
687
688impl<F: Fn(f64) -> f64> Density for DensityFn<F> {
689    fn density(&self, x: f64) -> f64 {
690        (self.0)(x)
691    }
692}
693
694/// Continuous uniform distribution over `[lo, hi)`.
695///
696/// Implements [`Distribution<f64>`] (drawing) and [`Density`] (evaluation), so
697/// it can serve as a proposal for [`RejectionSampler`].
698pub struct Uniform {
699    lo: f64,
700    hi: f64,
701    width: f64,
702}
703
704impl Uniform {
705    /// Construct a uniform distribution on `[lo, hi)`.
706    ///
707    /// Returns [`SamplerError::InvalidInterval`] when `lo >= hi` or either bound
708    /// is non-finite.
709    pub fn new(lo: f64, hi: f64) -> Result<Self, SamplerError> {
710        if !lo.is_finite() || !hi.is_finite() || lo >= hi {
711            return Err(SamplerError::InvalidInterval);
712        }
713        Ok(Uniform {
714            lo,
715            hi,
716            width: hi - lo,
717        })
718    }
719
720    /// Lower bound.
721    pub fn lo(&self) -> f64 {
722        self.lo
723    }
724
725    /// Upper bound.
726    pub fn hi(&self) -> f64 {
727        self.hi
728    }
729}
730
731impl Distribution<f64> for Uniform {
732    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 {
733        let u: f64 = Standard.sample(rng);
734        self.lo + u * self.width
735    }
736}
737
738impl Density for Uniform {
739    fn density(&self, x: f64) -> f64 {
740        if x >= self.lo && x < self.hi {
741            1.0 / self.width
742        } else {
743            0.0
744        }
745    }
746}
747
748/// Bernoulli (`p` success) distribution returning `bool`.
749pub struct Bernoulli {
750    p: f64,
751}
752
753impl Bernoulli {
754    /// Construct a Bernoulli distribution with success probability `p`.
755    ///
756    /// Returns [`SamplerError::InvalidProbability`] if `p` is outside `[0, 1]`.
757    pub fn new(p: f64) -> Result<Self, SamplerError> {
758        if !p.is_finite() || !(0.0..=1.0).contains(&p) {
759            return Err(SamplerError::InvalidProbability);
760        }
761        Ok(Bernoulli { p })
762    }
763
764    /// The success probability `p`.
765    pub fn p(&self) -> f64 {
766        self.p
767    }
768}
769
770impl Distribution<bool> for Bernoulli {
771    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool {
772        let u: f64 = Standard.sample(rng);
773        u < self.p
774    }
775}
776
777/// Standard rejection sampler.
778///
779/// Draws from a target [`Density`] `target` by proposing from `proposal`
780/// (any [`Distribution<f64>`] + [`Density`]) and accepting with probability
781///
782/// ```text
783/// accept = target.density(x) / (m * proposal.density(x))
784/// ```
785///
786/// for an envelope constant `m` satisfying `m * proposal.density(x) >=
787/// target.density(x)` for all `x`. Exposure via [`Distribution<f64>`] is
788/// guaranteed to terminate by giving up after [`max_iterations`](RejectionSampler::max_iterations)
789/// (default `1024`) rejections.
790///
791/// # Examples
792///
793/// ```
794/// use tpt_math_prob_sampler::{RejectionSampler, Uniform, DensityFn};
795/// use tpt_math_prob_core::{Rng, SplitMix64, Distribution};
796/// // Sample the triangular density 2x on [0,1] using a Uniform(0,1) proposal.
797/// let target = DensityFn(|x: f64| if x >= 0.0 && x <= 1.0 { 2.0 * x } else { 0.0 });
798/// let proposal = Uniform::new(0.0, 1.0).unwrap();
799/// let rs = RejectionSampler::new(target, proposal, 2.0).unwrap();
800/// let mut rng = SplitMix64::seed_from_u64(0);
801/// let x = rs.sample(&mut rng);
802/// assert!(x >= 0.0 && x <= 1.0);
803/// ```
804pub struct RejectionSampler<T, P> {
805    target: T,
806    proposal: P,
807    m: f64,
808    max_iterations: usize,
809}
810
811impl<T, P> RejectionSampler<T, P>
812where
813    T: Density,
814    P: Distribution<f64> + Density,
815{
816    /// Construct a rejection sampler with envelope constant `m > 0`.
817    ///
818    /// `m` must satisfy `m * proposal.density(x) >= target.density(x)` for all
819    /// `x`; it is validated to be finite and strictly positive.
820    pub fn new(target: T, proposal: P, m: f64) -> Result<Self, SamplerError> {
821        if !m.is_finite() || m <= 0.0 {
822            return Err(SamplerError::InvalidBound);
823        }
824        Ok(RejectionSampler {
825            target,
826            proposal,
827            m,
828            max_iterations: 1024,
829        })
830    }
831
832    /// Borrow the target density.
833    pub fn target(&self) -> &T {
834        &self.target
835    }
836
837    /// Borrow the proposal distribution.
838    pub fn proposal(&self) -> &P {
839        &self.proposal
840    }
841
842    /// The envelope constant `m`.
843    pub fn m(&self) -> f64 {
844        self.m
845    }
846
847    /// Set the maximum number of rejection attempts (default `1024`).
848    pub fn max_iterations(mut self, n: usize) -> Self {
849        self.max_iterations = n;
850        self
851    }
852
853    /// Best-case acceptance probability `1 / m` (the proposal is optimal when
854    /// the envelope is tight).
855    pub fn acceptance_probability(&self) -> f64 {
856        1.0 / self.m
857    }
858
859    /// Attempt to draw a sample, returning `None` if `max_iterations`
860    /// rejections occur first.
861    pub fn try_sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<f64> {
862        for _ in 0..self.max_iterations {
863            let x = self.proposal.sample(rng);
864            let pd = self.proposal.density(x);
865            if pd <= 0.0 {
866                continue;
867            }
868            let td = self.target.density(x);
869            let u: f64 = Standard.sample(rng);
870            if u * self.m * pd <= td {
871                return Some(x);
872            }
873        }
874        None
875    }
876}
877
878impl<T, P> Distribution<f64> for RejectionSampler<T, P>
879where
880    T: Density,
881    P: Distribution<f64> + Density,
882{
883    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 {
884        self.try_sample(rng)
885            .unwrap_or_else(|| self.proposal.sample(rng))
886    }
887}
888
889// =====================================================================
890// Prelude
891// =====================================================================
892
893/// Convenient re-exports for sampling work.
894pub mod prelude {
895    pub use crate::{
896        Bernoulli, Density, DensityFn, Distribution, InverseCdfSampler, RejectionSampler,
897        ReservoirSampler, Rng, Sampler, SamplerError, SystematicResampler, Uniform,
898    };
899    pub use tpt_math_prob_core::{SplitMix64, Standard};
900
901    #[cfg(any(feature = "std", feature = "alloc"))]
902    pub use crate::{categorical, WeightedIndex};
903}
904
905#[cfg(test)]
906mod tests {
907    use super::*;
908
909    #[cfg(any(feature = "std", feature = "alloc"))]
910    use alloc::vec;
911    #[cfg(any(feature = "std", feature = "alloc"))]
912    use alloc::vec::Vec;
913
914    const SEED: u64 = 0x1234_5678;
915
916    #[test]
917    fn cdf_from_weights_is_normalised() {
918        #[cfg(any(feature = "std", feature = "alloc"))]
919        {
920            let s = InverseCdfSampler::from_weights(&[1.0, 2.0, 3.0]).unwrap();
921            let cdf = s.cdf();
922            assert!((cdf.last().unwrap() - 1.0).abs() < 1e-12);
923            assert!((s.probability(0) - 1.0 / 6.0).abs() < 1e-12);
924            assert!((s.probability(1) - 2.0 / 6.0).abs() < 1e-12);
925            assert!((s.probability(2) - 3.0 / 6.0).abs() < 1e-12);
926        }
927    }
928
929    #[test]
930    fn from_cdf_rejects_bad_input() {
931        #[cfg(any(feature = "std", feature = "alloc"))]
932        {
933            assert_eq!(
934                InverseCdfSampler::from_cdf(vec![0.5, 0.4, 1.0]),
935                Err(SamplerError::InvalidCdf)
936            );
937            assert_eq!(
938                InverseCdfSampler::from_cdf(vec![0.5, 0.9]),
939                Err(SamplerError::InvalidCdf)
940            );
941        }
942        let _ = SEED;
943    }
944
945    #[test]
946    fn weights_validation_errors() {
947        #[cfg(any(feature = "std", feature = "alloc"))]
948        {
949            assert_eq!(
950                InverseCdfSampler::from_weights(&[]),
951                Err(SamplerError::Empty)
952            );
953            assert_eq!(
954                InverseCdfSampler::from_weights(&[-1.0]),
955                Err(SamplerError::NegativeWeight)
956            );
957            assert_eq!(
958                InverseCdfSampler::from_weights(&[f64::NAN]),
959                Err(SamplerError::NonFiniteWeight)
960            );
961            assert_eq!(
962                InverseCdfSampler::from_weights(&[0.0, 0.0]),
963                Err(SamplerError::ZeroTotal)
964            );
965        }
966    }
967
968    #[test]
969    fn zero_weight_never_selected() {
970        #[cfg(any(feature = "std", feature = "alloc"))]
971        {
972            let s = InverseCdfSampler::from_weights(&[1.0, 0.0, 0.0, 1.0]).unwrap();
973            let mut rng = SplitMix64::seed_from_u64(SEED);
974            for _ in 0..5000 {
975                let i = s.sample(&mut rng);
976                assert!(i == 0 || i == 3);
977            }
978        }
979    }
980
981    #[test]
982    fn sample_index_from_uniform_boundaries() {
983        #[cfg(any(feature = "std", feature = "alloc"))]
984        {
985            let s = InverseCdfSampler::from_weights(&[0.5, 0.5]).unwrap();
986            assert_eq!(s.sample_index_from_uniform(0.0), 0);
987            assert_eq!(s.sample_index_from_uniform(0.499999), 0);
988            assert_eq!(s.sample_index_from_uniform(0.5), 1);
989            assert_eq!(s.sample_index_from_uniform(0.999999), 1);
990        }
991    }
992
993    #[test]
994    fn linear_categorical_matches_alias() {
995        #[cfg(any(feature = "std", feature = "alloc"))]
996        {
997            let weights = [1.0, 3.0, 2.0, 4.0];
998            let alias = categorical(&weights).unwrap();
999            let mut rng = SplitMix64::seed_from_u64(SEED);
1000            let mut acc = [0usize; 4];
1001            for _ in 0..40000 {
1002                let a = alias.sample(&mut rng);
1003                let b = sample_categorical(&weights, &mut rng).unwrap();
1004                acc[a] += 1;
1005                acc[b] += 1;
1006            }
1007            let total = acc.iter().sum::<usize>() as f64;
1008            let sum = weights.iter().sum::<f64>();
1009            for i in 0..4 {
1010                let expected = weights[i] / sum;
1011                assert!((acc[i] as f64 / total - expected).abs() < 0.02, "bin {i}");
1012            }
1013        }
1014    }
1015
1016    #[test]
1017    fn systematic_resample_counts_bounded() {
1018        #[cfg(any(feature = "std", feature = "alloc"))]
1019        {
1020            let weights = [1.0, 1.0, 2.0];
1021            let r = SystematicResampler::from_weights(&weights).unwrap();
1022            let mut rng = SplitMix64::seed_from_u64(SEED);
1023            let n = 1000usize;
1024            let mut out = vec![0usize; n];
1025            // Each scheme should keep every index inside the category range.
1026            for &scheme in &[
1027                ResampleScheme::Multinomial,
1028                ResampleScheme::Systematic,
1029                ResampleScheme::Stratified,
1030            ] {
1031                r.sample_indices(&mut rng, scheme, &mut out);
1032                assert!(out.iter().all(|&i| i < 3));
1033                // counts within [floor, ceil] of n*p_i
1034                let mut counts = [0usize; 3];
1035                for &i in &out {
1036                    counts[i] += 1;
1037                }
1038                let total = weights.iter().sum::<f64>();
1039                let n_f = n as f64;
1040                for (i, &c) in counts.iter().enumerate() {
1041                    let p = weights[i] / total;
1042                    if scheme == ResampleScheme::Systematic {
1043                        // Systematic resampling keeps each count within
1044                        // [floor, ceil] of its expectation.
1045                        let lo = (n_f * p).floor() as usize;
1046                        let hi = (n_f * p).ceil() as usize;
1047                        assert!(
1048                            c >= lo && c <= hi,
1049                            "scheme {scheme:?} bin {i}: {c} not in [{lo},{hi}]"
1050                        );
1051                    } else {
1052                        // Multinomial / stratified have variance; only check
1053                        // the empirical mean is approximately correct.
1054                        let mean = c as f64 / n_f;
1055                        assert!(
1056                            (mean - p).abs() < 0.05,
1057                            "scheme {scheme:?} bin {i}: mean {mean} vs {p}"
1058                        );
1059                    }
1060                }
1061            }
1062        }
1063    }
1064
1065    #[test]
1066    fn reservoir_uniform_among_stream() {
1067        let mut rng = SplitMix64::seed_from_u64(SEED);
1068        let mut slots = [0u32; 10];
1069        let mut rs = ReservoirSampler::new(&mut slots);
1070        for x in 0u32..100 {
1071            rs.offer(x, &mut rng);
1072        }
1073        assert_eq!(rs.capacity(), 10);
1074        assert!(slots.iter().all(|&v| v < 100));
1075        assert!(slots.iter().any(|&v| v >= 90));
1076
1077        // Small stream: reservoir holds everything.
1078        let mut small = [0u32; 5];
1079        let mut rs2 = ReservoirSampler::new(&mut small);
1080        for x in 0u32..3 {
1081            rs2.offer(x, &mut rng);
1082        }
1083        let mut collected: Vec<u32> = rs2.sample().to_vec();
1084        collected.sort_unstable();
1085        assert_eq!(collected, vec![0, 1, 2]);
1086    }
1087
1088    #[test]
1089    fn reservoir_is_fair_over_trials() {
1090        let mut rng = SplitMix64::seed_from_u64(SEED);
1091        let mut hits = [0u32; 100];
1092        for _ in 0..20000u32 {
1093            let mut slots = [0u32; 10];
1094            let mut rs = ReservoirSampler::new(&mut slots);
1095            for x in 0u32..100 {
1096                rs.offer(x, &mut rng);
1097            }
1098            for &v in rs.sample() {
1099                hits[v as usize] += 1;
1100            }
1101        }
1102        for &h in &hits {
1103            // expected ~ (10/100) * 20000 = 2000
1104            assert!((h as f64 - 2000.0).abs() < 350.0, "hit count {h}");
1105        }
1106    }
1107
1108    #[test]
1109    fn uniform_index_is_unbiased() {
1110        let mut rng = SplitMix64::seed_from_u64(SEED);
1111        let n = 6usize;
1112        let mut counts = [0u32; 6];
1113        for _ in 0..60000 {
1114            let i = uniform_index(&mut rng, n).unwrap();
1115            counts[i] += 1;
1116        }
1117        for &c in &counts {
1118            assert!((c as f64 - 10000.0).abs() < 600.0, "count {c}");
1119        }
1120        assert_eq!(uniform_index(&mut rng, 0), None);
1121        assert_eq!(uniform_index(&mut rng, 1), Some(0));
1122    }
1123
1124    #[test]
1125    fn shuffle_is_a_permutation() {
1126        let mut rng = SplitMix64::seed_from_u64(SEED);
1127        let mut v = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
1128        shuffle(&mut v, &mut rng);
1129        let mut sorted = v;
1130        sorted.sort_unstable();
1131        assert_eq!(sorted, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1132    }
1133
1134    #[test]
1135    fn rejection_triangular_mean() {
1136        // Target: f(x) = 2x on [0,1] (mean 2/3). Proposal: Uniform(0,1), m=2.
1137        let target = DensityFn(|x: f64| {
1138            if (0.0..=1.0).contains(&x) {
1139                2.0 * x
1140            } else {
1141                0.0
1142            }
1143        });
1144        let proposal = Uniform::new(0.0, 1.0).unwrap();
1145        let rs = RejectionSampler::new(target, proposal, 2.0).unwrap();
1146        let mut rng = SplitMix64::seed_from_u64(SEED);
1147        let mut sum = 0.0;
1148        let trials = 50000u32;
1149        for _ in 0..trials {
1150            let x = rs.sample(&mut rng);
1151            assert!((0.0..=1.0).contains(&x));
1152            sum += x;
1153        }
1154        let mean = sum / trials as f64;
1155        assert!((mean - 2.0 / 3.0).abs() < 0.02, "mean {mean}");
1156        // Acceptance probability ~ 1/m.
1157        let _ = rs.acceptance_probability();
1158    }
1159
1160    #[test]
1161    fn rejection_invalid_bound() {
1162        let target = DensityFn(|_x: f64| 1.0);
1163        let proposal = Uniform::new(0.0, 1.0).unwrap();
1164        assert!(matches!(
1165            RejectionSampler::new(target, proposal, 0.0),
1166            Err(SamplerError::InvalidBound)
1167        ));
1168    }
1169
1170    #[test]
1171    fn bernoulli_mean() {
1172        let b = Bernoulli::new(0.3).unwrap();
1173        let mut rng = SplitMix64::seed_from_u64(SEED);
1174        let trials = 50000u32;
1175        let mut ones = 0u32;
1176        for _ in 0..trials {
1177            if b.sample(&mut rng) {
1178                ones += 1;
1179            }
1180        }
1181        let p = ones as f64 / trials as f64;
1182        assert!((p - 0.3).abs() < 0.02, "p {p}");
1183    }
1184
1185    #[test]
1186    fn sampler_slice_fills() {
1187        #[cfg(any(feature = "std", feature = "alloc"))]
1188        {
1189            let s = categorical(&[1.0, 1.0, 1.0, 1.0]).unwrap();
1190            let mut rng = SplitMix64::seed_from_u64(SEED);
1191            let mut buf = [0usize; 16];
1192            s.sample_slice(&mut rng, &mut buf);
1193            assert!(buf.iter().all(|&i| i < 4));
1194        }
1195    }
1196
1197    #[test]
1198    fn deterministic_with_seed() {
1199        let mut a = SplitMix64::seed_from_u64(SEED);
1200        let mut b = SplitMix64::seed_from_u64(SEED);
1201        #[cfg(any(feature = "std", feature = "alloc"))]
1202        {
1203            let s = categorical(&[1.0, 2.0, 3.0, 4.0]).unwrap();
1204            let x1 = s.sample(&mut a);
1205            let x2 = s.sample(&mut b);
1206            assert_eq!(x1, x2);
1207        }
1208        let _ = (&mut a, &mut b);
1209    }
1210}