#[derive(Debug)]
pub(crate) struct PrefixSumOffsets {
heights: Vec<f32>,
measured: Vec<bool>,
gap: f32,
top_inset: f32,
bottom_inset: f32,
estimated: f32,
offsets: Vec<f32>,
dirty_from: Option<usize>,
}
impl PrefixSumOffsets {
pub(crate) fn new(
rows: usize,
estimated: f32,
gap: f32,
top_inset: f32,
bottom_inset: f32,
) -> Self {
Self {
heights: vec![estimated; rows],
measured: vec![false; rows],
gap,
top_inset,
bottom_inset,
estimated,
offsets: vec![0.0; rows + 1],
dirty_from: Some(0),
}
}
pub(crate) fn rows(&self) -> usize {
self.heights.len()
}
pub(crate) fn is_measured(&self, r: usize) -> bool {
self.measured.get(r).copied().unwrap_or(false)
}
pub(crate) fn reset(&mut self, rows: usize) {
self.heights = vec![self.estimated; rows];
self.measured = vec![false; rows];
self.offsets = vec![0.0; rows + 1];
self.dirty_from = Some(0);
}
pub(crate) fn resize(&mut self, rows: usize) {
let old = self.heights.len();
if rows == old {
return;
}
self.heights.resize(rows, self.estimated);
self.measured.resize(rows, false);
self.offsets.resize(rows + 1, 0.0);
self.mark_dirty(old.min(rows));
}
fn mark_dirty(&mut self, from: usize) {
self.dirty_from = Some(self.dirty_from.map_or(from, |d| d.min(from)));
}
pub(crate) fn set_row_height(&mut self, r: usize, h: f32) -> f32 {
if r >= self.heights.len() {
return 0.0;
}
let old = self.heights[r];
let delta = h - old;
self.measured[r] = true;
if delta.abs() > 0.01 {
self.heights[r] = h;
self.mark_dirty(r);
delta
} else {
0.0
}
}
pub(crate) fn invalidate(&mut self, start: usize, end: usize) {
let end = end.min(self.heights.len());
if start >= end {
return;
}
for r in start..end {
self.heights[r] = self.estimated;
self.measured[r] = false;
}
self.mark_dirty(start);
}
fn rebuild(&mut self) {
let Some(from) = self.dirty_from.take() else {
return;
};
let rows = self.heights.len();
if self.offsets.len() != rows + 1 {
self.offsets.resize(rows + 1, 0.0);
}
if rows == 0 {
self.offsets[0] = 0.0;
return;
}
let from = from.min(rows);
let mut acc = if from == 0 {
self.top_inset
} else {
self.offsets[from - 1] + self.heights[from - 1] + self.gap
};
for r in from..rows {
self.offsets[r] = acc;
acc += self.heights[r] + self.gap;
}
self.offsets[rows] = acc - self.gap + self.bottom_inset;
}
pub(crate) fn total(&mut self) -> f32 {
self.rebuild();
let rows = self.heights.len();
if rows == 0 { 0.0 } else { self.offsets[rows] }
}
pub(crate) fn row_top(&mut self, r: usize) -> f32 {
self.rebuild();
let rows = self.heights.len();
if rows == 0 {
return self.top_inset;
}
self.offsets[r.min(rows)]
}
pub(crate) fn row_height(&self, r: usize) -> f32 {
self.heights.get(r).copied().unwrap_or(self.estimated)
}
pub(crate) fn row_at(&mut self, y: f32) -> usize {
self.rebuild();
let rows = self.heights.len();
if rows == 0 {
return 0;
}
if self.offsets[rows - 1] <= self.offsets[0] && self.heights[rows - 1] <= 0.0 {
return 0;
}
let pp = self.offsets[..rows].partition_point(|&o| o <= y);
pp.saturating_sub(1).min(rows - 1)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn estimated_offsets_and_total() {
let mut p = PrefixSumOffsets::new(4, 50.0, 8.0, 0.0, 0.0);
assert_eq!(p.row_top(0), 0.0);
assert_eq!(p.row_top(1), 58.0);
assert_eq!(p.row_top(2), 116.0);
assert_eq!(p.row_top(3), 174.0);
assert_eq!(p.total(), 224.0);
}
#[test]
fn insets_offset_the_content() {
let mut p = PrefixSumOffsets::new(2, 50.0, 8.0, 10.0, 6.0);
assert_eq!(p.row_top(0), 10.0);
assert_eq!(p.row_top(1), 68.0);
assert_eq!(p.total(), 124.0);
}
#[test]
fn set_row_height_returns_delta_and_shifts_following() {
let mut p = PrefixSumOffsets::new(3, 50.0, 8.0, 0.0, 0.0);
let delta = p.set_row_height(0, 90.0);
assert!((delta - 40.0).abs() < 0.01);
assert_eq!(p.row_top(1), 98.0); assert_eq!(p.row_top(2), 156.0); assert_eq!(p.set_row_height(0, 90.0), 0.0);
}
#[test]
fn row_at_maps_y_to_row() {
let mut p = PrefixSumOffsets::new(4, 50.0, 8.0, 0.0, 0.0);
assert_eq!(p.row_at(0.0), 0);
assert_eq!(p.row_at(57.0), 0);
assert_eq!(p.row_at(58.0), 1);
assert_eq!(p.row_at(200.0), 3);
assert_eq!(p.row_at(99999.0), 3); }
#[test]
fn resize_preserves_measured_heights() {
let mut p = PrefixSumOffsets::new(2, 50.0, 8.0, 0.0, 0.0);
p.set_row_height(0, 90.0);
p.resize(4); assert_eq!(p.rows(), 4);
assert_eq!(p.row_top(1), 98.0); assert!(p.is_measured(0));
assert!(!p.is_measured(2));
}
#[test]
fn resize_grow_uses_gap_not_bottom_inset_for_appended_rows() {
let mut p = PrefixSumOffsets::new(2, 50.0, 8.0, 0.0, 100.0);
let _ = p.total(); p.resize(4);
assert_eq!(p.row_top(2), 116.0);
assert_eq!(p.row_top(3), 174.0);
assert_eq!(p.total(), 174.0 + 50.0 + 100.0);
}
#[test]
fn invalidate_resets_to_estimate() {
let mut p = PrefixSumOffsets::new(3, 50.0, 8.0, 0.0, 0.0);
p.set_row_height(0, 90.0);
p.invalidate(0, 1);
assert!(!p.is_measured(0));
assert_eq!(p.row_top(1), 58.0); }
}
#[cfg(test)]
mod proptests {
use super::*;
use proptest::prelude::*;
fn arb_height() -> impl Strategy<Value = f32> {
prop_oneof![
4 => Just(0.0_f32),
1 => Just(1.0_f32),
3 => 0.5f32..400.0f32,
]
}
fn arb_heights(max_len: usize) -> impl Strategy<Value = Vec<f32>> {
prop::collection::vec(arb_height(), 0..=max_len)
}
fn arb_zero_run(max_len: usize) -> impl Strategy<Value = Vec<f32>> {
prop::collection::vec(Just(0.0_f32), 0..=max_len)
}
fn arb_positive_height() -> impl Strategy<Value = f32> {
0.5f32..400.0f32
}
fn arb_gap() -> impl Strategy<Value = f32> {
prop_oneof![3 => Just(0.0_f32), 1 => 0.5f32..20.0f32]
}
fn arb_inset() -> impl Strategy<Value = f32> {
prop_oneof![1 => Just(0.0_f32), 1 => 0.0f32..50.0f32]
}
fn arb_y() -> impl Strategy<Value = f32> {
prop_oneof![
1 => Just(0.0_f32),
1 => -500.0f32..0.0f32,
1 => 0.0f32..2000.0f32,
1 => Just(100_000.0_f32),
]
}
fn linear_row_top(heights: &[f32], gap: f32, top_inset: f32, row: usize) -> f32 {
let mut acc = top_inset;
for h in &heights[..row.min(heights.len())] {
acc += h + gap;
}
acc
}
fn expected_total(heights: &[f32], gap: f32, top_inset: f32, bottom_inset: f32) -> f32 {
let rows = heights.len();
if rows == 0 {
return 0.0;
}
let sum_heights: f32 = heights.iter().sum();
top_inset + sum_heights + (rows as f32 - 1.0) * gap + bottom_inset
}
fn build(heights: &[f32], gap: f32, top_inset: f32, bottom_inset: f32) -> PrefixSumOffsets {
let mut p = PrefixSumOffsets::new(heights.len(), 0.0, gap, top_inset, bottom_inset);
p.heights = heights.to_vec();
p.measured = vec![true; heights.len()];
p.dirty_from = Some(0);
p
}
proptest! {
#[test]
fn row_top_is_monotonically_non_decreasing_across_the_row_index(
heights in arb_heights(40),
gap in arb_gap(),
top_inset in arb_inset(),
bottom_inset in arb_inset(),
) {
let mut p = build(&heights, gap, top_inset, bottom_inset);
let rows = heights.len();
for i in 0..rows.saturating_sub(1) {
let a = p.row_top(i);
let b = p.row_top(i + 1);
prop_assert!(
a <= b,
"row_top regressed: row_top({})={} > row_top({})={} (heights={:?}, gap={})",
i, a, i + 1, b, heights, gap,
);
}
if rows > 0 {
let last_top = p.row_top(rows - 1);
let total = p.total();
let tol = 1e-4 * total.abs().max(last_top.abs()).max(1.0);
prop_assert!(
total >= last_top - tol,
"total()={} fell below the last row's own top {} by more than {} (heights={:?}, gap={})",
total, last_top, tol, heights, gap,
);
}
}
}
proptest! {
#[test]
fn row_at_returns_an_in_range_index_for_every_finite_y(
heights in arb_heights(40),
gap in arb_gap(),
y in arb_y(),
) {
let mut p = build(&heights, gap, 0.0, 0.0);
let rows = heights.len();
let r = p.row_at(y);
if rows == 0 {
prop_assert_eq!(r, 0, "row_at on an empty table must be 0, got {}", r);
} else {
prop_assert!(
r < rows,
"row_at({}) = {} is out of range for {} rows (heights={:?}, gap={})",
y, r, rows, heights, gap,
);
}
}
}
proptest! {
#[test]
fn row_at_is_monotone_non_decreasing_in_y(
heights in arb_heights(40),
gap in arb_gap(),
y1 in arb_y(),
y2 in arb_y(),
) {
let (lo, hi) = if y1 <= y2 { (y1, y2) } else { (y2, y1) };
let mut p = build(&heights, gap, 0.0, 0.0);
let r_lo = p.row_at(lo);
let r_hi = p.row_at(hi);
prop_assert!(
r_lo <= r_hi,
"row_at({}) = {} > row_at({}) = {}, not monotone (heights={:?}, gap={})",
lo, r_lo, hi, r_hi, heights, gap,
);
}
}
proptest! {
#![proptest_config(ProptestConfig { cases: 512, ..ProptestConfig::default() })]
#[test]
fn row_at_at_a_boundary_lands_on_real_content_not_a_zero_height_row(
leading_height in arb_positive_height(),
zero_run in 1usize..=6,
trailing_height in arb_positive_height(),
top_inset in prop_oneof![Just(0.0f32), 0.5f32..40.0f32],
) {
let mut heights = vec![leading_height];
heights.extend(std::iter::repeat_n(0.0f32, zero_run));
heights.push(trailing_height);
let last = heights.len() - 1;
let mut p = build(&heights, 0.0, top_inset, 0.0);
let boundary = p.row_top(last);
let got = p.row_at(boundary);
prop_assert_eq!(
got, last,
"row_at({}) = {} landed on a zero-height row; expected the \
trailing real row {} (heights={:?}, top_inset={})",
boundary, got, last, heights, top_inset,
);
prop_assert!(
p.row_height(got) > 0.0,
"row_at({}) = {} resolved to a row of height {}, which owns no \
span (heights={:?}, top_inset={})",
boundary, got, p.row_height(got), heights, top_inset,
);
}
}
proptest! {
#[test]
fn row_at_matches_a_linear_scan_oracle_inside_a_positive_band(
zeros_before in arb_zero_run(15),
target_height in arb_positive_height(),
zeros_after in arb_zero_run(15),
gap in arb_gap(),
frac in 0.001f32..0.999f32,
) {
let target_index = zeros_before.len();
let mut heights = zeros_before.clone();
heights.push(target_height);
heights.extend(zeros_after.iter().copied());
let mut p = build(&heights, gap, 0.0, 0.0);
let target_top = linear_row_top(&heights, gap, 0.0, target_index);
let y = target_top + target_height * frac;
let r = p.row_at(y);
let band_end = target_top + target_height;
prop_assert_eq!(
r, target_index,
"y={} sits strictly inside row {}'s band [{}, {}) but row_at returned {} \
(heights={:?}, gap={})",
y, target_index, target_top, band_end, r, heights, gap,
);
}
}
proptest! {
#[test]
fn total_conserves_the_sum_of_heights_and_gaps_and_insets(
heights in arb_heights(40),
gap in arb_gap(),
top_inset in arb_inset(),
bottom_inset in arb_inset(),
) {
let mut p = build(&heights, gap, top_inset, bottom_inset);
let expected = expected_total(&heights, gap, top_inset, bottom_inset);
let actual = p.total();
prop_assert!(
(actual - expected).abs() < 0.05,
"total()={} but the direct sum of heights+gaps+insets is {} \
(heights={:?}, gap={}, top_inset={}, bottom_inset={})",
actual, expected, heights, gap, top_inset, bottom_inset,
);
}
}
}