Struct RandomCutTree 

pub struct RandomCutTree<const D: usize> { /* private fields */ }

Incrementally-maintained random cut tree over up to capacity distinct D-dimensional points.

Examples

use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;
use anomstream_core::RandomCutTree;

let mut tree = RandomCutTree::<2>::new(8).unwrap();
let p = [1.0_f64, 2.0];
let points = vec![p];
let mut rng = ChaCha8Rng::seed_from_u64(42);
tree.add(0, &p, &points, &mut rng).unwrap();
assert!(tree.root().unwrap().is_leaf());

Implementations

impl<const D: usize> RandomCutTree<D>

pub fn new(capacity: u32) -> RcfResult<Self>

Build an empty tree with room for capacity distinct points.

Errors

Returns RcfError::InvalidConfig when D == 0, capacity == 0, or capacity exceeds the store limit.

pub fn root(&self) -> Option<NodeRef>

Root node reference, or None when the tree is empty.

pub const fn dimension(&self) -> usize

Configured dimensionality (compile-time D).

pub fn distinct_point_count(&self) -> usize

Number of distinct points currently stored (each leaf counts once regardless of its mass).

pub fn store(&self) -> &NodeStore<D>

Borrow the underlying node store. Used by tests and persistence.

pub fn contains(&self, point_idx: usize) -> bool

Whether the tree currently stores point_idx.

pub fn leaf_of(&self, point_idx: usize) -> Option<NodeRef>

NodeRef of the leaf currently mapped to point_idx, or None when the reservoir has evicted it (or never admitted it). Exposed so forest-level scoring paths that need to walk the leaf’s ancestor chain (e.g. codisp-style probe scoring) can locate the leaf without re-traversing from the root.

pub fn max_depth(&self) -> Option<usize>

Maximum depth from the root to any leaf, or None when the tree is empty. Used by tests and diagnostics to verify the expected O(log n) depth bound under uniform-random inserts.

pub fn add<R, P>( &mut self, point_idx: usize, point: &[f64], points: &P, rng: &mut R, ) -> RcfResult<()>

where R: Rng + ?Sized, P: PointAccessor<D> + ?Sized,

Insert point (registered under point_idx in the caller’s point store) into the tree.

When an identical point is already present, the existing leaf’s mass is incremented and point_idx is mapped to that same leaf — duplicate-point handling per Guha 2016.

Errors

• RcfError::DimensionMismatch when point.len() != self.dimension().
• RcfError::NaNValue when point contains a non-finite component.
• RcfError::InvalidConfig when point_idx is already present.
• RcfError::InvalidConfig when the underlying store runs out of internal or leaf slots.

pub fn delete<P>(&mut self, point_idx: usize, points: &P) -> RcfResult<()>

where P: PointAccessor<D> + ?Sized,

Remove the leaf currently mapped to point_idx. When the leaf has mass > 1 (duplicate point), only the mass is decremented and the leaf is preserved.

Errors

• RcfError::InvalidConfig when point_idx is not present.
• RcfError::OutOfBounds when the underlying store cannot look up a referenced point.

pub fn codisp_stateless(&self, point: &[f64]) -> RcfResult<f64>

Non-mutating codisp estimate — walks root → leaf following the stored cuts and accumulates the maximum per-depth ratio sibling_mass / subtree_mass across the descent path.

Matches the shape of the mutating crate::RandomCutForest::score_codisp walk but without inserting the probe into the reservoir. The classical codisp promises a frozen baseline (AWS / rrcf); the mutating path’s insert+delete cycle leaves reservoir points evicted permanently, eroding that baseline across long eval streams (observed on NAB rogue_hold: score drifts from 0.69 to 0.20 after ~5 k probes).

This path preserves the frozen-baseline promise exactly, takes &self so it parallelises across trees, and costs O(depth · D) per call — typically cheaper than the mutating walk since there is no reservoir housekeeping.

Errors

• RcfError::EmptyForest when the tree is empty.
• RcfError::DimensionMismatch when point.len() != D.
• RcfError::NaNValue when point contains a non-finite component.

pub fn traverse<V: Visitor<D>>( &self, point: &[f64], visitor: V, ) -> RcfResult<V::Output>

Walk from the root to the leaf matching point along the stored cuts, dispatching callbacks to visitor. Returns the visitor’s final output.

Errors

• RcfError::EmptyForest when the tree is empty.
• RcfError::DimensionMismatch when point.len() != self.dimension().
• RcfError::NaNValue when point contains a non-finite component.

Trait Implementations

impl<const D: usize> Debug for RandomCutTree<D>

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

Formats the value using the given formatter.

impl<'de, const D: usize> Deserialize<'de> for RandomCutTree<D>

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<const D: usize> Serialize for RandomCutTree<D>

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.