Struct VariableHeightsFenwick 

pub struct VariableHeightsFenwick { /* private fields */ }

Variable height tracker using Fenwick tree for O(log n) prefix sum queries.

This enables efficient scroll offset to item index mapping for virtualized lists with variable height items.

Operations

Operation	Time
find_item_at_offset	O(log n)
offset_of_item	O(log n)
set_height	O(log n)
total_height	O(log n)

Invariants

1. tree.prefix(i) == sum of heights [0..=i]
2. find_item_at_offset(offset) returns largest i where prefix(i-1) < offset
3. Heights are u32 internally (u16 input widened for large lists)

Implementations

impl VariableHeightsFenwick

pub fn new(default_height: u16, capacity: usize) -> Self

Create a new height tracker with given default height and initial capacity.

pub fn from_heights(heights: &[u16], default_height: u16) -> Self

Create from a slice of heights.

pub fn len(&self) -> usize

Number of items tracked.

pub fn is_empty(&self) -> bool

Whether tracking is empty.

pub fn default_height(&self) -> u16

Get the default height for unmeasured items.

pub fn get(&self, idx: usize) -> u16

Get height of a specific item. O(log n).

pub fn set(&mut self, idx: usize, height: u16)

Set height of a specific item. O(log n).

pub fn offset_of_item(&self, idx: usize) -> u32

Get the y-offset (in pixels/rows) of an item. O(log n).

Returns the sum of heights of all items before idx.

pub fn find_item_at_offset(&self, offset: u32) -> usize

Find the item index at a given scroll offset. O(log n).

Returns the index of the item that occupies the given offset. If offset is beyond all items, returns self.len.

Item i occupies offsets [offset_of_item(i), offset_of_item(i+1)).

pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize

Count how many items fit within a viewport starting at start_idx. O(log n).

Returns the number of items that fit completely within viewport_height.

pub fn total_height(&self) -> u32

Get total height of all items. O(log n).

pub fn resize(&mut self, new_len: usize)

Resize the tracker to accommodate new_len items.

New items are initialized with default height.

pub fn clear(&mut self)

Clear all height data.

pub fn rebuild(&mut self, heights: &[u16])

Rebuild from a fresh set of heights.

Trait Implementations

impl Clone for VariableHeightsFenwick

fn clone(&self) -> VariableHeightsFenwick

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for VariableHeightsFenwick

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

Formats the value using the given formatter.

impl Default for VariableHeightsFenwick

fn default() -> Self

Returns the “default value” for a type.