pub struct VariableHeightsFenwick { /* private fields */ }Expand description
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
- Internal prefix sums are exact u64 sums of u16 item heights.
- Inverse lookup searches these monotone sums without allocating.
- Public u32 offsets and totals saturate at u32::MAX; internal layout continues to use exact offsets beyond that boundary.
Implementations§
Source§impl VariableHeightsFenwick
impl VariableHeightsFenwick
Sourcepub fn new(default_height: u16, capacity: usize) -> Self
pub fn new(default_height: u16, capacity: usize) -> Self
Create a new height tracker with given default height and initial capacity.
Sourcepub fn from_heights(heights: &[u16], default_height: u16) -> Self
pub fn from_heights(heights: &[u16], default_height: u16) -> Self
Create from a slice of heights (all of them count as measured).
Sourcepub fn set_categories(&mut self, categories: impl IntoIterator<Item = usize>)
pub fn set_categories(&mut self, categories: impl IntoIterator<Item = usize>)
Assign category IDs to tracked slots and update unmeasured slot heights to match their category’s current fill height.
Sourcepub fn invalidate(&mut self, idx: usize)
pub fn invalidate(&mut self, idx: usize)
Clear the measured bit for idx and reset its tracked height to the
current fill height (default or predicted for its category).
Sourcepub fn take_last_violation(&mut self) -> bool
pub fn take_last_violation(&mut self) -> bool
Take and clear the pending violation flag accumulated from recent measurements.
Sourcepub fn with_predictor(self, config: PredictorConfig) -> Self
pub fn with_predictor(self, config: PredictorConfig) -> Self
Attach a Bayesian height predictor (HeightPredictor).
Unmeasured slots then hold the predictor’s current point prediction
instead of default_height; every set trains the model
and, whenever the rounded prediction moves by a whole row, the
unmeasured slots are refilled so offsets and the total height track
the rows measured so far instead of a constant guess. A refill costs
O(u log n) for u unmeasured slots and a converging posterior triggers
it only a handful of times.
Sourcepub fn predictor(&self) -> Option<&HeightPredictor>
pub fn predictor(&self) -> Option<&HeightPredictor>
The attached height predictor, if any.
Sourcepub fn predicted_height(&self) -> u16
pub fn predicted_height(&self) -> u16
Height every unmeasured slot currently holds (the prediction when a predictor is attached, otherwise the default height).
Sourcepub fn unmeasured_count(&self) -> usize
pub fn unmeasured_count(&self) -> usize
Number of slots that have not been measured through set.
Sourcepub fn is_measured(&self, idx: usize) -> bool
pub fn is_measured(&self, idx: usize) -> bool
Whether slot idx holds a measured height.
Sourcepub fn default_height(&self) -> u16
pub fn default_height(&self) -> u16
Get the default height for unmeasured items.
Sourcepub fn get(&self, idx: usize) -> u16
pub fn get(&self, idx: usize) -> u16
Get height of a specific item. O(log n).
Items beyond the tracked length report the fill height (the prediction when a predictor is attached).
Sourcepub fn set(&mut self, idx: usize, height: u16)
pub fn set(&mut self, idx: usize, height: u16)
Set (measure) the height of a specific item. O(log n), plus a refill of the unmeasured slots when an attached predictor’s rounded prediction changes.
Sourcepub fn refresh_category_predictions(&mut self)
pub fn refresh_category_predictions(&mut self)
Refresh unmeasured slot heights from the predictor’s current per-category point predictions in a single O(n) pass.
Sourcepub fn set_in_category(&mut self, idx: usize, height: u16, category: usize)
pub fn set_in_category(&mut self, idx: usize, height: u16, category: usize)
Measure an item and train its category’s predictor. Unmeasured slots in the same category track that category’s rounded posterior prediction.
Sourcepub fn offset_of_item(&self, idx: usize) -> u32
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, saturated at
u32::MAX. Indices beyond the tracked length return the total height.
Sourcepub fn find_item_at_offset(&self, offset: u32) -> usize
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 the interval between its exact prefix sums, including
when the total exceeds u32::MAX. Offset zero returns item zero even
if leading items have zero height. Saturated public offsets above the
u32 boundary cannot be used to address those later items.
Sourcepub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize
pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize
Count how many items are visible within a viewport starting at start_idx. O(log n).
Visibility here means partially or fully visible. The first partially visible trailing item is counted.
Returns at least 1 when start_idx < len and viewport_height > 0,
even if the first item is taller than the viewport.
Sourcepub fn total_height(&self) -> u32
pub fn total_height(&self) -> u32
Get total height of all items, saturated at u32::MAX. O(log n).
Sourcepub fn resize(&mut self, new_len: usize)
pub fn resize(&mut self, new_len: usize)
Resize the tracker to accommodate new_len items.
New items are initialized with the fill height (the default height, or the current prediction when a predictor is attached).
Sourcepub fn drop_front(&mut self, n: usize)
pub fn drop_front(&mut self, n: usize)
Drop the first n entries (the list trimmed its front): remaining
heights and their measured flags shift down by n; an attached
predictor keeps what it learned.