Struct WeightedIndex 

pub struct WeightedIndex { /* private fields */ }

A collection of weights at fixed indices supporting proportional and uniform draws and updates.

Construction takes O(n) time and space. Sampling and changing a weight take O(log n) time. Zero-weight entries are never sampled. Draws use only integer arithmetic, so a fixed sequence of weights and random input is reproducible across platforms.

Examples

use commonware_utils::sampling::WeightedIndex;
use rand::{SeedableRng, rngs::StdRng};

let mut rng = StdRng::seed_from_u64(0);
let mut weights = WeightedIndex::new([0, 5]);
assert_eq!(weights.sample(&mut rng), Some(1));
assert_eq!(weights.update(1, |weight| weight * 2), 5);
assert_eq!(weights.weight(1), 10);
weights.set(1, 0);
assert_eq!(weights.sample(&mut rng), None);

Implementations

impl WeightedIndex

pub fn new(weights: impl IntoIterator<Item = u64>) -> Self

Builds an index over weights, preserving their order.

pub const fn total(&self) -> u128

Returns the sum of all weights.

pub fn weight(&self, index: usize) -> u64

Returns the weight at index.

Panics

Panics if index is out of bounds.

pub fn set(&mut self, index: usize, weight: u64) -> u64

Replaces the weight at index, returning its previous value.

Panics

Panics if index is out of bounds.

pub fn update(&mut self, index: usize, f: impl FnOnce(u64) -> u64) -> u64

Applies f to the weight at index, returning its previous value. Returning the same weight skips the update.

Panics

Panics if index is out of bounds, before invoking f. If f panics, self is unchanged.

pub fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<usize>

Draws an index with probability proportional to its weight.

Returns None without consuming randomness when the total weight is zero.

pub fn sample_uniform<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<usize>

Draws uniformly from the indices with positive weight.

Returns None without consuming randomness when all weights are zero.

pub const fn without_replacement(&mut self) -> WithoutReplacement<'_>

Starts a sequence of draws that can choose each positive-weight index at most once.

Dropping the sequence restores all weights, including during unwinding. Construction takes constant time without allocating. Each draw takes amortized O(log n) time, and k draws use O(k) space. Stopping after the first draw leaves the index unchanged and needs no restoration.

Examples

use commonware_utils::sampling::WeightedIndex;
use rand::{SeedableRng, rngs::StdRng};

let mut rng = StdRng::seed_from_u64(0);
let mut weights = WeightedIndex::new([0, 5, 3]);
{
    let mut draws = weights.without_replacement();
    let first = draws.sample(&mut rng).unwrap();
    let second = draws.sample_uniform(&mut rng).unwrap();
    assert_ne!(first, second);
    assert!(draws.is_empty());
}
assert_eq!(weights.total(), 8);

pub const fn into_without_replacement(self) -> WithoutReplacement<'static>

Consumes this index for draws that can choose each positive-weight index at most once.

Construction takes constant time without allocating. Each draw takes O(log n) time and constant extra space, because a consumed index is never restored.