Enum DigitBinIndex 

pub enum DigitBinIndex {
    Small(DigitBinIndexGeneric<Vec<u32>>),
    Medium(DigitBinIndexGeneric<RoaringBitmap>),
    Large(DigitBinIndexGeneric<RoaringTreemap>),
}

A data structure that organizes weighted items into bins based on their decimal digits to enable fast weighted random selection and updates.

This structure is a specialized radix tree optimized for sequential sampling (like in Wallenius’ distribution). It makes a deliberate engineering trade-off: it sacrifices a small, controllable amount of precision by binning items, but in return, it achieves O(P) performance for its core operations, where P is the configured precision. This is significantly faster than the O(log N) performance of general-purpose structures like a Fenwick Tree for its ideal use case.

Examples

use digit_bin_index::DigitBinIndex;
let mut index = DigitBinIndex::with_precision_and_capacity(3, 100);

Variants

Small(DigitBinIndexGeneric<Vec<u32>>)

Medium(DigitBinIndexGeneric<RoaringBitmap>)

Large(DigitBinIndexGeneric<RoaringTreemap>)

Implementations

impl DigitBinIndex

pub fn with_precision_and_capacity(precision: u8, capacity: u64) -> Self

Creates a new DigitBinIndex with the given precision and expected capacity. Uses Vec for small bins, RoaringBitmap for large bins.

Arguments

• precision - The number of decimal places for binning (1 to 9).
• capacity - The expected number of items to be stored in the index.

Returns

A new DigitBinIndex instance with the appropriate bin type.

Panics

Panics if precision is 0 or greater than 9.

Examples

use digit_bin_index::DigitBinIndex;

let index = DigitBinIndex::with_precision_and_capacity(3, 100);
// Uses Vec<u32> because capacity is small

pub fn small(precision: u8) -> Self

Creates a new DigitBinIndex with Vec bins and the specified precision.

Optimized for small to medium-sized problems (average <= 1,000 items per bin). Provides the fastest O(1) select_and_remove performance but truncates u64 IDs to u32.

Arguments

• precision - The number of decimal places for binning (1 to 9).

Returns

A new DigitBinIndex instance with Vec bins.

Panics

Panics if precision is 0 or greater than 9.

Examples

use digit_bin_index::DigitBinIndex;

let index = DigitBinIndex::small(3);
assert_eq!(index.precision(), 3);

pub fn medium(precision: u8) -> Self

Creates a new DigitBinIndex with RoaringBitmap bins and the specified precision.

Optimized for large-scale problems (average > 1,000 items per bin) where IDs fit within u32. Provides excellent memory compression and fast set operations but truncates u64 IDs to u32.

Arguments

• precision - The number of decimal places for binning (1 to 9).

Returns

A new DigitBinIndex instance with RoaringBitmap bins.

Panics

Panics if precision is 0 or greater than 9.

Examples

use digit_bin_index::DigitBinIndex;

let index = DigitBinIndex::medium(3);
assert_eq!(index.precision(), 3);

pub fn large(precision: u8) -> Self

Creates a new DigitBinIndex with RoaringTreemap bins and the specified precision.

Optimized for massive-scale problems requiring full u64 ID support (average > 1,000,000,000 items per bin). Supports the full 64-bit ID space, ideal for extremely large datasets.

Arguments

• precision - The number of decimal places for binning (1 to 9).

Returns

A new DigitBinIndex instance with RoaringTreemap bins.

Panics

Panics if precision is 0 or greater than 9.

Examples

use digit_bin_index::DigitBinIndex;

let index = DigitBinIndex::large(3);
assert_eq!(index.precision(), 3);

pub fn new() -> Self

Creates a new DigitBinIndex instance with the default precision.

The default precision is set to 3 decimal places, which provides a good balance between accuracy and performance for most use cases. For custom precision, use with_precision.

Returns

A new DigitBinIndex instance.

Examples

use digit_bin_index::DigitBinIndex;

let index = DigitBinIndex::new();
assert_eq!(index.precision(), 3);

pub fn with_precision(precision: u8) -> Self

Creates a new DigitBinIndex instance with the specified precision.

The precision determines the number of decimal places used for binning weights. Higher precision improves sampling accuracy but increases memory usage and tree depth. Precision must be between 1 and 9 (inclusive).

Arguments

• precision - The number of decimal places for binning (1 to 9).

Returns

A new DigitBinIndex instance with the given precision.

Panics

Panics if precision is 0 or greater than 9.

Examples

use digit_bin_index::DigitBinIndex;

let index = DigitBinIndex::with_precision(4);
assert_eq!(index.precision(), 4);

pub fn add(&mut self, id: u64, weight: f64)

Adds an item with the given ID and weight to the index.

The weight is rescaled to the index’s precision and binned accordingly. If the weight is non-positive or becomes zero after scaling, the item is not added.

Arguments

• individual_id - The unique ID of the item to add (u32).
• weight - The positive weight (probability) of the item.

Returns

true if the item was successfully added, false otherwise (e.g., invalid weight).

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
let added = index.add(1, 0.5);
assert_eq!(index.count(), 1);

