Struct SheetIndex 

pub struct SheetIndex { /* private fields */ }

Sheet-level sparse index for efficient range queries on vertex positions.

Why SheetIndex with interval trees?

While cell_to_vertex: HashMap<CellRef, VertexId> provides O(1) exact lookups, structural operations (insert/delete rows/columns) need to find ALL vertices in a given range, which would require O(n) full scans of the hash map.

Performance comparison:

Operation	Hash map only	With SheetIndex
Insert 100 rows at row 20,000	O(total cells)	O(log n + k)*
Delete columns B:D	O(total cells)	O(log n + k)
Viewport query (visible cells)	O(total cells)	O(log n + k)

*where n = number of indexed vertices, k = vertices actually affected

Memory efficiency:

• Each interval is just 2×u32 + Vec pointer
• Spreadsheets are extremely sparse (1M row sheet typically has <10K cells)
• Point intervals (single cells) are the common case
• Trees stay small and cache-friendly

Future benefits:

1. Virtual scrolling - fetch viewport cells in microseconds
2. Lazy evaluation - mark row blocks dirty without scanning
3. Concurrent reads - trees are read-mostly, perfect for RwLock
4. Minimal undo/redo - know exactly which vertices were touched

Implementations

impl SheetIndex

pub fn new() -> Self

Create a new empty sheet index

pub fn build_from_sorted(&mut self, items: &[(PackedCoord, VertexId)])

Fast path build from sorted coordinates. Assumes items are row-major sorted.

pub fn add_vertex(&mut self, coord: PackedCoord, vertex_id: VertexId)

Add a vertex at the given coordinate to the index.

Complexity

O(log n) where n is the number of vertices in the index

pub fn add_vertices_batch(&mut self, items: &[(PackedCoord, VertexId)])

Add many vertices in a single pass. Assumes coords belong to same sheet index.

pub fn remove_vertex(&mut self, coord: PackedCoord, vertex_id: VertexId)

Remove a vertex from the index.

Complexity

O(log n) where n is the number of vertices in the index

pub fn update_vertex( &mut self, old_coord: PackedCoord, new_coord: PackedCoord, vertex_id: VertexId, )

Update a vertex’s position in the index (move operation).

Complexity

O(log n) for removal + O(log n) for insertion = O(log n)

pub fn vertices_in_row_range(&self, start: u32, end: u32) -> Vec<VertexId>

Query all vertices in the given row range.

Complexity

O(log n + k) where k is the number of vertices in the range

pub fn vertices_in_col_range(&self, start: u32, end: u32) -> Vec<VertexId>

Query all vertices in the given column range.

Complexity

O(log n + k) where k is the number of vertices in the range

pub fn vertices_in_rect( &self, start_row: u32, end_row: u32, start_col: u32, end_col: u32, ) -> Vec<VertexId>

Query all vertices in a rectangular range.

Complexity

O(log n + k) where k is the number of vertices in the range

pub fn len(&self) -> usize

Get the total number of indexed vertices (may count duplicates if vertex appears at multiple positions).

pub fn is_empty(&self) -> bool

Check if the index is empty.

pub fn clear(&mut self)

Clear all entries from the index.

Trait Implementations

impl Debug for SheetIndex

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

Formats the value using the given formatter.

impl Default for SheetIndex

fn default() -> SheetIndex

Returns the “default value” for a type.