Struct SumTree 

pub struct SumTree { /* private fields */ }

A binary sum tree holding exactly capacity leaves.

The backing tree is padded up to a power of two internally; the extra padding leaves stay at zero weight and are never returned by SumTree::get. The exposed SumTree::capacity is exactly what you requested.

Implementations

impl SumTree

pub fn new(capacity: usize) -> Self

Create a tree that holds exactly capacity leaves (at least one).

pub fn capacity(&self) -> usize

Number of leaves the tree can hold.

pub fn len(&self) -> usize

Number of leaves currently written.

pub fn is_empty(&self) -> bool

pub fn is_full(&self) -> bool

pub fn total(&self) -> f32

Sum of every priority in the tree.

pub fn priority(&self, index: usize) -> f32

Read the priority stored at index.

pub fn update(&mut self, index: usize, priority: f32)

Set the priority at index and repair the sums up to the root.

Ancestors are adjusted by the delta rather than recomputed from both children, halving the memory traffic per level. Over very many updates this can accumulate floating-point drift; call SumTree::rebuild to reset it.

pub fn rebuild(&mut self)

Recompute every internal sum from the leaves, clearing any drift left by repeated SumTree::update calls.

pub fn push(&mut self, priority: f32) -> usize

Append a priority at the next ring position, overwriting the oldest leaf when full. Returns the leaf index that was written.

pub fn get(&self, s: f32) -> Option<(usize, f32)>

Find the leaf whose cumulative-weight interval contains s, returning its index and priority. s is clamped to [0, total]. Returns None when the tree is empty or its total weight is zero.

The returned index is always in [0, len), so it is safe to use it in a side buffer sized to SumTree::capacity.

Trait Implementations

impl Clone for SumTree

fn clone(&self) -> SumTree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SumTree

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

Formats the value using the given formatter.