facett-grid/src/viewport.rs
//! **Virtualization math** — the part that makes a million-row grid scroll at
//! 60 fps. Rows are uniform-height, so the visible row window is pure arithmetic:
//! `first = floor(scroll_y / row_h)`, `count = ceil(viewport_h / row_h) + 1`.
//! Computing it is **O(visible)**, independent of the total row count — see the
//! timed test in `tests/perf.rs`.
//!
//! Columns have **variable** widths but there are few of them (tens, not
//! millions), so a prefix-sum (`x_starts`) gives each column's x in O(cols) and a
//! binary search finds the first visible column. Pinned leading columns are drawn
//! at a fixed x (they don't scroll horizontally).
/// The slice of rows currently on screen — `[first, first+count)`, clamped to
/// `total`. `y_of_first` is the pixel y (in content space) of `first`'s top, so
/// the caller paints from there without a per-row layout pass.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct RowWindow {
pub first: usize,
pub count: usize,
}
impl RowWindow {
pub fn range(self) -> std::ops::Range<usize> {
self.first..(self.first + self.count)
}
pub fn contains(self, i: usize) -> bool {
i >= self.first && i < self.first + self.count
}
}
/// Visible row window for a vertical scroll position. `overscan` extra rows above
/// and below avoid blank edges during fast scroll. All arithmetic, no allocation
/// — the core O(visible) guarantee.
pub fn row_window(scroll_y: f32, viewport_h: f32, row_h: f32, total: usize, overscan: usize) -> RowWindow {
if total == 0 || row_h <= 0.0 || viewport_h <= 0.0 {
return RowWindow { first: 0, count: 0 };
}
let raw_first = (scroll_y / row_h).floor() as i64;
let first = raw_first.saturating_sub(overscan as i64).max(0) as usize;
let first = first.min(total.saturating_sub(1));
let visible = (viewport_h / row_h).ceil() as usize + 1 + overscan * 2;
let count = visible.min(total - first);
RowWindow { first, count }
}
/// Prefix sums of column widths → `x_starts[i]` is the left edge of column `i` in
/// content space (and `x_starts[ncols]` is the total width). O(cols).
pub fn column_x_starts(widths: &[f32]) -> Vec<f32> {
let mut xs = Vec::with_capacity(widths.len() + 1);
let mut acc = 0.0;
xs.push(0.0);
for &w in widths {
acc += w;
xs.push(acc);
}
xs
}
/// The visible (scrolling) column range given a horizontal scroll offset and the
/// width available for the scrolling area (i.e. after pinned columns). `pinned`
/// leading columns are always drawn, so the search starts at `pinned`. Returns
/// `[first, last)` over the scrolling columns.
pub fn column_window(
x_starts: &[f32],
scroll_x: f32,
avail_w: f32,
pinned: usize,
) -> std::ops::Range<usize> {
let ncols = x_starts.len().saturating_sub(1);
if ncols == 0 || pinned >= ncols {
return pinned..ncols;
}
// Pinned columns occupy [0, pinned); their cumulative width is the left inset.
let pinned_w = x_starts[pinned] - x_starts[0];
let view_lo = scroll_x + pinned_w; // content-x of the scroll viewport's left
let view_hi = view_lo + (avail_w - pinned_w).max(0.0);
// first scrolling col whose right edge > view_lo
let mut first = pinned;
while first < ncols && x_starts[first + 1] <= view_lo {
first += 1;
}
// last scrolling col whose left edge < view_hi
let mut last = first;
while last < ncols && x_starts[last] < view_hi {
last += 1;
}
first..last.max(first)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn row_window_is_the_expected_slice() {
// 1_000_000 rows, 20px each, a 400px viewport scrolled to y=10_000.
let w = row_window(10_000.0, 400.0, 20.0, 1_000_000, 0);
assert_eq!(w.first, 500, "10000/20 = 500");
// 400/20 = 20 visible + 1 partial = 21
assert_eq!(w.count, 21);
assert!(w.contains(500) && w.contains(520) && !w.contains(521));
}
#[test]
fn row_window_overscan_and_clamp() {
let w = row_window(0.0, 100.0, 20.0, 3, 5);
// overscan can't go below 0, and count clamps to the 3 real rows.
assert_eq!(w.first, 0);
assert_eq!(w.count, 3);
}
#[test]
fn row_window_near_end_clamps_count() {
let w = row_window(19_980.0, 400.0, 20.0, 1000, 0);
// 19980/20 = 999 → only 1 row left.
assert_eq!(w.first, 999);
assert_eq!(w.count, 1);
}
#[test]
fn empty_is_empty() {
assert_eq!(row_window(0.0, 400.0, 20.0, 0, 2), RowWindow { first: 0, count: 0 });
}
#[test]
fn x_starts_are_prefix_sums() {
let xs = column_x_starts(&[50.0, 80.0, 120.0]);
assert_eq!(xs, vec![0.0, 50.0, 130.0, 250.0]);
}
#[test]
fn column_window_finds_visible_scrolling_cols() {
// 1 pinned (50px) + scrolling cols of 100px each, total 6 cols.
let widths = vec![50.0, 100.0, 100.0, 100.0, 100.0, 100.0];
let xs = column_x_starts(&widths);
// viewport 250px wide after the 50px pin = 200px scrollable; scrolled 0.
let r = column_window(&xs, 0.0, 250.0, 1);
// pinned_w=50, view_lo=50, view_hi=50+200=250 → cols 1,2 (starts 50,150 <250)
assert_eq!(r, 1..3);
// scroll right by 100 → view_lo=150, view_hi=350. col 1 ends exactly at
// 150 (not strictly > view_lo) so it's scrolled off; first visible is col 2.
let r2 = column_window(&xs, 100.0, 250.0, 1);
assert_eq!(r2.start, 2);
assert!(r2.end >= 4);
}
}