Skip to main content

ftui_widgets/
virtualized.rs

1#![forbid(unsafe_code)]
2
3//! Virtualization primitives for efficient rendering of large content.
4//!
5//! This module provides the foundational types for rendering only visible
6//! portions of large datasets, enabling smooth performance with 100K+ items.
7//!
8//! # Core Types
9//!
10//! - [`Virtualized<T>`] - Generic container with visible range calculation
11//! - [`VirtualizedList`] / [`VirtualizedListState`] - Stateful virtualized list widget
12//! - [`VirtualizedStorage`] - Owned vs external storage abstraction
13//! - [`ItemHeight`] - Three height strategies:
14//!   - [`ItemHeight::Fixed`] — constant height per item (`O(1)` scroll indexing)
15//!   - [`ItemHeight::VariableFenwick`] — default for [`Virtualized::with_variable_heights`] and [`VirtualizedList::variable_heights`] (`O(log n)` prefix-sum offsets via [`crate::fenwick::FenwickTree`], optional per-category Bayesian height prediction via [`crate::height_predictor::HeightPredictor`], and Beta-VOI remeasurement via [`RemeasurePolicy`])
16//!   - [`ItemHeight::Variable`] — legacy [`HeightCache`] LRU cache with linear scan
17//! - [`RemeasurePolicy`] - Beta-posterior Value-of-Information policy scheduling remeasurement checks and emitting `voi_sample` evidence (`source: "virtualized_list"`)
18//!
19//! # Example
20//!
21//! ```ignore
22//! use ftui_widgets::virtualized::{Virtualized, ItemHeight};
23//!
24//! // Create with owned storage
25//! let mut virt: Virtualized<String> = Virtualized::new(10_000);
26//!
27//! // Add items
28//! for i in 0..1000 {
29//!     virt.push(format!("Line {}", i));
30//! }
31//!
32//! // Get visible range for viewport height
33//! let range = virt.visible_range(24);
34//! println!("Visible: {}..{}", range.start, range.end);
35//! ```
36
37use std::cell::Cell as StdCell;
38use std::collections::VecDeque;
39use std::ops::Range;
40use std::time::Duration;
41
42use crate::scrollbar::{Scrollbar, ScrollbarOrientation, ScrollbarState};
43use crate::{StatefulWidget, clear_text_area};
44use ftui_core::geometry::Rect;
45pub use ftui_core::voi::{BetaPosterior, beta_voi};
46use ftui_render::cell::Cell;
47use ftui_render::frame::{Frame, RemeasureRequest};
48use ftui_style::Style;
49
50/// Outcome of a [`RemeasurePolicy`] evaluation when a remeasurement sample is warranted.
51#[derive(Debug, Clone, Copy, PartialEq)]
52pub struct RemeasureDecision {
53    /// Expected variance reduction (Value of Information) at decision time.
54    pub voi: f64,
55    /// Configured sample cost threshold.
56    pub cost: f64,
57}
58
59/// Value-of-Information policy deciding when to remeasure a previously measured
60/// item in a variable-height virtualized list.
61///
62/// The list defaults (`alpha = 1.0`, `beta = 9.0`, `sample_cost = 0.08`,
63/// `min_interval_frames = 6`) are tuned for virtualized row height drift and
64/// are distinct from the runtime's inline auto-height sampler defaults.
65#[derive(Debug, Clone, PartialEq)]
66pub struct RemeasurePolicy {
67    /// Beta posterior over the item height violation probability.
68    pub posterior: BetaPosterior,
69    /// Normalized cost threshold for taking one remeasurement sample.
70    pub sample_cost: f64,
71    /// Minimum frames between consecutive VOI remeasurement samples.
72    pub min_interval_frames: u32,
73    /// Frame index at which a sample was last taken (`u64::MAX` before any sample).
74    pub last_sample_frame: u64,
75}
76
77impl Default for RemeasurePolicy {
78    fn default() -> Self {
79        Self {
80            posterior: BetaPosterior::new(1.0, 9.0),
81            sample_cost: 0.08,
82            min_interval_frames: 6,
83            last_sample_frame: u64::MAX,
84        }
85    }
86}
87
88impl RemeasurePolicy {
89    /// Create a policy with explicit posterior, sample cost, and minimum frame interval.
90    #[must_use]
91    pub const fn new(posterior: BetaPosterior, sample_cost: f64, min_interval_frames: u32) -> Self {
92        Self {
93            posterior,
94            sample_cost,
95            min_interval_frames,
96            last_sample_frame: u64::MAX,
97        }
98    }
99
100    /// Evaluate whether to take a remeasurement sample at `frame_idx` under the
101    /// current posterior, respecting `min_interval_frames`.
102    pub fn should_sample(&mut self, frame_idx: u64) -> Option<RemeasureDecision> {
103        if self.last_sample_frame != u64::MAX
104            && frame_idx.saturating_sub(self.last_sample_frame)
105                < u64::from(self.min_interval_frames)
106        {
107            return None;
108        }
109        let voi = self.posterior.voi();
110        if voi >= self.sample_cost {
111            self.last_sample_frame = frame_idx;
112            Some(RemeasureDecision {
113                voi,
114                cost: self.sample_cost,
115            })
116        } else {
117            None
118        }
119    }
120
121    /// Evaluate whether to remeasure at `frame_idx` and fold `violation_observed`
122    /// into the Beta posterior (`alpha` increments on violation, `beta` on confirmation).
123    pub fn should_remeasure(
124        &mut self,
125        frame_idx: u64,
126        violation_observed: bool,
127    ) -> Option<RemeasureDecision> {
128        let cooldown_ok = self.last_sample_frame == u64::MAX
129            || frame_idx.saturating_sub(self.last_sample_frame)
130                >= u64::from(self.min_interval_frames);
131        let decision = self.should_sample(frame_idx).or_else(|| {
132            if violation_observed && cooldown_ok {
133                self.last_sample_frame = frame_idx;
134                Some(RemeasureDecision {
135                    voi: self.posterior.voi(),
136                    cost: self.sample_cost,
137                })
138            } else {
139                None
140            }
141        });
142        self.observe(violation_observed);
143        decision
144    }
145
146    /// Update the Beta posterior with a Bernoulli observation (`violation_observed = true`
147    /// increments `alpha`, `false` increments `beta`).
148    #[inline]
149    pub fn observe(&mut self, violation_observed: bool) {
150        self.posterior.observe(violation_observed);
151    }
152}
153
154/// A virtualized content container that tracks scroll state and computes visible ranges.
155///
156/// # Design Rationale
157/// - Generic over item type for flexibility
158/// - Supports both owned storage and external data sources
159/// - Computes visible ranges for O(visible) rendering
160/// - Optional overscan for smooth scrolling
161/// - Momentum scrolling support
162#[derive(Debug, Clone)]
163pub struct Virtualized<T> {
164    /// The stored items (or external storage reference).
165    storage: VirtualizedStorage<T>,
166    /// Current scroll offset (in items).
167    scroll_offset: usize,
168    /// Number of visible items (cached from last render).
169    visible_count: StdCell<usize>,
170    /// Overscan: extra items rendered above/below visible.
171    overscan: usize,
172    /// Height calculation strategy.
173    item_height: ItemHeight,
174    /// Whether to auto-scroll on new items.
175    follow_mode: bool,
176    /// Scroll velocity for momentum scrolling.
177    scroll_velocity: f32,
178    /// Optional VOI policy for periodic remeasurement of measured items.
179    remeasure_policy: Option<RemeasurePolicy>,
180}
181
182/// Storage strategy for virtualized items.
183#[derive(Debug, Clone)]
184pub enum VirtualizedStorage<T> {
185    /// Owned vector of items.
186    Owned(VecDeque<T>),
187    /// External storage with known length.
188    /// Note: External fetch is handled at the widget level.
189    External {
190        /// Total number of items available.
191        len: usize,
192        /// Maximum items to keep in local cache.
193        cache_capacity: usize,
194    },
195}
196
197/// Height calculation strategy for items.
198#[derive(Debug, Clone)]
199pub enum ItemHeight {
200    /// All items have fixed height.
201    Fixed(u16),
202    /// Legacy variable-height mode: an LRU cache of measured heights and a
203    /// linear scan per `visible_range`. Kept for callers that want bounded
204    /// memory over a sliding window; new code should use
205    /// [`Virtualized::with_variable_heights`] (Fenwick).
206    Variable(HeightCache),
207    /// Items have variable height with O(log n) scroll-to-index via Fenwick
208    /// tree; the default variable-height strategy.
209    VariableFenwick(VariableHeightsFenwick),
210}
211
212/// LRU cache for measured item heights.
213#[derive(Debug, Clone)]
214pub struct HeightCache {
215    /// Height measurements indexed by (item index - base_offset).
216    cache: Vec<Option<u16>>,
217    /// Offset of the first entry in the cache (cache[0] corresponds to this item index).
218    base_offset: usize,
219    /// Default height for unmeasured items.
220    default_height: u16,
221    /// Maximum entries to cache (for memory bounds).
222    capacity: usize,
223}
224
225impl<T> Virtualized<T> {
226    /// Create a new virtualized container with owned storage.
227    ///
228    /// # Arguments
229    /// * `capacity` - Maximum items to retain in memory.
230    #[must_use]
231    pub fn new(capacity: usize) -> Self {
232        Self {
233            storage: VirtualizedStorage::Owned(VecDeque::with_capacity(capacity.min(1024))),
234            scroll_offset: 0,
235            visible_count: StdCell::new(0),
236            overscan: 2,
237            item_height: ItemHeight::Fixed(1),
238            follow_mode: false,
239            scroll_velocity: 0.0,
240            remeasure_policy: None,
241        }
242    }
243
244    /// Create with external storage reference.
245    #[must_use]
246    pub fn external(len: usize, cache_capacity: usize) -> Self {
247        Self {
248            storage: VirtualizedStorage::External {
249                len,
250                cache_capacity,
251            },
252            scroll_offset: 0,
253            visible_count: StdCell::new(0),
254            overscan: 2,
255            item_height: ItemHeight::Fixed(1),
256            follow_mode: false,
257            scroll_velocity: 0.0,
258            remeasure_policy: None,
259        }
260    }
261
262    /// Attach a Value-of-Information remeasurement policy.
263    #[must_use]
264    pub fn with_remeasure_policy(mut self, policy: RemeasurePolicy) -> Self {
265        self.remeasure_policy = Some(policy);
266        self
267    }
268
269    /// Borrow the attached VOI remeasurement policy, if any.
270    #[must_use]
271    pub fn remeasure_policy(&self) -> Option<&RemeasurePolicy> {
272        self.remeasure_policy.as_ref()
273    }
274
275    /// Mutably borrow the attached VOI remeasurement policy, if any.
276    pub fn remeasure_policy_mut(&mut self) -> Option<&mut RemeasurePolicy> {
277        self.remeasure_policy.as_mut()
278    }
279
280    /// Clear the measured state of item `idx` so its height reverts to the
281    /// unmeasured fill prediction until measured again.
282    pub fn invalidate(&mut self, idx: usize) {
283        match &mut self.item_height {
284            ItemHeight::Fixed(_) => {}
285            ItemHeight::Variable(cache) => cache.invalidate(idx),
286            ItemHeight::VariableFenwick(tracker) => tracker.invalidate(idx),
287        }
288    }
289
290    /// Set item height strategy.
291    #[must_use]
292    pub fn with_item_height(mut self, height: ItemHeight) -> Self {
293        self.item_height = height;
294        self
295    }
296
297    /// Set fixed item height.
298    #[must_use]
299    pub fn with_fixed_height(mut self, height: u16) -> Self {
300        self.item_height = ItemHeight::Fixed(height);
301        self
302    }
303
304    /// Predict the heights of unmeasured items with a Bayesian model instead
305    /// of a constant default (see [`VariableHeightsFenwick::with_predictor`]).
306    ///
307    /// Switches the height strategy to the Fenwick tracker when it is not one
308    /// already (a fixed height becomes the tracker's default; a linear
309    /// [`HeightCache`] is replaced, dropping its cached measurements). Heights
310    /// recorded through [`Virtualized::observe_height`] train the model.
311    #[must_use]
312    pub fn with_height_prediction(mut self, config: PredictorConfig) -> Self {
313        let len = self.len();
314        let current = std::mem::replace(&mut self.item_height, ItemHeight::Fixed(1));
315        self.item_height = ItemHeight::VariableFenwick(match current {
316            ItemHeight::VariableFenwick(tracker) => tracker.with_predictor(config),
317            ItemHeight::Fixed(height) => {
318                VariableHeightsFenwick::new(height.max(1), len).with_predictor(config)
319            }
320            ItemHeight::Variable(cache) => {
321                VariableHeightsFenwick::new(cache.default_height, len).with_predictor(config)
322            }
323        });
324        self
325    }
326
327    /// Alias for [`Self::with_height_prediction`].
328    #[must_use]
329    pub fn with_height_predictor(self, config: PredictorConfig) -> Self {
330        self.with_height_prediction(config)
331    }
332
333    /// Record the measured height of item `idx`.
334    ///
335    /// A no-op for the fixed-height strategy. With a predictor attached this
336    /// also trains the height model, so unmeasured items follow what has been
337    /// measured instead of a constant guess.
338    pub fn observe_height(&mut self, idx: usize, height: u16) {
339        self.observe_height_in_category(idx, height, 0);
340    }
341
342    /// Record a measured height and its category, including externally stored
343    /// items whose category cannot be obtained through [`Self::get`].
344    pub fn observe_height_in_category(&mut self, idx: usize, height: u16, category: usize) {
345        match &mut self.item_height {
346            ItemHeight::Fixed(_) => {}
347            ItemHeight::Variable(cache) => cache.set(idx, height),
348            ItemHeight::VariableFenwick(tracker) => tracker.set_in_category(idx, height, category),
349        }
350    }
351
352    /// Return the row offset of item `idx` (sum of heights of items `< idx`).
353    #[must_use]
354    pub fn offset_of_item(&self, idx: usize) -> u32 {
355        let clamped = idx.min(self.len());
356        match &self.item_height {
357            ItemHeight::Fixed(h) => (clamped as u64)
358                .saturating_mul(u64::from(*h))
359                .min(u64::from(u32::MAX)) as u32,
360            ItemHeight::Variable(cache) => (0..clamped)
361                .fold(0u64, |acc, i| acc + u64::from(cache.get(i)))
362                .min(u64::from(u32::MAX)) as u32,
363            ItemHeight::VariableFenwick(tracker) => tracker.offset_of_item(clamped),
364        }
365    }
366
367    /// Find the item index containing `offset` rows from the top.
368    #[must_use]
369    pub fn find_item_at_offset(&self, offset: u32) -> usize {
370        let len = self.len();
371        match &self.item_height {
372            ItemHeight::Fixed(h) => {
373                let h = u32::from((*h).max(1));
374                ((offset / h) as usize).min(len)
375            }
376            ItemHeight::Variable(cache) => {
377                let mut acc = 0u64;
378                for i in 0..len {
379                    let next = acc + u64::from(cache.get(i).max(1));
380                    if u64::from(offset) < next {
381                        return i;
382                    }
383                    acc = next;
384                }
385                len
386            }
387            ItemHeight::VariableFenwick(tracker) => tracker.find_item_at_offset(offset),
388        }
389    }
390
391    /// Point prediction for a category, or the configured height without a model.
392    #[must_use]
393    pub fn predicted_height(&self, category: usize) -> u16 {
394        if let ItemHeight::VariableFenwick(tracker) = &self.item_height
395            && let Some(predictor) = tracker.predictor()
396        {
397            return predictor.predict(category).predicted.max(1);
398        }
399        self.unmeasured_item_height()
400    }
401
402    /// Statistics from actual height observations, when prediction is enabled.
403    #[must_use]
404    pub fn predictor_stats(&self) -> Option<PredictorStats> {
405        match &self.item_height {
406            ItemHeight::VariableFenwick(tracker) => tracker.predictor().map(HeightPredictor::stats),
407            _ => None,
408        }
409    }
410
411    /// Height assumed for items that have not been measured yet: the
412    /// predictor's current point estimate when one is attached, otherwise
413    /// the strategy's default (or the fixed height).
414    #[must_use]
415    pub fn unmeasured_item_height(&self) -> u16 {
416        match &self.item_height {
417            ItemHeight::Fixed(height) => *height,
418            ItemHeight::Variable(cache) => cache.default_height,
419            ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
420        }
421    }
422
423    /// Use variable item heights (Fenwick-tracked, the default strategy):
424    /// unmeasured rows count `default_height`, `observe_height` records
425    /// real ones, and offsets, `scroll_to` and `visible_range` stay
426    /// O(log n). The tracker is sized to the current length and follows the
427    /// items: it grows with `push` (a tracker pre-filled with more heights
428    /// than items keeps them), shifts on `trim_front`, clears on `clear`
429    /// and matches `set_external_len` exactly.
430    #[must_use]
431    pub fn with_variable_heights(mut self, default_height: u16) -> Self {
432        let len = self.len();
433        self.item_height =
434            ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
435        self
436    }
437
438    /// Variable heights with an explicit initial tracker capacity (the
439    /// tracker still follows the item count afterwards). Prefer
440    /// [`Self::with_variable_heights`] unless the list is filled in bulk
441    /// after construction.
442    #[must_use]
443    pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
444        self.item_height =
445            ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
446        self
447    }
448
449    /// Keep a Fenwick tracker's length in step with the item count: grow it
450    /// (`exact == false`, used by `push`, so a tracker pre-filled with more
451    /// heights than items keeps them) or set it exactly (`exact == true`,
452    /// used by `set_external_len`).
453    fn sync_height_tracker(&mut self, exact: bool) {
454        let len = self.len();
455        if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
456            && (tracker.len() < len || (exact && tracker.len() != len))
457        {
458            tracker.resize(len);
459        }
460    }
461
462    /// Set overscan amount.
463    #[must_use]
464    pub fn with_overscan(mut self, overscan: usize) -> Self {
465        self.overscan = overscan;
466        self
467    }
468
469    /// Enable follow mode.
470    #[must_use]
471    pub fn with_follow(mut self, follow: bool) -> Self {
472        self.follow_mode = follow;
473        self
474    }
475
476    /// Get total number of items.
477    #[must_use]
478    pub fn len(&self) -> usize {
479        match &self.storage {
480            VirtualizedStorage::Owned(items) => items.len(),
481            VirtualizedStorage::External { len, .. } => *len,
482        }
483    }
484
485    /// Check if empty.
486    #[must_use]
487    pub fn is_empty(&self) -> bool {
488        self.len() == 0
489    }
490
491    /// Get current scroll offset.
492    ///
493    /// The internal sentinel value (`usize::MAX`, used for lazy scroll-to-bottom)
494    /// is clamped to the actual item count so callers never see it.
495    #[must_use]
496    pub fn scroll_offset(&self) -> usize {
497        self.scroll_offset.min(self.len().saturating_sub(1))
498    }
499
500    /// Get current visible count (from last render).
501    #[must_use]
502    pub fn visible_count(&self) -> usize {
503        self.visible_count.get()
504    }
505
506    /// Check if follow mode is enabled.
507    #[must_use]
508    pub fn follow_mode(&self) -> bool {
509        self.follow_mode
510    }
511
512    /// Calculate visible range for given viewport height.
513    #[must_use]
514    pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
515        if self.is_empty() || viewport_height == 0 {
516            self.visible_count.set(0);
517            return 0..0;
518        }
519
520        let items_visible = match &self.item_height {
521            // Use div_ceil to include partially visible items
522            ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
523            ItemHeight::Fixed(_) => viewport_height as usize,
524            ItemHeight::Variable(cache) => {
525                // Sum heights until we fill or exceed viewport
526                let len = self.len();
527                let start = self.scroll_offset.min(len.saturating_sub(1));
528                let mut count = 0;
529                let mut total_height = 0u16;
530                while start + count < len {
531                    let next = cache.get(start + count);
532
533                    // Always include the item
534                    total_height = total_height.saturating_add(next);
535                    count += 1;
536
537                    // Stop if we've filled the viewport
538                    if total_height >= viewport_height {
539                        break;
540                    }
541                }
542                if total_height < viewport_height && start > 0 {
543                    // The tail from `start` cannot fill the viewport (e.g.
544                    // after scroll_to_bottom's lazy sentinel, or an offset
545                    // near the end). Anchor to the bottom like the Fixed arm:
546                    // count the trailing items that fit, so the clamped start
547                    // below shows a full last screenful instead of blank rows.
548                    count = 0;
549                    total_height = 0;
550                    while count < len {
551                        let next = cache.get(len - 1 - count);
552                        total_height = total_height.saturating_add(next);
553                        count += 1;
554                        if total_height >= viewport_height {
555                            break;
556                        }
557                    }
558                }
559                count
560            }
561            ItemHeight::VariableFenwick(tracker) => {
562                // O(log n) using Fenwick tree
563                let len = self.len();
564                let start = self.scroll_offset.min(len.saturating_sub(1));
565                let total = tracker.total_height_exact();
566                let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
567                if suffix < u64::from(viewport_height) {
568                    // Same bottom anchoring as the Variable arm, in O(log n):
569                    // when the last screenful is shown, its first (possibly
570                    // partially visible) item contains offset total-viewport.
571                    let anchor = total.saturating_sub(u64::from(viewport_height));
572                    len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
573                        .max(1)
574                } else {
575                    tracker.visible_count(start, viewport_height).max(1)
576                }
577            }
578        };
579
580        let max_offset = self.len().saturating_sub(items_visible);
581        let start = self.scroll_offset.min(max_offset);
582        let end = start.saturating_add(items_visible).min(self.len());
583        self.visible_count.set(items_visible);
584        start..end
585    }
586
587    /// Get render range with overscan for smooth scrolling.
588    #[must_use]
589    pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
590        let visible = self.visible_range(viewport_height);
591        let start = visible.start.saturating_sub(self.overscan);
592        let end = visible.end.saturating_add(self.overscan).min(self.len());
593        start..end
594    }
595
596    /// Scroll by delta (positive = down/forward).
597    pub fn scroll(&mut self, delta: i32) {
598        if self.is_empty() {
599            return;
600        }
601        // `visible_count` is a cache written by the last `visible_range`, taken
602        // at whatever offset was showing then. With variable heights the number
603        // of items that fit depends on position, so a count measured near the
604        // top clamps the ceiling too low and the list stalls before the end —
605        // holding the down key over `[1, 1, 4, 4]` at viewport 4 stopped at
606        // offset 1 even though offset 3 is valid and shows the final item.
607        //
608        // Only fixed heights can trust the count, because there it cannot vary
609        // with position. Otherwise allow any real index and let `visible_range`
610        // apply the true ceiling, which it recomputes for the current offset.
611        let visible_count = self.visible_count.get();
612        let max_offset = match self.item_height {
613            ItemHeight::Fixed(_) if visible_count > 0 => self.len().saturating_sub(visible_count),
614            _ => self.len().saturating_sub(1),
615        };
616        // Clamp current offset BEFORE adding delta, so lazy MAX doesn't swallow negative deltas
617        let clamped_current = self.scroll_offset.min(max_offset);
618        let new_offset = clamped_current
619            .saturating_add_signed(delta as isize)
620            .min(max_offset);
621        self.scroll_offset = new_offset;
622
623        // Disable follow mode on manual scroll
624        if delta != 0 {
625            self.follow_mode = false;
626        }
627    }
628
629    /// Scroll to specific item index.
630    pub fn scroll_to(&mut self, idx: usize) {
631        if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
632            tracker.refresh_category_predictions();
633        }
634        self.scroll_offset = idx.min(self.len().saturating_sub(1));
635        self.follow_mode = false;
636    }
637
638    /// Scroll to bottom.
639    pub fn scroll_to_bottom(&mut self) {
640        if self.is_empty() {
641            self.scroll_offset = 0;
642            return;
643        }
644
645        // With variable heights, how many items fit depends on *where* in the
646        // list you are, and `visible_count` was measured at the previous
647        // offset. Subtracting a count taken near the top lands short of the
648        // end when the trailing items are taller, leaving the final item off
649        // screen — which is what happens when a list renders and the user then
650        // presses End. Defer to `visible_range`, whose bottom-anchoring arm
651        // measures from the end instead.
652        //
653        // Fixed heights keep the concrete offset: the count cannot vary with
654        // position, so it is always right, and callers reading
655        // `scroll_offset()` still see a real index.
656        if !matches!(self.item_height, ItemHeight::Fixed(_)) {
657            self.scroll_offset = usize::MAX;
658            return;
659        }
660
661        let visible_count = self.visible_count.get();
662        if visible_count == 0 {
663            // Viewport unknown; keep a sentinel and let `visible_range` clamp lazily.
664            self.scroll_offset = usize::MAX;
665        } else if self.len() > visible_count {
666            self.scroll_offset = self.len().saturating_sub(visible_count);
667        } else {
668            self.scroll_offset = 0;
669        }
670    }
671
672    /// Scroll to top.
673    pub fn scroll_to_top(&mut self) {
674        self.scroll_offset = 0;
675        self.follow_mode = false;
676    }
677
678    /// Alias for scroll_to_top (Home key).
679    pub fn scroll_to_start(&mut self) {
680        self.scroll_to_top();
681    }
682
683    /// Scroll to bottom and enable follow mode (End key).
684    pub fn scroll_to_end(&mut self) {
685        self.scroll_to_bottom();
686        self.follow_mode = true;
687    }
688
689    /// Page up (scroll by visible count - 1).
690    pub fn page_up(&mut self) {
691        let visible_count = self.visible_count.get();
692        if visible_count > 0 {
693            let step = if visible_count > 1 {
694                visible_count - 1
695            } else {
696                1
697            };
698            let delta = i32::try_from(step).unwrap_or(i32::MAX);
699            self.scroll(-delta);
700        }
701    }
702
703    /// Page down (scroll by visible count - 1).
704    pub fn page_down(&mut self) {
705        let visible_count = self.visible_count.get();
706        if visible_count > 0 {
707            let step = if visible_count > 1 {
708                visible_count - 1
709            } else {
710                1
711            };
712            let delta = i32::try_from(step).unwrap_or(i32::MAX);
713            self.scroll(delta);
714        }
715    }
716
717    /// Set follow mode.
718    pub fn set_follow(&mut self, follow: bool) {
719        self.follow_mode = follow;
720        if follow {
721            self.scroll_to_bottom();
722        }
723    }
724
725    /// Check if scrolled to bottom.
726    #[must_use]
727    pub fn is_at_bottom(&self) -> bool {
728        let visible_count = self.visible_count.get();
729        if self.len() <= visible_count {
730            true
731        } else {
732            self.scroll_offset >= self.len().saturating_sub(visible_count)
733        }
734    }
735
736    /// Start momentum scroll.
737    pub fn fling(&mut self, velocity: f32) {
738        self.scroll_velocity = velocity;
739    }
740
741    /// Apply momentum scroll tick.
742    pub fn tick(&mut self, dt: Duration) {
743        if self.scroll_velocity.abs() > 0.1 {
744            let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
745            if delta != 0 {
746                self.scroll(delta);
747            }
748            // Apply friction
749            self.scroll_velocity *= 0.95;
750        } else {
751            self.scroll_velocity = 0.0;
752        }
753    }
754
755    /// Update visible count (called during render).
756    pub fn set_visible_count(&self, count: usize) {
757        self.visible_count.set(count);
758    }
759
760    /// Get reference to the item height strategy.
761    #[must_use]
762    pub fn item_height(&self) -> &ItemHeight {
763        &self.item_height
764    }
765
766    /// Get mutable reference to the item height strategy.
767    ///
768    /// Useful for updating variable height trackers (e.g. resizing Fenwick tree)
769    /// when items are added.
770    pub fn item_height_mut(&mut self) -> &mut ItemHeight {
771        &mut self.item_height
772    }
773}
774
775impl<T> Virtualized<T> {
776    /// Push an item (owned storage only).
777    pub fn push(&mut self, item: T) {
778        if let VirtualizedStorage::Owned(items) = &mut self.storage {
779            items.push_back(item);
780            self.sync_height_tracker(false);
781            if self.follow_mode {
782                self.scroll_to_bottom();
783            }
784        }
785    }
786
787    /// Get item by index (owned storage only).
788    #[must_use = "use the returned item (if any)"]
789    pub fn get(&self, idx: usize) -> Option<&T> {
790        if let VirtualizedStorage::Owned(items) = &self.storage {
791            items.get(idx)
792        } else {
793            None
794        }
795    }
796
797    /// Get mutable item by index (owned storage only).
798    #[must_use = "use the returned item (if any)"]
799    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
800        if let VirtualizedStorage::Owned(items) = &mut self.storage {
801            items.get_mut(idx)
802        } else {
803            None
804        }
805    }
806
807    /// Clear all items (owned storage only).
808    pub fn clear(&mut self) {
809        if let VirtualizedStorage::Owned(items) = &mut self.storage {
810            items.clear();
811            match &mut self.item_height {
812                ItemHeight::Fixed(_) => {}
813                ItemHeight::Variable(cache) => cache.clear(),
814                ItemHeight::VariableFenwick(tracker) => tracker.clear(),
815            }
816        }
817        self.scroll_offset = 0;
818    }
819
820    /// Trim items from the front to keep at most `max` items (owned storage only).
821    ///
822    /// Returns the number of items removed.
823    pub fn trim_front(&mut self, max: usize) -> usize {
824        if let VirtualizedStorage::Owned(items) = &mut self.storage
825            && items.len() > max
826        {
827            let to_remove = items.len() - max;
828            items.drain(..to_remove);
829            // Every surviving item moved down by `to_remove`, so a height
830            // tracker that keeps its old indices now reports each measurement
831            // against a different item.
832            match &mut self.item_height {
833                ItemHeight::Fixed(_) => {}
834                ItemHeight::Variable(cache) => cache.drop_front(to_remove),
835                ItemHeight::VariableFenwick(tracker) => tracker.drop_front(to_remove),
836            }
837            // Adjust scroll_offset if it was pointing beyond the new start
838            self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
839            return to_remove;
840        }
841        0
842    }
843
844    /// Iterate over items (owned storage only).
845    /// Returns empty iterator for external storage.
846    pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
847        match &self.storage {
848            VirtualizedStorage::Owned(items) => Box::new(items.iter()),
849            VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
850        }
851    }
852
853    /// Update external storage length.
854    pub fn set_external_len(&mut self, len: usize) {
855        if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
856            *l = len;
857            self.sync_height_tracker(true);
858            if self.follow_mode {
859                self.scroll_to_bottom();
860            }
861        }
862    }
863}
864
865impl Default for HeightCache {
866    fn default() -> Self {
867        Self::new(1, 1000)
868    }
869}
870
871impl HeightCache {
872    /// Create a new height cache.
873    #[must_use]
874    pub fn new(default_height: u16, capacity: usize) -> Self {
875        Self {
876            cache: Vec::new(),
877            base_offset: 0,
878            default_height,
879            capacity,
880        }
881    }
882
883    /// Get height for item, returning default if not cached.
884    #[must_use]
885    pub fn get(&self, idx: usize) -> u16 {
886        if idx < self.base_offset {
887            return self.default_height;
888        }
889        let local = idx - self.base_offset;
890        self.cache
891            .get(local)
892            .and_then(|h| *h)
893            .unwrap_or(self.default_height)
894    }
895
896    /// Set height for item.
897    pub fn set(&mut self, idx: usize, height: u16) {
898        if self.capacity == 0 {
899            return;
900        }
901        if idx < self.base_offset {
902            // Index has been trimmed away; ignore
903            return;
904        }
905        let mut local = idx - self.base_offset;
906
907        // If the jump is so large that we'd drain the entire current cache anyway,
908        // reset the window to avoid a huge allocation of Nones.
909        if local + 1 >= self.cache.len() + self.capacity {
910            self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
911            self.cache.clear();
912            local = idx - self.base_offset;
913        }
914
915        if local >= self.cache.len() {
916            self.cache.resize(local + 1, None);
917        }
918        self.cache[local] = Some(height);
919
920        // Trim if over capacity: remove oldest entries and adjust base_offset
921        if self.cache.len() > self.capacity {
922            let to_remove = self.cache.len() - self.capacity;
923            self.cache.drain(0..to_remove);
924            self.base_offset += to_remove;
925        }
926    }
927
928    /// Drop the first `count` items, shifting every remaining measurement down
929    /// by `count` so it still names the item it was taken from.
930    ///
931    /// The counterpart to [`VariableHeightsFenwick::drop_front`], for callers
932    /// that trim a sliding window with [`Virtualized::trim_front`].
933    pub fn drop_front(&mut self, count: usize) {
934        if count == 0 {
935            return;
936        }
937        if let Some(base) = self.base_offset.checked_sub(count) {
938            // The whole window sits past the trimmed prefix: renumber it.
939            self.base_offset = base;
940            return;
941        }
942        let dropped = count - self.base_offset;
943        if dropped >= self.cache.len() {
944            self.cache.clear();
945        } else {
946            self.cache.drain(0..dropped);
947        }
948        self.base_offset = 0;
949    }
950
951    /// Clear cached heights.
952    pub fn clear(&mut self) {
953        self.cache.clear();
954        self.base_offset = 0;
955    }
956
957    /// Clear the cached height for `idx`, reverting it to `default_height`.
958    pub fn invalidate(&mut self, idx: usize) {
959        if idx < self.base_offset {
960            return;
961        }
962        let local = idx - self.base_offset;
963        if let Some(slot) = self.cache.get_mut(local) {
964            *slot = None;
965        }
966    }
967}
968
969// ============================================================================
970// VariableHeightsFenwick - O(log n) scroll-to-index mapping
971// ============================================================================
972
973use crate::height_predictor::{HeightPredictor, PredictorConfig, PredictorStats};
974
975/// Variable height tracker using Fenwick tree for O(log n) prefix sum queries.
976///
977/// This enables efficient scroll offset to item index mapping for virtualized
978/// lists with variable height items.
979///
980/// # Operations
981///
982/// | Operation | Time |
983/// |-----------|------|
984/// | `find_item_at_offset` | O(log n) |
985/// | `offset_of_item` | O(log n) |
986/// | `set_height` | O(log n) |
987/// | `total_height` | O(log n) |
988///
989/// # Invariants
990///
991/// 1. Internal prefix sums are exact u64 sums of u16 item heights.
992/// 2. Inverse lookup searches these monotone sums without allocating.
993/// 3. Public u32 offsets and totals saturate at u32::MAX; internal layout
994///    continues to use exact offsets beyond that boundary.
995#[derive(Debug, Clone)]
996pub struct VariableHeightsFenwick {
997    /// One-indexed Fenwick tree storing exact aggregate heights.
998    tree: Vec<u64>,
999    /// Default height for items not yet measured.
1000    default_height: u16,
1001    /// Number of items tracked.
1002    len: usize,
1003    /// Which slots hold a measured height (`set`) rather than the fill value.
1004    measured: Vec<u64>,
1005    /// Number of tracked slots without a measured bit.
1006    unmeasured: usize,
1007    /// Optional Bayesian model for the heights of unmeasured slots.
1008    predictor: Option<HeightPredictor>,
1009    /// Height every unmeasured category-0 slot currently holds: the predictor's
1010    /// point prediction when one is attached, otherwise `default_height`.
1011    fill_height: u16,
1012    /// Per-slot category IDs (0 = default category).
1013    categories: Vec<u16>,
1014    /// Per-category fill heights for unmeasured slots.
1015    cat_fill_heights: Vec<u16>,
1016    /// Length at which `categories` was last synced from owned `RenderItem`s.
1017    categories_synced_len: usize,
1018    /// Whether any measurement since the last VOI tick violated the predictor's
1019    /// conformal interval or changed a previously measured height.
1020    last_violation: bool,
1021}
1022
1023impl Default for VariableHeightsFenwick {
1024    fn default() -> Self {
1025        Self::new(1, 0)
1026    }
1027}
1028
1029impl VariableHeightsFenwick {
1030    /// Create a new height tracker with given default height and initial capacity.
1031    #[must_use]
1032    pub fn new(default_height: u16, capacity: usize) -> Self {
1033        let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
1034        Self {
1035            tree,
1036            default_height,
1037            len: capacity,
1038            measured: vec![0; capacity.div_ceil(64)],
1039            unmeasured: capacity,
1040            predictor: None,
1041            fill_height: default_height,
1042            categories: vec![0; capacity],
1043            cat_fill_heights: vec![default_height],
1044            categories_synced_len: 0,
1045            last_violation: false,
1046        }
1047    }
1048
1049    /// Create from a slice of heights (all of them count as measured).
1050    #[must_use]
1051    pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
1052        Self {
1053            tree: Self::build_height_tree(heights.iter().copied()),
1054            default_height,
1055            len: heights.len(),
1056            measured: Self::all_measured_bits(heights.len()),
1057            unmeasured: 0,
1058            predictor: None,
1059            fill_height: default_height,
1060            categories: vec![0; heights.len()],
1061            cat_fill_heights: vec![default_height],
1062            categories_synced_len: 0,
1063            last_violation: false,
1064        }
1065    }
1066
1067    /// Build in O(n), bounding the item count so every possible height update
1068    /// also fits in u64. This limit exceeds any practically allocatable list.
1069    fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
1070        let len = heights.len();
1071        assert!(
1072            u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
1073            "too many items for exact height aggregates"
1074        );
1075        let mut tree = vec![0; len + 1];
1076        for (slot, height) in tree[1..].iter_mut().zip(heights) {
1077            *slot = u64::from(height);
1078        }
1079        for idx in 1..=len {
1080            let parent = idx + idx.isolate_lowest_one();
1081            if parent <= len {
1082                tree[parent] += tree[idx];
1083            }
1084        }
1085        tree
1086    }
1087
1088    fn all_measured_bits(len: usize) -> Vec<u64> {
1089        let mut bits = vec![u64::MAX; len.div_ceil(64)];
1090        if !len.is_multiple_of(64) {
1091            *bits.last_mut().expect("partial word exists") = (1_u64 << (len % 64)) - 1;
1092        }
1093        bits
1094    }
1095
1096    fn mark_measured(&mut self, idx: usize) {
1097        if !self.is_measured(idx) {
1098            self.measured[idx / 64] |= 1_u64 << (idx % 64);
1099            self.unmeasured -= 1;
1100        }
1101    }
1102
1103    #[inline]
1104    fn fill_height_for_category(&self, category: usize) -> u16 {
1105        self.cat_fill_heights
1106            .get(category)
1107            .copied()
1108            .unwrap_or(self.fill_height)
1109    }
1110
1111    /// Assign category IDs to tracked slots and update unmeasured slot heights
1112    /// to match their category's current fill height.
1113    pub fn set_categories(&mut self, categories: impl IntoIterator<Item = usize>) {
1114        self.categories.clear();
1115        self.categories.extend(
1116            categories
1117                .into_iter()
1118                .take(self.len)
1119                .map(|c| u16::try_from(c).unwrap_or(u16::MAX)),
1120        );
1121        self.categories.resize(self.len, 0);
1122        self.categories_synced_len = self.len;
1123        for idx in 0..self.len {
1124            if !self.is_measured(idx) {
1125                let cat = self.categories[idx] as usize;
1126                let h = self.fill_height_for_category(cat);
1127                if self.get(idx) != h {
1128                    self.set_tracked_height(idx, h);
1129                }
1130            }
1131        }
1132    }
1133
1134    /// Clear the measured bit for `idx` and reset its tracked height to the
1135    /// current fill height (default or predicted for its category).
1136    pub fn invalidate(&mut self, idx: usize) {
1137        if idx < self.len && self.is_measured(idx) {
1138            self.measured[idx / 64] &= !(1_u64 << (idx % 64));
1139            self.unmeasured += 1;
1140            let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
1141            self.set_tracked_height(idx, self.fill_height_for_category(cat));
1142        }
1143    }
1144
1145    /// Take and clear the pending violation flag accumulated from recent measurements.
1146    #[inline]
1147    pub fn take_last_violation(&mut self) -> bool {
1148        std::mem::replace(&mut self.last_violation, false)
1149    }
1150
1151    fn set_tracked_height(&mut self, idx: usize, height: u16) {
1152        let old = self.get(idx);
1153        let mut node = idx + 1;
1154        while node <= self.len {
1155            if height >= old {
1156                self.tree[node] += u64::from(height - old);
1157            } else {
1158                self.tree[node] -= u64::from(old - height);
1159            }
1160            node += node.isolate_lowest_one();
1161        }
1162    }
1163
1164    fn offset_of_item_exact(&self, idx: usize) -> u64 {
1165        let mut node = idx.min(self.len);
1166        let mut sum = 0;
1167        while node > 0 {
1168            sum += self.tree[node];
1169            node &= node - 1;
1170        }
1171        sum
1172    }
1173
1174    fn total_height_exact(&self) -> u64 {
1175        self.offset_of_item_exact(self.len)
1176    }
1177
1178    fn find_item_at_offset_exact(&self, offset: u64) -> usize {
1179        // Preserve the origin convention even when leading items have height 0.
1180        if self.len == 0 || offset == 0 {
1181            return 0;
1182        }
1183        let mut idx = 0;
1184        let mut sum = 0;
1185        let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
1186        while step > 0 {
1187            if step <= self.len - idx {
1188                let next = idx + step;
1189                let prefix = sum + self.tree[next];
1190                if prefix <= offset {
1191                    idx = next;
1192                    sum = prefix;
1193                }
1194            }
1195            step >>= 1;
1196        }
1197        idx
1198    }
1199
1200    /// Attach a Bayesian height predictor ([`HeightPredictor`]).
1201    ///
1202    /// Unmeasured slots then hold the predictor's current point prediction
1203    /// instead of `default_height`; every [`set`](Self::set) trains the model
1204    /// and, whenever the rounded prediction moves by a whole row, the
1205    /// unmeasured slots are refilled so offsets and the total height track
1206    /// the rows measured so far instead of a constant guess. A refill costs
1207    /// O(u log n) for u unmeasured slots and a converging posterior triggers
1208    /// it only a handful of times.
1209    #[must_use]
1210    pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
1211        let predictor = HeightPredictor::new(config);
1212        self.fill_height = predictor.predict(0).predicted.max(1);
1213        self.cat_fill_heights.fill(self.fill_height);
1214        if self.cat_fill_heights.is_empty() {
1215            self.cat_fill_heights.push(self.fill_height);
1216        }
1217        self.predictor = Some(predictor);
1218        self.refill_unmeasured();
1219        self
1220    }
1221
1222    /// The attached height predictor, if any.
1223    #[must_use]
1224    pub fn predictor(&self) -> Option<&HeightPredictor> {
1225        self.predictor.as_ref()
1226    }
1227
1228    /// Height every unmeasured slot currently holds (the prediction when a
1229    /// predictor is attached, otherwise the default height).
1230    #[must_use]
1231    pub fn predicted_height(&self) -> u16 {
1232        self.fill_height
1233    }
1234
1235    /// Number of slots that have not been measured through [`set`](Self::set).
1236    #[must_use]
1237    pub fn unmeasured_count(&self) -> usize {
1238        self.unmeasured
1239    }
1240
1241    /// Whether slot `idx` holds a measured height.
1242    #[must_use]
1243    pub fn is_measured(&self, idx: usize) -> bool {
1244        idx < self.len && self.measured[idx / 64] & (1_u64 << (idx % 64)) != 0
1245    }
1246
1247    /// Rewrite every unmeasured slot with its category's current fill height.
1248    /// Returns the number of slots rewritten.
1249    fn refill_unmeasured(&mut self) -> usize {
1250        let mut rewritten = 0;
1251        for idx in 0..self.len {
1252            if !self.is_measured(idx) {
1253                let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
1254                let h = self.fill_height_for_category(cat);
1255                self.set_tracked_height(idx, h);
1256                rewritten += 1;
1257            }
1258        }
1259        rewritten
1260    }
1261
1262    /// Number of items tracked.
1263    #[must_use]
1264    pub fn len(&self) -> usize {
1265        self.len
1266    }
1267
1268    /// Whether tracking is empty.
1269    #[must_use]
1270    pub fn is_empty(&self) -> bool {
1271        self.len == 0
1272    }
1273
1274    /// Get the default height for unmeasured items.
1275    #[must_use]
1276    pub fn default_height(&self) -> u16 {
1277        self.default_height
1278    }
1279
1280    /// Get height of a specific item. O(log n).
1281    ///
1282    /// Items beyond the tracked length report the fill height (the
1283    /// prediction when a predictor is attached).
1284    #[must_use]
1285    pub fn get(&self, idx: usize) -> u16 {
1286        if idx >= self.len {
1287            return self.fill_height;
1288        }
1289        (self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
1290    }
1291
1292    /// Set (measure) the height of a specific item. O(log n), plus a refill
1293    /// of the unmeasured slots when an attached predictor's rounded
1294    /// prediction changes.
1295    pub fn set(&mut self, idx: usize, height: u16) {
1296        self.set_in_category(idx, height, 0);
1297    }
1298
1299    /// Refresh unmeasured slot heights from the predictor's current per-category
1300    /// point predictions in a single O(n) pass.
1301    pub fn refresh_category_predictions(&mut self) {
1302        let Some(predictor) = self.predictor.as_ref() else {
1303            return;
1304        };
1305        if self.unmeasured == 0 || self.categories_synced_len == 0 {
1306            return;
1307        }
1308        let cat_count = predictor.category_count().max(1);
1309        if self.cat_fill_heights.len() < cat_count {
1310            self.cat_fill_heights.resize(cat_count, self.fill_height);
1311        }
1312        let mut any_changed = false;
1313        for cat in 0..cat_count {
1314            let next = predictor.predict(cat).predicted.max(1);
1315            if cat == 0 {
1316                self.fill_height = next;
1317            }
1318            if self.cat_fill_heights[cat] != next {
1319                self.cat_fill_heights[cat] = next;
1320                any_changed = true;
1321            }
1322        }
1323        if !any_changed {
1324            return;
1325        }
1326        for idx in 0..self.len {
1327            if !self.is_measured(idx) {
1328                let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
1329                let h = self.fill_height_for_category(cat);
1330                self.set_tracked_height(idx, h);
1331            }
1332        }
1333    }
1334
1335    /// Measure an item and train its category's predictor. Unmeasured slots in
1336    /// the same category track that category's rounded posterior prediction.
1337    pub fn set_in_category(&mut self, idx: usize, height: u16, category: usize) {
1338        if idx >= self.len {
1339            // Need to resize
1340            self.resize(idx.checked_add(1).expect("height index exceeds usize"));
1341        }
1342        let cat_u16 = u16::try_from(category).unwrap_or(u16::MAX);
1343        self.categories[idx] = cat_u16;
1344        let was_measured = self.is_measured(idx);
1345        let old_height = self.get(idx);
1346        self.set_tracked_height(idx, height);
1347        self.mark_measured(idx);
1348        if was_measured && old_height != height {
1349            self.last_violation = true;
1350        }
1351        if let Some(predictor) = self.predictor.as_mut() {
1352            let within_bounds = predictor.observe(category, height);
1353            if !within_bounds {
1354                self.last_violation = true;
1355            }
1356            let next = predictor.predict(category).predicted.max(1);
1357            if self.cat_fill_heights.len() <= category {
1358                self.cat_fill_heights.resize(category + 1, self.fill_height);
1359            }
1360            if category == 0 {
1361                self.fill_height = next;
1362            }
1363            if self.categories_synced_len == 0 && category == 0 && self.cat_fill_heights[0] != next
1364            {
1365                self.cat_fill_heights[0] = next;
1366                self.refill_unmeasured();
1367            }
1368        }
1369    }
1370
1371    /// Get the y-offset (in pixels/rows) of an item. O(log n).
1372    ///
1373    /// Returns the sum of heights of all items before `idx`, saturated at
1374    /// `u32::MAX`. Indices beyond the tracked length return the total height.
1375    #[must_use]
1376    pub fn offset_of_item(&self, idx: usize) -> u32 {
1377        self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
1378    }
1379
1380    /// Find the item index at a given scroll offset. O(log n).
1381    ///
1382    /// Returns the index of the item that occupies the given offset.
1383    /// If offset is beyond all items, returns `self.len`.
1384    ///
1385    /// Item i occupies the interval between its exact prefix sums, including
1386    /// when the total exceeds `u32::MAX`. Offset zero returns item zero even
1387    /// if leading items have zero height. Saturated public offsets above the
1388    /// u32 boundary cannot be used to address those later items.
1389    #[must_use]
1390    pub fn find_item_at_offset(&self, offset: u32) -> usize {
1391        self.find_item_at_offset_exact(u64::from(offset))
1392    }
1393
1394    /// Count how many items are visible within a viewport starting at `start_idx`. O(log n).
1395    ///
1396    /// Visibility here means partially or fully visible. The first partially
1397    /// visible trailing item is counted.
1398    ///
1399    /// Returns **at least 1** when `start_idx < len` and `viewport_height > 0`,
1400    /// even if the first item is taller than the viewport.
1401    #[must_use]
1402    pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
1403        if self.len == 0 || viewport_height == 0 {
1404            return 0;
1405        }
1406        let start = start_idx.min(self.len);
1407        let start_offset = self.offset_of_item_exact(start);
1408        let end_offset = start_offset.saturating_add(u64::from(viewport_height));
1409
1410        // Find last item that fits
1411        let end_idx = self.find_item_at_offset_exact(end_offset);
1412
1413        // Count items from start to end (including partially visible trailing item)
1414        if end_idx > start {
1415            // `find_item_at_offset` returns `len` when `end_offset` is at/after the end
1416            // of the list. In that case, everything from `start` to the end fits.
1417            if end_idx >= self.len {
1418                return self.len.saturating_sub(start);
1419            }
1420            // Check if end_idx item is visible (partially or fully)
1421            let end_item_start = self.offset_of_item_exact(end_idx);
1422            if end_offset > end_item_start {
1423                end_idx - start + 1
1424            } else {
1425                end_idx - start
1426            }
1427        } else {
1428            // At least show one item if viewport has space
1429            if viewport_height > 0 && start < self.len {
1430                1
1431            } else {
1432                0
1433            }
1434        }
1435    }
1436
1437    /// Get total height of all items, saturated at `u32::MAX`. O(log n).
1438    #[must_use]
1439    pub fn total_height(&self) -> u32 {
1440        self.total_height_exact().min(u64::from(u32::MAX)) as u32
1441    }
1442
1443    /// Resize the tracker to accommodate `new_len` items.
1444    ///
1445    /// New items are initialized with the fill height (the default height,
1446    /// or the current prediction when a predictor is attached).
1447    pub fn resize(&mut self, new_len: usize) {
1448        if new_len == self.len {
1449            return;
1450        }
1451        assert!(
1452            u64::try_from(new_len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
1453            "too many items for exact height aggregates"
1454        );
1455        if new_len > self.len {
1456            self.tree.reserve(new_len + 1 - self.tree.len());
1457            let fill = u64::from(self.fill_height);
1458            for node in (self.len + 1)..=new_len {
1459                let mut sum = fill;
1460                let tz = node.trailing_zeros();
1461                for k in 0..tz {
1462                    sum += self.tree[node - (1usize << k)];
1463                }
1464                self.tree.push(sum);
1465            }
1466            self.unmeasured += new_len - self.len;
1467            self.measured.resize(new_len.div_ceil(64), 0);
1468        } else {
1469            let dropped_unmeasured = (new_len..self.len)
1470                .filter(|&idx| !self.is_measured(idx))
1471                .count();
1472            self.unmeasured -= dropped_unmeasured;
1473            self.tree.truncate(new_len + 1);
1474            self.measured.truncate(new_len.div_ceil(64));
1475            if !new_len.is_multiple_of(64) {
1476                *self.measured.last_mut().expect("partial word exists") &=
1477                    (1_u64 << (new_len % 64)) - 1;
1478            }
1479        }
1480        self.categories.resize(new_len, 0);
1481        self.len = new_len;
1482    }
1483
1484    /// Drop the first `n` entries (the list trimmed its front): remaining
1485    /// heights and their measured flags shift down by `n`; an attached
1486    /// predictor keeps what it learned.
1487    pub fn drop_front(&mut self, n: usize) {
1488        if n == 0 {
1489            return;
1490        }
1491        if n >= self.len {
1492            self.clear();
1493            return;
1494        }
1495        let kept: Vec<(u16, bool, u16)> = (n..self.len)
1496            .map(|idx| (self.get(idx), self.is_measured(idx), self.categories[idx]))
1497            .collect();
1498        self.tree = Self::build_height_tree(kept.iter().map(|&(height, _, _)| height));
1499        self.len = kept.len();
1500        self.measured = vec![0; self.len.div_ceil(64)];
1501        self.categories = kept.iter().map(|&(_, _, cat)| cat).collect();
1502        self.categories_synced_len = self.categories_synced_len.saturating_sub(n);
1503        self.unmeasured = self.len;
1504        for (idx, (_, measured, _)) in kept.into_iter().enumerate() {
1505            if measured {
1506                self.mark_measured(idx);
1507            }
1508        }
1509    }
1510
1511    /// Clear all height data (an attached predictor keeps what it learned).
1512    pub fn clear(&mut self) {
1513        self.tree = vec![0];
1514        self.len = 0;
1515        self.measured.clear();
1516        self.categories.clear();
1517        self.categories_synced_len = 0;
1518        self.unmeasured = 0;
1519        self.last_violation = false;
1520    }
1521
1522    /// Rebuild from a fresh set of heights; all of them count as measured and
1523    /// train an attached predictor.
1524    pub fn rebuild(&mut self, heights: &[u16]) {
1525        self.tree = Self::build_height_tree(heights.iter().copied());
1526        self.len = heights.len();
1527        self.measured = Self::all_measured_bits(heights.len());
1528        self.categories.resize(heights.len(), 0);
1529        self.unmeasured = 0;
1530        if let Some(predictor) = self.predictor.as_mut() {
1531            for &height in heights {
1532                predictor.observe(0, height);
1533            }
1534            self.fill_height = predictor.predict(0).predicted.max(1);
1535            if !self.cat_fill_heights.is_empty() {
1536                self.cat_fill_heights[0] = self.fill_height;
1537            }
1538        }
1539    }
1540}
1541
1542// ============================================================================
1543// VirtualizedList Widget
1544// ============================================================================
1545
1546/// Trait for items that can render themselves.
1547///
1548/// Implement this trait for item types that should render in a `VirtualizedList`.
1549pub trait RenderItem {
1550    /// Render the item into the frame at the given area.
1551    ///
1552    /// # Arguments
1553    ///
1554    /// * `area` - The area to render into.
1555    /// * `frame` - The frame to render into.
1556    /// * `selected` - Whether the item is selected.
1557    /// * `skip_rows` - Number of rows to skip from the top of the item content.
1558    ///   This is non-zero when the item partially overlaps the top of the viewport.
1559    fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
1560
1561    /// Height of this item in terminal rows.
1562    fn height(&self) -> u16 {
1563        1
1564    }
1565
1566    /// Height-prediction category. Use a small stable category ID for each
1567    /// item shape; zero is the default for unclassified rows.
1568    fn category(&self) -> usize {
1569        0
1570    }
1571}
1572
1573impl<T: RenderItem> Virtualized<T> {
1574    /// Synchronize owned item categories into the Fenwick height tracker so
1575    /// unmeasured items use their category's predicted height.
1576    pub fn sync_item_categories(&mut self) {
1577        if let (VirtualizedStorage::Owned(items), ItemHeight::VariableFenwick(tracker)) =
1578            (&self.storage, &mut self.item_height)
1579            && tracker.categories_synced_len != items.len()
1580        {
1581            tracker.set_categories(items.iter().map(RenderItem::category));
1582        }
1583    }
1584
1585    /// Measure an owned item using its [`RenderItem::category`]. External
1586    /// storage has no item to inspect and uses category zero; use
1587    /// [`Self::observe_height_in_category`] to supply an external category.
1588    pub fn measure(&mut self, idx: usize, height: u16) {
1589        self.sync_item_categories();
1590        let category = self.get(idx).map_or(0, RenderItem::category);
1591        self.observe_height_in_category(idx, height, category);
1592    }
1593}
1594
1595/// How a [`VirtualizedList`] sizes its rows.
1596#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1597pub enum ListHeightMode {
1598    /// Every row is this many terminal rows tall (default: 1).
1599    Fixed(u16),
1600    /// Each row is as tall as [`RenderItem::height`] reports. Rows are
1601    /// measured into the state's Fenwick tracker as they render, so scroll
1602    /// offsets and the scrollbar stay O(log n) in the item count. Scrolling
1603    /// is item-aligned: the first visible row starts at the viewport top.
1604    Variable,
1605}
1606
1607/// State for the VirtualizedList widget.
1608#[derive(Debug, Clone)]
1609pub struct VirtualizedListState {
1610    /// Currently selected index.
1611    pub selected: Option<usize>,
1612    /// Scroll offset.
1613    scroll_offset: usize,
1614    /// Visible count (from last render).
1615    visible_count: usize,
1616    /// Overscan amount.
1617    overscan: usize,
1618    /// Whether follow mode is enabled.
1619    follow_mode: bool,
1620    /// Scroll velocity for momentum.
1621    scroll_velocity: f32,
1622    /// Drag anchor for scrollbar thumb (offset from thumb top).
1623    scrollbar_drag_anchor: Option<usize>,
1624    /// Optional persistence ID for state saving/restoration.
1625    persistence_id: Option<String>,
1626    /// Row heights measured while rendering in [`ListHeightMode::Variable`]
1627    /// (`None` until the first variable-height render).
1628    heights: Option<VariableHeightsFenwick>,
1629    /// Optional VOI policy deciding when to remeasure visible rows.
1630    remeasure_policy: Option<RemeasurePolicy>,
1631    /// Monotone counter of variable-height render passes on this state.
1632    render_frame_idx: u64,
1633}
1634
1635impl Default for VirtualizedListState {
1636    fn default() -> Self {
1637        Self::new()
1638    }
1639}
1640
1641impl VirtualizedListState {
1642    /// Create a new state.
1643    #[must_use]
1644    pub fn new() -> Self {
1645        Self {
1646            selected: None,
1647            scroll_offset: 0,
1648            visible_count: 0,
1649            overscan: 2,
1650            follow_mode: false,
1651            scroll_velocity: 0.0,
1652            scrollbar_drag_anchor: None,
1653            persistence_id: None,
1654            heights: None,
1655            remeasure_policy: None,
1656            render_frame_idx: 0,
1657        }
1658    }
1659
1660    /// Create variable-height state before its first render.
1661    #[must_use]
1662    pub fn variable(default_height: u16) -> Self {
1663        Self {
1664            heights: Some(VariableHeightsFenwick::new(default_height.max(1), 0)),
1665            ..Self::new()
1666        }
1667    }
1668
1669    /// Enable category-aware prediction of unmeasured row heights.
1670    /// Measured heights remain exact; unclassified rows use category zero.
1671    #[must_use]
1672    pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
1673        self.heights = Some(
1674            self.heights
1675                .take()
1676                .unwrap_or_default()
1677                .with_predictor(config),
1678        );
1679        self
1680    }
1681
1682    /// Attach a Value-of-Information remeasurement policy.
1683    #[must_use]
1684    pub fn with_remeasure_policy(mut self, policy: RemeasurePolicy) -> Self {
1685        self.remeasure_policy = Some(policy);
1686        self
1687    }
1688
1689    /// Borrow the attached VOI remeasurement policy, if any.
1690    #[must_use]
1691    pub fn remeasure_policy(&self) -> Option<&RemeasurePolicy> {
1692        self.remeasure_policy.as_ref()
1693    }
1694
1695    /// Mutably borrow the attached VOI remeasurement policy, if any.
1696    pub fn remeasure_policy_mut(&mut self) -> Option<&mut RemeasurePolicy> {
1697        self.remeasure_policy.as_mut()
1698    }
1699
1700    /// Clear the measured bit for item `idx` so its height reverts to the
1701    /// unmeasured fill prediction until measured again.
1702    pub fn invalidate(&mut self, idx: usize) {
1703        if let Some(heights) = self.heights.as_mut() {
1704            heights.invalidate(idx);
1705        }
1706    }
1707
1708    /// Advance the VOI remeasurement policy by one render tick. When sampling is
1709    /// triggered, invalidates the topmost visible item (`scroll_offset`) so the
1710    /// next render remeasures it and returns the [`RemeasureRequest`] for the frame.
1711    pub fn remeasure_tick(&mut self, frame_idx: u64, widget_id: u64) -> Option<RemeasureRequest> {
1712        let violation_observed = self
1713            .heights
1714            .as_mut()
1715            .is_some_and(VariableHeightsFenwick::take_last_violation);
1716        let policy = self.remeasure_policy.as_mut()?;
1717        let alpha = policy.posterior.alpha;
1718        let beta = policy.posterior.beta;
1719        let decision = policy.should_remeasure(frame_idx, violation_observed)?;
1720        let index = self.scroll_offset;
1721        if let Some(heights) = self.heights.as_mut() {
1722            heights.invalidate(index);
1723        }
1724        Some(RemeasureRequest {
1725            widget_id,
1726            index,
1727            voi: decision.voi,
1728            cost: decision.cost,
1729            alpha,
1730            beta,
1731        })
1732    }
1733
1734    /// Point prediction for a category, or the configured default height.
1735    #[must_use]
1736    pub fn predicted_height(&self, category: usize) -> u16 {
1737        self.heights.as_ref().map_or(1, |heights| {
1738            heights
1739                .predictor()
1740                .map_or(heights.default_height(), |predictor| {
1741                    predictor.predict(category).predicted.max(1)
1742                })
1743        })
1744    }
1745
1746    /// Statistics from measured rows, when prediction is enabled.
1747    #[must_use]
1748    pub fn predictor_stats(&self) -> Option<PredictorStats> {
1749        self.heights
1750            .as_ref()
1751            .and_then(VariableHeightsFenwick::predictor)
1752            .map(HeightPredictor::stats)
1753    }
1754
1755    /// Record the measured height of item `idx` for a variable-height
1756    /// list. Rendering measures the visible rows itself; call this when an
1757    /// item's height changed while off-screen so offsets stay exact. Ignored
1758    /// until the first variable-height render creates the tracker.
1759    pub fn measure(&mut self, idx: usize, height: u16) {
1760        self.measure_in_category(idx, height, 0);
1761    }
1762
1763    /// Record an off-screen measurement together with its item category.
1764    pub fn measure_in_category(&mut self, idx: usize, height: u16, category: usize) {
1765        if let Some(heights) = self.heights.as_mut() {
1766            if idx >= heights.len() {
1767                heights.resize(idx + 1);
1768            }
1769            heights.set_in_category(idx, height.max(1), category);
1770        }
1771    }
1772
1773    /// Resize the variable-height Fenwick tracker to `len` items.
1774    pub fn resize_heights(&mut self, len: usize) {
1775        if let Some(heights) = self.heights.as_mut()
1776            && heights.len() != len
1777        {
1778            heights.resize(len);
1779        }
1780    }
1781
1782    /// Return the row offset of item `idx` (sum of heights of items `< idx`).
1783    #[must_use]
1784    pub fn offset_of_item(&self, idx: usize) -> u32 {
1785        self.heights
1786            .as_ref()
1787            .map_or(idx as u32, |h| h.offset_of_item(idx))
1788    }
1789
1790    /// Find the item index containing `offset` rows from the top.
1791    #[must_use]
1792    pub fn find_item_at_offset(&self, offset: u32) -> usize {
1793        self.heights
1794            .as_ref()
1795            .map_or(offset as usize, |h| h.find_item_at_offset(offset))
1796    }
1797
1798    /// Currently selected item index, if any.
1799    #[must_use]
1800    pub fn selected(&self) -> Option<usize> {
1801        self.selected
1802    }
1803
1804    /// The variable-height tracker (after the first variable-height render).
1805    #[must_use]
1806    pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
1807        self.heights.as_ref()
1808    }
1809
1810    /// Create with overscan.
1811    #[must_use]
1812    pub fn with_overscan(mut self, overscan: usize) -> Self {
1813        self.overscan = overscan;
1814        self
1815    }
1816
1817    /// Create with follow mode enabled.
1818    #[must_use]
1819    pub fn with_follow(mut self, follow: bool) -> Self {
1820        self.follow_mode = follow;
1821        self
1822    }
1823
1824    /// Create with a persistence ID for state saving. Without one the list has
1825    /// no [`StateKey`](crate::stateful::StateKey) and its state is not persisted.
1826    #[must_use]
1827    pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
1828        self.persistence_id = Some(id.into());
1829        self
1830    }
1831
1832    /// Get the persistence ID, if set.
1833    #[must_use = "use the persistence id (if any)"]
1834    pub fn persistence_id(&self) -> Option<&str> {
1835        self.persistence_id.as_deref()
1836    }
1837
1838    /// Get raw scroll offset.
1839    ///
1840    /// **Warning:** After `scroll_to_bottom`, this may return `usize::MAX`
1841    /// (a lazy sentinel that gets clamped during rendering). Use
1842    /// [`scroll_offset_clamped`](Self::scroll_offset_clamped) with a known
1843    /// `total_items` to get a safe value for display or indexing.
1844    #[must_use]
1845    pub fn scroll_offset(&self) -> usize {
1846        self.scroll_offset
1847    }
1848
1849    /// Get scroll offset clamped against a known total item count.
1850    ///
1851    /// Prefer this over [`scroll_offset()`](Self::scroll_offset) when the total is available,
1852    /// because `scroll_to_bottom` may store `usize::MAX` internally.
1853    #[must_use]
1854    pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
1855        if total_items == 0 {
1856            return 0;
1857        }
1858        self.scroll_offset.min(total_items.saturating_sub(1))
1859    }
1860
1861    /// Get visible item count (from last render).
1862    #[must_use]
1863    pub fn visible_count(&self) -> usize {
1864        self.visible_count
1865    }
1866
1867    /// Scroll by delta (positive = down).
1868    pub fn scroll(&mut self, delta: i32, total_items: usize) {
1869        if total_items == 0 {
1870            return;
1871        }
1872        let max_offset = if self.visible_count > 0 {
1873            total_items.saturating_sub(self.visible_count)
1874        } else {
1875            total_items.saturating_sub(1)
1876        };
1877        // Clamp current offset BEFORE adding delta, so lazy MAX doesn't swallow negative deltas
1878        let clamped_current = self.scroll_offset.min(max_offset);
1879        let new_offset = clamped_current
1880            .saturating_add_signed(delta as isize)
1881            .min(max_offset);
1882        self.scroll_offset = new_offset;
1883
1884        if delta != 0 {
1885            self.follow_mode = false;
1886        }
1887    }
1888
1889    /// Scroll to specific index.
1890    pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
1891        self.scroll_offset = idx.min(total_items.saturating_sub(1));
1892        self.follow_mode = false;
1893    }
1894
1895    /// Scroll to top.
1896    pub fn scroll_to_top(&mut self) {
1897        self.scroll_offset = 0;
1898        self.follow_mode = false;
1899    }
1900
1901    /// Scroll to bottom.
1902    pub fn scroll_to_bottom(&mut self, total_items: usize) {
1903        if total_items == 0 {
1904            self.scroll_offset = 0;
1905        } else {
1906            // Set to MAX; render() will clamp to (total - viewport)
1907            // once viewport height is known.
1908            self.scroll_offset = usize::MAX;
1909        }
1910    }
1911
1912    /// Page up (scroll by visible count - 1).
1913    pub fn page_up(&mut self, total_items: usize) {
1914        if self.visible_count > 0 {
1915            let step = if self.visible_count > 1 {
1916                self.visible_count - 1
1917            } else {
1918                1
1919            };
1920            let delta = i32::try_from(step).unwrap_or(i32::MAX);
1921            self.scroll(-delta, total_items);
1922        }
1923    }
1924
1925    /// Page down (scroll by visible count - 1).
1926    pub fn page_down(&mut self, total_items: usize) {
1927        if self.visible_count > 0 {
1928            let step = if self.visible_count > 1 {
1929                self.visible_count - 1
1930            } else {
1931                1
1932            };
1933            let delta = i32::try_from(step).unwrap_or(i32::MAX);
1934            self.scroll(delta, total_items);
1935        }
1936    }
1937
1938    /// Select an item.
1939    pub fn select(&mut self, index: Option<usize>) {
1940        self.selected = index;
1941    }
1942
1943    /// Select previous item.
1944    pub fn select_previous(&mut self, total_items: usize) {
1945        if total_items == 0 {
1946            self.selected = None;
1947            return;
1948        }
1949        self.selected = Some(match self.selected {
1950            Some(i) if i > 0 => i - 1,
1951            Some(_) => 0,
1952            None => 0,
1953        });
1954    }
1955
1956    /// Select next item.
1957    pub fn select_next(&mut self, total_items: usize) {
1958        if total_items == 0 {
1959            self.selected = None;
1960            return;
1961        }
1962        self.selected = Some(match self.selected {
1963            Some(i) if i < total_items - 1 => i + 1,
1964            Some(i) => i,
1965            None => 0,
1966        });
1967    }
1968
1969    /// Check if at bottom.
1970    #[must_use]
1971    pub fn is_at_bottom(&self, total_items: usize) -> bool {
1972        if total_items <= self.visible_count {
1973            true
1974        } else {
1975            self.scroll_offset >= total_items - self.visible_count
1976        }
1977    }
1978
1979    /// Enable/disable follow mode.
1980    pub fn set_follow(&mut self, follow: bool, total_items: usize) {
1981        self.follow_mode = follow;
1982        if follow {
1983            self.scroll_to_bottom(total_items);
1984        }
1985    }
1986
1987    /// Check if follow mode is enabled.
1988    #[must_use]
1989    pub fn follow_mode(&self) -> bool {
1990        self.follow_mode
1991    }
1992
1993    /// Start momentum scroll.
1994    pub fn fling(&mut self, velocity: f32) {
1995        self.scroll_velocity = velocity;
1996    }
1997
1998    /// Apply momentum scrolling tick.
1999    pub fn tick(&mut self, dt: Duration, total_items: usize) {
2000        if self.scroll_velocity.abs() > 0.1 {
2001            let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
2002            if delta != 0 {
2003                self.scroll(delta, total_items);
2004            }
2005            self.scroll_velocity *= 0.95;
2006        } else {
2007            self.scroll_velocity = 0.0;
2008        }
2009    }
2010
2011    /// Handle mouse events, including scrollbar interaction.
2012    ///
2013    /// The caller must provide the hit test result and the expected hit ID for
2014    /// the scrollbar.
2015    ///
2016    /// After a [`ListHeightMode::Variable`] render the scrollbar works in
2017    /// rows, as it was drawn, and `fixed_item_height` is ignored: the thumb
2018    /// position maps back to the nearest item start, and a wheel or arrow
2019    /// step always moves at least one item.
2020    pub fn handle_mouse(
2021        &mut self,
2022        event: &ftui_core::event::MouseEvent,
2023        hit: Option<(
2024            ftui_render::frame::HitId,
2025            ftui_render::frame::HitRegion,
2026            u64,
2027        )>,
2028        scrollbar_hit_id: ftui_render::frame::HitId,
2029        total_items: usize,
2030        viewport_height: u16,
2031        fixed_item_height: u16,
2032    ) -> crate::mouse::MouseResult {
2033        if let Some(heights) = self.heights.as_ref()
2034            && heights.len() == total_items
2035            && total_items > 0
2036        {
2037            let old_item = self.scroll_offset.min(total_items - 1);
2038            let old_row = heights.offset_of_item_exact(old_item);
2039            let mut scrollbar_state = scrollbar_state_for_rows(
2040                heights.total_height_exact(),
2041                old_row,
2042                viewport_height,
2043                usize::MAX,
2044            );
2045            scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
2046            let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
2047            self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
2048
2049            // Rows below the first screenful may still be estimates, so the
2050            // end of the track means the end of the list (render clamps it
2051            // to the last item-aligned screenful).
2052            let total_rows = heights.total_height_exact();
2053            let row = scrollbar_state.position as u64;
2054            let mut item = heights.find_item_at_offset_exact(row);
2055            let start = heights.offset_of_item_exact(item);
2056            if row + u64::from(viewport_height) >= total_rows {
2057                item = total_items - 1;
2058            } else if row.saturating_sub(start) * 2 > u64::from(heights.get(item)) {
2059                item += 1;
2060            }
2061            // A step smaller than the item under it still has to move.
2062            if row > old_row && item <= old_item {
2063                item = old_item + 1;
2064            } else if row < old_row && item >= old_item {
2065                item = old_item.saturating_sub(1);
2066            }
2067            self.scroll_offset = item.min(total_items - 1);
2068
2069            if result == crate::mouse::MouseResult::Scrolled {
2070                self.follow_mode = false;
2071            }
2072            return result;
2073        }
2074
2075        // Construct temporary scrollbar state
2076        let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
2077        let mut scrollbar_state =
2078            ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
2079
2080        // Restore drag anchor
2081        scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
2082
2083        let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
2084
2085        // Sync back
2086        self.scroll_offset = scrollbar_state.position;
2087        self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
2088
2089        if result == crate::mouse::MouseResult::Scrolled {
2090            self.follow_mode = false;
2091        }
2092
2093        result
2094    }
2095}
2096
2097// ============================================================================
2098// Stateful Persistence Implementation for VirtualizedListState
2099// ============================================================================
2100
2101/// Persistable state for a [`VirtualizedListState`].
2102///
2103/// Contains the user-facing scroll state that should survive sessions.
2104/// Transient values like scroll_velocity and visible_count are not persisted.
2105#[derive(Clone, Debug, Default, PartialEq)]
2106#[cfg_attr(
2107    feature = "state-persistence",
2108    derive(serde::Serialize, serde::Deserialize)
2109)]
2110pub struct VirtualizedListPersistState {
2111    /// Selected item index.
2112    pub selected: Option<usize>,
2113    /// Scroll offset (first visible item).
2114    pub scroll_offset: usize,
2115    /// Whether follow mode is enabled.
2116    pub follow_mode: bool,
2117}
2118
2119impl crate::stateful::Stateful for VirtualizedListState {
2120    type State = VirtualizedListPersistState;
2121
2122    fn state_key(&self) -> Option<crate::stateful::StateKey> {
2123        // No persistence_id, no identity: two unnamed lists must not share one.
2124        self.persistence_id
2125            .as_deref()
2126            .map(|id| crate::stateful::StateKey::new("VirtualizedList", id))
2127    }
2128
2129    fn save_state(&self) -> VirtualizedListPersistState {
2130        VirtualizedListPersistState {
2131            selected: self.selected,
2132            scroll_offset: self.scroll_offset,
2133            follow_mode: self.follow_mode,
2134        }
2135    }
2136
2137    fn restore_state(&mut self, state: VirtualizedListPersistState) {
2138        self.selected = state.selected;
2139        self.scroll_offset = state.scroll_offset;
2140        self.follow_mode = state.follow_mode;
2141        // Reset transient values
2142        self.scroll_velocity = 0.0;
2143        self.scrollbar_drag_anchor = None;
2144    }
2145}
2146
2147/// A virtualized list widget that renders only visible items.
2148///
2149/// This widget efficiently renders large lists by only drawing items
2150/// that are currently visible in the viewport, with optional overscan
2151/// for smooth scrolling.
2152///
2153/// # Variable heights
2154///
2155/// Use [`Self::variable_heights`] to measure visible items through
2156/// [`RenderItem::height`]. Enable [`VirtualizedListState::with_predictor`] to
2157/// learn from those measurements; unmeasured items use the category-zero
2158/// prediction. Scrolling remains item-aligned.
2159#[derive(Debug)]
2160pub struct VirtualizedList<'a, T> {
2161    /// Items to render.
2162    items: &'a [T],
2163    /// Base style.
2164    style: Style,
2165    /// Style for selected item.
2166    highlight_style: Style,
2167    /// Whether to show scrollbar.
2168    show_scrollbar: bool,
2169    /// Row sizing: fixed rows or per-item heights.
2170    height_mode: ListHeightMode,
2171    /// Optional hit ID for scrollbar interaction.
2172    hit_id: Option<ftui_render::frame::HitId>,
2173}
2174
2175impl<'a, T> VirtualizedList<'a, T> {
2176    /// Create a new virtualized list.
2177    #[must_use]
2178    pub fn new(items: &'a [T]) -> Self {
2179        Self {
2180            items,
2181            style: Style::default(),
2182            highlight_style: Style::default(),
2183            show_scrollbar: true,
2184            height_mode: ListHeightMode::Fixed(1),
2185            hit_id: None,
2186        }
2187    }
2188
2189    /// Set base style.
2190    #[must_use]
2191    pub fn style(mut self, style: Style) -> Self {
2192        self.style = style;
2193        self
2194    }
2195
2196    /// Set highlight style for selected item.
2197    #[must_use]
2198    pub fn highlight_style(mut self, style: Style) -> Self {
2199        self.highlight_style = style;
2200        self
2201    }
2202
2203    /// Enable/disable scrollbar.
2204    #[must_use]
2205    pub fn show_scrollbar(mut self, show: bool) -> Self {
2206        self.show_scrollbar = show;
2207        self
2208    }
2209
2210    /// Set fixed item height.
2211    #[must_use]
2212    pub fn fixed_height(mut self, height: u16) -> Self {
2213        self.height_mode = ListHeightMode::Fixed(height);
2214        self
2215    }
2216
2217    /// Size each row by [`RenderItem::height`] (see
2218    /// [`ListHeightMode::Variable`]).
2219    #[must_use]
2220    pub fn variable_heights(mut self) -> Self {
2221        self.height_mode = ListHeightMode::Variable;
2222        self
2223    }
2224
2225    /// The row sizing mode.
2226    #[must_use]
2227    pub fn height_mode(&self) -> ListHeightMode {
2228        self.height_mode
2229    }
2230
2231    /// Set hit ID for scrollbar interaction.
2232    #[must_use]
2233    pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
2234        self.hit_id = Some(id);
2235        self
2236    }
2237}
2238
2239impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
2240    type State = VirtualizedListState;
2241
2242    fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
2243        #[cfg(feature = "tracing")]
2244        let _span = tracing::debug_span!(
2245            "widget_render",
2246            widget = "VirtualizedList",
2247            x = area.x,
2248            y = area.y,
2249            w = area.width,
2250            h = area.height,
2251            items = self.items.len(),
2252            height_mode = ?self.height_mode
2253        )
2254        .entered();
2255
2256        if area.is_empty() {
2257            return;
2258        }
2259
2260        // Clear the full owned viewport so empty renders and shorter rows do
2261        // not leak prior buffer content.
2262        clear_text_area(frame, area, self.style);
2263
2264        let total_items = self.items.len();
2265        if total_items == 0 {
2266            state.visible_count = 0;
2267            state.scroll_offset = 0;
2268            if let Some(heights) = state.heights.as_mut() {
2269                heights.clear();
2270            }
2271            return;
2272        }
2273
2274        let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
2275            self.render_variable(area, frame, state);
2276            return;
2277        };
2278
2279        // Reserve space for scrollbar if needed
2280        let fixed_h = fixed_h.max(1);
2281        // Use div_ceil to include partially visible items and avoid 0 count for large items
2282        let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
2283        let fully_visible_items = (area.height / fixed_h) as usize;
2284        let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
2285        let content_width = if needs_scrollbar {
2286            area.width.saturating_sub(1)
2287        } else {
2288            area.width
2289        };
2290
2291        // Ensure selection is within bounds
2292        if let Some(selected) = state.selected
2293            && selected >= total_items
2294        {
2295            // Use saturating_sub to handle empty list case (total_items = 0)
2296            state.selected = if total_items > 0 {
2297                Some(total_items - 1)
2298            } else {
2299                None
2300            };
2301        }
2302
2303        // Ensure visible range includes selected item (it must be fully visible if possible)
2304        if let Some(selected) = state.selected {
2305            let vis_count = fully_visible_items.max(1);
2306            if selected >= state.scroll_offset.saturating_add(vis_count) {
2307                state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
2308            } else if selected < state.scroll_offset {
2309                state.scroll_offset = selected;
2310            }
2311        }
2312
2313        // Clamp scroll offset
2314        let max_offset = if fully_visible_items > 0 {
2315            total_items.saturating_sub(fully_visible_items)
2316        } else {
2317            total_items.saturating_sub(1)
2318        };
2319        state.scroll_offset = state.scroll_offset.min(max_offset);
2320
2321        // Update visible count — use fully_visible_items (not items_per_viewport
2322        // which includes partial items via div_ceil) so scroll calculations
2323        // (page size, max_offset) use a consistent metric.
2324        state.visible_count = fully_visible_items.max(1).min(total_items);
2325
2326        // Calculate render range with overscan
2327        let render_start = state.scroll_offset.saturating_sub(state.overscan);
2328        let render_end = state
2329            .scroll_offset
2330            .saturating_add(items_per_viewport)
2331            .saturating_add(state.overscan)
2332            .min(total_items);
2333
2334        // Render visible items
2335        for idx in render_start..render_end {
2336            // Calculate Y position relative to viewport
2337            // Use relative arithmetic to prevent overflow when indices exceed i32::MAX.
2338            let relative_idx = if idx >= state.scroll_offset {
2339                i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
2340            } else {
2341                // Handle overscan items before the scroll offset
2342                -(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
2343            };
2344
2345            let height_i32 = i32::from(fixed_h);
2346            let y_offset = relative_idx.saturating_mul(height_i32);
2347
2348            // Skip items above viewport
2349            // We use area.y as the viewport top.
2350            // Absolute top of item = area.y + y_offset.
2351            // Absolute bottom of item = area.y + y_offset + height.
2352            // If absolute_bottom <= area.y, it is fully above.
2353            // i.e. y_offset + height <= 0
2354            if y_offset.saturating_add(height_i32) <= 0 {
2355                continue;
2356            }
2357
2358            // Stop if below viewport
2359            if y_offset >= i32::from(area.height) {
2360                break;
2361            }
2362
2363            // Check if item starts off-screen top.
2364            // If so, we must render partially by skipping the top rows.
2365            let skip_rows = if y_offset < 0 {
2366                y_offset.unsigned_abs() as u16
2367            } else {
2368                0
2369            };
2370
2371            // Calculate actual render area
2372            // Use i32 arithmetic to avoid overflow when casting y_offset to i16
2373            let y = i32::from(area.y)
2374                .saturating_add(y_offset)
2375                .clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
2376
2377            if y >= area.bottom() {
2378                break;
2379            }
2380
2381            let visible_height = fixed_h
2382                .saturating_sub(skip_rows)
2383                .min(area.bottom().saturating_sub(y));
2384
2385            if visible_height == 0 {
2386                continue;
2387            }
2388
2389            let row_area = Rect::new(area.x, y, content_width, visible_height);
2390
2391            let is_selected = state.selected == Some(idx);
2392
2393            let row_style = if is_selected {
2394                self.highlight_style.merge(&self.style)
2395            } else {
2396                self.style
2397            };
2398            clear_text_area(frame, row_area, row_style);
2399
2400            // Render the item
2401            self.items[idx].render(row_area, frame, is_selected, skip_rows);
2402        }
2403
2404        // Render scrollbar
2405        if needs_scrollbar {
2406            let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
2407
2408            let mut scrollbar_state =
2409                ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
2410
2411            // Sync drag anchor from persistent state to transient scrollbar state
2412            scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
2413
2414            let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
2415            if let Some(id) = self.hit_id {
2416                scrollbar = scrollbar.hit_id(id);
2417            }
2418            scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
2419        }
2420    }
2421}
2422
2423/// First item that starts at or after `offset` (the item containing
2424/// `offset` when it starts exactly there, the next one otherwise), clamped
2425/// to the last item.
2426fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
2427    let mut idx = heights.find_item_at_offset_exact(offset);
2428    if heights.offset_of_item_exact(idx) < offset {
2429        idx += 1;
2430    }
2431    idx.min(heights.len().saturating_sub(1))
2432}
2433
2434/// Preserve exact row metrics when they fit, otherwise scale both thumb size
2435/// and scroll progress into the target's representable range. `capacity` is
2436/// usize::MAX in production and permits exercising the 32-bit boundary on a
2437/// 64-bit test host. Independent saturation of position and total loses the
2438/// scroll ratio and can put a halfway-scrolled list's thumb at the bottom.
2439fn scrollbar_state_for_rows(
2440    total: u64,
2441    position: u64,
2442    viewport: u16,
2443    capacity: usize,
2444) -> ScrollbarState {
2445    let limit = capacity as u64;
2446    if total <= limit {
2447        return ScrollbarState::new(
2448            total as usize,
2449            position.min(total) as usize,
2450            viewport.into(),
2451        );
2452    }
2453    let scaled_viewport = (u128::from(viewport) * u128::from(limit))
2454        .div_ceil(u128::from(total))
2455        .min(u128::from(limit)) as usize;
2456    let max_position = total.saturating_sub(u64::from(viewport));
2457    let scaled_position = if max_position == 0 {
2458        0
2459    } else {
2460        (u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
2461            / u128::from(max_position)) as usize
2462    };
2463    ScrollbarState::new(capacity, scaled_position, scaled_viewport)
2464}
2465
2466impl<T: RenderItem> VirtualizedList<'_, T> {
2467    /// Render in [`ListHeightMode::Variable`]: every row is as tall as
2468    /// [`RenderItem::height`] reports. The rows that can matter this frame
2469    /// (the selection, one screenful from the scroll offset and the last
2470    /// screenful) are measured
2471    /// into the state's Fenwick tracker first, so the selection adjustment,
2472    /// the bottom clamp and the scrollbar all work in rows with O(log n)
2473    /// offset queries instead of multiplying by a fixed height.
2474    fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
2475        let total_items = self.items.len();
2476        let viewport = area.height;
2477        let heights = state
2478            .heights
2479            .get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
2480        if heights.len() != total_items {
2481            heights.resize(total_items);
2482        }
2483        if heights.categories_synced_len != total_items {
2484            heights.set_categories(self.items.iter().map(RenderItem::category));
2485        }
2486
2487        let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
2488            let height = self.items[idx].height().max(1);
2489            if !heights.is_measured(idx) || heights.get(idx) != height {
2490                heights.set_in_category(idx, height, self.items[idx].category());
2491            }
2492        };
2493        // Measure rows from `start` until they fill the viewport; returns how
2494        // many rows that took (at least one).
2495        let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
2496            let mut rows = 0u16;
2497            let mut idx = start;
2498            while idx < total_items && rows < viewport {
2499                measure(heights, idx);
2500                rows = rows.saturating_add(heights.get(idx));
2501                idx += 1;
2502            }
2503            (idx - start).max(1)
2504        };
2505
2506        // Keep the selection in range and in view.
2507        if let Some(selected) = state.selected
2508            && selected >= total_items
2509        {
2510            state.selected = Some(total_items - 1);
2511        }
2512        if let Some(selected) = state.selected {
2513            measure(heights, selected);
2514            if selected < state.scroll_offset {
2515                state.scroll_offset = selected;
2516            } else {
2517                measure_screenful(heights, state.scroll_offset);
2518                let mut sel_rows = 0u16;
2519                for idx in (0..=selected).rev() {
2520                    if sel_rows >= viewport {
2521                        break;
2522                    }
2523                    measure(heights, idx);
2524                    sel_rows = sel_rows.saturating_add(heights.get(idx));
2525                }
2526                heights.refresh_category_predictions();
2527                let top = heights.offset_of_item_exact(state.scroll_offset);
2528                let bottom = heights.offset_of_item_exact(selected + 1);
2529                if bottom.saturating_sub(top) > u64::from(viewport) {
2530                    let anchor = bottom.saturating_sub(u64::from(viewport));
2531                    state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
2532                }
2533            }
2534        }
2535
2536        // Clamp so the last screenful is as full as item alignment allows.
2537        // Measure that screenful first: an unmeasured tail counts at the
2538        // default height and would clamp a scroll to the end short of it.
2539        let mut tail_rows = 0u16;
2540        for idx in (0..total_items).rev() {
2541            if tail_rows >= viewport {
2542                break;
2543            }
2544            measure(heights, idx);
2545            tail_rows = tail_rows.saturating_add(heights.get(idx));
2546        }
2547        heights.refresh_category_predictions();
2548        let total_height = heights.total_height_exact();
2549        let max_start = if total_height > u64::from(viewport) {
2550            first_item_from_offset(heights, total_height - u64::from(viewport))
2551        } else {
2552            0
2553        };
2554        state.scroll_offset = state.scroll_offset.min(max_start);
2555
2556        let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
2557        heights.refresh_category_predictions();
2558        state.visible_count = visible;
2559
2560        let total_height = heights.total_height_exact();
2561        let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
2562        let content_width = if needs_scrollbar {
2563            area.width.saturating_sub(1)
2564        } else {
2565            area.width
2566        };
2567
2568        let mut y = 0u16;
2569        for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
2570        {
2571            if y >= viewport {
2572                break;
2573            }
2574            let row_h = heights.get(idx).min(viewport - y);
2575            if row_h == 0 {
2576                continue;
2577            }
2578            let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
2579            let is_selected = state.selected == Some(idx);
2580            let row_style = if is_selected {
2581                self.highlight_style.merge(&self.style)
2582            } else {
2583                self.style
2584            };
2585            clear_text_area(frame, row_area, row_style);
2586            self.items[idx].render(row_area, frame, is_selected, 0);
2587            y = y.saturating_add(row_h);
2588        }
2589
2590        if needs_scrollbar {
2591            let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
2592            let mut scrollbar_state = scrollbar_state_for_rows(
2593                total_height,
2594                heights.offset_of_item_exact(state.scroll_offset),
2595                viewport,
2596                usize::MAX,
2597            );
2598            scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
2599            let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
2600            if let Some(id) = self.hit_id {
2601                scrollbar = scrollbar.hit_id(id);
2602            }
2603            scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
2604        }
2605
2606        let widget_id = self.hit_id.map_or_else(
2607            || ftui_a11y::node::A11yNodeInfo::stable_id_for(ftui_a11y::node::A11yRole::List, area),
2608            |id| u64::from(id.id()),
2609        );
2610        let frame_idx = state.render_frame_idx;
2611        state.render_frame_idx = state.render_frame_idx.wrapping_add(1);
2612        if let Some(req) = state.remeasure_tick(frame_idx, widget_id) {
2613            frame.push_remeasure_request(req);
2614        }
2615    }
2616}
2617
2618// ============================================================================
2619// Simple RenderItem implementations for common types
2620// ============================================================================
2621
2622impl RenderItem for String {
2623    fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2624        if area.is_empty() {
2625            return;
2626        }
2627        let max_chars = area.width as usize;
2628        // String is assumed to be single-line in this implementation, so skip_rows > 0
2629        // implies the whole item is skipped. However, for robustness we check bounds.
2630        // If a String *did* contain newlines and we rendered it multiline, skip_rows would apply.
2631        // Here we just render the first line.
2632        if skip_rows > 0 {
2633            return;
2634        }
2635        for (i, ch) in self.chars().take(max_chars).enumerate() {
2636            frame
2637                .buffer
2638                .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2639        }
2640    }
2641}
2642
2643impl RenderItem for &str {
2644    fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2645        if area.is_empty() {
2646            return;
2647        }
2648        if skip_rows > 0 {
2649            return;
2650        }
2651        let max_chars = area.width as usize;
2652        for (i, ch) in self.chars().take(max_chars).enumerate() {
2653            frame
2654                .buffer
2655                .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2656        }
2657    }
2658}
2659
2660#[cfg(test)]
2661mod tests {
2662    use super::*;
2663    use proptest::prelude::*;
2664
2665    fn raw_row_text(frame: &Frame, y: u16) -> String {
2666        let width = frame.buffer.width();
2667        let mut actual = String::new();
2668        for x in 0..width {
2669            let ch = frame
2670                .buffer
2671                .get(x, y)
2672                .and_then(|cell| cell.content.as_char())
2673                .unwrap_or(' ');
2674            actual.push(ch);
2675        }
2676        actual
2677    }
2678
2679    #[test]
2680    fn test_new_virtualized() {
2681        let virt: Virtualized<String> = Virtualized::new(100);
2682        assert_eq!(virt.len(), 0);
2683        assert!(virt.is_empty());
2684    }
2685
2686    #[test]
2687    fn test_push_and_len() {
2688        let mut virt: Virtualized<i32> = Virtualized::new(100);
2689        virt.push(1);
2690        virt.push(2);
2691        virt.push(3);
2692        assert_eq!(virt.len(), 3);
2693        assert!(!virt.is_empty());
2694    }
2695
2696    #[test]
2697    fn test_visible_range_fixed_height() {
2698        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
2699        for i in 0..20 {
2700            virt.push(i);
2701        }
2702        // 10 items visible with height 2 in viewport 20
2703        let range = virt.visible_range(20);
2704        assert_eq!(range, 0..10);
2705    }
2706
2707    #[test]
2708    fn test_visible_range_variable_height_clamps() {
2709        let mut cache = HeightCache::new(1, 16);
2710        cache.set(0, 3);
2711        cache.set(1, 3);
2712        cache.set(2, 3);
2713        let mut virt: Virtualized<i32> =
2714            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2715        for i in 0..3 {
2716            virt.push(i);
2717        }
2718        let range = virt.visible_range(5);
2719        // Includes the partially visible second item.
2720        assert_eq!(range, 0..2);
2721    }
2722
2723    #[test]
2724    fn test_visible_range_variable_height_exact_fit() {
2725        let mut cache = HeightCache::new(1, 16);
2726        cache.set(0, 2);
2727        cache.set(1, 3);
2728        let mut virt: Virtualized<i32> =
2729            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2730        for i in 0..2 {
2731            virt.push(i);
2732        }
2733        let range = virt.visible_range(5);
2734        assert_eq!(range, 0..2);
2735    }
2736
2737    #[test]
2738    fn test_visible_range_with_scroll() {
2739        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
2740        for i in 0..50 {
2741            virt.push(i);
2742        }
2743        virt.scroll(10);
2744        let range = virt.visible_range(10);
2745        assert_eq!(range, 10..20);
2746    }
2747
2748    #[test]
2749    fn test_visible_range_variable_height_excludes_partial() {
2750        let mut cache = HeightCache::new(1, 16);
2751        cache.set(0, 6);
2752        cache.set(1, 6);
2753        let mut virt: Virtualized<i32> =
2754            Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2755        virt.push(1);
2756        virt.push(2);
2757        virt.push(3);
2758
2759        let range = virt.visible_range(10);
2760        // Includes the partially visible second item.
2761        assert_eq!(range, 0..2);
2762    }
2763
2764    #[test]
2765    fn test_visible_range_variable_height_exact_fit_larger() {
2766        let mut cache = HeightCache::new(1, 16);
2767        cache.set(0, 4);
2768        cache.set(1, 6);
2769        let mut virt: Virtualized<i32> =
2770            Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2771        virt.push(1);
2772        virt.push(2);
2773        virt.push(3);
2774
2775        let range = virt.visible_range(10);
2776        assert_eq!(range, 0..2);
2777    }
2778
2779    #[test]
2780    fn test_visible_range_variable_height_default_for_unmeasured() {
2781        let cache = HeightCache::new(2, 16);
2782        let mut virt: Virtualized<i32> =
2783            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2784        for i in 0..3 {
2785            virt.push(i);
2786        }
2787
2788        // Default height = 2, viewport 5 fits 2 items (2 + 2) but not the third.
2789        let range = virt.visible_range(5);
2790        // Includes the partially visible third item.
2791        assert_eq!(range, 0..3);
2792    }
2793
2794    #[test]
2795    fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
2796        let mut virt: Virtualized<i32> =
2797            Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2798        for i in 0..20 {
2799            virt.push(i);
2800        }
2801        // Viewport unknown (visible_count = 0): scroll_to_bottom stores the
2802        // lazy sentinel. The last screenful is 5 items of height 2.
2803        virt.scroll_to_bottom();
2804        assert_eq!(virt.visible_range(10), 15..20);
2805    }
2806
2807    #[test]
2808    fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
2809        let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
2810        for i in 0..20 {
2811            virt.push(i);
2812        }
2813        // Regression: this used to return the empty range 20..20 because the
2814        // unclamped sentinel offset reached the tracker as start_idx == len.
2815        virt.scroll_to_bottom();
2816        assert_eq!(virt.visible_range(10), 15..20);
2817    }
2818
2819    #[test]
2820    fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
2821        // Heights [3,2,5,1,4]: the last 5 rows are exactly items 3 (h=1) and
2822        // 4 (h=4); a 6-row viewport additionally clips into item 2.
2823        let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
2824        let mut virt: Virtualized<i32> =
2825            Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
2826        for i in 0..5 {
2827            virt.push(i);
2828        }
2829        virt.scroll_to_bottom();
2830        assert_eq!(virt.visible_range(5), 3..5);
2831        virt.scroll_to_bottom();
2832        assert_eq!(virt.visible_range(6), 2..5);
2833    }
2834
2835    #[test]
2836    fn test_visible_range_variable_near_end_clamps_like_fixed() {
2837        // Scrolling to the last item must not leave blank rows below it,
2838        // matching the Fixed arm's max_offset clamping.
2839        let mut virt: Virtualized<i32> =
2840            Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2841        for i in 0..20 {
2842            virt.push(i);
2843        }
2844        virt.scroll_to(18);
2845        assert_eq!(virt.visible_range(10), 15..20);
2846    }
2847
2848    #[test]
2849    fn test_render_range_with_overscan() {
2850        let mut virt: Virtualized<i32> =
2851            Virtualized::new(100).with_fixed_height(1).with_overscan(2);
2852        for i in 0..50 {
2853            virt.push(i);
2854        }
2855        virt.scroll(10);
2856        let range = virt.render_range(10);
2857        // Visible: 10..20, Overscan: 2
2858        // Render: 8..22
2859        assert_eq!(range, 8..22);
2860    }
2861
2862    #[test]
2863    fn test_scroll_bounds() {
2864        let mut virt: Virtualized<i32> = Virtualized::new(100);
2865        for i in 0..10 {
2866            virt.push(i);
2867        }
2868
2869        // Can't scroll negative
2870        virt.scroll(-100);
2871        assert_eq!(virt.scroll_offset(), 0);
2872
2873        // Can't scroll past end
2874        virt.scroll(100);
2875        assert_eq!(virt.scroll_offset(), 9);
2876    }
2877
2878    #[test]
2879    fn test_scroll_to() {
2880        let mut virt: Virtualized<i32> = Virtualized::new(100);
2881        for i in 0..20 {
2882            virt.push(i);
2883        }
2884
2885        virt.scroll_to(15);
2886        assert_eq!(virt.scroll_offset(), 15);
2887
2888        // Clamps to max
2889        virt.scroll_to(100);
2890        assert_eq!(virt.scroll_offset(), 19);
2891    }
2892
2893    #[test]
2894    fn test_follow_mode() {
2895        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
2896        virt.set_visible_count(5);
2897
2898        for i in 0..10 {
2899            virt.push(i);
2900        }
2901
2902        // Should be at bottom
2903        assert!(virt.is_at_bottom());
2904
2905        // Manual scroll disables follow
2906        virt.scroll(-5);
2907        assert!(!virt.follow_mode());
2908    }
2909
2910    #[test]
2911    fn test_scroll_to_start_and_end() {
2912        let mut virt: Virtualized<i32> = Virtualized::new(100);
2913        virt.set_visible_count(5);
2914        for i in 0..20 {
2915            virt.push(i);
2916        }
2917
2918        // scroll_to_start goes to top and disables follow
2919        virt.scroll_to(10);
2920        virt.set_follow(true);
2921        virt.scroll_to_start();
2922        assert_eq!(virt.scroll_offset(), 0);
2923        assert!(!virt.follow_mode());
2924
2925        // scroll_to_end goes to bottom and enables follow
2926        virt.scroll_to_end();
2927        assert!(virt.is_at_bottom());
2928        assert!(virt.follow_mode());
2929    }
2930
2931    #[test]
2932    fn test_virtualized_page_navigation() {
2933        let mut virt: Virtualized<i32> = Virtualized::new(100);
2934        virt.set_visible_count(5);
2935        for i in 0..30 {
2936            virt.push(i);
2937        }
2938
2939        virt.scroll_to(15);
2940        virt.page_up();
2941        // Page navigation keeps 1 row of context (visible_count - 1).
2942        assert_eq!(virt.scroll_offset(), 11);
2943
2944        virt.page_down();
2945        assert_eq!(virt.scroll_offset(), 15);
2946
2947        // Page up at start clamps to 0
2948        virt.scroll_to(2);
2949        virt.page_up();
2950        assert_eq!(virt.scroll_offset(), 0);
2951    }
2952
2953    #[test]
2954    fn test_height_cache() {
2955        let mut cache = HeightCache::new(1, 100);
2956
2957        // Default value
2958        assert_eq!(cache.get(0), 1);
2959        assert_eq!(cache.get(50), 1);
2960
2961        // Set value
2962        cache.set(5, 3);
2963        assert_eq!(cache.get(5), 3);
2964
2965        // Other indices still default
2966        assert_eq!(cache.get(4), 1);
2967        assert_eq!(cache.get(6), 1);
2968    }
2969
2970    #[test]
2971    fn test_height_cache_large_index_window() {
2972        let mut cache = HeightCache::new(1, 8);
2973        cache.set(10_000, 4);
2974        assert_eq!(cache.get(10_000), 4);
2975        assert_eq!(cache.get(0), 1);
2976        assert!(cache.cache.len() <= cache.capacity);
2977    }
2978
2979    #[test]
2980    fn test_clear() {
2981        let mut virt: Virtualized<i32> = Virtualized::new(100);
2982        for i in 0..10 {
2983            virt.push(i);
2984        }
2985        virt.scroll(5);
2986
2987        virt.clear();
2988        assert_eq!(virt.len(), 0);
2989        assert_eq!(virt.scroll_offset(), 0);
2990    }
2991
2992    #[test]
2993    fn test_get_item() {
2994        let mut virt: Virtualized<String> = Virtualized::new(100);
2995        virt.push("hello".to_string());
2996        virt.push("world".to_string());
2997
2998        assert_eq!(virt.get(0), Some(&"hello".to_string()));
2999        assert_eq!(virt.get(1), Some(&"world".to_string()));
3000        assert_eq!(virt.get(2), None);
3001    }
3002
3003    #[test]
3004    fn test_external_storage_len() {
3005        let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
3006        assert_eq!(virt.len(), 1000);
3007
3008        virt.set_external_len(2000);
3009        assert_eq!(virt.len(), 2000);
3010    }
3011
3012    #[test]
3013    fn test_momentum_scrolling() {
3014        let mut virt: Virtualized<i32> = Virtualized::new(100);
3015        for i in 0..50 {
3016            virt.push(i);
3017        }
3018
3019        virt.fling(10.0);
3020
3021        // Simulate tick
3022        virt.tick(Duration::from_millis(100));
3023
3024        // Should have scrolled
3025        assert!(virt.scroll_offset() > 0);
3026    }
3027
3028    // ========================================================================
3029    // VirtualizedListState tests
3030    // ========================================================================
3031
3032    #[test]
3033    fn test_virtualized_list_state_new() {
3034        let state = VirtualizedListState::new();
3035        assert_eq!(state.selected, None);
3036        assert_eq!(state.scroll_offset(), 0);
3037        assert_eq!(state.visible_count(), 0);
3038    }
3039
3040    #[test]
3041    fn test_virtualized_list_state_select_next() {
3042        let mut state = VirtualizedListState::new();
3043
3044        state.select_next(10);
3045        assert_eq!(state.selected, Some(0));
3046
3047        state.select_next(10);
3048        assert_eq!(state.selected, Some(1));
3049
3050        // At last item, stays there
3051        state.selected = Some(9);
3052        state.select_next(10);
3053        assert_eq!(state.selected, Some(9));
3054    }
3055
3056    #[test]
3057    fn test_virtualized_list_state_select_previous() {
3058        let mut state = VirtualizedListState::new();
3059        state.selected = Some(5);
3060
3061        state.select_previous(10);
3062        assert_eq!(state.selected, Some(4));
3063
3064        state.selected = Some(0);
3065        state.select_previous(10);
3066        assert_eq!(state.selected, Some(0));
3067    }
3068
3069    #[test]
3070    fn test_virtualized_list_state_scroll() {
3071        let mut state = VirtualizedListState::new();
3072
3073        state.scroll(5, 20);
3074        assert_eq!(state.scroll_offset(), 5);
3075
3076        state.scroll(-3, 20);
3077        assert_eq!(state.scroll_offset(), 2);
3078
3079        // Can't scroll negative
3080        state.scroll(-100, 20);
3081        assert_eq!(state.scroll_offset(), 0);
3082
3083        // Can't scroll past end
3084        state.scroll(100, 20);
3085        assert_eq!(state.scroll_offset(), 19);
3086    }
3087
3088    #[test]
3089    fn test_virtualized_list_state_follow_mode() {
3090        let mut state = VirtualizedListState::new().with_follow(true);
3091        assert!(state.follow_mode());
3092
3093        // Manual scroll disables follow
3094        state.scroll(5, 20);
3095        assert!(!state.follow_mode());
3096    }
3097
3098    #[test]
3099    fn test_render_item_string() {
3100        // Verify String implements RenderItem
3101        let s = String::from("hello");
3102        assert_eq!(s.height(), 1);
3103    }
3104
3105    #[test]
3106    fn test_page_up_down() {
3107        let mut virt: Virtualized<i32> = Virtualized::new(100);
3108        for i in 0..50 {
3109            virt.push(i);
3110        }
3111        virt.set_visible_count(10);
3112
3113        // Start at top
3114        assert_eq!(virt.scroll_offset(), 0);
3115
3116        // Page down
3117        virt.page_down();
3118        assert_eq!(virt.scroll_offset(), 9);
3119
3120        // Page down again
3121        virt.page_down();
3122        assert_eq!(virt.scroll_offset(), 18);
3123
3124        // Page up
3125        virt.page_up();
3126        assert_eq!(virt.scroll_offset(), 9);
3127
3128        // Page up again
3129        virt.page_up();
3130        assert_eq!(virt.scroll_offset(), 0);
3131
3132        // Page up at top stays at 0
3133        virt.page_up();
3134        assert_eq!(virt.scroll_offset(), 0);
3135    }
3136
3137    // ========================================================================
3138    // Performance invariant tests (bd-uo6v)
3139    // ========================================================================
3140
3141    #[test]
3142    fn test_render_scales_with_visible_not_total() {
3143        use ftui_render::grapheme_pool::GraphemePool;
3144        use std::time::Instant;
3145
3146        // Setup: VirtualizedList with 1K items
3147        let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
3148        let small_list = VirtualizedList::new(&small_items);
3149        let mut small_state = VirtualizedListState::new();
3150
3151        let area = Rect::new(0, 0, 80, 24);
3152        let mut pool = GraphemePool::new();
3153        let mut frame = Frame::new(80, 24, &mut pool);
3154
3155        // Warm up
3156        small_list.render(area, &mut frame, &mut small_state);
3157
3158        let start = Instant::now();
3159        for _ in 0..100 {
3160            frame.buffer.clear();
3161            small_list.render(area, &mut frame, &mut small_state);
3162        }
3163        let small_time = start.elapsed();
3164
3165        // Setup: VirtualizedList with 100K items
3166        let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
3167        let large_list = VirtualizedList::new(&large_items);
3168        let mut large_state = VirtualizedListState::new();
3169
3170        // Warm up
3171        large_list.render(area, &mut frame, &mut large_state);
3172
3173        let start = Instant::now();
3174        for _ in 0..100 {
3175            frame.buffer.clear();
3176            large_list.render(area, &mut frame, &mut large_state);
3177        }
3178        let large_time = start.elapsed();
3179
3180        // 100K should be within 3x of 1K (both render ~24 items)
3181        assert!(
3182            large_time < small_time * 3,
3183            "Render does not scale O(visible): 1K={:?}, 100K={:?}",
3184            small_time,
3185            large_time
3186        );
3187    }
3188
3189    #[test]
3190    fn test_scroll_is_constant_time() {
3191        use std::time::Instant;
3192
3193        let mut small: Virtualized<i32> = Virtualized::new(1_000);
3194        for i in 0..1_000 {
3195            small.push(i);
3196        }
3197        small.set_visible_count(24);
3198
3199        let mut large: Virtualized<i32> = Virtualized::new(100_000);
3200        for i in 0..100_000 {
3201            large.push(i);
3202        }
3203        large.set_visible_count(24);
3204
3205        let iterations = 10_000;
3206
3207        // Warm up both paths so the timed runs are not skewed by first-touch
3208        // page faults / branch predictor / cache warming.
3209        for _ in 0..iterations {
3210            small.scroll(1);
3211            small.scroll(-1);
3212            large.scroll(1);
3213            large.scroll(-1);
3214        }
3215
3216        // Take the best (minimum) of several timed runs for each list. The
3217        // minimum is the measurement least contaminated by scheduling jitter,
3218        // GC of other processes, and CI load — exactly the noise that made the
3219        // old single-shot comparison flaky.
3220        let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
3221            let runs = 5;
3222            let mut best = std::time::Duration::MAX;
3223            for _ in 0..runs {
3224                let start = Instant::now();
3225                for _ in 0..iterations {
3226                    v.scroll(1);
3227                    v.scroll(-1);
3228                }
3229                best = best.min(start.elapsed());
3230            }
3231            best
3232        };
3233
3234        let small_time = measure(&mut small);
3235        let large_time = measure(&mut large);
3236
3237        // The real signal we care about is "scroll cost does NOT grow with list
3238        // size" (i.e. it is O(1), not O(n)). With n differing by 100x, a truly
3239        // O(n) scroll would make `large_time` ~100x `small_time`. A generous
3240        // constant-factor ceiling distinguishes O(1) from O(n) without flaking
3241        // on scheduling jitter, so we allow a wide multiplier here.
3242        let ceiling = small_time
3243            .checked_mul(10)
3244            .unwrap_or(std::time::Duration::MAX);
3245        assert!(
3246            large_time < ceiling,
3247            "Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
3248            small_time,
3249            large_time
3250        );
3251    }
3252
3253    #[test]
3254    fn render_partially_offscreen_top_skips_item() {
3255        use ftui_render::grapheme_pool::GraphemePool;
3256
3257        // Items with height 2, each rendering its index as a character
3258        struct IndexedItem(usize);
3259        impl RenderItem for IndexedItem {
3260            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
3261                let ch = char::from_digit(self.0 as u32, 10).unwrap();
3262                for y in area.y..area.bottom() {
3263                    frame.buffer.set(area.x, y, Cell::from_char(ch));
3264                }
3265            }
3266            fn height(&self) -> u16 {
3267                2
3268            }
3269        }
3270
3271        // Need 4+ items so scroll_offset=1 is valid:
3272        // items_per_viewport = 5/2 = 2, max_offset = 4-2 = 2
3273        let items = vec![
3274            IndexedItem(0),
3275            IndexedItem(1),
3276            IndexedItem(2),
3277            IndexedItem(3),
3278        ];
3279        let list = VirtualizedList::new(&items).fixed_height(2);
3280
3281        // Scroll so item 1 is at top, item 0 is in overscan (above viewport)
3282        let mut state = VirtualizedListState::new().with_overscan(1);
3283        state.scroll_offset = 1; // Item 1 is top visible. Item 0 is in overscan.
3284
3285        let mut pool = GraphemePool::new();
3286        let mut frame = Frame::new(10, 5, &mut pool);
3287
3288        // Render at y=0 (terminal top edge)
3289        list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
3290
3291        // With scroll_offset=1 and overscan=1:
3292        // - render_start = 1 - 1 = 0 (include item 0 in overscan)
3293        // - Item 0 would render at y_offset = (0-1)*2 = -2
3294        // - area.y + y_offset = 0 + (-2) = -2 < 0, so item 0 must be SKIPPED
3295        // - Item 1 renders at y_offset = (1-1)*2 = 0
3296        //
3297        // Row 0 should be '1' (from Item 1), NOT '0' (from Item 0 ghosting)
3298        let cell = frame.buffer.get(0, 0).unwrap();
3299        assert_eq!(cell.content.as_char(), Some('1'));
3300    }
3301
3302    #[test]
3303    fn render_bottom_boundary_clips_partial_item() {
3304        use ftui_render::grapheme_pool::GraphemePool;
3305
3306        struct IndexedItem(u16);
3307        impl RenderItem for IndexedItem {
3308            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
3309                let ch = char::from_digit(self.0 as u32, 10).unwrap();
3310                for y in area.y..area.bottom() {
3311                    frame.buffer.set(area.x, y, Cell::from_char(ch));
3312                }
3313            }
3314            fn height(&self) -> u16 {
3315                2
3316            }
3317        }
3318
3319        let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
3320        let list = VirtualizedList::new(&items)
3321            .fixed_height(2)
3322            .show_scrollbar(false);
3323        let mut state = VirtualizedListState::new();
3324
3325        let mut pool = GraphemePool::new();
3326        let mut frame = Frame::new(4, 4, &mut pool);
3327
3328        // Viewport height 3 means the second item is only partially visible.
3329        list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
3330
3331        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
3332        assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
3333        assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
3334        // Row outside the viewport should remain empty.
3335        assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
3336    }
3337
3338    #[test]
3339    fn render_after_fling_advances_visible_rows() {
3340        use ftui_render::grapheme_pool::GraphemePool;
3341
3342        struct IndexedItem(u16);
3343        impl RenderItem for IndexedItem {
3344            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
3345                let ch = char::from_digit(self.0 as u32, 10).unwrap();
3346                for y in area.y..area.bottom() {
3347                    frame.buffer.set(area.x, y, Cell::from_char(ch));
3348                }
3349            }
3350        }
3351
3352        let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
3353        let list = VirtualizedList::new(&items)
3354            .fixed_height(1)
3355            .show_scrollbar(false);
3356        let mut state = VirtualizedListState::new();
3357
3358        let mut pool = GraphemePool::new();
3359        let mut frame = Frame::new(4, 3, &mut pool);
3360        let area = Rect::new(0, 0, 4, 3);
3361
3362        // Initial render establishes visible_count and baseline top row.
3363        list.render(area, &mut frame, &mut state);
3364        assert_eq!(state.scroll_offset(), 0);
3365        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
3366
3367        // Momentum scroll: 40.0 * 0.1s = 4 rows.
3368        state.fling(40.0);
3369        state.tick(Duration::from_millis(100), items.len());
3370        assert_eq!(state.scroll_offset(), 4);
3371
3372        frame.buffer.clear();
3373        list.render(area, &mut frame, &mut state);
3374        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
3375    }
3376
3377    #[test]
3378    fn render_empty_virtualized_list_clears_stale_viewport() {
3379        use ftui_render::grapheme_pool::GraphemePool;
3380
3381        let items: Vec<String> = Vec::new();
3382        let list = VirtualizedList::new(&items).show_scrollbar(false);
3383        let mut state = VirtualizedListState::new();
3384        let mut pool = GraphemePool::new();
3385        let mut frame = Frame::new(6, 3, &mut pool);
3386        let area = Rect::new(0, 0, 6, 3);
3387        frame.buffer.fill(area, Cell::from_char('X'));
3388
3389        list.render(area, &mut frame, &mut state);
3390
3391        assert_eq!(raw_row_text(&frame, 0), "      ");
3392        assert_eq!(raw_row_text(&frame, 1), "      ");
3393        assert_eq!(raw_row_text(&frame, 2), "      ");
3394    }
3395
3396    #[test]
3397    fn render_shorter_virtualized_row_clears_stale_suffix() {
3398        use ftui_render::grapheme_pool::GraphemePool;
3399
3400        let long_items = vec!["Hello".to_string()];
3401        let short_items = vec!["Hi".to_string()];
3402        let area = Rect::new(0, 0, 6, 1);
3403        let mut state = VirtualizedListState::new();
3404        let mut pool = GraphemePool::new();
3405        let mut frame = Frame::new(6, 1, &mut pool);
3406
3407        VirtualizedList::new(&long_items)
3408            .show_scrollbar(false)
3409            .render(area, &mut frame, &mut state);
3410        VirtualizedList::new(&short_items)
3411            .show_scrollbar(false)
3412            .render(area, &mut frame, &mut state);
3413
3414        assert_eq!(raw_row_text(&frame, 0), "Hi    ");
3415    }
3416
3417    #[test]
3418    fn test_memory_bounded_by_ring_capacity() {
3419        use crate::log_ring::LogRing;
3420
3421        let mut ring: LogRing<String> = LogRing::new(1_000);
3422
3423        // Add 100K items
3424        for i in 0..100_000 {
3425            ring.push(format!("Line {}", i));
3426        }
3427
3428        // Only 1K in memory
3429        assert_eq!(ring.len(), 1_000);
3430        assert_eq!(ring.total_count(), 100_000);
3431        assert_eq!(ring.first_index(), 99_000);
3432
3433        // Can still access recent items
3434        assert!(ring.get(99_999).is_some());
3435        assert!(ring.get(99_000).is_some());
3436        // Old items evicted
3437        assert!(ring.get(0).is_none());
3438        assert!(ring.get(98_999).is_none());
3439    }
3440
3441    #[test]
3442    fn test_visible_range_constant_regardless_of_total() {
3443        let mut small: Virtualized<i32> = Virtualized::new(100);
3444        for i in 0..100 {
3445            small.push(i);
3446        }
3447        let small_range = small.visible_range(24);
3448
3449        let mut large: Virtualized<i32> = Virtualized::new(100_000);
3450        for i in 0..100_000 {
3451            large.push(i);
3452        }
3453        let large_range = large.visible_range(24);
3454
3455        // Both should return exactly 24 visible items
3456        assert_eq!(small_range.end - small_range.start, 24);
3457        assert_eq!(large_range.end - large_range.start, 24);
3458    }
3459
3460    #[test]
3461    fn test_virtualized_list_state_page_up_down() {
3462        let mut state = VirtualizedListState::new();
3463        state.visible_count = 10;
3464
3465        // Page down
3466        state.page_down(50);
3467        assert_eq!(state.scroll_offset(), 9);
3468
3469        // Page down again
3470        state.page_down(50);
3471        assert_eq!(state.scroll_offset(), 18);
3472
3473        // Page up
3474        state.page_up(50);
3475        assert_eq!(state.scroll_offset(), 9);
3476
3477        // Page up again
3478        state.page_up(50);
3479        assert_eq!(state.scroll_offset(), 0);
3480    }
3481
3482    // ========================================================================
3483    // VariableHeightsFenwick tests (bd-2zbk.7)
3484    // ========================================================================
3485
3486    #[test]
3487    fn test_variable_heights_fenwick_new() {
3488        let tracker = VariableHeightsFenwick::new(2, 10);
3489        assert_eq!(tracker.len(), 10);
3490        assert!(!tracker.is_empty());
3491        assert_eq!(tracker.default_height(), 2);
3492    }
3493
3494    #[test]
3495    fn test_variable_heights_fenwick_empty() {
3496        let tracker = VariableHeightsFenwick::new(1, 0);
3497        assert!(tracker.is_empty());
3498        assert_eq!(tracker.total_height(), 0);
3499    }
3500
3501    #[test]
3502    fn test_variable_heights_fenwick_from_heights() {
3503        let heights = vec![3, 2, 5, 1, 4];
3504        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3505
3506        assert_eq!(tracker.len(), 5);
3507        assert_eq!(tracker.get(0), 3);
3508        assert_eq!(tracker.get(1), 2);
3509        assert_eq!(tracker.get(2), 5);
3510        assert_eq!(tracker.get(3), 1);
3511        assert_eq!(tracker.get(4), 4);
3512        assert_eq!(tracker.total_height(), 15);
3513    }
3514
3515    #[test]
3516    fn test_variable_heights_fenwick_offset_of_item() {
3517        // Heights: [3, 2, 5, 1, 4] -> offsets: [0, 3, 5, 10, 11]
3518        let heights = vec![3, 2, 5, 1, 4];
3519        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3520
3521        assert_eq!(tracker.offset_of_item(0), 0);
3522        assert_eq!(tracker.offset_of_item(1), 3);
3523        assert_eq!(tracker.offset_of_item(2), 5);
3524        assert_eq!(tracker.offset_of_item(3), 10);
3525        assert_eq!(tracker.offset_of_item(4), 11);
3526        assert_eq!(tracker.offset_of_item(5), 15); // beyond end
3527    }
3528
3529    #[test]
3530    fn test_variable_heights_fenwick_find_item_at_offset() {
3531        // Heights: [3, 2, 5, 1, 4] -> cumulative: [3, 5, 10, 11, 15]
3532        let heights = vec![3, 2, 5, 1, 4];
3533        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3534
3535        // Offset 0 should be item 0
3536        assert_eq!(tracker.find_item_at_offset(0), 0);
3537        // Offset 1 should be item 0 (within first item)
3538        assert_eq!(tracker.find_item_at_offset(1), 0);
3539        // Offset 3 should be item 1 (starts at offset 3)
3540        assert_eq!(tracker.find_item_at_offset(3), 1);
3541        // Offset 5 should be item 2
3542        assert_eq!(tracker.find_item_at_offset(5), 2);
3543        // Offset 10 should be item 3
3544        assert_eq!(tracker.find_item_at_offset(10), 3);
3545        // Offset 11 should be item 4
3546        assert_eq!(tracker.find_item_at_offset(11), 4);
3547        // Offset 15 should be end (beyond all items)
3548        assert_eq!(tracker.find_item_at_offset(15), 5);
3549    }
3550
3551    #[test]
3552    fn fenwick_large_height_totals_do_not_wrap() {
3553        let heights = vec![u16::MAX; 131_072];
3554        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3555        let offset = 4_294_836_224_u32;
3556        assert_eq!(
3557            tracker.find_item_at_offset(offset),
3558            (u64::from(offset) / u64::from(u16::MAX)) as usize,
3559            "a wrapped root aggregate must not skip the entire list"
3560        );
3561        assert_eq!(tracker.total_height(), u32::MAX);
3562        assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
3563    }
3564
3565    #[test]
3566    #[should_panic(expected = "height index exceeds usize")]
3567    fn fenwick_rejects_unrepresentable_index() {
3568        VariableHeightsFenwick::default().set(usize::MAX, 1);
3569    }
3570
3571    #[test]
3572    fn fenwick_large_updates_and_resize_match_u64_oracle() {
3573        fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
3574            let mut prefixes = Vec::with_capacity(heights.len() + 1);
3575            prefixes.push(0u64);
3576            for &height in heights {
3577                prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
3578            }
3579            let total = prefixes.last().copied().unwrap();
3580            assert_eq!(tracker.len(), heights.len());
3581            assert_eq!(tracker.total_height_exact(), total);
3582            assert_eq!(
3583                tracker.total_height(),
3584                total.min(u64::from(u32::MAX)) as u32
3585            );
3586            let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
3587            for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
3588                assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
3589                assert_eq!(
3590                    tracker.offset_of_item(idx),
3591                    prefixes[idx].min(u64::from(u32::MAX)) as u32
3592                );
3593                queries.extend([
3594                    prefixes[idx].saturating_sub(1),
3595                    prefixes[idx],
3596                    prefixes[idx] + 1,
3597                ]);
3598            }
3599            for offset in queries {
3600                let expected = if offset == 0 {
3601                    0
3602                } else {
3603                    prefixes[1..].partition_point(|&prefix| prefix <= offset)
3604                };
3605                assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
3606                if let Ok(offset) = u32::try_from(offset) {
3607                    assert_eq!(tracker.find_item_at_offset(offset), expected);
3608                }
3609            }
3610        }
3611
3612        // The middle length totals exactly u32::MAX; neighboring lengths
3613        // exercise both sides of the public saturation boundary.
3614        for len in [65_536, 65_537, 65_538, 131_072] {
3615            let mut heights = vec![u16::MAX; len];
3616            let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
3617            check(&tracker, &heights);
3618            for idx in [0, 1, 32_768, 65_535, len - 1] {
3619                tracker.set(idx, 0);
3620                heights[idx] = 0;
3621                assert_eq!(tracker.get(idx), 0);
3622            }
3623            check(&tracker, &heights);
3624            tracker.set(0, u16::MAX);
3625            heights[0] = u16::MAX;
3626            tracker.resize(65_536);
3627            heights.truncate(65_536);
3628            check(&tracker, &heights);
3629            tracker.resize(65_540);
3630            heights.resize(65_540, u16::MAX);
3631            check(&tracker, &heights);
3632        }
3633
3634        // Deterministic varied heights and repeated signed updates exercise
3635        // aggregate values that uniform-height arithmetic alone cannot cover.
3636        let mut seed = 0xa076_1d64_78bd_642fu64;
3637        let mut heights: Vec<u16> = (0..131_072)
3638            .map(|_| {
3639                seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
3640                32_768 + ((seed >> 48) as u16 / 2)
3641            })
3642            .collect();
3643        let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3644        for idx in (0..heights.len()).step_by(997) {
3645            heights[idx] = (idx % 65_536) as u16;
3646            tracker.set(idx, heights[idx]);
3647            assert_eq!(tracker.get(idx), heights[idx]);
3648        }
3649        check(&tracker, &heights);
3650        tracker.drop_front(3);
3651        check(&tracker, &heights[3..]);
3652        heights.fill(u16::MAX);
3653        tracker.rebuild(&heights);
3654        check(&tracker, &heights);
3655        tracker.clear();
3656        check(&tracker, &[]);
3657        tracker.resize(4);
3658        check(&tracker, &[1; 4]);
3659    }
3660
3661    #[test]
3662    fn fenwick_large_visible_range_keeps_tail_reachable() {
3663        let len = 65_548;
3664        let mut virt: Virtualized<()> =
3665            Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
3666        for idx in 65_538..len {
3667            virt.observe_height(idx, 1);
3668        }
3669        virt.scroll_to_bottom();
3670        assert_eq!(virt.visible_range(5), len - 5..len);
3671        virt.scroll_to(len - 8);
3672        assert_eq!(virt.visible_range(5), len - 8..len - 3);
3673    }
3674
3675    #[test]
3676    fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
3677        fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
3678            let scrollbar =
3679                Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
3680            let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
3681            let mut frame = Frame::new(1, 21, &mut pool);
3682            scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
3683            (0..21)
3684                .filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
3685                .collect()
3686        }
3687
3688        // Execute the production scaling helper and real scrollbar renderer
3689        // with a simulated 32-bit capacity; this is not a wasm execution.
3690        let capacity = u32::MAX as usize;
3691        let total = 131_072 * u64::from(u16::MAX);
3692        let viewport = 20;
3693        let max_position = total - u64::from(viewport);
3694        for (position, expected_row) in [
3695            (0, 0),
3696            (max_position / 4, 5),
3697            (max_position / 2, 10),
3698            (max_position / 4 * 3, 15),
3699            (max_position, 20),
3700            (total, 20),
3701        ] {
3702            let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3703            assert_eq!(scaled.content_length, capacity);
3704            assert!(scaled.viewport_length > 0);
3705            assert_eq!(thumb_rows(scaled), vec![expected_row]);
3706        }
3707
3708        let position = u64::from(u32::MAX) + u64::from(u16::MAX);
3709        let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3710        assert_eq!(thumb_rows(scaled), vec![10]);
3711        // The former independent saturation gives the wrong actual geometry.
3712        let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
3713        assert_eq!(thumb_rows(saturated), vec![20]);
3714
3715        for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
3716            let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
3717            assert_eq!(exact.content_length, total as usize);
3718            assert_eq!(exact.position, position as usize);
3719            assert_eq!(exact.viewport_length, usize::from(viewport));
3720        }
3721        if usize::BITS > 32 {
3722            let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
3723            assert_eq!(exact.content_length as u64, total);
3724            assert_eq!(exact.position as u64, position);
3725            assert_eq!(exact.viewport_length, usize::from(viewport));
3726        }
3727    }
3728
3729    #[test]
3730    fn test_variable_heights_fenwick_visible_count() {
3731        // Heights: [3, 2, 5, 1, 4]
3732        let heights = vec![3, 2, 5, 1, 4];
3733        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3734
3735        // Viewport 5: items 0 (h=3) + 1 (h=2) = 5 exactly
3736        assert_eq!(tracker.visible_count(0, 5), 2);
3737
3738        // Viewport 4: item 0 fits and item 1 is partially visible.
3739        assert_eq!(tracker.visible_count(0, 4), 2);
3740
3741        // Viewport 10: items 0+1+2 = 10 exactly
3742        assert_eq!(tracker.visible_count(0, 10), 3);
3743
3744        // From item 2, viewport 6: item 2 (h=5) + item 3 (h=1) = 6
3745        assert_eq!(tracker.visible_count(2, 6), 2);
3746    }
3747
3748    #[test]
3749    fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
3750        let heights = vec![1, 1, 1];
3751        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3752
3753        // Viewport extends past the end: must never overcount.
3754        assert_eq!(tracker.visible_count(0, 10), 3);
3755        assert_eq!(tracker.visible_count(1, 10), 2);
3756        assert_eq!(tracker.visible_count(2, 10), 1);
3757    }
3758
3759    #[test]
3760    fn test_variable_heights_fenwick_set() {
3761        let mut tracker = VariableHeightsFenwick::new(1, 5);
3762
3763        // All items should start with default height
3764        assert_eq!(tracker.get(0), 1);
3765        assert_eq!(tracker.total_height(), 5);
3766
3767        // Set item 2 to height 10
3768        tracker.set(2, 10);
3769        assert_eq!(tracker.get(2), 10);
3770        assert_eq!(tracker.total_height(), 14); // 1+1+10+1+1
3771    }
3772
3773    #[test]
3774    fn test_variable_heights_fenwick_resize() {
3775        let mut tracker = VariableHeightsFenwick::new(2, 3);
3776        assert_eq!(tracker.len(), 3);
3777        assert_eq!(tracker.total_height(), 6);
3778
3779        // Grow
3780        tracker.resize(5);
3781        assert_eq!(tracker.len(), 5);
3782        assert_eq!(tracker.total_height(), 10);
3783        assert_eq!(tracker.get(4), 2);
3784
3785        // Shrink
3786        tracker.resize(2);
3787        assert_eq!(tracker.len(), 2);
3788        assert_eq!(tracker.total_height(), 4);
3789    }
3790
3791    #[test]
3792    fn test_variable_heights_fenwick_point_update_and_range_query() {
3793        fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
3794            tracker
3795                .offset_of_item(right.saturating_add(1))
3796                .saturating_sub(tracker.offset_of_item(left))
3797        }
3798
3799        let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
3800        let mut naive = [2_u32, 4, 1, 3, 5, 2];
3801
3802        tracker.set(2, 7);
3803        naive[2] = 7;
3804        tracker.set(5, 1);
3805        naive[5] = 1;
3806        tracker.set(0, 6);
3807        naive[0] = 6;
3808
3809        let mut running = 0u32;
3810        for (i, value) in naive.iter().enumerate() {
3811            running = running.saturating_add(*value);
3812            assert_eq!(tracker.offset_of_item(i + 1), running);
3813        }
3814
3815        let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
3816        assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
3817        assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
3818        assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
3819    }
3820
3821    proptest! {
3822        #![proptest_config(ProptestConfig::with_cases(96))]
3823
3824        #[test]
3825        fn property_measured_heights_survive_mutations(
3826            operations in proptest::collection::vec((0u8..3, 0usize..150, 1u16..32), 1..80)
3827        ) {
3828            let mut tracker = VariableHeightsFenwick::new(2, 0);
3829            let mut expected: Vec<Option<u16>> = Vec::new();
3830            for (operation, index, height) in operations {
3831                match operation {
3832                    0 => {
3833                        if index >= expected.len() {
3834                            expected.resize(index + 1, None);
3835                        }
3836                        expected[index] = Some(height);
3837                        tracker.set(index, height);
3838                    }
3839                    1 => {
3840                        expected.resize(index, None);
3841                        tracker.resize(index);
3842                    }
3843                    _ => {
3844                        expected.drain(..index.min(expected.len()));
3845                        tracker.drop_front(index);
3846                    }
3847                }
3848                prop_assert_eq!(tracker.len(), expected.len());
3849                prop_assert_eq!(
3850                    tracker.unmeasured_count(),
3851                    expected.iter().filter(|height| height.is_none()).count()
3852                );
3853                let mut prefix = 0;
3854                for (index, height) in expected.iter().enumerate() {
3855                    prop_assert_eq!(tracker.offset_of_item(index), prefix);
3856                    prop_assert_eq!(tracker.is_measured(index), height.is_some());
3857                    prop_assert_eq!(tracker.get(index), height.unwrap_or(2));
3858                    prefix += u32::from(height.unwrap_or(2));
3859                }
3860                prop_assert_eq!(tracker.total_height(), prefix);
3861            }
3862        }
3863
3864        #[test]
3865        fn property_variable_heights_fenwick_prefix_sums_match_naive(
3866            heights in proptest::collection::vec(1u16..=32u16, 1..160)
3867        ) {
3868            let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3869
3870            let mut naive_prefix = 0u32;
3871            prop_assert_eq!(tracker.offset_of_item(0), 0);
3872            for (i, height) in heights.iter().enumerate() {
3873                naive_prefix = naive_prefix.saturating_add(u32::from(*height));
3874                prop_assert_eq!(
3875                    tracker.offset_of_item(i + 1),
3876                    naive_prefix,
3877                    "prefix mismatch at index {} for heights {:?}",
3878                    i,
3879                    heights
3880                );
3881            }
3882        }
3883
3884        #[test]
3885        fn property_variable_heights_fenwick_visible_count_matches_naive(
3886            heights in proptest::collection::vec(1u16..=24u16, 1..128),
3887            start_idx in 0usize..192usize,
3888            viewport_height in 1u16..=120u16
3889        ) {
3890            fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
3891                if heights.is_empty() || viewport_height == 0 {
3892                    return 0;
3893                }
3894                let start = start_idx.min(heights.len());
3895                if start >= heights.len() {
3896                    return 0;
3897                }
3898
3899                let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
3900                let end_offset = start_offset.saturating_add(u32::from(viewport_height));
3901                let mut count = 0usize;
3902                let mut cursor = start_offset;
3903                for &height in &heights[start..] {
3904                    if cursor >= end_offset {
3905                        break;
3906                    }
3907                    count = count.saturating_add(1);
3908                    cursor = cursor.saturating_add(u32::from(height));
3909                }
3910
3911                if count == 0 { 1 } else { count }
3912            }
3913
3914            let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3915            let expected = naive_visible_count(&heights, start_idx, viewport_height);
3916            let actual = tracker.visible_count(start_idx, viewport_height);
3917            prop_assert_eq!(
3918                actual,
3919                expected,
3920                "visible_count mismatch for start={} viewport={} heights={:?}",
3921                start_idx,
3922                viewport_height,
3923                heights
3924            );
3925        }
3926    }
3927
3928    /// With a predictor attached, unmeasured slots follow the posterior mean
3929    /// of the measured rows (Normal-Normal update, prior κ₀=2 at μ₀=1) instead
3930    /// of the constant default, and measured slots are never touched.
3931    #[test]
3932    fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
3933        let config = PredictorConfig {
3934            default_height: 1,
3935            prior_mean: 1.0,
3936            prior_strength: 2.0,
3937            ..PredictorConfig::default()
3938        };
3939        let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
3940        assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
3941        assert_eq!(tracker.unmeasured_count(), 10);
3942        assert_eq!(tracker.total_height(), 10);
3943
3944        // Three rows measure 3 tall: posterior mean (2·1 + 3·3) / 5 = 2.2 → 2.
3945        for idx in 0..3 {
3946            tracker.set(idx, 3);
3947        }
3948        assert_eq!(tracker.predicted_height(), 2);
3949        assert_eq!(tracker.unmeasured_count(), 7);
3950        assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
3951        assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
3952        assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
3953        assert_eq!(tracker.offset_of_item(4), 9 + 2);
3954
3955        // Three more: (2·1 + 6·3) / 8 = 2.5 → 3; the unmeasured tail is refilled.
3956        for idx in 3..6 {
3957            tracker.set(idx, 3);
3958        }
3959        assert_eq!(tracker.predicted_height(), 3);
3960        assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
3961        assert!(tracker.is_measured(5) && !tracker.is_measured(6));
3962        assert_eq!(
3963            tracker.predictor().map(HeightPredictor::total_measurements),
3964            Some(6)
3965        );
3966
3967        // Growth uses the prediction, not the constructor default.
3968        tracker.resize(12);
3969        assert_eq!(tracker.get(11), 3);
3970        assert_eq!(tracker.unmeasured_count(), 6);
3971        assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
3972
3973        // Shrinking below measured rows keeps the bookkeeping consistent.
3974        tracker.resize(4);
3975        assert_eq!(tracker.unmeasured_count(), 0);
3976        tracker.resize(6);
3977        assert_eq!(tracker.unmeasured_count(), 2);
3978        assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
3979
3980        // Rebuild trains on every provided height and marks all as measured.
3981        tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
3982        assert_eq!(tracker.unmeasured_count(), 0);
3983        assert_eq!(tracker.total_height(), 40);
3984        assert!(
3985            tracker.predicted_height() >= 4,
3986            "posterior pulled toward the taller rows"
3987        );
3988
3989        // Without a predictor nothing changes: unmeasured slots stay at the default.
3990        let mut plain = VariableHeightsFenwick::new(2, 4);
3991        plain.set(0, 9);
3992        assert_eq!(plain.predicted_height(), 2);
3993        assert_eq!(plain.get(3), 2);
3994        assert_eq!(plain.unmeasured_count(), 3);
3995        assert!(plain.predictor().is_none());
3996    }
3997
3998    /// `Virtualized::with_height_prediction` switches to the Fenwick tracker
3999    /// and `observe_height` trains the model; fixed heights ignore it.
4000    #[test]
4001    fn virtualized_height_prediction_observe_height_trains_the_model() {
4002        let mut virt: Virtualized<i32> = Virtualized::new(100)
4003            .with_fixed_height(1)
4004            .with_height_prediction(PredictorConfig::default());
4005        assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
4006        assert_eq!(virt.unmeasured_item_height(), 1);
4007
4008        // Four rows of height 4: (2·1 + 4·4) / 6 = 3.
4009        for idx in 0..4 {
4010            virt.observe_height(idx, 4);
4011        }
4012        assert_eq!(virt.unmeasured_item_height(), 3);
4013        let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
4014            panic!("expected the Fenwick tracker");
4015        };
4016        assert_eq!(tracker.get(0), 4);
4017        assert_eq!(tracker.len(), 4);
4018        assert_eq!(
4019            tracker.get(40),
4020            3,
4021            "beyond the tracked length: the prediction"
4022        );
4023
4024        let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
4025        fixed.observe_height(0, 9);
4026        assert_eq!(
4027            fixed.unmeasured_item_height(),
4028            2,
4029            "fixed heights ignore observations"
4030        );
4031
4032        let mut linear: Virtualized<i32> =
4033            Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
4034        linear.observe_height(1, 5);
4035        assert_eq!(linear.unmeasured_item_height(), 2);
4036        let ItemHeight::Variable(cache) = linear.item_height() else {
4037            panic!("expected the linear cache");
4038        };
4039        assert_eq!(cache.get(1), 5);
4040    }
4041
4042    #[test]
4043    fn test_virtualized_with_variable_heights_fenwick() {
4044        let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
4045
4046        for i in 0..10 {
4047            virt.push(i);
4048        }
4049
4050        // All items height 2, viewport 6 -> 3 items visible
4051        let range = virt.visible_range(6);
4052        assert_eq!(range.end - range.start, 3);
4053    }
4054
4055    proptest! {
4056        /// The Fenwick tracker is an O(log n) reimplementation of the cache's
4057        /// linear scan, and the two must answer identically. The only existing
4058        /// Fenwick coverage uses one viewport and uniform heights, which cannot
4059        /// catch a divergence in the bottom-anchoring arms - those only engage
4060        /// when the tail from the current offset cannot fill the viewport.
4061        #[test]
4062        fn variable_height_implementations_agree(
4063            heights in proptest::collection::vec(1u16..=5, 1..40),
4064            viewport in 1u16..=20,
4065            default_height in 1u16..=4,
4066            offset_seed in 0usize..64,
4067        ) {
4068            let len = heights.len();
4069            // `with_variable_heights` has built a Fenwick tracker since
4070            // 4c697f8c, so naming it as the cache side compared one
4071            // implementation against itself. The capacity holds every item,
4072            // so nothing is evicted and the two must agree exactly.
4073            let mut cache: Virtualized<usize> = Virtualized::new(len)
4074                .with_item_height(ItemHeight::Variable(HeightCache::new(default_height, len)));
4075            let mut fenwick: Virtualized<usize> =
4076                Virtualized::new(len).with_variable_heights_fenwick(default_height, len);
4077            for i in 0..len {
4078                cache.push(i);
4079                fenwick.push(i);
4080            }
4081            for (idx, height) in heights.iter().enumerate() {
4082                cache.observe_height(idx, *height);
4083                fenwick.observe_height(idx, *height);
4084            }
4085
4086            let offset = offset_seed % len;
4087            cache.scroll_to(offset);
4088            fenwick.scroll_to(offset);
4089            prop_assert_eq!(
4090                cache.visible_range(viewport),
4091                fenwick.visible_range(viewport),
4092                "implementations disagree at len={} viewport={} offset={}",
4093                len,
4094                viewport,
4095                offset
4096            );
4097
4098            // Both must also be able to reach the last item.
4099            cache.scroll_to_bottom();
4100            fenwick.scroll_to_bottom();
4101            let bottom_cache = cache.visible_range(viewport);
4102            let bottom_fenwick = fenwick.visible_range(viewport);
4103            prop_assert_eq!(&bottom_cache, &bottom_fenwick, "bottom anchoring disagrees");
4104            prop_assert!(
4105                bottom_cache.contains(&(len - 1)),
4106                "last item unreachable: range {:?} of {} items",
4107                bottom_cache,
4108                len
4109            );
4110
4111            // A trim renumbers every surviving item. A tracker that keeps the
4112            // old indices then reports each measurement against an item it was
4113            // not taken from, which is what the legacy cache did.
4114            let keep = 1 + offset_seed % len;
4115            if keep < len {
4116                prop_assert_eq!(cache.trim_front(keep), fenwick.trim_front(keep));
4117                let len = cache.len();
4118                cache.scroll_to_bottom();
4119                fenwick.scroll_to_bottom();
4120                let trimmed_cache = cache.visible_range(viewport);
4121                let trimmed_fenwick = fenwick.visible_range(viewport);
4122                prop_assert_eq!(
4123                    &trimmed_cache,
4124                    &trimmed_fenwick,
4125                    "implementations disagree after trimming to {} items",
4126                    keep
4127                );
4128                prop_assert!(
4129                    trimmed_cache.contains(&(len - 1)),
4130                    "last item unreachable after a trim: range {:?} of {} items",
4131                    trimmed_cache,
4132                    len
4133                );
4134            }
4135        }
4136    }
4137
4138    #[test]
4139    fn test_variable_heights_fenwick_performance() {
4140        use std::time::Instant;
4141
4142        // Create large tracker
4143        let n = 100_000;
4144        let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
4145        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
4146
4147        // Warm up
4148        let _ = tracker.find_item_at_offset(500_000);
4149        let _ = tracker.offset_of_item(50_000);
4150
4151        // Benchmark find_item_at_offset (O(log n))
4152        let start = Instant::now();
4153        let mut _sink = 0usize;
4154        for i in 0..10_000 {
4155            _sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
4156        }
4157        let find_time = start.elapsed();
4158
4159        // Benchmark offset_of_item (O(log n))
4160        let start = Instant::now();
4161        let mut _sink2 = 0u32;
4162        for i in 0..10_000 {
4163            _sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
4164        }
4165        let offset_time = start.elapsed();
4166
4167        eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
4168        eprintln!("10k find_item_at_offset: {:?}", find_time);
4169        eprintln!("10k offset_of_item:      {:?}", offset_time);
4170
4171        // Both should be under 50ms for 10k operations
4172        assert!(
4173            find_time < std::time::Duration::from_millis(50),
4174            "find_item_at_offset too slow: {:?}",
4175            find_time
4176        );
4177        assert!(
4178            offset_time < std::time::Duration::from_millis(50),
4179            "offset_of_item too slow: {:?}",
4180            offset_time
4181        );
4182    }
4183
4184    #[test]
4185    fn test_variable_heights_fenwick_scales_logarithmically() {
4186        use std::time::Instant;
4187
4188        // Small dataset
4189        let small_n = 1_000;
4190        let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
4191        let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
4192
4193        // Large dataset
4194        let large_n = 100_000;
4195        let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
4196        let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
4197
4198        let iterations = 5_000;
4199
4200        // Time small
4201        let start = Instant::now();
4202        for i in 0..iterations {
4203            let _ = small_tracker.find_item_at_offset((i * 2) as u32);
4204        }
4205        let small_time = start.elapsed();
4206
4207        // Time large
4208        let start = Instant::now();
4209        for i in 0..iterations {
4210            let _ = large_tracker.find_item_at_offset((i * 200) as u32);
4211        }
4212        let large_time = start.elapsed();
4213
4214        // Large should be within 10x of small (O(log n) vs O(n) would be 100x).
4215        // Use a generous bound to avoid flakiness on loaded CI workers.
4216        assert!(
4217            large_time < small_time * 10,
4218            "Not O(log n): small={:?}, large={:?}",
4219            small_time,
4220            large_time
4221        );
4222    }
4223
4224    // ========================================================================
4225    // Edge-case tests (bd-2f15w)
4226    // ========================================================================
4227
4228    // ── Virtualized: construction & empty state ─────────────────────────
4229
4230    #[test]
4231    fn new_zero_capacity() {
4232        let virt: Virtualized<i32> = Virtualized::new(0);
4233        assert_eq!(virt.len(), 0);
4234        assert!(virt.is_empty());
4235        assert_eq!(virt.scroll_offset(), 0);
4236        assert_eq!(virt.visible_count(), 0);
4237        assert!(!virt.follow_mode());
4238    }
4239
4240    #[test]
4241    fn external_zero_len_zero_cache() {
4242        let virt: Virtualized<i32> = Virtualized::external(0, 0);
4243        assert_eq!(virt.len(), 0);
4244        assert!(virt.is_empty());
4245    }
4246
4247    #[test]
4248    fn external_storage_returns_none_for_get() {
4249        let virt: Virtualized<i32> = Virtualized::external(100, 10);
4250        assert_eq!(virt.get(0), None);
4251        assert_eq!(virt.get(50), None);
4252    }
4253
4254    #[test]
4255    fn external_storage_returns_none_for_get_mut() {
4256        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4257        assert!(virt.get_mut(0).is_none());
4258    }
4259
4260    #[test]
4261    fn push_on_external_is_noop() {
4262        let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
4263        virt.push(42);
4264        // Length unchanged because push only works on Owned
4265        assert_eq!(virt.len(), 5);
4266    }
4267
4268    #[test]
4269    fn iter_on_external_is_empty() {
4270        let virt: Virtualized<i32> = Virtualized::external(100, 10);
4271        assert_eq!(virt.iter().count(), 0);
4272    }
4273
4274    #[test]
4275    fn set_external_len_on_owned_is_noop() {
4276        let mut virt: Virtualized<i32> = Virtualized::new(100);
4277        virt.push(1);
4278        virt.set_external_len(999);
4279        assert_eq!(virt.len(), 1); // unchanged
4280    }
4281
4282    // ── Virtualized: visible_range edge cases ───────────────────────────
4283
4284    #[test]
4285    fn visible_range_zero_viewport() {
4286        let mut virt: Virtualized<i32> = Virtualized::new(100);
4287        virt.push(1);
4288        let range = virt.visible_range(0);
4289        assert_eq!(range, 0..0);
4290        assert_eq!(virt.visible_count(), 0);
4291    }
4292
4293    #[test]
4294    fn visible_range_empty_container() {
4295        let virt: Virtualized<i32> = Virtualized::new(100);
4296        let range = virt.visible_range(24);
4297        assert_eq!(range, 0..0);
4298    }
4299
4300    #[test]
4301    fn visible_range_fixed_height_zero() {
4302        // Fixed(0) should not divide by zero; falls through to viewport_height items
4303        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
4304        for i in 0..10 {
4305            virt.push(i);
4306        }
4307        let range = virt.visible_range(5);
4308        // ItemHeight::Fixed(0) → viewport_height as usize = 5
4309        assert_eq!(range, 0..5);
4310    }
4311
4312    #[test]
4313    fn visible_range_fewer_items_than_viewport() {
4314        let mut virt: Virtualized<i32> = Virtualized::new(100);
4315        for i in 0..3 {
4316            virt.push(i);
4317        }
4318        let range = virt.visible_range(24);
4319        // Only 3 items, viewport fits 24
4320        assert_eq!(range, 0..3);
4321    }
4322
4323    #[test]
4324    fn visible_range_single_item() {
4325        let mut virt: Virtualized<i32> = Virtualized::new(100);
4326        virt.push(42);
4327        let range = virt.visible_range(1);
4328        assert_eq!(range, 0..1);
4329    }
4330
4331    // ── Virtualized: render_range edge cases ────────────────────────────
4332
4333    #[test]
4334    fn render_range_at_start_clamps_overscan() {
4335        let mut virt: Virtualized<i32> =
4336            Virtualized::new(100).with_fixed_height(1).with_overscan(5);
4337        for i in 0..20 {
4338            virt.push(i);
4339        }
4340        // At scroll_offset=0, start.saturating_sub(5) = 0
4341        let range = virt.render_range(10);
4342        assert_eq!(range.start, 0);
4343    }
4344
4345    #[test]
4346    fn render_range_at_end_clamps_overscan() {
4347        let mut virt: Virtualized<i32> =
4348            Virtualized::new(100).with_fixed_height(1).with_overscan(5);
4349        for i in 0..20 {
4350            virt.push(i);
4351        }
4352        virt.set_visible_count(10);
4353        virt.scroll_to(10); // offset=10, visible 10..20
4354        let range = virt.render_range(10);
4355        // end = min(20 + 5, 20) = 20
4356        assert_eq!(range.end, 20);
4357    }
4358
4359    #[test]
4360    fn render_range_zero_overscan() {
4361        let mut virt: Virtualized<i32> =
4362            Virtualized::new(100).with_fixed_height(1).with_overscan(0);
4363        for i in 0..20 {
4364            virt.push(i);
4365        }
4366        virt.set_visible_count(10);
4367        virt.scroll_to(5);
4368        let range = virt.render_range(10);
4369        // No overscan: render_range == visible_range
4370        let visible = virt.visible_range(10);
4371        assert_eq!(range, visible);
4372    }
4373
4374    // ── Virtualized: scroll edge cases ──────────────────────────────────
4375
4376    #[test]
4377    fn scroll_on_empty_is_noop() {
4378        let mut virt: Virtualized<i32> = Virtualized::new(100);
4379        virt.scroll(10);
4380        assert_eq!(virt.scroll_offset(), 0);
4381    }
4382
4383    #[test]
4384    fn scroll_delta_zero_does_not_disable_follow() {
4385        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4386        virt.push(1);
4387        virt.scroll(0);
4388        // delta=0 doesn't disable follow_mode
4389        assert!(virt.follow_mode());
4390    }
4391
4392    #[test]
4393    fn scroll_negative_beyond_start() {
4394        let mut virt: Virtualized<i32> = Virtualized::new(100);
4395        for i in 0..10 {
4396            virt.push(i);
4397        }
4398        virt.scroll(-1);
4399        assert_eq!(virt.scroll_offset(), 0);
4400    }
4401
4402    #[test]
4403    fn scroll_to_on_empty() {
4404        let mut virt: Virtualized<i32> = Virtualized::new(100);
4405        // scroll_to on empty: idx.min(0.saturating_sub(1)) = idx.min(0) = 0
4406        virt.scroll_to(100);
4407        assert_eq!(virt.scroll_offset(), 0);
4408    }
4409
4410    #[test]
4411    fn scroll_to_top_already_at_top() {
4412        let mut virt: Virtualized<i32> = Virtualized::new(100);
4413        virt.push(1);
4414        virt.scroll_to_top();
4415        assert_eq!(virt.scroll_offset(), 0);
4416    }
4417
4418    #[test]
4419    fn scroll_to_bottom_fewer_items_than_visible() {
4420        let mut virt: Virtualized<i32> = Virtualized::new(100);
4421        virt.set_visible_count(10);
4422        for i in 0..3 {
4423            virt.push(i);
4424        }
4425        virt.scroll_to_bottom();
4426        // len (3) <= visible_count (10), so offset = 0
4427        assert_eq!(virt.scroll_offset(), 0);
4428    }
4429
4430    #[test]
4431    fn scroll_to_bottom_visible_count_zero() {
4432        let mut virt: Virtualized<i32> = Virtualized::new(100);
4433        for i in 0..20 {
4434            virt.push(i);
4435        }
4436        // visible_count=0 (default), scroll_to_bottom stores a sentinel internally.
4437        virt.scroll_to_bottom();
4438        // Internal field stores MAX sentinel…
4439        assert_eq!(virt.scroll_offset, usize::MAX);
4440        // …but public API clamps to last valid index.
4441        assert_eq!(virt.scroll_offset(), 19);
4442    }
4443
4444    // ── Virtualized: page navigation edge cases ─────────────────────────
4445
4446    #[test]
4447    fn page_up_visible_count_zero_is_noop() {
4448        let mut virt: Virtualized<i32> = Virtualized::new(100);
4449        for i in 0..20 {
4450            virt.push(i);
4451        }
4452        virt.scroll_to(10);
4453        // visible_count=0, page_up is no-op
4454        virt.page_up();
4455        assert_eq!(virt.scroll_offset(), 10);
4456    }
4457
4458    #[test]
4459    fn page_down_visible_count_zero_is_noop() {
4460        let mut virt: Virtualized<i32> = Virtualized::new(100);
4461        for i in 0..20 {
4462            virt.push(i);
4463        }
4464        // visible_count=0, page_down is no-op
4465        virt.page_down();
4466        assert_eq!(virt.scroll_offset(), 0);
4467    }
4468
4469    // ── Virtualized: is_at_bottom edge cases ────────────────────────────
4470
4471    #[test]
4472    fn is_at_bottom_fewer_items_than_visible() {
4473        let mut virt: Virtualized<i32> = Virtualized::new(100);
4474        virt.set_visible_count(10);
4475        for i in 0..3 {
4476            virt.push(i);
4477        }
4478        assert!(virt.is_at_bottom());
4479    }
4480
4481    #[test]
4482    fn is_at_bottom_empty() {
4483        let virt: Virtualized<i32> = Virtualized::new(100);
4484        // len=0 <= visible_count=0, so true
4485        assert!(virt.is_at_bottom());
4486    }
4487
4488    // ── Virtualized: trim_front edge cases ──────────────────────────────
4489
4490    #[test]
4491    fn trim_front_under_max_returns_zero() {
4492        let mut virt: Virtualized<i32> = Virtualized::new(100);
4493        for i in 0..5 {
4494            virt.push(i);
4495        }
4496        let removed = virt.trim_front(10);
4497        assert_eq!(removed, 0);
4498        assert_eq!(virt.len(), 5);
4499    }
4500
4501    #[test]
4502    fn trim_front_adjusts_scroll_offset() {
4503        let mut virt: Virtualized<i32> = Virtualized::new(100);
4504        for i in 0..20 {
4505            virt.push(i);
4506        }
4507        virt.scroll_to(10);
4508        let removed = virt.trim_front(15);
4509        assert_eq!(removed, 5);
4510        assert_eq!(virt.len(), 15);
4511        // scroll_offset adjusted: 10 - 5 = 5
4512        assert_eq!(virt.scroll_offset(), 5);
4513    }
4514
4515    #[test]
4516    fn trim_front_scroll_offset_saturates_to_zero() {
4517        let mut virt: Virtualized<i32> = Virtualized::new(100);
4518        for i in 0..20 {
4519            virt.push(i);
4520        }
4521        virt.scroll_to(2);
4522        let removed = virt.trim_front(10);
4523        assert_eq!(removed, 10);
4524        // scroll_offset 2 - 10 saturates to 0
4525        assert_eq!(virt.scroll_offset(), 0);
4526    }
4527
4528    #[test]
4529    fn trim_front_on_external_returns_zero() {
4530        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4531        let removed = virt.trim_front(5);
4532        assert_eq!(removed, 0);
4533    }
4534
4535    #[test]
4536    fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
4537        let mut virt: Virtualized<i32> = Virtualized::new(100);
4538        for i in 0..20 {
4539            virt.push(i);
4540        }
4541
4542        // Before rendering, visible_count is 0.
4543        // scroll_to_bottom should set MAX instead of 0.
4544        virt.scroll_to_bottom();
4545        assert_eq!(virt.scroll_offset, usize::MAX);
4546
4547        // Render (simulate by calling visible_range with height 10)
4548        // Should clamp start to 20 - 10 = 10.
4549        let range = virt.visible_range(10);
4550        assert_eq!(range, 10..20);
4551        assert_eq!(virt.visible_count(), 10);
4552    }
4553
4554    // ── Virtualized: clear edge cases ───────────────────────────────────
4555
4556    #[test]
4557    fn clear_on_external_resets_scroll() {
4558        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4559        virt.scroll_to(50);
4560        virt.clear();
4561        assert_eq!(virt.scroll_offset(), 0);
4562        // External len unchanged since clear only clears Owned
4563        assert_eq!(virt.len(), 100);
4564    }
4565
4566    // ── Virtualized: momentum scrolling edge cases ──────────────────────
4567
4568    #[test]
4569    fn tick_zero_velocity_is_noop() {
4570        let mut virt: Virtualized<i32> = Virtualized::new(100);
4571        for i in 0..20 {
4572            virt.push(i);
4573        }
4574        virt.tick(Duration::from_millis(100));
4575        assert_eq!(virt.scroll_offset(), 0);
4576    }
4577
4578    #[test]
4579    fn tick_below_threshold_stops_momentum() {
4580        let mut virt: Virtualized<i32> = Virtualized::new(100);
4581        for i in 0..20 {
4582            virt.push(i);
4583        }
4584        virt.fling(0.05); // below 0.1 threshold
4585        virt.tick(Duration::from_millis(100));
4586        // velocity <= 0.1, so it's zeroed out
4587        assert_eq!(virt.scroll_offset(), 0);
4588    }
4589
4590    #[test]
4591    fn tick_zero_duration_no_scroll() {
4592        let mut virt: Virtualized<i32> = Virtualized::new(100);
4593        for i in 0..50 {
4594            virt.push(i);
4595        }
4596        virt.fling(100.0);
4597        virt.tick(Duration::ZERO);
4598        // delta = (100.0 * 0.0) as i32 = 0, no scroll
4599        assert_eq!(virt.scroll_offset(), 0);
4600    }
4601
4602    #[test]
4603    fn fling_negative_scrolls_up() {
4604        let mut virt: Virtualized<i32> = Virtualized::new(100);
4605        for i in 0..50 {
4606            virt.push(i);
4607        }
4608        virt.scroll(20);
4609        let before = virt.scroll_offset();
4610        virt.fling(-50.0);
4611        virt.tick(Duration::from_millis(100));
4612        assert!(virt.scroll_offset() < before);
4613    }
4614
4615    // ── Virtualized: follow mode edge cases ─────────────────────────────
4616
4617    #[test]
4618    fn follow_mode_auto_scrolls_on_push() {
4619        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4620        virt.set_visible_count(5);
4621        for i in 0..20 {
4622            virt.push(i);
4623        }
4624        // With follow mode, should be at bottom
4625        assert!(virt.is_at_bottom());
4626        assert_eq!(virt.scroll_offset(), 15); // 20 - 5
4627    }
4628
4629    #[test]
4630    fn set_follow_false_does_not_scroll() {
4631        let mut virt: Virtualized<i32> = Virtualized::new(100);
4632        virt.set_visible_count(5);
4633        for i in 0..20 {
4634            virt.push(i);
4635        }
4636        virt.scroll_to(5);
4637        virt.set_follow(false);
4638        assert_eq!(virt.scroll_offset(), 5); // unchanged
4639    }
4640
4641    #[test]
4642    fn scroll_to_start_disables_follow() {
4643        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4644        virt.set_visible_count(5);
4645        for i in 0..20 {
4646            virt.push(i);
4647        }
4648        virt.scroll_to_start();
4649        assert!(!virt.follow_mode());
4650        assert_eq!(virt.scroll_offset(), 0);
4651    }
4652
4653    #[test]
4654    fn scroll_to_end_enables_follow() {
4655        let mut virt: Virtualized<i32> = Virtualized::new(100);
4656        virt.set_visible_count(5);
4657        for i in 0..20 {
4658            virt.push(i);
4659        }
4660        assert!(!virt.follow_mode());
4661        virt.scroll_to_end();
4662        assert!(virt.follow_mode());
4663        assert!(virt.is_at_bottom());
4664    }
4665
4666    #[test]
4667    fn external_follow_mode_scrolls_on_set_external_len() {
4668        let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
4669        virt.set_visible_count(5);
4670        virt.set_external_len(20);
4671        assert_eq!(virt.len(), 20);
4672        assert!(virt.is_at_bottom());
4673    }
4674
4675    // ── Virtualized: builder chain ──────────────────────────────────────
4676
4677    #[test]
4678    fn builder_chain_all_options() {
4679        let virt: Virtualized<i32> = Virtualized::new(100)
4680            .with_fixed_height(3)
4681            .with_overscan(5)
4682            .with_follow(true);
4683        assert!(virt.follow_mode());
4684        // Verify visible_range uses height=3
4685        // (no items, so empty range regardless)
4686        let range = virt.visible_range(9);
4687        assert_eq!(range, 0..0);
4688    }
4689
4690    // ── HeightCache edge cases ──────────────────────────────────────────
4691
4692    #[test]
4693    fn height_cache_default() {
4694        let cache = HeightCache::default();
4695        assert_eq!(cache.get(0), 1); // default_height=1
4696        assert_eq!(cache.capacity, 1000);
4697    }
4698
4699    #[test]
4700    fn height_cache_get_before_base_offset() {
4701        let mut cache = HeightCache::new(5, 100);
4702        // Set something to push base_offset forward
4703        cache.set(200, 10); // This resets window since 200 > capacity
4704        // Index 0 < base_offset, returns default
4705        assert_eq!(cache.get(0), 5);
4706    }
4707
4708    #[test]
4709    fn height_cache_set_before_base_offset_ignored() {
4710        let mut cache = HeightCache::new(5, 100);
4711        cache.set(200, 10);
4712        let base = cache.base_offset;
4713        cache.set(0, 99); // before base_offset, should be ignored
4714        assert_eq!(cache.get(0), 5); // still default
4715        assert_eq!(cache.base_offset, base); // unchanged
4716    }
4717
4718    #[test]
4719    fn height_cache_capacity_zero_ignores_all_sets() {
4720        let mut cache = HeightCache::new(3, 0);
4721        cache.set(0, 10);
4722        cache.set(5, 20);
4723        // Everything returns default since capacity=0
4724        assert_eq!(cache.get(0), 3);
4725        assert_eq!(cache.get(5), 3);
4726    }
4727
4728    #[test]
4729    fn height_cache_clear_resets_base() {
4730        let mut cache = HeightCache::new(1, 100);
4731        cache.set(50, 10);
4732        cache.clear();
4733        assert_eq!(cache.base_offset, 0);
4734        assert_eq!(cache.get(50), 1); // back to default
4735    }
4736
4737    #[test]
4738    fn height_cache_eviction_trims_oldest() {
4739        let mut cache = HeightCache::new(1, 4);
4740        // Set indices 0..6 to fill and trigger eviction
4741        for i in 0..6 {
4742            cache.set(i, (i + 10) as u16);
4743        }
4744        // Cache capacity=4, so indices 0-1 should be evicted
4745        assert!(cache.cache.len() <= cache.capacity);
4746        // Recent indices should be accessible
4747        assert_eq!(cache.get(5), 15);
4748        assert_eq!(cache.get(4), 14);
4749        assert_eq!(cache.get(3), 13);
4750        assert_eq!(cache.get(2), 12);
4751        // Old indices return default
4752        assert_eq!(cache.get(1), 1);
4753        assert_eq!(cache.get(0), 1);
4754    }
4755
4756    // ── VariableHeightsFenwick edge cases ───────────────────────────────
4757
4758    #[test]
4759    fn fenwick_default_is_empty() {
4760        let tracker = VariableHeightsFenwick::default();
4761        assert!(tracker.is_empty());
4762        assert_eq!(tracker.len(), 0);
4763        assert_eq!(tracker.total_height(), 0);
4764        assert_eq!(tracker.default_height(), 1);
4765    }
4766
4767    #[test]
4768    fn fenwick_get_beyond_len_returns_default() {
4769        let tracker = VariableHeightsFenwick::new(3, 5);
4770        assert_eq!(tracker.get(5), 3); // beyond len
4771        assert_eq!(tracker.get(100), 3);
4772    }
4773
4774    #[test]
4775    fn fenwick_set_beyond_len_resizes() {
4776        let mut tracker = VariableHeightsFenwick::new(2, 3);
4777        assert_eq!(tracker.len(), 3);
4778        tracker.set(10, 7);
4779        assert!(tracker.len() > 10);
4780        assert_eq!(tracker.get(10), 7);
4781    }
4782
4783    #[test]
4784    fn fenwick_offset_of_item_zero_always_zero() {
4785        let tracker = VariableHeightsFenwick::new(5, 10);
4786        assert_eq!(tracker.offset_of_item(0), 0);
4787
4788        let empty = VariableHeightsFenwick::new(5, 0);
4789        assert_eq!(empty.offset_of_item(0), 0);
4790    }
4791
4792    #[test]
4793    fn fenwick_find_item_at_offset_empty() {
4794        let tracker = VariableHeightsFenwick::new(1, 0);
4795        assert_eq!(tracker.find_item_at_offset(0), 0);
4796        assert_eq!(tracker.find_item_at_offset(100), 0);
4797    }
4798
4799    #[test]
4800    fn fenwick_visible_count_zero_viewport() {
4801        let tracker = VariableHeightsFenwick::new(2, 10);
4802        assert_eq!(tracker.visible_count(0, 0), 0);
4803    }
4804
4805    #[test]
4806    fn fenwick_visible_count_start_beyond_len() {
4807        let tracker = VariableHeightsFenwick::new(2, 5);
4808        // start_idx clamped to len
4809        let count = tracker.visible_count(100, 10);
4810        // start=5 (clamped), offset=total, no items visible
4811        assert_eq!(count, 0);
4812    }
4813
4814    #[test]
4815    fn fenwick_clear_then_operations() {
4816        let mut tracker = VariableHeightsFenwick::new(3, 5);
4817        assert_eq!(tracker.total_height(), 15);
4818        tracker.clear();
4819        assert_eq!(tracker.len(), 0);
4820        assert_eq!(tracker.total_height(), 0);
4821        assert_eq!(tracker.find_item_at_offset(0), 0);
4822    }
4823
4824    #[test]
4825    fn fenwick_rebuild_replaces_data() {
4826        let mut tracker = VariableHeightsFenwick::new(1, 10);
4827        assert_eq!(tracker.total_height(), 10);
4828        tracker.rebuild(&[5, 3, 2]);
4829        assert_eq!(tracker.len(), 3);
4830        assert_eq!(tracker.total_height(), 10);
4831        assert_eq!(tracker.get(0), 5);
4832        assert_eq!(tracker.get(1), 3);
4833        assert_eq!(tracker.get(2), 2);
4834    }
4835
4836    #[test]
4837    fn fenwick_resize_same_size_is_noop() {
4838        let mut tracker = VariableHeightsFenwick::new(2, 5);
4839        tracker.set(2, 10);
4840        tracker.resize(5);
4841        // Item 2 still has custom height
4842        assert_eq!(tracker.get(2), 10);
4843        assert_eq!(tracker.len(), 5);
4844    }
4845
4846    // ── VirtualizedListState edge cases ─────────────────────────────────
4847
4848    #[test]
4849    fn list_state_default_matches_new() {
4850        let d = VirtualizedListState::default();
4851        let n = VirtualizedListState::new();
4852        assert_eq!(d.selected, n.selected);
4853        assert_eq!(d.scroll_offset(), n.scroll_offset());
4854        assert_eq!(d.visible_count(), n.visible_count());
4855        assert_eq!(d.follow_mode(), n.follow_mode());
4856    }
4857
4858    #[test]
4859    fn list_state_select_next_on_empty() {
4860        let mut state = VirtualizedListState::new();
4861        state.select_next(0);
4862        assert_eq!(state.selected, None);
4863    }
4864
4865    #[test]
4866    fn list_state_select_previous_on_empty() {
4867        let mut state = VirtualizedListState::new();
4868        state.select_previous(0);
4869        assert_eq!(state.selected, None);
4870    }
4871
4872    #[test]
4873    fn list_state_select_previous_from_none() {
4874        let mut state = VirtualizedListState::new();
4875        state.select_previous(10);
4876        assert_eq!(state.selected, Some(0));
4877    }
4878
4879    #[test]
4880    fn list_state_select_next_from_none() {
4881        let mut state = VirtualizedListState::new();
4882        state.select_next(10);
4883        assert_eq!(state.selected, Some(0));
4884    }
4885
4886    #[test]
4887    fn list_state_scroll_zero_items() {
4888        let mut state = VirtualizedListState::new();
4889        state.scroll(10, 0);
4890        assert_eq!(state.scroll_offset(), 0);
4891    }
4892
4893    #[test]
4894    fn list_state_scroll_to_clamps() {
4895        let mut state = VirtualizedListState::new();
4896        state.scroll_to(100, 10);
4897        assert_eq!(state.scroll_offset(), 9);
4898    }
4899
4900    #[test]
4901    fn list_state_scroll_to_bottom_zero_items() {
4902        let mut state = VirtualizedListState::new();
4903        state.scroll_to_bottom(0);
4904        assert_eq!(state.scroll_offset(), 0);
4905    }
4906
4907    #[test]
4908    fn list_state_is_at_bottom_zero_items() {
4909        let state = VirtualizedListState::new();
4910        assert!(state.is_at_bottom(0));
4911    }
4912
4913    #[test]
4914    fn list_state_page_up_visible_count_zero() {
4915        let mut state = VirtualizedListState::new();
4916        state.scroll_offset = 5;
4917        state.page_up(20);
4918        // visible_count=0, no-op
4919        assert_eq!(state.scroll_offset(), 5);
4920    }
4921
4922    #[test]
4923    fn list_state_page_down_visible_count_zero() {
4924        let mut state = VirtualizedListState::new();
4925        state.page_down(20);
4926        // visible_count=0, no-op
4927        assert_eq!(state.scroll_offset(), 0);
4928    }
4929
4930    #[test]
4931    fn list_state_set_follow_false_no_scroll() {
4932        let mut state = VirtualizedListState::new();
4933        state.scroll_offset = 5;
4934        state.set_follow(false, 20);
4935        assert_eq!(state.scroll_offset(), 5); // unchanged
4936        assert!(!state.follow_mode());
4937    }
4938
4939    #[test]
4940    fn list_state_persistence_id() {
4941        let state = VirtualizedListState::new().with_persistence_id("my-list");
4942        assert_eq!(state.persistence_id(), Some("my-list"));
4943    }
4944
4945    #[test]
4946    fn list_state_persistence_id_none() {
4947        let state = VirtualizedListState::new();
4948        assert_eq!(state.persistence_id(), None);
4949    }
4950
4951    #[test]
4952    fn list_state_momentum_tick_zero_items() {
4953        let mut state = VirtualizedListState::new();
4954        state.fling(50.0);
4955        state.tick(Duration::from_millis(100), 0);
4956        // total_items=0, scroll is no-op
4957        assert_eq!(state.scroll_offset(), 0);
4958    }
4959
4960    // ── VirtualizedListPersistState edge cases ──────────────────────────
4961
4962    #[test]
4963    fn persist_state_default() {
4964        let ps = VirtualizedListPersistState::default();
4965        assert_eq!(ps.selected, None);
4966        assert_eq!(ps.scroll_offset, 0);
4967        assert!(!ps.follow_mode);
4968    }
4969
4970    #[test]
4971    fn persist_state_eq() {
4972        let a = VirtualizedListPersistState {
4973            selected: Some(5),
4974            scroll_offset: 10,
4975            follow_mode: true,
4976        };
4977        let b = a.clone();
4978        assert_eq!(a, b);
4979    }
4980
4981    // ── Stateful trait impl edge cases ──────────────────────────────────
4982
4983    #[test]
4984    fn stateful_state_key_with_persistence_id() {
4985        use crate::stateful::Stateful;
4986        let state = VirtualizedListState::new().with_persistence_id("logs");
4987        let key = state.state_key().expect("named list has a key");
4988        assert_eq!(key.widget_type, "VirtualizedList");
4989        assert_eq!(key.instance_id, "logs");
4990    }
4991
4992    #[test]
4993    fn stateful_state_without_id_is_not_persisted() {
4994        use crate::stateful::Stateful;
4995        assert!(VirtualizedListState::new().state_key().is_none());
4996    }
4997
4998    #[test]
4999    fn stateful_save_restore_roundtrip() {
5000        use crate::stateful::Stateful;
5001        let mut state = VirtualizedListState::new();
5002        state.selected = Some(7);
5003        state.scroll_offset = 15;
5004        state.follow_mode = true;
5005        state.scroll_velocity = 42.0; // transient — not persisted
5006
5007        let saved = state.save_state();
5008        assert_eq!(saved.selected, Some(7));
5009        assert_eq!(saved.scroll_offset, 15);
5010        assert!(saved.follow_mode);
5011
5012        let mut restored = VirtualizedListState::new();
5013        restored.scroll_velocity = 99.0;
5014        restored.restore_state(saved);
5015        assert_eq!(restored.selected, Some(7));
5016        assert_eq!(restored.scroll_offset, 15);
5017        assert!(restored.follow_mode);
5018        // velocity reset to 0 on restore
5019        assert_eq!(restored.scroll_velocity, 0.0);
5020    }
5021
5022    // ── VirtualizedList widget edge cases ───────────────────────────────
5023
5024    #[test]
5025    fn virtualized_list_builder() {
5026        let items: Vec<String> = vec!["a".into()];
5027        let list = VirtualizedList::new(&items)
5028            .style(Style::default())
5029            .highlight_style(Style::default())
5030            .show_scrollbar(false)
5031            .fixed_height(3);
5032        assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
5033        assert!(!list.show_scrollbar);
5034        assert_eq!(
5035            VirtualizedList::new(&items)
5036                .variable_heights()
5037                .height_mode(),
5038            ListHeightMode::Variable
5039        );
5040    }
5041
5042    /// `with_variable_heights` selects the Fenwick tracker sized to the
5043    /// list: offsets are exact before any measurement, offset/index queries
5044    /// round-trip, scrolling to the end computes the last screenful, and a
5045    /// measurement shifts every later offset.
5046    #[test]
5047    fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
5048        let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
5049        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5050            panic!("expected the Fenwick tracker, got {:?}", v.item_height());
5051        };
5052        assert_eq!(tracker.len(), 10_000);
5053        assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
5054        for k in 0..100u32 {
5055            let offset = k * 297;
5056            let idx = tracker.find_item_at_offset(offset);
5057            let start = tracker.offset_of_item(idx);
5058            assert!(
5059                start <= offset && offset < start + u32::from(tracker.get(idx)),
5060                "offset {offset} must land inside item {idx} [{start}, +{})",
5061                tracker.get(idx)
5062            );
5063        }
5064
5065        v.scroll_to(9_999);
5066        let range = v.visible_range(24);
5067        assert_eq!(range.end, 10_000);
5068        assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
5069
5070        v.observe_height(5, 7);
5071        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5072            unreachable!()
5073        };
5074        assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
5075        assert!(tracker.is_measured(5));
5076        assert_eq!(v.unmeasured_item_height(), 3);
5077    }
5078
5079    /// The tracker follows the item count through push, trim_front and
5080    /// clear, keeping measured heights aligned with their items.
5081    #[test]
5082    fn variable_height_tracker_follows_owned_storage() {
5083        let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
5084        for i in 0..5 {
5085            v.push(format!("row {i}"));
5086        }
5087        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5088            unreachable!()
5089        };
5090        assert_eq!(tracker.len(), 5);
5091        assert_eq!(tracker.total_height(), 10);
5092
5093        v.observe_height(0, 5);
5094        v.observe_height(3, 4);
5095        assert_eq!(v.trim_front(3), 2);
5096        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5097            unreachable!()
5098        };
5099        assert_eq!(tracker.len(), 3);
5100        // Old item 3 (height 4) is now item 1; the others are unmeasured (2).
5101        assert!(!tracker.is_measured(0));
5102        assert!(tracker.is_measured(1));
5103        assert_eq!(tracker.get(1), 4);
5104        assert_eq!(tracker.total_height(), 2 + 4 + 2);
5105
5106        v.clear();
5107        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5108            unreachable!()
5109        };
5110        assert_eq!(tracker.len(), 0);
5111        assert_eq!(tracker.total_height(), 0);
5112    }
5113
5114    /// The legacy cache follows the same trims. Its indices are absolute, so
5115    /// without a shift a `trim_front` hands every measurement to the item
5116    /// three places later — the sliding window this strategy exists for.
5117    #[test]
5118    fn legacy_height_cache_follows_owned_storage() {
5119        let mut v: Virtualized<String> =
5120            Virtualized::new(8).with_item_height(ItemHeight::Variable(HeightCache::new(1, 64)));
5121        for i in 0..6 {
5122            v.push(format!("row {i}"));
5123        }
5124        v.observe_height(0, 9);
5125        v.observe_height(4, 4);
5126        assert_eq!(v.trim_front(3), 3);
5127
5128        let ItemHeight::Variable(cache) = v.item_height() else {
5129            unreachable!()
5130        };
5131        // Old item 0 went with the trim; old item 4 (height 4) is now item 1.
5132        assert_eq!(cache.get(0), 1);
5133        assert_eq!(cache.get(1), 4);
5134        // So the first item no longer claims the nine lines of a trimmed one.
5135        assert_eq!(v.visible_range(4), 0..2);
5136
5137        v.clear();
5138        for i in 0..3 {
5139            v.push(format!("fresh {i}"));
5140        }
5141        let ItemHeight::Variable(cache) = v.item_height() else {
5142            unreachable!()
5143        };
5144        assert_eq!(cache.get(0), 1);
5145        assert_eq!(cache.get(1), 1);
5146        assert_eq!(v.visible_range(4), 0..3);
5147    }
5148
5149    /// `drop_front` renumbers a window that starts past the trimmed prefix
5150    /// instead of discarding it.
5151    #[test]
5152    fn height_cache_drop_front_shifts_a_window_past_the_prefix() {
5153        let mut cache = HeightCache::new(1, 4);
5154        for idx in 10..14 {
5155            cache.set(idx, idx as u16);
5156        }
5157        cache.drop_front(10);
5158        for idx in 0..4 {
5159            assert_eq!(cache.get(idx), 10 + idx as u16);
5160        }
5161
5162        // A trim that reaches into the window drops only what it covers.
5163        cache.drop_front(2);
5164        assert_eq!(cache.get(0), 12);
5165        assert_eq!(cache.get(1), 13);
5166        assert_eq!(cache.get(2), 1);
5167
5168        // A trim past the end leaves nothing behind.
5169        cache.drop_front(9);
5170        assert_eq!(cache.get(0), 1);
5171    }
5172
5173    #[test]
5174    fn measure_updates_fenwick_and_predictor() {
5175        let mut list: Virtualized<String> = Virtualized::external(10, 0)
5176            .with_variable_heights(3)
5177            .with_height_prediction(PredictorConfig {
5178                default_height: 3,
5179                prior_mean: 3.0,
5180                prior_strength: 100.0,
5181                ..PredictorConfig::default()
5182            });
5183        let ItemHeight::VariableFenwick(before) = list.item_height() else {
5184            panic!("expected Fenwick heights");
5185        };
5186        let offset = before.offset_of_item(6);
5187        list.measure(5, 7);
5188        let ItemHeight::VariableFenwick(after) = list.item_height() else {
5189            panic!("expected Fenwick heights");
5190        };
5191        assert_eq!(after.offset_of_item(6), offset + 4);
5192        assert_eq!(list.predictor_stats().unwrap().measurements, 1);
5193        assert_eq!(list.predicted_height(0), 3);
5194    }
5195
5196    #[test]
5197    fn unmeasured_rows_use_predicted_mean() {
5198        let mut list: Virtualized<String> = Virtualized::external(100, 0)
5199            .with_variable_heights(1)
5200            .with_height_prediction(PredictorConfig::default());
5201        for idx in 0..20 {
5202            list.measure(idx, 4);
5203        }
5204        assert_eq!(list.predicted_height(0), 4);
5205        assert_eq!(list.predictor_stats().unwrap().measurements, 20);
5206        let ItemHeight::VariableFenwick(heights) = list.item_height() else {
5207            panic!("expected Fenwick heights");
5208        };
5209        assert!(!heights.is_measured(99));
5210        assert_eq!(heights.get(99), 4);
5211        assert_eq!(heights.total_height(), 400);
5212        assert_eq!(String::from("uncategorized").category(), 0);
5213    }
5214
5215    #[test]
5216    fn measured_bitset_tracks_word_boundaries_resize_and_rebuild() {
5217        let mut heights = VariableHeightsFenwick::new(2, 130);
5218        for idx in [0, 63, 64, 65, 127, 128, 129] {
5219            heights.set(idx, 3);
5220        }
5221        assert_eq!(heights.unmeasured_count(), 123);
5222        assert_eq!(heights.measured.len(), 3);
5223        heights.resize(65);
5224        assert_eq!(heights.unmeasured_count(), 62);
5225        heights.resize(130);
5226        for idx in 65..130 {
5227            assert!(!heights.is_measured(idx), "stale bit at {idx}");
5228            assert_eq!(heights.get(idx), 2);
5229        }
5230        heights.rebuild(&[4; 65]);
5231        assert_eq!(heights.unmeasured_count(), 0);
5232        assert!(heights.is_measured(64));
5233        assert!(!heights.is_measured(65));
5234        heights.resize(66);
5235        assert!(!heights.is_measured(65));
5236        heights.drop_front(64);
5237        assert!(heights.is_measured(0));
5238        assert!(!heights.is_measured(1));
5239        assert_eq!(heights.get(0), 4);
5240        assert_eq!(heights.get(1), 2);
5241        heights.clear();
5242        assert!(!heights.is_measured(0));
5243        assert_eq!(heights.unmeasured_count(), 0);
5244        assert!(heights.measured.is_empty());
5245    }
5246
5247    #[test]
5248    fn trimming_measured_rows_does_not_retrain_predictor() {
5249        let mut heights =
5250            VariableHeightsFenwick::new(1, 80).with_predictor(PredictorConfig::default());
5251        for idx in 0..70 {
5252            heights.set_in_category(idx, 5, 1);
5253        }
5254        let before = heights.predictor().unwrap().stats();
5255        heights.drop_front(65);
5256        assert_eq!(heights.predictor().unwrap().stats(), before);
5257        assert_eq!(heights.unmeasured_count(), 10);
5258        for idx in 0..5 {
5259            assert!(heights.is_measured(idx));
5260            assert_eq!(heights.get(idx), 5);
5261        }
5262    }
5263
5264    #[test]
5265    fn variable_list_trains_categories_once_per_measurement() {
5266        struct Row {
5267            height: u16,
5268            category: usize,
5269        }
5270        impl RenderItem for Row {
5271            fn render(&self, area: Rect, frame: &mut Frame, _: bool, _: u16) {
5272                for y in area.y..area.bottom() {
5273                    frame.buffer.set(area.x, y, Cell::from_char('x'));
5274                }
5275            }
5276
5277            fn height(&self) -> u16 {
5278                self.height
5279            }
5280
5281            fn category(&self) -> usize {
5282                self.category
5283            }
5284        }
5285        let mut items = [
5286            Row {
5287                height: 3,
5288                category: 1,
5289            },
5290            Row {
5291                height: 1,
5292                category: 0,
5293            },
5294        ];
5295        let mut state =
5296            VirtualizedListState::variable(2).with_predictor(PredictorConfig::default());
5297        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5298        let mut frame = Frame::new(10, 5, &mut pool);
5299        let area = Rect::new(0, 0, 10, 5);
5300        VirtualizedList::new(&items)
5301            .variable_heights()
5302            .render(area, &mut frame, &mut state);
5303        assert_eq!(state.predictor_stats().unwrap().measurements, 2);
5304        assert_eq!(state.predictor_stats().unwrap().categories, 2);
5305        let predictor = state.heights().unwrap().predictor().unwrap();
5306        assert_eq!(predictor.category_observations(1), 1);
5307        assert_eq!(predictor.category_observations(0), 1);
5308        assert_eq!(state.heights().unwrap().offset_of_item(1), 3);
5309        assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), Some('x'));
5310        assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some(' '));
5311        VirtualizedList::new(&items)
5312            .variable_heights()
5313            .render(area, &mut frame, &mut state);
5314        assert_eq!(state.predictor_stats().unwrap().measurements, 2);
5315        items[0].height = 4;
5316        VirtualizedList::new(&items)
5317            .variable_heights()
5318            .render(area, &mut frame, &mut state);
5319        assert_eq!(state.predictor_stats().unwrap().measurements, 3);
5320        assert_eq!(
5321            state
5322                .heights()
5323                .unwrap()
5324                .predictor()
5325                .unwrap()
5326                .category_observations(1),
5327            2
5328        );
5329
5330        VirtualizedList::new(&items[..0])
5331            .variable_heights()
5332            .render(area, &mut frame, &mut state);
5333        assert_eq!(state.visible_count(), 0);
5334        assert_eq!(state.scroll_offset(), 0);
5335        assert!(state.heights().unwrap().is_empty());
5336        assert_eq!(state.predictor_stats().unwrap().measurements, 3);
5337        VirtualizedList::new(&items)
5338            .variable_heights()
5339            .render(area, &mut frame, &mut state);
5340        assert_eq!(state.predictor_stats().unwrap().measurements, 5);
5341
5342        let mut owned = Virtualized::new(2)
5343            .with_variable_heights(2)
5344            .with_height_prediction(PredictorConfig::default());
5345        owned.push(Row {
5346            height: 4,
5347            category: 1,
5348        });
5349        owned.measure(0, 4);
5350        assert_eq!(owned.predictor_stats().unwrap().categories, 2);
5351        assert_eq!(owned.predictor_stats().unwrap().measurements, 1);
5352        assert!(owned.predicted_height(1) > owned.predicted_height(0));
5353    }
5354
5355    /// A variable-height `VirtualizedList` lays rows out by
5356    /// `RenderItem::height`, measures them into the state, keeps the
5357    /// selection visible and clamps to the last item-aligned screenful.
5358    #[test]
5359    fn virtualized_list_variable_heights_renders_by_item_height() {
5360        struct Tall(u16);
5361        impl RenderItem for Tall {
5362            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
5363                let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
5364                for row in 0..area.height {
5365                    frame
5366                        .buffer
5367                        .set(area.x, area.y + row, Cell::from_char(glyph));
5368                }
5369            }
5370            fn height(&self) -> u16 {
5371                self.0
5372            }
5373        }
5374        let column = |frame: &Frame| -> String {
5375            (0..frame.buffer.height())
5376                .map(|y| {
5377                    frame
5378                        .buffer
5379                        .get(0, y)
5380                        .and_then(|cell| cell.content.as_char())
5381                        .unwrap_or(' ')
5382                })
5383                .collect()
5384        };
5385
5386        let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
5387        let list = VirtualizedList::new(&items)
5388            .variable_heights()
5389            .show_scrollbar(false);
5390        let mut state = VirtualizedListState::new();
5391        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5392
5393        let mut frame = Frame::new(4, 5, &mut pool);
5394        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5395        // item0 (1 row), item1 (2 rows), item2 (3 rows, cut to the 2 left).
5396        assert_eq!(column(&frame), "12233");
5397        assert_eq!(state.visible_count(), 3);
5398        let heights = state.heights().expect("tracker created by render");
5399        assert_eq!(heights.get(1), 2);
5400        assert!(heights.is_measured(2));
5401        // The last screenful is measured too, for the bottom clamp.
5402        assert!(heights.is_measured(4) && heights.is_measured(3));
5403        drop(frame);
5404
5405        // Selecting the last item scrolls so it is visible; the clamp keeps
5406        // the first visible row item-aligned (item3 at the top).
5407        state.select(Some(4));
5408        let mut frame = Frame::new(4, 5, &mut pool);
5409        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5410        assert_eq!(state.scroll_offset(), 3);
5411        assert_eq!(column(&frame), "122  ");
5412        assert_eq!(state.visible_count(), 2);
5413        let heights = state.heights().expect("tracker");
5414        assert_eq!(heights.total_height(), 9);
5415        assert_eq!(heights.offset_of_item(4), 7);
5416        drop(frame);
5417
5418        // A manual measurement moves later offsets.
5419        state.measure(0, 3);
5420        assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
5421
5422        // With the scrollbar on, the thumb works in rows.
5423        let list = VirtualizedList::new(&items).variable_heights();
5424        let mut state = VirtualizedListState::new();
5425        let mut frame = Frame::new(4, 5, &mut pool);
5426        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5427        assert!(
5428            frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
5429            "the last column belongs to the scrollbar"
5430        );
5431        assert_eq!(column(&frame), "12233");
5432    }
5433
5434    #[test]
5435    fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
5436        #[derive(Clone, Copy)]
5437        struct Row(u16, char);
5438        impl RenderItem for Row {
5439            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
5440                for y in area.y..area.bottom() {
5441                    frame.buffer.set(area.x, y, Cell::from_char(self.1));
5442                }
5443            }
5444
5445            fn height(&self) -> u16 {
5446                self.0
5447            }
5448        }
5449
5450        let mut items = vec![Row(u16::MAX, 'X'); 65_538];
5451        items.extend([Row(1, '.'); 9]);
5452        items.push(Row(1, 'Z'));
5453        let list = VirtualizedList::new(&items).variable_heights();
5454        let mut state = VirtualizedListState::new();
5455        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5456        {
5457            let mut frame = Frame::new(4, 5, &mut pool);
5458            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5459            assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
5460        }
5461        // Populate off-screen measurements through the real list-state API.
5462        for (idx, row) in items.iter().enumerate() {
5463            state.measure(idx, row.height());
5464        }
5465        assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
5466        state.select(Some(items.len() - 1));
5467        {
5468            let mut frame = Frame::new(4, 5, &mut pool);
5469            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5470            assert_eq!(state.scroll_offset(), items.len() - 5);
5471            assert_eq!(state.visible_count(), 5);
5472            let column: String = (0..5)
5473                .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
5474                .collect();
5475            assert_eq!(column, "....Z");
5476            assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
5477        }
5478        state.select(None);
5479        state.scroll_to_top();
5480        {
5481            let mut frame = Frame::new(4, 5, &mut pool);
5482            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5483            assert_eq!(state.scroll_offset(), 0);
5484            assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
5485        }
5486        state.scroll_to_bottom(items.len());
5487        let mut frame = Frame::new(4, 5, &mut pool);
5488        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5489        assert_eq!(state.scroll_offset(), items.len() - 5);
5490        assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
5491    }
5492
5493    // ── VirtualizedStorage Debug/Clone ───────────────────────────────────
5494
5495    #[test]
5496    fn virtualized_storage_debug() {
5497        let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
5498        let dbg = format!("{:?}", storage);
5499        assert!(dbg.contains("Owned"));
5500
5501        let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
5502            len: 100,
5503            cache_capacity: 10,
5504        };
5505        let dbg = format!("{:?}", ext);
5506        assert!(dbg.contains("External"));
5507    }
5508
5509    #[test]
5510    fn test_virtualized_list_handle_mouse_drag_smooth() {
5511        use crate::scrollbar::SCROLLBAR_PART_THUMB;
5512        use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5513        use ftui_render::frame::{HitId, HitRegion};
5514
5515        let mut state = VirtualizedListState::new();
5516        let scrollbar_hit_id = HitId::new(1);
5517        let total_items = 100;
5518        let viewport_height = 10;
5519        let fixed_height = 1;
5520
5521        // Simulate click on thumb.
5522        // Track length 10. Thumb size 1. Content 100.
5523        // Thumb at top (pos 0).
5524        // Click at track_pos 0 (top of thumb).
5525        // Hit data: [8: part] [28: len] [28: pos]
5526        let track_len = 10u64;
5527        let track_pos = 0u64;
5528        let hit_data = (SCROLLBAR_PART_THUMB << 56)
5529            | ((track_len & 0x0FFF_FFFF) << 28)
5530            | (track_pos & 0x0FFF_FFFF);
5531
5532        let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
5533        let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
5534
5535        state.handle_mouse(
5536            &down_event,
5537            hit,
5538            scrollbar_hit_id,
5539            total_items,
5540            viewport_height,
5541            fixed_height,
5542        );
5543
5544        assert!(
5545            state.scrollbar_drag_anchor.is_some(),
5546            "Drag anchor should be set on down"
5547        );
5548        assert_eq!(
5549            state.scrollbar_drag_anchor.unwrap(),
5550            0,
5551            "Anchor should be 0 (clicked top of thumb)"
5552        );
5553
5554        // Drag down by 1 cell.
5555        // track_pos = 1. anchor = 0. target thumb top = 1.
5556        // available = 9. max_pos = 90.
5557        // pos = (1 * 90) / 9 = 10.
5558        let drag_pos = 1u64;
5559        let drag_data = (SCROLLBAR_PART_THUMB << 56)
5560            | ((track_len & 0x0FFF_FFFF) << 28)
5561            | (drag_pos & 0x0FFF_FFFF);
5562        let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
5563        let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
5564
5565        state.handle_mouse(
5566            &drag_event,
5567            drag_hit,
5568            scrollbar_hit_id,
5569            total_items,
5570            viewport_height,
5571            fixed_height,
5572        );
5573
5574        assert_eq!(
5575            state.scroll_offset, 10,
5576            "Scroll offset should update smoothly"
5577        );
5578    }
5579
5580    /// After a variable-height render the scrollbar is in rows. Five items
5581    /// six rows tall fill a five-row viewport, so counting items (the
5582    /// fixed-height path) leaves nothing to scroll.
5583    #[test]
5584    fn variable_height_mouse_scrolls_in_rows() {
5585        use crate::scrollbar::SCROLLBAR_PART_TRACK;
5586        use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5587        use ftui_render::frame::{HitId, HitRegion};
5588
5589        struct Tall;
5590        impl RenderItem for Tall {
5591            fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip: u16) {}
5592            fn height(&self) -> u16 {
5593                6
5594            }
5595        }
5596        let items = [Tall, Tall, Tall, Tall, Tall];
5597        let list = VirtualizedList::new(&items).variable_heights();
5598        let mut state = VirtualizedListState::new();
5599        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5600        let area = Rect::new(0, 0, 4, 5);
5601        let mut frame = Frame::new(4, 5, &mut pool);
5602        StatefulWidget::render(&list, area, &mut frame, &mut state);
5603
5604        let id = HitId::new(1);
5605        let mouse = |state: &mut VirtualizedListState, kind, hit| {
5606            state.handle_mouse(&MouseEvent::new(kind, 3, 4), hit, id, items.len(), 5, 1);
5607        };
5608
5609        // A three-row wheel step inside a six-row item still moves one item.
5610        mouse(&mut state, MouseEventKind::ScrollDown, None);
5611        assert_eq!(state.scroll_offset(), 1);
5612        mouse(&mut state, MouseEventKind::ScrollUp, None);
5613        assert_eq!(state.scroll_offset(), 0);
5614
5615        // Clicking the bottom of the track reaches the last item.
5616        let track = (SCROLLBAR_PART_TRACK << 56) | (5 << 28) | 4;
5617        mouse(
5618            &mut state,
5619            MouseEventKind::Down(MouseButton::Left),
5620            Some((id, HitRegion::Scrollbar, track)),
5621        );
5622        assert_eq!(state.scroll_offset(), 4);
5623        StatefulWidget::render(&list, area, &mut frame, &mut state);
5624        assert_eq!(state.scroll_offset(), 4, "render keeps the offset");
5625    }
5626
5627    #[test]
5628    fn remeasure_policy_samples_when_voi_exceeds_cost() {
5629        let mut high_voi = RemeasurePolicy::new(BetaPosterior::new(1.0, 1.0), 0.01, 2);
5630        let decision = high_voi.should_sample(0);
5631        assert!(
5632            decision.is_some(),
5633            "Beta(1,1) VOI (~0.0278) should exceed cost 0.01"
5634        );
5635
5636        let mut low_voi = RemeasurePolicy::new(BetaPosterior::new(1.0, 200.0), 0.08, 2);
5637        assert!(
5638            low_voi.should_sample(0).is_none(),
5639            "Beta(1,200) VOI should fall below cost 0.08"
5640        );
5641    }
5642
5643    #[test]
5644    fn remeasure_policy_respects_min_interval() {
5645        let mut policy = RemeasurePolicy::new(BetaPosterior::new(1.0, 1.0), 0.001, 4);
5646        assert!(policy.should_sample(0).is_some(), "frame 0 should sample");
5647        assert!(
5648            policy.should_sample(1).is_none(),
5649            "frame 1 within min_interval_frames=4 must be skipped"
5650        );
5651        assert!(
5652            policy.should_sample(3).is_none(),
5653            "frame 3 within min_interval_frames=4 must be skipped"
5654        );
5655        assert!(
5656            policy.should_sample(4).is_some(),
5657            "frame 4 at min_interval_frames=4 should sample"
5658        );
5659    }
5660
5661    #[test]
5662    fn invalidate_clears_measured_bit() {
5663        let mut fenwick = VariableHeightsFenwick::new(1, 4);
5664        fenwick.set(2, 5);
5665        assert!(fenwick.is_measured(2));
5666        assert_eq!(fenwick.get(2), 5);
5667        assert_eq!(fenwick.unmeasured_count(), 3);
5668
5669        fenwick.invalidate(2);
5670        assert!(!fenwick.is_measured(2));
5671        assert_eq!(fenwick.get(2), 1);
5672        assert_eq!(fenwick.unmeasured_count(), 4);
5673    }
5674
5675    #[test]
5676    fn variable_heights_defaults_to_fenwick() {
5677        let v: Virtualized<String> = Virtualized::new(16).with_variable_heights(2);
5678        assert!(matches!(v.item_height(), ItemHeight::VariableFenwick(_)));
5679    }
5680
5681    #[test]
5682    fn offset_of_item_is_prefix_sum() {
5683        let heights = [2u16, 5, 1, 4, 3, 6];
5684        let fenwick = VariableHeightsFenwick::from_heights(&heights, 1);
5685        let mut prefix = 0u32;
5686        for (i, &h) in heights.iter().enumerate() {
5687            assert_eq!(fenwick.offset_of_item(i), prefix);
5688            prefix += u32::from(h);
5689        }
5690        assert_eq!(fenwick.total_height(), prefix);
5691    }
5692
5693    #[test]
5694    fn find_item_at_offset_round_trips() {
5695        let heights = [3u16, 1, 4, 2, 5];
5696        let fenwick = VariableHeightsFenwick::from_heights(&heights, 1);
5697        for (i, &h) in heights.iter().enumerate() {
5698            let start = fenwick.offset_of_item(i);
5699            for off in start..start + u32::from(h) {
5700                assert_eq!(fenwick.find_item_at_offset(off), i);
5701            }
5702        }
5703    }
5704
5705    #[test]
5706    fn variable_list_renders_multi_line_items_at_correct_rows() {
5707        #[derive(Clone, Copy)]
5708        struct MultiRow(u16, char);
5709        impl RenderItem for MultiRow {
5710            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip: u16) {
5711                for y in area.y..area.bottom() {
5712                    frame.buffer.set(area.x, y, Cell::from_char(self.1));
5713                }
5714            }
5715            fn height(&self) -> u16 {
5716                self.0
5717            }
5718        }
5719        let items = [MultiRow(2, 'A'), MultiRow(3, 'B'), MultiRow(1, 'C')];
5720        let list = VirtualizedList::new(&items)
5721            .variable_heights()
5722            .show_scrollbar(false);
5723        let mut state = VirtualizedListState::new();
5724        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5725        let mut frame = Frame::new(4, 6, &mut pool);
5726        StatefulWidget::render(&list, Rect::new(0, 0, 4, 6), &mut frame, &mut state);
5727        let col: String = (0..6)
5728            .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
5729            .collect();
5730        assert_eq!(col, "AABBBC");
5731    }
5732
5733    #[test]
5734    fn category_default_is_zero() {
5735        assert_eq!(String::from("default").category(), 0);
5736    }
5737
5738    #[test]
5739    fn measured_bitset_tracks_set_and_rebuild() {
5740        let mut fenwick = VariableHeightsFenwick::new(1, 10);
5741        assert_eq!(fenwick.unmeasured_count(), 10);
5742        fenwick.set(3, 4);
5743        assert!(fenwick.is_measured(3));
5744        assert!(!fenwick.is_measured(2));
5745        assert_eq!(fenwick.unmeasured_count(), 9);
5746        fenwick.rebuild(&[2; 10]);
5747        assert_eq!(fenwick.unmeasured_count(), 0);
5748        assert!(fenwick.is_measured(2));
5749    }
5750
5751    mod scroll_stability_proptests {
5752        use super::*;
5753        use proptest::prelude::{ProptestConfig, any, prop_assert, proptest};
5754
5755        #[derive(Clone, Copy, Debug)]
5756        struct CorpusRow {
5757            height: u16,
5758            category: usize,
5759        }
5760
5761        impl RenderItem for CorpusRow {
5762            fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip_rows: u16) {}
5763
5764            fn height(&self) -> u16 {
5765                self.height
5766            }
5767
5768            fn category(&self) -> usize {
5769                self.category
5770            }
5771        }
5772
5773        fn generate_long_tail_corpus(n: usize, seed: u64) -> (Vec<CorpusRow>, Vec<usize>) {
5774            let mut state = seed ^ 0x9E37_79B9_7F4A_7C15;
5775            let mut next_u64 = || -> u64 {
5776                state = state
5777                    .wrapping_mul(6364136223846793005)
5778                    .wrapping_add(1442695040888963407);
5779                state
5780            };
5781
5782            let mut rows = Vec::with_capacity(n);
5783            for _ in 0..n {
5784                let bucket = (next_u64() >> 32) % 100;
5785                let (height, category) = if bucket < 80 {
5786                    (1u16, 0usize)
5787                } else if bucket < 95 {
5788                    let r = next_u64();
5789                    let h = 2 + (((r >> 32) % 2) + ((r >> 48) % 2)) as u16; // 2..=4 centered at 3
5790                    (h, 1usize)
5791                } else {
5792                    let r = next_u64();
5793                    let tier = ((r >> 48) % 3) as usize;
5794                    let jitter = (((r & 0xFF) % 3) + (((r >> 8) & 0xFF) % 3)) as u16; // 0..=4 centered at 2
5795                    let h = match tier {
5796                        0 => 6 + jitter,  // 6..=10 (in 5..=30)
5797                        1 => 15 + jitter, // 15..=19 (in 5..=30)
5798                        _ => 25 + jitter, // 25..=29 (in 5..=30)
5799                    };
5800                    (h, 2 + tier)
5801                };
5802                rows.push(CorpusRow { height, category });
5803            }
5804
5805            let mut perm: Vec<usize> = (0..n).collect();
5806            for idx in (1..n).rev() {
5807                let swap_idx = (next_u64() as usize) % (idx + 1);
5808                perm.swap(idx, swap_idx);
5809            }
5810
5811            // Ensure the initial 10% training prefix observes at least 4 samples
5812            // of each category so cold-start categories are calibrated before scroll_to.
5813            let train_count = (n / 10).max(1);
5814            let mut swap_pos = 0usize;
5815            for target_cat in 1..=4usize {
5816                let mut seen = perm[..train_count]
5817                    .iter()
5818                    .filter(|&&idx| rows[idx].category == target_cat)
5819                    .count();
5820                for pos in train_count..n {
5821                    if seen >= 4 || swap_pos >= train_count {
5822                        break;
5823                    }
5824                    if rows[perm[pos]].category == target_cat {
5825                        while swap_pos < train_count && rows[perm[swap_pos]].category != 0 {
5826                            swap_pos += 1;
5827                        }
5828                        if swap_pos < train_count {
5829                            perm.swap(swap_pos, pos);
5830                            seen += 1;
5831                            swap_pos += 1;
5832                        }
5833                    }
5834                }
5835            }
5836
5837            (rows, perm)
5838        }
5839
5840        proptest! {
5841            #![proptest_config(ProptestConfig { cases: 256, ..ProptestConfig::default() })]
5842
5843            #[test]
5844            fn scroll_to_index_is_stable_under_late_measurements(
5845                n in 500usize..5000,
5846                seed in any::<u64>(),
5847                target_frac in 0usize..10_000,
5848            ) {
5849                let min_target = n / 4;
5850                let i = min_target + (target_frac % (n - min_target).max(1));
5851                let (rows, perm) = generate_long_tail_corpus(n, seed);
5852                let total_true_sum: u64 = rows.iter().map(|r| u64::from(r.height)).sum();
5853                let mean_height = ((total_true_sum as f64) / (n as f64)).round().max(1.0) as u16;
5854                let true_offset: u32 = rows[..i].iter().map(|r| u32::from(r.height)).sum();
5855
5856                let mut pred_list: Virtualized<CorpusRow> = Virtualized::new(n)
5857                    .with_variable_heights(1)
5858                    .with_height_predictor(PredictorConfig::default());
5859                let mut base_list: Virtualized<CorpusRow> = Virtualized::new(n)
5860                    .with_variable_heights(mean_height);
5861
5862                for &row in &rows {
5863                    pred_list.push(row);
5864                    base_list.push(row);
5865                }
5866
5867                let train_count = (n / 10).max(1);
5868                for &idx in &perm[..train_count] {
5869                    let h = rows[idx].height;
5870                    pred_list.measure(idx, h);
5871                    base_list.observe_height(idx, h);
5872                }
5873
5874                pred_list.scroll_to(i);
5875                base_list.scroll_to(i);
5876
5877                let mut prev_pred_offset = pred_list.offset_of_item(i);
5878                let mut prev_base_offset = base_list.offset_of_item(i);
5879                let mut jump_predictor = 0u64;
5880                let mut jump_mean_baseline = 0u64;
5881
5882                for chunk in perm[train_count..].chunks(50) {
5883                    for &idx in chunk {
5884                        let h = rows[idx].height;
5885                        pred_list.measure(idx, h);
5886                        base_list.observe_height(idx, h);
5887                    }
5888                    let next_pred_offset = pred_list.offset_of_item(i);
5889                    let next_base_offset = base_list.offset_of_item(i);
5890                    jump_predictor += u64::from(next_pred_offset.abs_diff(prev_pred_offset));
5891                    jump_mean_baseline += u64::from(next_base_offset.abs_diff(prev_base_offset));
5892                    prev_pred_offset = next_pred_offset;
5893                    prev_base_offset = next_base_offset;
5894                }
5895
5896                let final_offset = pred_list.offset_of_item(i);
5897                let cat = rows[i].category;
5898                let (lower, upper) = match pred_list.item_height() {
5899                    ItemHeight::VariableFenwick(t) => t
5900                        .predictor()
5901                        .map_or((1, 1), |p| {
5902                            let b = p.predict(cat);
5903                            (b.lower, b.upper)
5904                        }),
5905                    _ => (1, 1),
5906                };
5907                let bound_width = u32::from(upper.saturating_sub(lower));
5908
5909                prop_assert!(
5910                    final_offset.abs_diff(true_offset) <= bound_width,
5911                    "seed={seed} n={n} i={i} final_offset={final_offset} true_offset={true_offset} bounds=[{lower}, {upper}]"
5912                );
5913                prop_assert!(
5914                    jump_predictor <= jump_mean_baseline,
5915                    "seed={seed} n={n} i={i} jump_predictor={jump_predictor} > jump_mean_baseline={jump_mean_baseline} bounds=[{lower}, {upper}]"
5916                );
5917            }
5918        }
5919    }
5920}