Struct VPTree 

pub struct VPTree { /* private fields */ }

Vantage Point tree for O(log n) spatial queries under the hyperbolic metric.

Uses a buffer + lazy-deletion strategy for efficient dynamic updates:

• Insertions accumulate in a small buffer; the tree rebuilds when the buffer fills.
• Deletions mark entries as dead; the tree rebuilds when too many are marked.
• Queries search both the tree and the buffer, preserving correctness.

Within each hash table bucket, this replaces the previous linear scan (O(n/B) per bucket) with O(log(n/B)) queries.

Implementations

impl VPTree

pub fn new() -> Self

Create an empty VP-tree.

pub fn insert(&mut self, entry: BucketEntry)

Insert an entry. Duplicates (by unique_id) in the buffer are ignored.

pub fn remove(&mut self, unique_id: &str)

Remove an entry by unique_id.

pub fn live_count(&self) -> usize

Number of live entries (tree + buffer - deleted).

pub fn is_empty(&self) -> bool

Whether the tree has any live entries.

pub fn find_in_radius( &self, center: &HyperbolicPoint, radius: FixedPoint, ) -> Vec<(String, FixedPoint)>

Find all live entries within hyperbolic radius of center.

pub fn find_nearest( &self, point: &HyperbolicPoint, k: usize, ) -> Vec<(String, FixedPoint)>

Find the k nearest live entries to a point. Returns results sorted by ascending distance.

pub fn farthest_from( &self, center: &HyperbolicPoint, ) -> Option<(String, FixedPoint)>

The live entry whose hyperbolic distance from center is greatest, as (unique_id, distance), or None if there are no live entries.

Linear in the number of live entries (tree + buffer). Callers use this to recompute a bucket’s effective pruning radius exactly after the farthest node is removed, so the bound shrinks back under churn rather than staying permanently inflated by a since-deleted outlier.

Trait Implementations

impl Clone for VPTree

fn clone(&self) -> VPTree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for VPTree

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

Formats the value using the given formatter.