pub fn add_many(&mut self, items: &[(u64, f64)])

Adds multiple items to the index in a highly optimized batch operation.

This method is significantly faster than calling add in a loop for large collections of items. It works by pre-processing the input, grouping items by their shared weight, and then propagating each group through the tree in a single pass. This minimizes cache misses and reduces function call overhead.

Weights are rescaled to the index’s precision and binned accordingly. Items with non-positive weights or weights that become zero after scaling will be ignored.

Arguments

• items - A slice of (id, weight) tuples to add to the index.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
let items_to_add = vec![(1, 0.1), (2, 0.2), (3, 0.1)];
index.add_many(&items_to_add);

assert_eq!(index.count(), 3);
// The total weight should be 0.1 + 0.2 + 0.1 = 0.4
assert!((index.total_weight() - 0.4).abs() < f64::EPSILON);

pub fn remove(&mut self, id: u64, weight: f64) -> bool

Removes an item with the given ID and weight from the index.

The weight must match the one used during addition (after rescaling). If the item is not found in the corresponding bin, no removal occurs.

Arguments

• individual_id - The ID of the item to remove.
• weight - The weight of the item (must match the added weight).

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
index.add(1, 0.5);
index.remove(1, 0.5);
assert_eq!(index.count(), 0);

pub fn remove_many(&mut self, items: &[(u64, f64)]) -> bool

Removes multiple items from the index in a highly optimized batch operation.

This method is significantly faster than calling remove in a loop. It groups the items to be removed by their weight path and traverses the tree only once per group, performing aggregated updates on the way up.

The (id, weight) pairs must match items that are currently in the index. If a given pair is not found, it is silently ignored.

Arguments

• items - A slice of (id, weight) tuples to remove from the index.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
let items_to_add = vec![(1, 0.1), (2, 0.2), (3, 0.1), (4, 0.3)];
index.add_many(&items_to_add);
assert_eq!(index.count(), 4);

let items_to_remove = vec![(2, 0.2), (3, 0.1)];
index.remove_many(&items_to_remove);

assert_eq!(index.count(), 2); // Items 1 and 4 should remain
// The total weight should be 0.1 + 0.3 = 0.4
assert!((index.total_weight() - 0.4).abs() < f64::EPSILON);

pub fn select(&mut self) -> Option<(u64, f64)>

Selects a single item randomly based on weights without removal.

Performs weighted random selection. Returns None if the index is empty.

Returns

An Option containing the selected item’s ID and its (rescaled) weight.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
index.add(1, 0.5);
if let Some((id, weight)) = index.select() {
    assert_eq!(id, 1);
    assert_eq!(weight, 0.5);
}

pub fn select_and_remove(&mut self) -> Option<(u64, f64)>

Selects a single item randomly and removes it from the index.

Combines selection and removal in one operation. Returns None if empty.

Returns

An Option containing the selected item’s ID and weight.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
index.add(1, 0.5);
if let Some((id, _)) = index.select_and_remove() {
    assert_eq!(id, 1);
}
assert_eq!(index.count(), 0);

pub fn select_many(&mut self, num_to_draw: u64) -> Option<Vec<(u64, f64)>>

Selects multiple unique items randomly based on weights without removal.

Uses rejection sampling to ensure uniqueness. Returns None if num_to_draw exceeds the number of items in the index.

Arguments

• num_to_draw - The number of unique items to select.

Returns

An Option containing a vector of selected (ID, weight) pairs.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
index.add(1, 0.3);
index.add(2, 0.7);
if let Some(selected) = index.select_many(2) {
    assert_eq!(selected.len(), 2);
}

pub fn select_many_and_remove( &mut self, num_to_draw: u64, ) -> Option<Vec<(u64, f64)>>

Selects multiple unique items randomly and removes them from the index.

Selects and removes in batch. Returns None if num_to_draw exceeds item count.

Arguments

• num_to_draw - The number of unique items to select and remove.

Returns

An Option containing a vector of selected (ID, weight) pairs.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
index.add(1, 0.3);
index.add(2, 0.7);
if let Some(selected) = index.select_many_and_remove(2) {
    assert_eq!(selected.len(), 2);
}
assert_eq!(index.count(), 0);

pub fn count(&self) -> u64

Returns the total number of items currently in the index.

Returns

The count of items as a u32.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
assert_eq!(index.count(), 0);

pub fn total_weight(&self) -> f64

Returns the sum of all weights in the index.

This represents the total accumulated probability mass.

Returns

The total weight as a f64.

Examples

use digit_bin_index::DigitBinIndex;

let mut index = DigitBinIndex::new();
index.add(1, 0.5);
assert_eq!(index.total_weight(), 0.5);

pub fn print_stats(&self)

Prints detailed statistics about the index’s structure, memory usage, and data distribution.

pub fn precision(&self) -> u8

Returns the precision (number of decimal places) used for binning.

Trait Implementations

impl Clone for DigitBinIndex

fn clone(&self) -> DigitBinIndex

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DigitBinIndex

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.