Struct IntervalTree 

pub struct IntervalTree<T: Clone + Eq + Hash> { /* private fields */ }

Custom interval tree optimized for spreadsheet cell indexing.

Design decisions:

1. Point intervals are the common case - Most cells are single points [r,r] or [c,c]
2. Sparse data - Even million-row sheets typically have <10K cells
3. Batch updates - During shifts, we update many intervals at once
4. Small value sets - Each interval maps to a small set of VertexIds

Implementation:

Uses an augmented BST where each node stores:

• Interval [low, high]
• Max endpoint in subtree (for efficient pruning)
• Value set (HashSet)

This is simpler than generic interval trees because we optimize for our specific use case.

Implementations

impl<T: Clone + Eq + Hash> IntervalTree<T>

pub fn new() -> Self

Create a new empty interval tree

pub fn insert(&mut self, low: u32, high: u32, value: T)

Insert a value for the given interval [low, high]

pub fn remove(&mut self, low: u32, high: u32, value: &T) -> bool

Remove a value from the interval [low, high]

pub fn query( &self, query_low: u32, query_high: u32, ) -> Vec<(u32, u32, HashSet<T>)>

Query all intervals that overlap with [query_low, query_high]

pub fn get_mut(&mut self, low: u32, high: u32) -> Option<&mut HashSet<T>>

Get mutable reference to values for an exact interval match

pub fn is_empty(&self) -> bool

Check if the tree is empty

pub fn len(&self) -> usize

Get the number of intervals in the tree

pub fn clear(&mut self)

Clear all intervals from the tree

pub fn entry(&mut self, low: u32, high: u32) -> Entry<'_, T>

Entry API for convenient insert-or-update operations

pub fn bulk_build_points(&mut self, items: Vec<(u32, HashSet<T>)>)

Bulk build optimization for a collection of point intervals [x,x]. Expects (low == high) for all items. Existing content is discarded if tree is empty; if not empty, falls back to incremental inserts.

Trait Implementations

impl<T: Clone + Clone + Eq + Hash> Clone for IntervalTree<T>

fn clone(&self) -> IntervalTree<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Clone + Eq + Hash> Debug for IntervalTree<T>

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

Formats the value using the given formatter.

impl<T: Clone + Eq + Hash> Default for IntervalTree<T>

fn default() -> Self

Returns the “default value” for a type.