Struct FenwickTree

pub struct FenwickTree { /* private fields */ }

Prefix-sum index used to map vertical offsets to paragraph indices.

FenwickTree::lower_bound assumes finite, non-negative values so prefix sums are monotonic; construction does not validate this invariant.

Examples

use ailloli_ui_editor::layout::FenwickTree;
let tree = FenwickTree::from_values(&[10.0, 20.0, 30.0]);
assert_eq!(tree.prefix_sum(2), 30.0);

Implementations

impl FenwickTree

Builds and queries prefix sums.

pub fn from_values(values: &[f32]) -> Self

Builds a tree in O(n log n) from copied values.

An empty slice is valid and produces a zero-length index.

Examples

use ailloli_ui_editor::layout::FenwickTree;
assert_eq!(FenwickTree::from_values(&[]).prefix_sum(9), 0.0);
assert_eq!(FenwickTree::from_values(&[2.0, 3.0]).prefix_sum(2), 5.0);

pub fn prefix_sum(&self, end: usize) -> f32

Returns the sum of values before end.

end is clamped to the number of values. Queries take O(log n) time.

Examples

use ailloli_ui_editor::layout::FenwickTree;
let tree = FenwickTree::from_values(&[2.0, 3.0, 5.0]);
assert_eq!(tree.prefix_sum(0), 0.0);
assert_eq!(tree.prefix_sum(usize::MAX), 10.0);

pub fn lower_bound(&self, target: f32) -> usize

Locates the zero-based value whose cumulative end reaches target.

Non-positive targets return zero. A target greater than the total sum returns the number of values. Equality belongs to the preceding value, which matches viewport offsets on a paragraph’s lower edge. Queries take O(log n) time and require non-negative finite values for meaningful ordering.

Examples

use ailloli_ui_editor::layout::FenwickTree;
let tree = FenwickTree::from_values(&[10.0, 20.0, 30.0]);
assert_eq!(tree.lower_bound(0.0), 0);
assert_eq!(tree.lower_bound(10.0), 0);
assert_eq!(tree.lower_bound(10.5), 1);
assert_eq!(tree.lower_bound(60.5), 3);

Trait Implementations

impl Clone for FenwickTree

fn clone(&self) -> FenwickTree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for FenwickTree

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

Formats the value using the given formatter.

impl PartialEq for FenwickTree

fn eq(&self, other: &FenwickTree) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for FenwickTree