use rand::RngCore;
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
use std::cell::Cell;
const F64_UNIT_INTERVAL_SCALE: f64 = 1.0 / ((1u64 << 53) as f64);
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct RareErrorTelemetry {
pub iterator_builds: usize,
pub rng_core_draws: usize,
}
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
thread_local! {
static ITERATOR_BUILDS: Cell<usize> = const { Cell::new(0) };
static RNG_CORE_DRAWS: Cell<usize> = const { Cell::new(0) };
}
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
#[doc(hidden)]
pub fn reset_rare_error_telemetry() {
ITERATOR_BUILDS.with(|builds| builds.set(0));
RNG_CORE_DRAWS.with(|draws| draws.set(0));
}
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
#[doc(hidden)]
pub fn rare_error_telemetry() -> RareErrorTelemetry {
RareErrorTelemetry {
iterator_builds: ITERATOR_BUILDS.with(Cell::get),
rng_core_draws: RNG_CORE_DRAWS.with(Cell::get),
}
}
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
fn record_iterator_build() {
ITERATOR_BUILDS.with(|builds| builds.set(builds.get().saturating_add(1)));
}
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
fn record_rng_core_draw() {
RNG_CORE_DRAWS.with(|draws| draws.set(draws.get().saturating_add(1)));
}
#[derive(Debug, Clone, Copy)]
enum RareErrorMode {
Empty,
Dense,
Sparse { log_one_minus_p: f64 },
}
pub(crate) struct RareErrorIndexSampler {
attempt_count: usize,
next_candidate: usize,
mode: RareErrorMode,
}
impl RareErrorIndexSampler {
pub(crate) fn new(probability: f64, attempt_count: usize) -> Self {
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
record_iterator_build();
let mode = if attempt_count == 0 || probability <= 0.0 || probability.is_nan() {
RareErrorMode::Empty
} else if probability >= 1.0 {
RareErrorMode::Dense
} else {
RareErrorMode::Sparse {
log_one_minus_p: (-probability).ln_1p(),
}
};
Self {
attempt_count,
next_candidate: 0,
mode,
}
}
pub(crate) fn next_index<R: RngCore + ?Sized>(&mut self, rng: &mut R) -> Option<usize> {
match self.mode {
RareErrorMode::Empty => None,
RareErrorMode::Dense => {
if self.next_candidate >= self.attempt_count {
return None;
}
let index = self.next_candidate;
self.next_candidate += 1;
Some(index)
}
RareErrorMode::Sparse { log_one_minus_p } => {
while self.next_candidate < self.attempt_count {
let uniform = draw_open_unit_f64(rng);
let skip = (uniform.ln() / log_one_minus_p).floor();
let skip = if skip.is_finite() && skip >= 0.0 {
skip as usize
} else {
usize::MAX
};
let index = self.next_candidate.saturating_add(skip);
if index >= self.attempt_count {
self.next_candidate = self.attempt_count;
return None;
}
self.next_candidate = index + 1;
return Some(index);
}
None
}
}
}
}
pub struct RareErrorIterator<'a, R: RngCore + ?Sized> {
rng: &'a mut R,
sampler: RareErrorIndexSampler,
}
pub fn rare_error_indices<'a, R: RngCore + ?Sized>(
probability: f64,
attempt_count: usize,
rng: &'a mut R,
) -> RareErrorIterator<'a, R> {
RareErrorIterator::new(probability, attempt_count, rng)
}
impl<'a, R: RngCore + ?Sized> RareErrorIterator<'a, R> {
pub fn new(probability: f64, attempt_count: usize, rng: &'a mut R) -> Self {
Self {
rng,
sampler: RareErrorIndexSampler::new(probability, attempt_count),
}
}
}
impl<R: RngCore + ?Sized> Iterator for RareErrorIterator<'_, R> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
self.sampler.next_index(self.rng)
}
}
fn draw_open_unit_f64<R: RngCore + ?Sized>(rng: &mut R) -> f64 {
loop {
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
record_rng_core_draw();
let raw = rng.next_u64();
let value = ((raw >> 11) as f64) * F64_UNIT_INTERVAL_SCALE;
if value > 0.0 {
return value;
}
}
}