Skip to main content

VariableHeightsFenwick

Struct VariableHeightsFenwick 

Source
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

OperationTime
find_item_at_offsetO(log n)
offset_of_itemO(log n)
set_heightO(log n)
total_heightO(log n)

§Invariants

  1. Internal prefix sums are exact u64 sums of u16 item heights.
  2. Inverse lookup searches these monotone sums without allocating.
  3. Public u32 offsets and totals saturate at u32::MAX; internal layout continues to use exact offsets beyond that boundary.

Implementations§

Source§

impl VariableHeightsFenwick

Source

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

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

Source

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

Create from a slice of heights (all of them count as measured).

Source

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.

Source

pub fn predictor(&self) -> Option<&HeightPredictor>

The attached height predictor, if any.

Source

pub fn predicted_height(&self) -> u16

Height every unmeasured slot currently holds (the prediction when a predictor is attached, otherwise the default height).

Source

pub fn unmeasured_count(&self) -> usize

Number of slots that have not been measured through set.

Source

pub fn is_measured(&self, idx: usize) -> bool

Whether slot idx holds a measured height.

Source

pub fn len(&self) -> usize

Number of items tracked.

Source

pub fn is_empty(&self) -> bool

Whether tracking is empty.

Source

pub fn default_height(&self) -> u16

Get the default height for unmeasured items.

Source

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).

Source

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.

Source

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.

Source

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.

Source

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.

Source

pub fn total_height(&self) -> u32

Get total height of all items, saturated at u32::MAX. O(log n).

Source

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).

Source

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.

Source

pub fn clear(&mut self)

Clear all height data (an attached predictor keeps what it learned).

Source

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

Rebuild from a fresh set of heights; all of them count as measured and train an attached predictor.

Trait Implementations§

Source§

impl Clone for VariableHeightsFenwick

Source§

fn clone(&self) -> VariableHeightsFenwick

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

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

Performs copy-assignment from source. Read more
Source§

impl Debug for VariableHeightsFenwick

Source§

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

Formats the value using the given formatter. Read more
Source§

impl Default for VariableHeightsFenwick

Source§

fn default() -> Self

Returns the “default value” for a type. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<ST, DT> CastableFrom<ST, Initialized, Initialized> for DT
where ST: ?Sized, DT: ?Sized,

Source§

impl<ST, DT> CastableFrom<ST, Uninit, Uninit> for DT
where ST: ?Sized, DT: ?Sized,

Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T> Instrument for T

Source§

fn instrument(self, span: Span) -> Instrumented<Self> ⓘ

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
Source§

fn in_current_span(self) -> Instrumented<Self> ⓘ

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> Read<Exclusive, BecauseExclusive> for T
where T: ?Sized,

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<T> WithSubscriber for T

Source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self> ⓘ
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
Source§

fn with_current_subscriber(self) -> WithDispatch<Self> ⓘ

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more