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//! - [`VirtualizedStorage`] - Owned vs external storage abstraction
12//! - [`ItemHeight`] - Fixed vs variable height support
13//! - [`HeightCache`] - LRU cache for measured item heights
14//!
15//! # Example
16//!
17//! ```ignore
18//! use ftui_widgets::virtualized::{Virtualized, ItemHeight};
19//!
20//! // Create with owned storage
21//! let mut virt: Virtualized<String> = Virtualized::new(10_000);
22//!
23//! // Add items
24//! for i in 0..1000 {
25//!     virt.push(format!("Line {}", i));
26//! }
27//!
28//! // Get visible range for viewport height
29//! let range = virt.visible_range(24);
30//! println!("Visible: {}..{}", range.start, range.end);
31//! ```
32
33use std::cell::Cell as StdCell;
34use std::collections::VecDeque;
35use std::ops::Range;
36use std::time::Duration;
37
38use crate::scrollbar::{Scrollbar, ScrollbarOrientation, ScrollbarState};
39use crate::{StatefulWidget, clear_text_area};
40use ftui_core::geometry::Rect;
41use ftui_render::cell::Cell;
42use ftui_render::frame::Frame;
43use ftui_style::Style;
44
45/// A virtualized content container that tracks scroll state and computes visible ranges.
46///
47/// # Design Rationale
48/// - Generic over item type for flexibility
49/// - Supports both owned storage and external data sources
50/// - Computes visible ranges for O(visible) rendering
51/// - Optional overscan for smooth scrolling
52/// - Momentum scrolling support
53#[derive(Debug, Clone)]
54pub struct Virtualized<T> {
55    /// The stored items (or external storage reference).
56    storage: VirtualizedStorage<T>,
57    /// Current scroll offset (in items).
58    scroll_offset: usize,
59    /// Number of visible items (cached from last render).
60    visible_count: StdCell<usize>,
61    /// Overscan: extra items rendered above/below visible.
62    overscan: usize,
63    /// Height calculation strategy.
64    item_height: ItemHeight,
65    /// Whether to auto-scroll on new items.
66    follow_mode: bool,
67    /// Scroll velocity for momentum scrolling.
68    scroll_velocity: f32,
69}
70
71/// Storage strategy for virtualized items.
72#[derive(Debug, Clone)]
73pub enum VirtualizedStorage<T> {
74    /// Owned vector of items.
75    Owned(VecDeque<T>),
76    /// External storage with known length.
77    /// Note: External fetch is handled at the widget level.
78    External {
79        /// Total number of items available.
80        len: usize,
81        /// Maximum items to keep in local cache.
82        cache_capacity: usize,
83    },
84}
85
86/// Height calculation strategy for items.
87#[derive(Debug, Clone)]
88pub enum ItemHeight {
89    /// All items have fixed height.
90    Fixed(u16),
91    /// Legacy variable-height mode: an LRU cache of measured heights and a
92    /// linear scan per `visible_range`. Kept for callers that want bounded
93    /// memory over a sliding window; new code should use
94    /// [`Virtualized::with_variable_heights`] (Fenwick).
95    Variable(HeightCache),
96    /// Items have variable height with O(log n) scroll-to-index via Fenwick
97    /// tree; the default variable-height strategy.
98    VariableFenwick(VariableHeightsFenwick),
99}
100
101/// LRU cache for measured item heights.
102#[derive(Debug, Clone)]
103pub struct HeightCache {
104    /// Height measurements indexed by (item index - base_offset).
105    cache: Vec<Option<u16>>,
106    /// Offset of the first entry in the cache (cache[0] corresponds to this item index).
107    base_offset: usize,
108    /// Default height for unmeasured items.
109    default_height: u16,
110    /// Maximum entries to cache (for memory bounds).
111    capacity: usize,
112}
113
114impl<T> Virtualized<T> {
115    /// Create a new virtualized container with owned storage.
116    ///
117    /// # Arguments
118    /// * `capacity` - Maximum items to retain in memory.
119    #[must_use]
120    pub fn new(capacity: usize) -> Self {
121        Self {
122            storage: VirtualizedStorage::Owned(VecDeque::with_capacity(capacity.min(1024))),
123            scroll_offset: 0,
124            visible_count: StdCell::new(0),
125            overscan: 2,
126            item_height: ItemHeight::Fixed(1),
127            follow_mode: false,
128            scroll_velocity: 0.0,
129        }
130    }
131
132    /// Create with external storage reference.
133    #[must_use]
134    pub fn external(len: usize, cache_capacity: usize) -> Self {
135        Self {
136            storage: VirtualizedStorage::External {
137                len,
138                cache_capacity,
139            },
140            scroll_offset: 0,
141            visible_count: StdCell::new(0),
142            overscan: 2,
143            item_height: ItemHeight::Fixed(1),
144            follow_mode: false,
145            scroll_velocity: 0.0,
146        }
147    }
148
149    /// Set item height strategy.
150    #[must_use]
151    pub fn with_item_height(mut self, height: ItemHeight) -> Self {
152        self.item_height = height;
153        self
154    }
155
156    /// Set fixed item height.
157    #[must_use]
158    pub fn with_fixed_height(mut self, height: u16) -> Self {
159        self.item_height = ItemHeight::Fixed(height);
160        self
161    }
162
163    /// Predict the heights of unmeasured items with a Bayesian model instead
164    /// of a constant default (see [`VariableHeightsFenwick::with_predictor`]).
165    ///
166    /// Switches the height strategy to the Fenwick tracker when it is not one
167    /// already (a fixed height becomes the tracker's default; a linear
168    /// [`HeightCache`] is replaced, dropping its cached measurements). Heights
169    /// recorded through [`Virtualized::observe_height`] train the model.
170    #[must_use]
171    pub fn with_height_prediction(mut self, config: PredictorConfig) -> Self {
172        let len = self.len();
173        let current = std::mem::replace(&mut self.item_height, ItemHeight::Fixed(1));
174        self.item_height = ItemHeight::VariableFenwick(match current {
175            ItemHeight::VariableFenwick(tracker) => tracker.with_predictor(config),
176            ItemHeight::Fixed(height) => {
177                VariableHeightsFenwick::new(height.max(1), len).with_predictor(config)
178            }
179            ItemHeight::Variable(cache) => {
180                VariableHeightsFenwick::new(cache.default_height, len).with_predictor(config)
181            }
182        });
183        self
184    }
185
186    /// Record the measured height of item `idx`.
187    ///
188    /// A no-op for the fixed-height strategy. With a predictor attached this
189    /// also trains the height model, so unmeasured items follow what has been
190    /// measured instead of a constant guess.
191    pub fn observe_height(&mut self, idx: usize, height: u16) {
192        match &mut self.item_height {
193            ItemHeight::Fixed(_) => {}
194            ItemHeight::Variable(cache) => cache.set(idx, height),
195            ItemHeight::VariableFenwick(tracker) => tracker.set(idx, height),
196        }
197    }
198
199    /// Height assumed for items that have not been measured yet: the
200    /// predictor's current point estimate when one is attached, otherwise
201    /// the strategy's default (or the fixed height).
202    #[must_use]
203    pub fn unmeasured_item_height(&self) -> u16 {
204        match &self.item_height {
205            ItemHeight::Fixed(height) => *height,
206            ItemHeight::Variable(cache) => cache.default_height,
207            ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
208        }
209    }
210
211    /// Use variable item heights (Fenwick-tracked, the default strategy):
212    /// unmeasured rows count `default_height`, `observe_height` records
213    /// real ones, and offsets, `scroll_to` and `visible_range` stay
214    /// O(log n). The tracker is sized to the current length and follows the
215    /// items: it grows with `push` (a tracker pre-filled with more heights
216    /// than items keeps them), shifts on `trim_front`, clears on `clear`
217    /// and matches `set_external_len` exactly.
218    #[must_use]
219    pub fn with_variable_heights(mut self, default_height: u16) -> Self {
220        let len = self.len();
221        self.item_height =
222            ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
223        self
224    }
225
226    /// Variable heights with an explicit initial tracker capacity (the
227    /// tracker still follows the item count afterwards). Prefer
228    /// [`Self::with_variable_heights`] unless the list is filled in bulk
229    /// after construction.
230    #[must_use]
231    pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
232        self.item_height =
233            ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
234        self
235    }
236
237    /// Keep a Fenwick tracker's length in step with the item count: grow it
238    /// (`exact == false`, used by `push`, so a tracker pre-filled with more
239    /// heights than items keeps them) or set it exactly (`exact == true`,
240    /// used by `set_external_len`).
241    fn sync_height_tracker(&mut self, exact: bool) {
242        let len = self.len();
243        if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
244            && (tracker.len() < len || (exact && tracker.len() != len))
245        {
246            tracker.resize(len);
247        }
248    }
249
250    /// Set overscan amount.
251    #[must_use]
252    pub fn with_overscan(mut self, overscan: usize) -> Self {
253        self.overscan = overscan;
254        self
255    }
256
257    /// Enable follow mode.
258    #[must_use]
259    pub fn with_follow(mut self, follow: bool) -> Self {
260        self.follow_mode = follow;
261        self
262    }
263
264    /// Get total number of items.
265    #[must_use]
266    pub fn len(&self) -> usize {
267        match &self.storage {
268            VirtualizedStorage::Owned(items) => items.len(),
269            VirtualizedStorage::External { len, .. } => *len,
270        }
271    }
272
273    /// Check if empty.
274    #[must_use]
275    pub fn is_empty(&self) -> bool {
276        self.len() == 0
277    }
278
279    /// Get current scroll offset.
280    ///
281    /// The internal sentinel value (`usize::MAX`, used for lazy scroll-to-bottom)
282    /// is clamped to the actual item count so callers never see it.
283    #[must_use]
284    pub fn scroll_offset(&self) -> usize {
285        self.scroll_offset.min(self.len().saturating_sub(1))
286    }
287
288    /// Get current visible count (from last render).
289    #[must_use]
290    pub fn visible_count(&self) -> usize {
291        self.visible_count.get()
292    }
293
294    /// Check if follow mode is enabled.
295    #[must_use]
296    pub fn follow_mode(&self) -> bool {
297        self.follow_mode
298    }
299
300    /// Calculate visible range for given viewport height.
301    #[must_use]
302    pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
303        if self.is_empty() || viewport_height == 0 {
304            self.visible_count.set(0);
305            return 0..0;
306        }
307
308        let items_visible = match &self.item_height {
309            // Use div_ceil to include partially visible items
310            ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
311            ItemHeight::Fixed(_) => viewport_height as usize,
312            ItemHeight::Variable(cache) => {
313                // Sum heights until we fill or exceed viewport
314                let len = self.len();
315                let start = self.scroll_offset.min(len.saturating_sub(1));
316                let mut count = 0;
317                let mut total_height = 0u16;
318                while start + count < len {
319                    let next = cache.get(start + count);
320
321                    // Always include the item
322                    total_height = total_height.saturating_add(next);
323                    count += 1;
324
325                    // Stop if we've filled the viewport
326                    if total_height >= viewport_height {
327                        break;
328                    }
329                }
330                if total_height < viewport_height && start > 0 {
331                    // The tail from `start` cannot fill the viewport (e.g.
332                    // after scroll_to_bottom's lazy sentinel, or an offset
333                    // near the end). Anchor to the bottom like the Fixed arm:
334                    // count the trailing items that fit, so the clamped start
335                    // below shows a full last screenful instead of blank rows.
336                    count = 0;
337                    total_height = 0;
338                    while count < len {
339                        let next = cache.get(len - 1 - count);
340                        total_height = total_height.saturating_add(next);
341                        count += 1;
342                        if total_height >= viewport_height {
343                            break;
344                        }
345                    }
346                }
347                count
348            }
349            ItemHeight::VariableFenwick(tracker) => {
350                // O(log n) using Fenwick tree
351                let len = self.len();
352                let start = self.scroll_offset.min(len.saturating_sub(1));
353                let total = tracker.total_height_exact();
354                let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
355                if suffix < u64::from(viewport_height) {
356                    // Same bottom anchoring as the Variable arm, in O(log n):
357                    // when the last screenful is shown, its first (possibly
358                    // partially visible) item contains offset total-viewport.
359                    let anchor = total.saturating_sub(u64::from(viewport_height));
360                    len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
361                        .max(1)
362                } else {
363                    tracker.visible_count(start, viewport_height).max(1)
364                }
365            }
366        };
367
368        let max_offset = self.len().saturating_sub(items_visible);
369        let start = self.scroll_offset.min(max_offset);
370        let end = start.saturating_add(items_visible).min(self.len());
371        self.visible_count.set(items_visible);
372        start..end
373    }
374
375    /// Get render range with overscan for smooth scrolling.
376    #[must_use]
377    pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
378        let visible = self.visible_range(viewport_height);
379        let start = visible.start.saturating_sub(self.overscan);
380        let end = visible.end.saturating_add(self.overscan).min(self.len());
381        start..end
382    }
383
384    /// Scroll by delta (positive = down/forward).
385    pub fn scroll(&mut self, delta: i32) {
386        if self.is_empty() {
387            return;
388        }
389        let visible_count = self.visible_count.get();
390        let max_offset = if visible_count > 0 {
391            self.len().saturating_sub(visible_count)
392        } else {
393            self.len().saturating_sub(1)
394        };
395        // Clamp current offset BEFORE adding delta, so lazy MAX doesn't swallow negative deltas
396        let clamped_current = self.scroll_offset.min(max_offset);
397        let new_offset = clamped_current
398            .saturating_add_signed(delta as isize)
399            .min(max_offset);
400        self.scroll_offset = new_offset;
401
402        // Disable follow mode on manual scroll
403        if delta != 0 {
404            self.follow_mode = false;
405        }
406    }
407
408    /// Scroll to specific item index.
409    pub fn scroll_to(&mut self, idx: usize) {
410        self.scroll_offset = idx.min(self.len().saturating_sub(1));
411        self.follow_mode = false;
412    }
413
414    /// Scroll to bottom.
415    pub fn scroll_to_bottom(&mut self) {
416        if self.is_empty() {
417            self.scroll_offset = 0;
418            return;
419        }
420
421        let visible_count = self.visible_count.get();
422        if visible_count == 0 {
423            // Viewport unknown; keep a sentinel and let `visible_range` clamp lazily.
424            self.scroll_offset = usize::MAX;
425        } else if self.len() > visible_count {
426            self.scroll_offset = self.len().saturating_sub(visible_count);
427        } else {
428            self.scroll_offset = 0;
429        }
430    }
431
432    /// Scroll to top.
433    pub fn scroll_to_top(&mut self) {
434        self.scroll_offset = 0;
435        self.follow_mode = false;
436    }
437
438    /// Alias for scroll_to_top (Home key).
439    pub fn scroll_to_start(&mut self) {
440        self.scroll_to_top();
441    }
442
443    /// Scroll to bottom and enable follow mode (End key).
444    pub fn scroll_to_end(&mut self) {
445        self.scroll_to_bottom();
446        self.follow_mode = true;
447    }
448
449    /// Page up (scroll by visible count - 1).
450    pub fn page_up(&mut self) {
451        let visible_count = self.visible_count.get();
452        if visible_count > 0 {
453            let step = if visible_count > 1 {
454                visible_count - 1
455            } else {
456                1
457            };
458            let delta = i32::try_from(step).unwrap_or(i32::MAX);
459            self.scroll(-delta);
460        }
461    }
462
463    /// Page down (scroll by visible count - 1).
464    pub fn page_down(&mut self) {
465        let visible_count = self.visible_count.get();
466        if visible_count > 0 {
467            let step = if visible_count > 1 {
468                visible_count - 1
469            } else {
470                1
471            };
472            let delta = i32::try_from(step).unwrap_or(i32::MAX);
473            self.scroll(delta);
474        }
475    }
476
477    /// Set follow mode.
478    pub fn set_follow(&mut self, follow: bool) {
479        self.follow_mode = follow;
480        if follow {
481            self.scroll_to_bottom();
482        }
483    }
484
485    /// Check if scrolled to bottom.
486    #[must_use]
487    pub fn is_at_bottom(&self) -> bool {
488        let visible_count = self.visible_count.get();
489        if self.len() <= visible_count {
490            true
491        } else {
492            self.scroll_offset >= self.len().saturating_sub(visible_count)
493        }
494    }
495
496    /// Start momentum scroll.
497    pub fn fling(&mut self, velocity: f32) {
498        self.scroll_velocity = velocity;
499    }
500
501    /// Apply momentum scroll tick.
502    pub fn tick(&mut self, dt: Duration) {
503        if self.scroll_velocity.abs() > 0.1 {
504            let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
505            if delta != 0 {
506                self.scroll(delta);
507            }
508            // Apply friction
509            self.scroll_velocity *= 0.95;
510        } else {
511            self.scroll_velocity = 0.0;
512        }
513    }
514
515    /// Update visible count (called during render).
516    pub fn set_visible_count(&self, count: usize) {
517        self.visible_count.set(count);
518    }
519
520    /// Get reference to the item height strategy.
521    #[must_use]
522    pub fn item_height(&self) -> &ItemHeight {
523        &self.item_height
524    }
525
526    /// Get mutable reference to the item height strategy.
527    ///
528    /// Useful for updating variable height trackers (e.g. resizing Fenwick tree)
529    /// when items are added.
530    pub fn item_height_mut(&mut self) -> &mut ItemHeight {
531        &mut self.item_height
532    }
533}
534
535impl<T> Virtualized<T> {
536    /// Push an item (owned storage only).
537    pub fn push(&mut self, item: T) {
538        if let VirtualizedStorage::Owned(items) = &mut self.storage {
539            items.push_back(item);
540            self.sync_height_tracker(false);
541            if self.follow_mode {
542                self.scroll_to_bottom();
543            }
544        }
545    }
546
547    /// Get item by index (owned storage only).
548    #[must_use = "use the returned item (if any)"]
549    pub fn get(&self, idx: usize) -> Option<&T> {
550        if let VirtualizedStorage::Owned(items) = &self.storage {
551            items.get(idx)
552        } else {
553            None
554        }
555    }
556
557    /// Get mutable item by index (owned storage only).
558    #[must_use = "use the returned item (if any)"]
559    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
560        if let VirtualizedStorage::Owned(items) = &mut self.storage {
561            items.get_mut(idx)
562        } else {
563            None
564        }
565    }
566
567    /// Clear all items (owned storage only).
568    pub fn clear(&mut self) {
569        if let VirtualizedStorage::Owned(items) = &mut self.storage {
570            items.clear();
571            if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
572                tracker.clear();
573            }
574        }
575        self.scroll_offset = 0;
576    }
577
578    /// Trim items from the front to keep at most `max` items (owned storage only).
579    ///
580    /// Returns the number of items removed.
581    pub fn trim_front(&mut self, max: usize) -> usize {
582        if let VirtualizedStorage::Owned(items) = &mut self.storage
583            && items.len() > max
584        {
585            let to_remove = items.len() - max;
586            items.drain(..to_remove);
587            if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
588                tracker.drop_front(to_remove);
589            }
590            // Adjust scroll_offset if it was pointing beyond the new start
591            self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
592            return to_remove;
593        }
594        0
595    }
596
597    /// Iterate over items (owned storage only).
598    /// Returns empty iterator for external storage.
599    pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
600        match &self.storage {
601            VirtualizedStorage::Owned(items) => Box::new(items.iter()),
602            VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
603        }
604    }
605
606    /// Update external storage length.
607    pub fn set_external_len(&mut self, len: usize) {
608        if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
609            *l = len;
610            self.sync_height_tracker(true);
611            if self.follow_mode {
612                self.scroll_to_bottom();
613            }
614        }
615    }
616}
617
618impl Default for HeightCache {
619    fn default() -> Self {
620        Self::new(1, 1000)
621    }
622}
623
624impl HeightCache {
625    /// Create a new height cache.
626    #[must_use]
627    pub fn new(default_height: u16, capacity: usize) -> Self {
628        Self {
629            cache: Vec::new(),
630            base_offset: 0,
631            default_height,
632            capacity,
633        }
634    }
635
636    /// Get height for item, returning default if not cached.
637    #[must_use]
638    pub fn get(&self, idx: usize) -> u16 {
639        if idx < self.base_offset {
640            return self.default_height;
641        }
642        let local = idx - self.base_offset;
643        self.cache
644            .get(local)
645            .and_then(|h| *h)
646            .unwrap_or(self.default_height)
647    }
648
649    /// Set height for item.
650    pub fn set(&mut self, idx: usize, height: u16) {
651        if self.capacity == 0 {
652            return;
653        }
654        if idx < self.base_offset {
655            // Index has been trimmed away; ignore
656            return;
657        }
658        let mut local = idx - self.base_offset;
659
660        // If the jump is so large that we'd drain the entire current cache anyway,
661        // reset the window to avoid a huge allocation of Nones.
662        if local + 1 >= self.cache.len() + self.capacity {
663            self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
664            self.cache.clear();
665            local = idx - self.base_offset;
666        }
667
668        if local >= self.cache.len() {
669            self.cache.resize(local + 1, None);
670        }
671        self.cache[local] = Some(height);
672
673        // Trim if over capacity: remove oldest entries and adjust base_offset
674        if self.cache.len() > self.capacity {
675            let to_remove = self.cache.len() - self.capacity;
676            self.cache.drain(0..to_remove);
677            self.base_offset += to_remove;
678        }
679    }
680
681    /// Clear cached heights.
682    pub fn clear(&mut self) {
683        self.cache.clear();
684        self.base_offset = 0;
685    }
686}
687
688// ============================================================================
689// VariableHeightsFenwick - O(log n) scroll-to-index mapping
690// ============================================================================
691
692use crate::height_predictor::{HeightPredictor, PredictorConfig};
693
694/// Variable height tracker using Fenwick tree for O(log n) prefix sum queries.
695///
696/// This enables efficient scroll offset to item index mapping for virtualized
697/// lists with variable height items.
698///
699/// # Operations
700///
701/// | Operation | Time |
702/// |-----------|------|
703/// | `find_item_at_offset` | O(log n) |
704/// | `offset_of_item` | O(log n) |
705/// | `set_height` | O(log n) |
706/// | `total_height` | O(log n) |
707///
708/// # Invariants
709///
710/// 1. Internal prefix sums are exact u64 sums of u16 item heights.
711/// 2. Inverse lookup searches these monotone sums without allocating.
712/// 3. Public u32 offsets and totals saturate at u32::MAX; internal layout
713///    continues to use exact offsets beyond that boundary.
714#[derive(Debug, Clone)]
715pub struct VariableHeightsFenwick {
716    /// One-indexed Fenwick tree storing exact aggregate heights.
717    tree: Vec<u64>,
718    /// Default height for items not yet measured.
719    default_height: u16,
720    /// Number of items tracked.
721    len: usize,
722    /// Which slots hold a measured height (`set`) rather than the fill value.
723    measured: Vec<bool>,
724    /// Number of `false` entries in `measured`.
725    unmeasured: usize,
726    /// Optional Bayesian model for the heights of unmeasured slots.
727    predictor: Option<HeightPredictor>,
728    /// Height every unmeasured slot currently holds: the predictor's point
729    /// prediction when one is attached, otherwise `default_height`.
730    fill_height: u16,
731}
732
733impl Default for VariableHeightsFenwick {
734    fn default() -> Self {
735        Self::new(1, 0)
736    }
737}
738
739impl VariableHeightsFenwick {
740    /// Create a new height tracker with given default height and initial capacity.
741    #[must_use]
742    pub fn new(default_height: u16, capacity: usize) -> Self {
743        let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
744        Self {
745            tree,
746            default_height,
747            len: capacity,
748            measured: vec![false; capacity],
749            unmeasured: capacity,
750            predictor: None,
751            fill_height: default_height,
752        }
753    }
754
755    /// Create from a slice of heights (all of them count as measured).
756    #[must_use]
757    pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
758        Self {
759            tree: Self::build_height_tree(heights.iter().copied()),
760            default_height,
761            len: heights.len(),
762            measured: vec![true; heights.len()],
763            unmeasured: 0,
764            predictor: None,
765            fill_height: default_height,
766        }
767    }
768
769    /// Build in O(n), bounding the item count so every possible height update
770    /// also fits in u64. This limit exceeds any practically allocatable list.
771    fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
772        let len = heights.len();
773        assert!(
774            u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
775            "too many items for exact height aggregates"
776        );
777        let mut tree = vec![0; len + 1];
778        for (slot, height) in tree[1..].iter_mut().zip(heights) {
779            *slot = u64::from(height);
780        }
781        for idx in 1..=len {
782            let parent = idx + idx.isolate_lowest_one();
783            if parent <= len {
784                tree[parent] += tree[idx];
785            }
786        }
787        tree
788    }
789
790    fn set_tracked_height(&mut self, idx: usize, height: u16) {
791        let old = self.get(idx);
792        let mut node = idx + 1;
793        while node <= self.len {
794            if height >= old {
795                self.tree[node] += u64::from(height - old);
796            } else {
797                self.tree[node] -= u64::from(old - height);
798            }
799            node += node.isolate_lowest_one();
800        }
801    }
802
803    fn offset_of_item_exact(&self, idx: usize) -> u64 {
804        let mut node = idx.min(self.len);
805        let mut sum = 0;
806        while node > 0 {
807            sum += self.tree[node];
808            node &= node - 1;
809        }
810        sum
811    }
812
813    fn total_height_exact(&self) -> u64 {
814        self.offset_of_item_exact(self.len)
815    }
816
817    fn find_item_at_offset_exact(&self, offset: u64) -> usize {
818        // Preserve the origin convention even when leading items have height 0.
819        if self.len == 0 || offset == 0 {
820            return 0;
821        }
822        let mut idx = 0;
823        let mut sum = 0;
824        let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
825        while step > 0 {
826            if step <= self.len - idx {
827                let next = idx + step;
828                let prefix = sum + self.tree[next];
829                if prefix <= offset {
830                    idx = next;
831                    sum = prefix;
832                }
833            }
834            step >>= 1;
835        }
836        idx
837    }
838
839    /// Attach a Bayesian height predictor ([`HeightPredictor`]).
840    ///
841    /// Unmeasured slots then hold the predictor's current point prediction
842    /// instead of `default_height`; every [`set`](Self::set) trains the model
843    /// and, whenever the rounded prediction moves by a whole row, the
844    /// unmeasured slots are refilled so offsets and the total height track
845    /// the rows measured so far instead of a constant guess. A refill costs
846    /// O(u log n) for u unmeasured slots and a converging posterior triggers
847    /// it only a handful of times.
848    #[must_use]
849    pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
850        let predictor = HeightPredictor::new(config);
851        self.fill_height = predictor.predict(0).predicted.max(1);
852        self.predictor = Some(predictor);
853        self.refill_unmeasured();
854        self
855    }
856
857    /// The attached height predictor, if any.
858    #[must_use]
859    pub fn predictor(&self) -> Option<&HeightPredictor> {
860        self.predictor.as_ref()
861    }
862
863    /// Height every unmeasured slot currently holds (the prediction when a
864    /// predictor is attached, otherwise the default height).
865    #[must_use]
866    pub fn predicted_height(&self) -> u16 {
867        self.fill_height
868    }
869
870    /// Number of slots that have not been measured through [`set`](Self::set).
871    #[must_use]
872    pub fn unmeasured_count(&self) -> usize {
873        self.unmeasured
874    }
875
876    /// Whether slot `idx` holds a measured height.
877    #[must_use]
878    pub fn is_measured(&self, idx: usize) -> bool {
879        self.measured.get(idx).copied().unwrap_or(false)
880    }
881
882    /// Rewrite every unmeasured slot with the current fill height.
883    /// Returns the number of slots rewritten.
884    fn refill_unmeasured(&mut self) -> usize {
885        let mut rewritten = 0;
886        for idx in 0..self.len {
887            if !self.measured[idx] {
888                self.set_tracked_height(idx, self.fill_height);
889                rewritten += 1;
890            }
891        }
892        rewritten
893    }
894
895    /// Number of items tracked.
896    #[must_use]
897    pub fn len(&self) -> usize {
898        self.len
899    }
900
901    /// Whether tracking is empty.
902    #[must_use]
903    pub fn is_empty(&self) -> bool {
904        self.len == 0
905    }
906
907    /// Get the default height for unmeasured items.
908    #[must_use]
909    pub fn default_height(&self) -> u16 {
910        self.default_height
911    }
912
913    /// Get height of a specific item. O(log n).
914    ///
915    /// Items beyond the tracked length report the fill height (the
916    /// prediction when a predictor is attached).
917    #[must_use]
918    pub fn get(&self, idx: usize) -> u16 {
919        if idx >= self.len {
920            return self.fill_height;
921        }
922        (self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
923    }
924
925    /// Set (measure) the height of a specific item. O(log n), plus a refill
926    /// of the unmeasured slots when an attached predictor's rounded
927    /// prediction changes.
928    pub fn set(&mut self, idx: usize, height: u16) {
929        if idx >= self.len {
930            // Need to resize
931            self.resize(idx.checked_add(1).expect("height index exceeds usize"));
932        }
933        self.set_tracked_height(idx, height);
934        if !self.measured[idx] {
935            self.measured[idx] = true;
936            self.unmeasured -= 1;
937        }
938        if let Some(predictor) = self.predictor.as_mut() {
939            predictor.observe(0, height);
940            let next = predictor.predict(0).predicted.max(1);
941            if next != self.fill_height {
942                self.fill_height = next;
943                self.refill_unmeasured();
944            }
945        }
946    }
947
948    /// Get the y-offset (in pixels/rows) of an item. O(log n).
949    ///
950    /// Returns the sum of heights of all items before `idx`, saturated at
951    /// `u32::MAX`. Indices beyond the tracked length return the total height.
952    #[must_use]
953    pub fn offset_of_item(&self, idx: usize) -> u32 {
954        self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
955    }
956
957    /// Find the item index at a given scroll offset. O(log n).
958    ///
959    /// Returns the index of the item that occupies the given offset.
960    /// If offset is beyond all items, returns `self.len`.
961    ///
962    /// Item i occupies the interval between its exact prefix sums, including
963    /// when the total exceeds `u32::MAX`. Offset zero returns item zero even
964    /// if leading items have zero height. Saturated public offsets above the
965    /// u32 boundary cannot be used to address those later items.
966    #[must_use]
967    pub fn find_item_at_offset(&self, offset: u32) -> usize {
968        self.find_item_at_offset_exact(u64::from(offset))
969    }
970
971    /// Count how many items are visible within a viewport starting at `start_idx`. O(log n).
972    ///
973    /// Visibility here means partially or fully visible. The first partially
974    /// visible trailing item is counted.
975    ///
976    /// Returns **at least 1** when `start_idx < len` and `viewport_height > 0`,
977    /// even if the first item is taller than the viewport.
978    #[must_use]
979    pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
980        if self.len == 0 || viewport_height == 0 {
981            return 0;
982        }
983        let start = start_idx.min(self.len);
984        let start_offset = self.offset_of_item_exact(start);
985        let end_offset = start_offset.saturating_add(u64::from(viewport_height));
986
987        // Find last item that fits
988        let end_idx = self.find_item_at_offset_exact(end_offset);
989
990        // Count items from start to end (including partially visible trailing item)
991        if end_idx > start {
992            // `find_item_at_offset` returns `len` when `end_offset` is at/after the end
993            // of the list. In that case, everything from `start` to the end fits.
994            if end_idx >= self.len {
995                return self.len.saturating_sub(start);
996            }
997            // Check if end_idx item is visible (partially or fully)
998            let end_item_start = self.offset_of_item_exact(end_idx);
999            if end_offset > end_item_start {
1000                end_idx - start + 1
1001            } else {
1002                end_idx - start
1003            }
1004        } else {
1005            // At least show one item if viewport has space
1006            if viewport_height > 0 && start < self.len {
1007                1
1008            } else {
1009                0
1010            }
1011        }
1012    }
1013
1014    /// Get total height of all items, saturated at `u32::MAX`. O(log n).
1015    #[must_use]
1016    pub fn total_height(&self) -> u32 {
1017        self.total_height_exact().min(u64::from(u32::MAX)) as u32
1018    }
1019
1020    /// Resize the tracker to accommodate `new_len` items.
1021    ///
1022    /// New items are initialized with the fill height (the default height,
1023    /// or the current prediction when a predictor is attached).
1024    pub fn resize(&mut self, new_len: usize) {
1025        if new_len == self.len {
1026            return;
1027        }
1028        self.tree = Self::build_height_tree((0..new_len).map(|idx| self.get(idx)));
1029        if new_len > self.len {
1030            self.unmeasured += new_len - self.len;
1031            self.measured.resize(new_len, false);
1032        } else {
1033            let dropped_unmeasured = self.measured[new_len..].iter().filter(|m| !**m).count();
1034            self.unmeasured -= dropped_unmeasured;
1035            self.measured.truncate(new_len);
1036        }
1037        self.len = new_len;
1038    }
1039
1040    /// Drop the first `n` entries (the list trimmed its front): remaining
1041    /// heights and their measured flags shift down by `n`; an attached
1042    /// predictor keeps what it learned.
1043    pub fn drop_front(&mut self, n: usize) {
1044        if n == 0 {
1045            return;
1046        }
1047        if n >= self.len {
1048            self.clear();
1049            return;
1050        }
1051        let kept: Vec<(u16, bool)> = (n..self.len)
1052            .map(|idx| (self.get(idx), self.is_measured(idx)))
1053            .collect();
1054        self.clear();
1055        self.resize(kept.len());
1056        for (idx, (height, measured)) in kept.into_iter().enumerate() {
1057            if measured {
1058                self.set(idx, height);
1059            }
1060        }
1061    }
1062
1063    /// Clear all height data (an attached predictor keeps what it learned).
1064    pub fn clear(&mut self) {
1065        self.tree = vec![0];
1066        self.len = 0;
1067        self.measured.clear();
1068        self.unmeasured = 0;
1069    }
1070
1071    /// Rebuild from a fresh set of heights; all of them count as measured and
1072    /// train an attached predictor.
1073    pub fn rebuild(&mut self, heights: &[u16]) {
1074        self.tree = Self::build_height_tree(heights.iter().copied());
1075        self.len = heights.len();
1076        self.measured = vec![true; heights.len()];
1077        self.unmeasured = 0;
1078        if let Some(predictor) = self.predictor.as_mut() {
1079            for &height in heights {
1080                predictor.observe(0, height);
1081            }
1082            self.fill_height = predictor.predict(0).predicted.max(1);
1083        }
1084    }
1085}
1086
1087// ============================================================================
1088// VirtualizedList Widget
1089// ============================================================================
1090
1091/// Trait for items that can render themselves.
1092///
1093/// Implement this trait for item types that should render in a `VirtualizedList`.
1094pub trait RenderItem {
1095    /// Render the item into the frame at the given area.
1096    ///
1097    /// # Arguments
1098    ///
1099    /// * `area` - The area to render into.
1100    /// * `frame` - The frame to render into.
1101    /// * `selected` - Whether the item is selected.
1102    /// * `skip_rows` - Number of rows to skip from the top of the item content.
1103    ///   This is non-zero when the item partially overlaps the top of the viewport.
1104    fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
1105
1106    /// Height of this item in terminal rows.
1107    fn height(&self) -> u16 {
1108        1
1109    }
1110}
1111
1112/// How a [`VirtualizedList`] sizes its rows.
1113#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1114pub enum ListHeightMode {
1115    /// Every row is this many terminal rows tall (default: 1).
1116    Fixed(u16),
1117    /// Each row is as tall as [`RenderItem::height`] reports. Rows are
1118    /// measured into the state's Fenwick tracker as they render, so scroll
1119    /// offsets and the scrollbar stay O(log n) in the item count. Scrolling
1120    /// is item-aligned: the first visible row starts at the viewport top.
1121    Variable,
1122}
1123
1124/// State for the VirtualizedList widget.
1125#[derive(Debug, Clone)]
1126pub struct VirtualizedListState {
1127    /// Currently selected index.
1128    pub selected: Option<usize>,
1129    /// Scroll offset.
1130    scroll_offset: usize,
1131    /// Visible count (from last render).
1132    visible_count: usize,
1133    /// Overscan amount.
1134    overscan: usize,
1135    /// Whether follow mode is enabled.
1136    follow_mode: bool,
1137    /// Scroll velocity for momentum.
1138    scroll_velocity: f32,
1139    /// Drag anchor for scrollbar thumb (offset from thumb top).
1140    scrollbar_drag_anchor: Option<usize>,
1141    /// Optional persistence ID for state saving/restoration.
1142    persistence_id: Option<String>,
1143    /// Row heights measured while rendering in [`ListHeightMode::Variable`]
1144    /// (`None` until the first variable-height render).
1145    heights: Option<VariableHeightsFenwick>,
1146}
1147
1148impl Default for VirtualizedListState {
1149    fn default() -> Self {
1150        Self::new()
1151    }
1152}
1153
1154impl VirtualizedListState {
1155    /// Create a new state.
1156    #[must_use]
1157    pub fn new() -> Self {
1158        Self {
1159            selected: None,
1160            scroll_offset: 0,
1161            visible_count: 0,
1162            overscan: 2,
1163            follow_mode: false,
1164            scroll_velocity: 0.0,
1165            scrollbar_drag_anchor: None,
1166            persistence_id: None,
1167            heights: None,
1168        }
1169    }
1170
1171    /// Record the measured height of item `idx` for a variable-height
1172    /// list. Rendering measures the visible rows itself; call this when an
1173    /// item's height changed while off-screen so offsets stay exact. Ignored
1174    /// until the first variable-height render creates the tracker.
1175    pub fn measure(&mut self, idx: usize, height: u16) {
1176        if let Some(heights) = self.heights.as_mut()
1177            && idx < heights.len()
1178        {
1179            heights.set(idx, height.max(1));
1180        }
1181    }
1182
1183    /// The variable-height tracker (after the first variable-height render).
1184    #[must_use]
1185    pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
1186        self.heights.as_ref()
1187    }
1188
1189    /// Create with overscan.
1190    #[must_use]
1191    pub fn with_overscan(mut self, overscan: usize) -> Self {
1192        self.overscan = overscan;
1193        self
1194    }
1195
1196    /// Create with follow mode enabled.
1197    #[must_use]
1198    pub fn with_follow(mut self, follow: bool) -> Self {
1199        self.follow_mode = follow;
1200        self
1201    }
1202
1203    /// Create with a persistence ID for state saving.
1204    #[must_use]
1205    pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
1206        self.persistence_id = Some(id.into());
1207        self
1208    }
1209
1210    /// Get the persistence ID, if set.
1211    #[must_use = "use the persistence id (if any)"]
1212    pub fn persistence_id(&self) -> Option<&str> {
1213        self.persistence_id.as_deref()
1214    }
1215
1216    /// Get raw scroll offset.
1217    ///
1218    /// **Warning:** After `scroll_to_bottom`, this may return `usize::MAX`
1219    /// (a lazy sentinel that gets clamped during rendering). Use
1220    /// [`scroll_offset_clamped`](Self::scroll_offset_clamped) with a known
1221    /// `total_items` to get a safe value for display or indexing.
1222    #[must_use]
1223    pub fn scroll_offset(&self) -> usize {
1224        self.scroll_offset
1225    }
1226
1227    /// Get scroll offset clamped against a known total item count.
1228    ///
1229    /// Prefer this over [`scroll_offset()`](Self::scroll_offset) when the total is available,
1230    /// because `scroll_to_bottom` may store `usize::MAX` internally.
1231    #[must_use]
1232    pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
1233        if total_items == 0 {
1234            return 0;
1235        }
1236        self.scroll_offset.min(total_items.saturating_sub(1))
1237    }
1238
1239    /// Get visible item count (from last render).
1240    #[must_use]
1241    pub fn visible_count(&self) -> usize {
1242        self.visible_count
1243    }
1244
1245    /// Scroll by delta (positive = down).
1246    pub fn scroll(&mut self, delta: i32, total_items: usize) {
1247        if total_items == 0 {
1248            return;
1249        }
1250        let max_offset = if self.visible_count > 0 {
1251            total_items.saturating_sub(self.visible_count)
1252        } else {
1253            total_items.saturating_sub(1)
1254        };
1255        // Clamp current offset BEFORE adding delta, so lazy MAX doesn't swallow negative deltas
1256        let clamped_current = self.scroll_offset.min(max_offset);
1257        let new_offset = clamped_current
1258            .saturating_add_signed(delta as isize)
1259            .min(max_offset);
1260        self.scroll_offset = new_offset;
1261
1262        if delta != 0 {
1263            self.follow_mode = false;
1264        }
1265    }
1266
1267    /// Scroll to specific index.
1268    pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
1269        self.scroll_offset = idx.min(total_items.saturating_sub(1));
1270        self.follow_mode = false;
1271    }
1272
1273    /// Scroll to top.
1274    pub fn scroll_to_top(&mut self) {
1275        self.scroll_offset = 0;
1276        self.follow_mode = false;
1277    }
1278
1279    /// Scroll to bottom.
1280    pub fn scroll_to_bottom(&mut self, total_items: usize) {
1281        if total_items == 0 {
1282            self.scroll_offset = 0;
1283        } else {
1284            // Set to MAX; render() will clamp to (total - viewport)
1285            // once viewport height is known.
1286            self.scroll_offset = usize::MAX;
1287        }
1288    }
1289
1290    /// Page up (scroll by visible count - 1).
1291    pub fn page_up(&mut self, total_items: usize) {
1292        if self.visible_count > 0 {
1293            let step = if self.visible_count > 1 {
1294                self.visible_count - 1
1295            } else {
1296                1
1297            };
1298            let delta = i32::try_from(step).unwrap_or(i32::MAX);
1299            self.scroll(-delta, total_items);
1300        }
1301    }
1302
1303    /// Page down (scroll by visible count - 1).
1304    pub fn page_down(&mut self, total_items: usize) {
1305        if self.visible_count > 0 {
1306            let step = if self.visible_count > 1 {
1307                self.visible_count - 1
1308            } else {
1309                1
1310            };
1311            let delta = i32::try_from(step).unwrap_or(i32::MAX);
1312            self.scroll(delta, total_items);
1313        }
1314    }
1315
1316    /// Select an item.
1317    pub fn select(&mut self, index: Option<usize>) {
1318        self.selected = index;
1319    }
1320
1321    /// Select previous item.
1322    pub fn select_previous(&mut self, total_items: usize) {
1323        if total_items == 0 {
1324            self.selected = None;
1325            return;
1326        }
1327        self.selected = Some(match self.selected {
1328            Some(i) if i > 0 => i - 1,
1329            Some(_) => 0,
1330            None => 0,
1331        });
1332    }
1333
1334    /// Select next item.
1335    pub fn select_next(&mut self, total_items: usize) {
1336        if total_items == 0 {
1337            self.selected = None;
1338            return;
1339        }
1340        self.selected = Some(match self.selected {
1341            Some(i) if i < total_items - 1 => i + 1,
1342            Some(i) => i,
1343            None => 0,
1344        });
1345    }
1346
1347    /// Check if at bottom.
1348    #[must_use]
1349    pub fn is_at_bottom(&self, total_items: usize) -> bool {
1350        if total_items <= self.visible_count {
1351            true
1352        } else {
1353            self.scroll_offset >= total_items - self.visible_count
1354        }
1355    }
1356
1357    /// Enable/disable follow mode.
1358    pub fn set_follow(&mut self, follow: bool, total_items: usize) {
1359        self.follow_mode = follow;
1360        if follow {
1361            self.scroll_to_bottom(total_items);
1362        }
1363    }
1364
1365    /// Check if follow mode is enabled.
1366    #[must_use]
1367    pub fn follow_mode(&self) -> bool {
1368        self.follow_mode
1369    }
1370
1371    /// Start momentum scroll.
1372    pub fn fling(&mut self, velocity: f32) {
1373        self.scroll_velocity = velocity;
1374    }
1375
1376    /// Apply momentum scrolling tick.
1377    pub fn tick(&mut self, dt: Duration, total_items: usize) {
1378        if self.scroll_velocity.abs() > 0.1 {
1379            let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
1380            if delta != 0 {
1381                self.scroll(delta, total_items);
1382            }
1383            self.scroll_velocity *= 0.95;
1384        } else {
1385            self.scroll_velocity = 0.0;
1386        }
1387    }
1388
1389    /// Handle mouse events, including scrollbar interaction.
1390    ///
1391    /// The caller must provide the hit test result and the expected hit ID for
1392    /// the scrollbar.
1393    pub fn handle_mouse(
1394        &mut self,
1395        event: &ftui_core::event::MouseEvent,
1396        hit: Option<(
1397            ftui_render::frame::HitId,
1398            ftui_render::frame::HitRegion,
1399            u64,
1400        )>,
1401        scrollbar_hit_id: ftui_render::frame::HitId,
1402        total_items: usize,
1403        viewport_height: u16,
1404        fixed_item_height: u16,
1405    ) -> crate::mouse::MouseResult {
1406        // Construct temporary scrollbar state
1407        let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
1408        let mut scrollbar_state =
1409            ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
1410
1411        // Restore drag anchor
1412        scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
1413
1414        let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
1415
1416        // Sync back
1417        self.scroll_offset = scrollbar_state.position;
1418        self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
1419
1420        if result == crate::mouse::MouseResult::Scrolled {
1421            self.follow_mode = false;
1422        }
1423
1424        result
1425    }
1426}
1427
1428// ============================================================================
1429// Stateful Persistence Implementation for VirtualizedListState
1430// ============================================================================
1431
1432/// Persistable state for a [`VirtualizedListState`].
1433///
1434/// Contains the user-facing scroll state that should survive sessions.
1435/// Transient values like scroll_velocity and visible_count are not persisted.
1436#[derive(Clone, Debug, Default, PartialEq)]
1437#[cfg_attr(
1438    feature = "state-persistence",
1439    derive(serde::Serialize, serde::Deserialize)
1440)]
1441pub struct VirtualizedListPersistState {
1442    /// Selected item index.
1443    pub selected: Option<usize>,
1444    /// Scroll offset (first visible item).
1445    pub scroll_offset: usize,
1446    /// Whether follow mode is enabled.
1447    pub follow_mode: bool,
1448}
1449
1450impl crate::stateful::Stateful for VirtualizedListState {
1451    type State = VirtualizedListPersistState;
1452
1453    fn state_key(&self) -> crate::stateful::StateKey {
1454        crate::stateful::StateKey::new(
1455            "VirtualizedList",
1456            self.persistence_id.as_deref().unwrap_or("default"),
1457        )
1458    }
1459
1460    fn save_state(&self) -> VirtualizedListPersistState {
1461        VirtualizedListPersistState {
1462            selected: self.selected,
1463            scroll_offset: self.scroll_offset,
1464            follow_mode: self.follow_mode,
1465        }
1466    }
1467
1468    fn restore_state(&mut self, state: VirtualizedListPersistState) {
1469        self.selected = state.selected;
1470        self.scroll_offset = state.scroll_offset;
1471        self.follow_mode = state.follow_mode;
1472        // Reset transient values
1473        self.scroll_velocity = 0.0;
1474        self.scrollbar_drag_anchor = None;
1475    }
1476}
1477
1478/// A virtualized list widget that renders only visible items.
1479///
1480/// This widget efficiently renders large lists by only drawing items
1481/// that are currently visible in the viewport, with optional overscan
1482/// for smooth scrolling.
1483///
1484/// # Limitations
1485///
1486/// Currently, `VirtualizedList` only supports **fixed height** items.
1487/// For variable height virtualization, use the [`Virtualized`] primitive directly.
1488#[derive(Debug)]
1489pub struct VirtualizedList<'a, T> {
1490    /// Items to render.
1491    items: &'a [T],
1492    /// Base style.
1493    style: Style,
1494    /// Style for selected item.
1495    highlight_style: Style,
1496    /// Whether to show scrollbar.
1497    show_scrollbar: bool,
1498    /// Row sizing: fixed rows or per-item heights.
1499    height_mode: ListHeightMode,
1500    /// Optional hit ID for scrollbar interaction.
1501    hit_id: Option<ftui_render::frame::HitId>,
1502}
1503
1504impl<'a, T> VirtualizedList<'a, T> {
1505    /// Create a new virtualized list.
1506    #[must_use]
1507    pub fn new(items: &'a [T]) -> Self {
1508        Self {
1509            items,
1510            style: Style::default(),
1511            highlight_style: Style::default(),
1512            show_scrollbar: true,
1513            height_mode: ListHeightMode::Fixed(1),
1514            hit_id: None,
1515        }
1516    }
1517
1518    /// Set base style.
1519    #[must_use]
1520    pub fn style(mut self, style: Style) -> Self {
1521        self.style = style;
1522        self
1523    }
1524
1525    /// Set highlight style for selected item.
1526    #[must_use]
1527    pub fn highlight_style(mut self, style: Style) -> Self {
1528        self.highlight_style = style;
1529        self
1530    }
1531
1532    /// Enable/disable scrollbar.
1533    #[must_use]
1534    pub fn show_scrollbar(mut self, show: bool) -> Self {
1535        self.show_scrollbar = show;
1536        self
1537    }
1538
1539    /// Set fixed item height.
1540    #[must_use]
1541    pub fn fixed_height(mut self, height: u16) -> Self {
1542        self.height_mode = ListHeightMode::Fixed(height);
1543        self
1544    }
1545
1546    /// Size each row by [`RenderItem::height`] (see
1547    /// [`ListHeightMode::Variable`]).
1548    #[must_use]
1549    pub fn variable_heights(mut self) -> Self {
1550        self.height_mode = ListHeightMode::Variable;
1551        self
1552    }
1553
1554    /// The row sizing mode.
1555    #[must_use]
1556    pub fn height_mode(&self) -> ListHeightMode {
1557        self.height_mode
1558    }
1559
1560    /// Set hit ID for scrollbar interaction.
1561    #[must_use]
1562    pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
1563        self.hit_id = Some(id);
1564        self
1565    }
1566}
1567
1568impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
1569    type State = VirtualizedListState;
1570
1571    fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
1572        #[cfg(feature = "tracing")]
1573        let _span = tracing::debug_span!(
1574            "widget_render",
1575            widget = "VirtualizedList",
1576            x = area.x,
1577            y = area.y,
1578            w = area.width,
1579            h = area.height,
1580            items = self.items.len()
1581        )
1582        .entered();
1583
1584        if area.is_empty() {
1585            return;
1586        }
1587
1588        // Clear the full owned viewport so empty renders and shorter rows do
1589        // not leak prior buffer content.
1590        clear_text_area(frame, area, self.style);
1591
1592        let total_items = self.items.len();
1593        if total_items == 0 {
1594            return;
1595        }
1596
1597        let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
1598            self.render_variable(area, frame, state);
1599            return;
1600        };
1601
1602        // Reserve space for scrollbar if needed
1603        let fixed_h = fixed_h.max(1);
1604        // Use div_ceil to include partially visible items and avoid 0 count for large items
1605        let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
1606        let fully_visible_items = (area.height / fixed_h) as usize;
1607        let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
1608        let content_width = if needs_scrollbar {
1609            area.width.saturating_sub(1)
1610        } else {
1611            area.width
1612        };
1613
1614        // Ensure selection is within bounds
1615        if let Some(selected) = state.selected
1616            && selected >= total_items
1617        {
1618            // Use saturating_sub to handle empty list case (total_items = 0)
1619            state.selected = if total_items > 0 {
1620                Some(total_items - 1)
1621            } else {
1622                None
1623            };
1624        }
1625
1626        // Ensure visible range includes selected item (it must be fully visible if possible)
1627        if let Some(selected) = state.selected {
1628            let vis_count = fully_visible_items.max(1);
1629            if selected >= state.scroll_offset.saturating_add(vis_count) {
1630                state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
1631            } else if selected < state.scroll_offset {
1632                state.scroll_offset = selected;
1633            }
1634        }
1635
1636        // Clamp scroll offset
1637        let max_offset = if fully_visible_items > 0 {
1638            total_items.saturating_sub(fully_visible_items)
1639        } else {
1640            total_items.saturating_sub(1)
1641        };
1642        state.scroll_offset = state.scroll_offset.min(max_offset);
1643
1644        // Update visible count — use fully_visible_items (not items_per_viewport
1645        // which includes partial items via div_ceil) so scroll calculations
1646        // (page size, max_offset) use a consistent metric.
1647        state.visible_count = fully_visible_items.max(1).min(total_items);
1648
1649        // Calculate render range with overscan
1650        let render_start = state.scroll_offset.saturating_sub(state.overscan);
1651        let render_end = state
1652            .scroll_offset
1653            .saturating_add(items_per_viewport)
1654            .saturating_add(state.overscan)
1655            .min(total_items);
1656
1657        // Render visible items
1658        for idx in render_start..render_end {
1659            // Calculate Y position relative to viewport
1660            // Use relative arithmetic to prevent overflow when indices exceed i32::MAX.
1661            let relative_idx = if idx >= state.scroll_offset {
1662                i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
1663            } else {
1664                // Handle overscan items before the scroll offset
1665                -(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
1666            };
1667
1668            let height_i32 = i32::from(fixed_h);
1669            let y_offset = relative_idx.saturating_mul(height_i32);
1670
1671            // Skip items above viewport
1672            // We use area.y as the viewport top.
1673            // Absolute top of item = area.y + y_offset.
1674            // Absolute bottom of item = area.y + y_offset + height.
1675            // If absolute_bottom <= area.y, it is fully above.
1676            // i.e. y_offset + height <= 0
1677            if y_offset.saturating_add(height_i32) <= 0 {
1678                continue;
1679            }
1680
1681            // Stop if below viewport
1682            if y_offset >= i32::from(area.height) {
1683                break;
1684            }
1685
1686            // Check if item starts off-screen top.
1687            // If so, we must render partially by skipping the top rows.
1688            let skip_rows = if y_offset < 0 {
1689                y_offset.unsigned_abs() as u16
1690            } else {
1691                0
1692            };
1693
1694            // Calculate actual render area
1695            // Use i32 arithmetic to avoid overflow when casting y_offset to i16
1696            let y = i32::from(area.y)
1697                .saturating_add(y_offset)
1698                .clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
1699
1700            if y >= area.bottom() {
1701                break;
1702            }
1703
1704            let visible_height = fixed_h
1705                .saturating_sub(skip_rows)
1706                .min(area.bottom().saturating_sub(y));
1707
1708            if visible_height == 0 {
1709                continue;
1710            }
1711
1712            let row_area = Rect::new(area.x, y, content_width, visible_height);
1713
1714            let is_selected = state.selected == Some(idx);
1715
1716            let row_style = if is_selected {
1717                self.highlight_style.merge(&self.style)
1718            } else {
1719                self.style
1720            };
1721            clear_text_area(frame, row_area, row_style);
1722
1723            // Render the item
1724            self.items[idx].render(row_area, frame, is_selected, skip_rows);
1725        }
1726
1727        // Render scrollbar
1728        if needs_scrollbar {
1729            let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
1730
1731            let mut scrollbar_state =
1732                ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
1733
1734            // Sync drag anchor from persistent state to transient scrollbar state
1735            scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
1736
1737            let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
1738            if let Some(id) = self.hit_id {
1739                scrollbar = scrollbar.hit_id(id);
1740            }
1741            scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
1742        }
1743    }
1744}
1745
1746/// First item that starts at or after `offset` (the item containing
1747/// `offset` when it starts exactly there, the next one otherwise), clamped
1748/// to the last item.
1749fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
1750    let mut idx = heights.find_item_at_offset_exact(offset);
1751    if heights.offset_of_item_exact(idx) < offset {
1752        idx += 1;
1753    }
1754    idx.min(heights.len().saturating_sub(1))
1755}
1756
1757/// Preserve exact row metrics when they fit, otherwise scale both thumb size
1758/// and scroll progress into the target's representable range. `capacity` is
1759/// usize::MAX in production and permits exercising the 32-bit boundary on a
1760/// 64-bit test host. Independent saturation of position and total loses the
1761/// scroll ratio and can put a halfway-scrolled list's thumb at the bottom.
1762fn scrollbar_state_for_rows(
1763    total: u64,
1764    position: u64,
1765    viewport: u16,
1766    capacity: usize,
1767) -> ScrollbarState {
1768    let limit = capacity as u64;
1769    if total <= limit {
1770        return ScrollbarState::new(
1771            total as usize,
1772            position.min(total) as usize,
1773            viewport.into(),
1774        );
1775    }
1776    let scaled_viewport = (u128::from(viewport) * u128::from(limit))
1777        .div_ceil(u128::from(total))
1778        .min(u128::from(limit)) as usize;
1779    let max_position = total.saturating_sub(u64::from(viewport));
1780    let scaled_position = if max_position == 0 {
1781        0
1782    } else {
1783        (u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
1784            / u128::from(max_position)) as usize
1785    };
1786    ScrollbarState::new(capacity, scaled_position, scaled_viewport)
1787}
1788
1789impl<T: RenderItem> VirtualizedList<'_, T> {
1790    /// Render in [`ListHeightMode::Variable`]: every row is as tall as
1791    /// [`RenderItem::height`] reports. The rows that can matter this frame
1792    /// (the selection and one screenful from the scroll offset) are measured
1793    /// into the state's Fenwick tracker first, so the selection adjustment,
1794    /// the bottom clamp and the scrollbar all work in rows with O(log n)
1795    /// offset queries instead of multiplying by a fixed height.
1796    fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
1797        let total_items = self.items.len();
1798        let viewport = area.height;
1799        let heights = state
1800            .heights
1801            .get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
1802        if heights.len() != total_items {
1803            heights.resize(total_items);
1804        }
1805
1806        let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
1807            let height = self.items[idx].height().max(1);
1808            if !heights.is_measured(idx) || heights.get(idx) != height {
1809                heights.set(idx, height);
1810            }
1811        };
1812        // Measure rows from `start` until they fill the viewport; returns how
1813        // many rows that took (at least one).
1814        let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
1815            let mut rows = 0u16;
1816            let mut idx = start;
1817            while idx < total_items && rows < viewport {
1818                measure(heights, idx);
1819                rows = rows.saturating_add(heights.get(idx));
1820                idx += 1;
1821            }
1822            (idx - start).max(1)
1823        };
1824
1825        // Keep the selection in range and in view.
1826        if let Some(selected) = state.selected
1827            && selected >= total_items
1828        {
1829            state.selected = Some(total_items - 1);
1830        }
1831        if let Some(selected) = state.selected {
1832            measure(heights, selected);
1833            if selected < state.scroll_offset {
1834                state.scroll_offset = selected;
1835            } else {
1836                measure_screenful(heights, state.scroll_offset);
1837                let top = heights.offset_of_item_exact(state.scroll_offset);
1838                let bottom = heights.offset_of_item_exact(selected + 1);
1839                if bottom.saturating_sub(top) > u64::from(viewport) {
1840                    let anchor = bottom.saturating_sub(u64::from(viewport));
1841                    state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
1842                }
1843            }
1844        }
1845
1846        // Clamp so the last screenful is as full as item alignment allows.
1847        let total_height = heights.total_height_exact();
1848        let max_start = if total_height > u64::from(viewport) {
1849            first_item_from_offset(heights, total_height - u64::from(viewport))
1850        } else {
1851            0
1852        };
1853        state.scroll_offset = state.scroll_offset.min(max_start);
1854
1855        let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
1856        state.visible_count = visible;
1857
1858        let total_height = heights.total_height_exact();
1859        let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
1860        let content_width = if needs_scrollbar {
1861            area.width.saturating_sub(1)
1862        } else {
1863            area.width
1864        };
1865
1866        let mut y = 0u16;
1867        for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
1868        {
1869            if y >= viewport {
1870                break;
1871            }
1872            let row_h = heights.get(idx).min(viewport - y);
1873            if row_h == 0 {
1874                continue;
1875            }
1876            let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
1877            let is_selected = state.selected == Some(idx);
1878            let row_style = if is_selected {
1879                self.highlight_style.merge(&self.style)
1880            } else {
1881                self.style
1882            };
1883            clear_text_area(frame, row_area, row_style);
1884            self.items[idx].render(row_area, frame, is_selected, 0);
1885            y = y.saturating_add(row_h);
1886        }
1887
1888        if needs_scrollbar {
1889            let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
1890            let mut scrollbar_state = scrollbar_state_for_rows(
1891                total_height,
1892                heights.offset_of_item_exact(state.scroll_offset),
1893                viewport,
1894                usize::MAX,
1895            );
1896            scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
1897            let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
1898            if let Some(id) = self.hit_id {
1899                scrollbar = scrollbar.hit_id(id);
1900            }
1901            scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
1902        }
1903    }
1904}
1905
1906// ============================================================================
1907// Simple RenderItem implementations for common types
1908// ============================================================================
1909
1910impl RenderItem for String {
1911    fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
1912        if area.is_empty() {
1913            return;
1914        }
1915        let max_chars = area.width as usize;
1916        // String is assumed to be single-line in this implementation, so skip_rows > 0
1917        // implies the whole item is skipped. However, for robustness we check bounds.
1918        // If a String *did* contain newlines and we rendered it multiline, skip_rows would apply.
1919        // Here we just render the first line.
1920        if skip_rows > 0 {
1921            return;
1922        }
1923        for (i, ch) in self.chars().take(max_chars).enumerate() {
1924            frame
1925                .buffer
1926                .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
1927        }
1928    }
1929}
1930
1931impl RenderItem for &str {
1932    fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
1933        if area.is_empty() {
1934            return;
1935        }
1936        if skip_rows > 0 {
1937            return;
1938        }
1939        let max_chars = area.width as usize;
1940        for (i, ch) in self.chars().take(max_chars).enumerate() {
1941            frame
1942                .buffer
1943                .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
1944        }
1945    }
1946}
1947
1948#[cfg(test)]
1949mod tests {
1950    use super::*;
1951    use proptest::prelude::*;
1952
1953    fn raw_row_text(frame: &Frame, y: u16) -> String {
1954        let width = frame.buffer.width();
1955        let mut actual = String::new();
1956        for x in 0..width {
1957            let ch = frame
1958                .buffer
1959                .get(x, y)
1960                .and_then(|cell| cell.content.as_char())
1961                .unwrap_or(' ');
1962            actual.push(ch);
1963        }
1964        actual
1965    }
1966
1967    #[test]
1968    fn test_new_virtualized() {
1969        let virt: Virtualized<String> = Virtualized::new(100);
1970        assert_eq!(virt.len(), 0);
1971        assert!(virt.is_empty());
1972    }
1973
1974    #[test]
1975    fn test_push_and_len() {
1976        let mut virt: Virtualized<i32> = Virtualized::new(100);
1977        virt.push(1);
1978        virt.push(2);
1979        virt.push(3);
1980        assert_eq!(virt.len(), 3);
1981        assert!(!virt.is_empty());
1982    }
1983
1984    #[test]
1985    fn test_visible_range_fixed_height() {
1986        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
1987        for i in 0..20 {
1988            virt.push(i);
1989        }
1990        // 10 items visible with height 2 in viewport 20
1991        let range = virt.visible_range(20);
1992        assert_eq!(range, 0..10);
1993    }
1994
1995    #[test]
1996    fn test_visible_range_variable_height_clamps() {
1997        let mut cache = HeightCache::new(1, 16);
1998        cache.set(0, 3);
1999        cache.set(1, 3);
2000        cache.set(2, 3);
2001        let mut virt: Virtualized<i32> =
2002            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2003        for i in 0..3 {
2004            virt.push(i);
2005        }
2006        let range = virt.visible_range(5);
2007        // Includes the partially visible second item.
2008        assert_eq!(range, 0..2);
2009    }
2010
2011    #[test]
2012    fn test_visible_range_variable_height_exact_fit() {
2013        let mut cache = HeightCache::new(1, 16);
2014        cache.set(0, 2);
2015        cache.set(1, 3);
2016        let mut virt: Virtualized<i32> =
2017            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2018        for i in 0..2 {
2019            virt.push(i);
2020        }
2021        let range = virt.visible_range(5);
2022        assert_eq!(range, 0..2);
2023    }
2024
2025    #[test]
2026    fn test_visible_range_with_scroll() {
2027        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
2028        for i in 0..50 {
2029            virt.push(i);
2030        }
2031        virt.scroll(10);
2032        let range = virt.visible_range(10);
2033        assert_eq!(range, 10..20);
2034    }
2035
2036    #[test]
2037    fn test_visible_range_variable_height_excludes_partial() {
2038        let mut cache = HeightCache::new(1, 16);
2039        cache.set(0, 6);
2040        cache.set(1, 6);
2041        let mut virt: Virtualized<i32> =
2042            Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2043        virt.push(1);
2044        virt.push(2);
2045        virt.push(3);
2046
2047        let range = virt.visible_range(10);
2048        // Includes the partially visible second item.
2049        assert_eq!(range, 0..2);
2050    }
2051
2052    #[test]
2053    fn test_visible_range_variable_height_exact_fit_larger() {
2054        let mut cache = HeightCache::new(1, 16);
2055        cache.set(0, 4);
2056        cache.set(1, 6);
2057        let mut virt: Virtualized<i32> =
2058            Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2059        virt.push(1);
2060        virt.push(2);
2061        virt.push(3);
2062
2063        let range = virt.visible_range(10);
2064        assert_eq!(range, 0..2);
2065    }
2066
2067    #[test]
2068    fn test_visible_range_variable_height_default_for_unmeasured() {
2069        let cache = HeightCache::new(2, 16);
2070        let mut virt: Virtualized<i32> =
2071            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2072        for i in 0..3 {
2073            virt.push(i);
2074        }
2075
2076        // Default height = 2, viewport 5 fits 2 items (2 + 2) but not the third.
2077        let range = virt.visible_range(5);
2078        // Includes the partially visible third item.
2079        assert_eq!(range, 0..3);
2080    }
2081
2082    #[test]
2083    fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
2084        let mut virt: Virtualized<i32> =
2085            Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2086        for i in 0..20 {
2087            virt.push(i);
2088        }
2089        // Viewport unknown (visible_count = 0): scroll_to_bottom stores the
2090        // lazy sentinel. The last screenful is 5 items of height 2.
2091        virt.scroll_to_bottom();
2092        assert_eq!(virt.visible_range(10), 15..20);
2093    }
2094
2095    #[test]
2096    fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
2097        let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
2098        for i in 0..20 {
2099            virt.push(i);
2100        }
2101        // Regression: this used to return the empty range 20..20 because the
2102        // unclamped sentinel offset reached the tracker as start_idx == len.
2103        virt.scroll_to_bottom();
2104        assert_eq!(virt.visible_range(10), 15..20);
2105    }
2106
2107    #[test]
2108    fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
2109        // Heights [3,2,5,1,4]: the last 5 rows are exactly items 3 (h=1) and
2110        // 4 (h=4); a 6-row viewport additionally clips into item 2.
2111        let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
2112        let mut virt: Virtualized<i32> =
2113            Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
2114        for i in 0..5 {
2115            virt.push(i);
2116        }
2117        virt.scroll_to_bottom();
2118        assert_eq!(virt.visible_range(5), 3..5);
2119        virt.scroll_to_bottom();
2120        assert_eq!(virt.visible_range(6), 2..5);
2121    }
2122
2123    #[test]
2124    fn test_visible_range_variable_near_end_clamps_like_fixed() {
2125        // Scrolling to the last item must not leave blank rows below it,
2126        // matching the Fixed arm's max_offset clamping.
2127        let mut virt: Virtualized<i32> =
2128            Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2129        for i in 0..20 {
2130            virt.push(i);
2131        }
2132        virt.scroll_to(18);
2133        assert_eq!(virt.visible_range(10), 15..20);
2134    }
2135
2136    #[test]
2137    fn test_render_range_with_overscan() {
2138        let mut virt: Virtualized<i32> =
2139            Virtualized::new(100).with_fixed_height(1).with_overscan(2);
2140        for i in 0..50 {
2141            virt.push(i);
2142        }
2143        virt.scroll(10);
2144        let range = virt.render_range(10);
2145        // Visible: 10..20, Overscan: 2
2146        // Render: 8..22
2147        assert_eq!(range, 8..22);
2148    }
2149
2150    #[test]
2151    fn test_scroll_bounds() {
2152        let mut virt: Virtualized<i32> = Virtualized::new(100);
2153        for i in 0..10 {
2154            virt.push(i);
2155        }
2156
2157        // Can't scroll negative
2158        virt.scroll(-100);
2159        assert_eq!(virt.scroll_offset(), 0);
2160
2161        // Can't scroll past end
2162        virt.scroll(100);
2163        assert_eq!(virt.scroll_offset(), 9);
2164    }
2165
2166    #[test]
2167    fn test_scroll_to() {
2168        let mut virt: Virtualized<i32> = Virtualized::new(100);
2169        for i in 0..20 {
2170            virt.push(i);
2171        }
2172
2173        virt.scroll_to(15);
2174        assert_eq!(virt.scroll_offset(), 15);
2175
2176        // Clamps to max
2177        virt.scroll_to(100);
2178        assert_eq!(virt.scroll_offset(), 19);
2179    }
2180
2181    #[test]
2182    fn test_follow_mode() {
2183        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
2184        virt.set_visible_count(5);
2185
2186        for i in 0..10 {
2187            virt.push(i);
2188        }
2189
2190        // Should be at bottom
2191        assert!(virt.is_at_bottom());
2192
2193        // Manual scroll disables follow
2194        virt.scroll(-5);
2195        assert!(!virt.follow_mode());
2196    }
2197
2198    #[test]
2199    fn test_scroll_to_start_and_end() {
2200        let mut virt: Virtualized<i32> = Virtualized::new(100);
2201        virt.set_visible_count(5);
2202        for i in 0..20 {
2203            virt.push(i);
2204        }
2205
2206        // scroll_to_start goes to top and disables follow
2207        virt.scroll_to(10);
2208        virt.set_follow(true);
2209        virt.scroll_to_start();
2210        assert_eq!(virt.scroll_offset(), 0);
2211        assert!(!virt.follow_mode());
2212
2213        // scroll_to_end goes to bottom and enables follow
2214        virt.scroll_to_end();
2215        assert!(virt.is_at_bottom());
2216        assert!(virt.follow_mode());
2217    }
2218
2219    #[test]
2220    fn test_virtualized_page_navigation() {
2221        let mut virt: Virtualized<i32> = Virtualized::new(100);
2222        virt.set_visible_count(5);
2223        for i in 0..30 {
2224            virt.push(i);
2225        }
2226
2227        virt.scroll_to(15);
2228        virt.page_up();
2229        // Page navigation keeps 1 row of context (visible_count - 1).
2230        assert_eq!(virt.scroll_offset(), 11);
2231
2232        virt.page_down();
2233        assert_eq!(virt.scroll_offset(), 15);
2234
2235        // Page up at start clamps to 0
2236        virt.scroll_to(2);
2237        virt.page_up();
2238        assert_eq!(virt.scroll_offset(), 0);
2239    }
2240
2241    #[test]
2242    fn test_height_cache() {
2243        let mut cache = HeightCache::new(1, 100);
2244
2245        // Default value
2246        assert_eq!(cache.get(0), 1);
2247        assert_eq!(cache.get(50), 1);
2248
2249        // Set value
2250        cache.set(5, 3);
2251        assert_eq!(cache.get(5), 3);
2252
2253        // Other indices still default
2254        assert_eq!(cache.get(4), 1);
2255        assert_eq!(cache.get(6), 1);
2256    }
2257
2258    #[test]
2259    fn test_height_cache_large_index_window() {
2260        let mut cache = HeightCache::new(1, 8);
2261        cache.set(10_000, 4);
2262        assert_eq!(cache.get(10_000), 4);
2263        assert_eq!(cache.get(0), 1);
2264        assert!(cache.cache.len() <= cache.capacity);
2265    }
2266
2267    #[test]
2268    fn test_clear() {
2269        let mut virt: Virtualized<i32> = Virtualized::new(100);
2270        for i in 0..10 {
2271            virt.push(i);
2272        }
2273        virt.scroll(5);
2274
2275        virt.clear();
2276        assert_eq!(virt.len(), 0);
2277        assert_eq!(virt.scroll_offset(), 0);
2278    }
2279
2280    #[test]
2281    fn test_get_item() {
2282        let mut virt: Virtualized<String> = Virtualized::new(100);
2283        virt.push("hello".to_string());
2284        virt.push("world".to_string());
2285
2286        assert_eq!(virt.get(0), Some(&"hello".to_string()));
2287        assert_eq!(virt.get(1), Some(&"world".to_string()));
2288        assert_eq!(virt.get(2), None);
2289    }
2290
2291    #[test]
2292    fn test_external_storage_len() {
2293        let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
2294        assert_eq!(virt.len(), 1000);
2295
2296        virt.set_external_len(2000);
2297        assert_eq!(virt.len(), 2000);
2298    }
2299
2300    #[test]
2301    fn test_momentum_scrolling() {
2302        let mut virt: Virtualized<i32> = Virtualized::new(100);
2303        for i in 0..50 {
2304            virt.push(i);
2305        }
2306
2307        virt.fling(10.0);
2308
2309        // Simulate tick
2310        virt.tick(Duration::from_millis(100));
2311
2312        // Should have scrolled
2313        assert!(virt.scroll_offset() > 0);
2314    }
2315
2316    // ========================================================================
2317    // VirtualizedListState tests
2318    // ========================================================================
2319
2320    #[test]
2321    fn test_virtualized_list_state_new() {
2322        let state = VirtualizedListState::new();
2323        assert_eq!(state.selected, None);
2324        assert_eq!(state.scroll_offset(), 0);
2325        assert_eq!(state.visible_count(), 0);
2326    }
2327
2328    #[test]
2329    fn test_virtualized_list_state_select_next() {
2330        let mut state = VirtualizedListState::new();
2331
2332        state.select_next(10);
2333        assert_eq!(state.selected, Some(0));
2334
2335        state.select_next(10);
2336        assert_eq!(state.selected, Some(1));
2337
2338        // At last item, stays there
2339        state.selected = Some(9);
2340        state.select_next(10);
2341        assert_eq!(state.selected, Some(9));
2342    }
2343
2344    #[test]
2345    fn test_virtualized_list_state_select_previous() {
2346        let mut state = VirtualizedListState::new();
2347        state.selected = Some(5);
2348
2349        state.select_previous(10);
2350        assert_eq!(state.selected, Some(4));
2351
2352        state.selected = Some(0);
2353        state.select_previous(10);
2354        assert_eq!(state.selected, Some(0));
2355    }
2356
2357    #[test]
2358    fn test_virtualized_list_state_scroll() {
2359        let mut state = VirtualizedListState::new();
2360
2361        state.scroll(5, 20);
2362        assert_eq!(state.scroll_offset(), 5);
2363
2364        state.scroll(-3, 20);
2365        assert_eq!(state.scroll_offset(), 2);
2366
2367        // Can't scroll negative
2368        state.scroll(-100, 20);
2369        assert_eq!(state.scroll_offset(), 0);
2370
2371        // Can't scroll past end
2372        state.scroll(100, 20);
2373        assert_eq!(state.scroll_offset(), 19);
2374    }
2375
2376    #[test]
2377    fn test_virtualized_list_state_follow_mode() {
2378        let mut state = VirtualizedListState::new().with_follow(true);
2379        assert!(state.follow_mode());
2380
2381        // Manual scroll disables follow
2382        state.scroll(5, 20);
2383        assert!(!state.follow_mode());
2384    }
2385
2386    #[test]
2387    fn test_render_item_string() {
2388        // Verify String implements RenderItem
2389        let s = String::from("hello");
2390        assert_eq!(s.height(), 1);
2391    }
2392
2393    #[test]
2394    fn test_page_up_down() {
2395        let mut virt: Virtualized<i32> = Virtualized::new(100);
2396        for i in 0..50 {
2397            virt.push(i);
2398        }
2399        virt.set_visible_count(10);
2400
2401        // Start at top
2402        assert_eq!(virt.scroll_offset(), 0);
2403
2404        // Page down
2405        virt.page_down();
2406        assert_eq!(virt.scroll_offset(), 9);
2407
2408        // Page down again
2409        virt.page_down();
2410        assert_eq!(virt.scroll_offset(), 18);
2411
2412        // Page up
2413        virt.page_up();
2414        assert_eq!(virt.scroll_offset(), 9);
2415
2416        // Page up again
2417        virt.page_up();
2418        assert_eq!(virt.scroll_offset(), 0);
2419
2420        // Page up at top stays at 0
2421        virt.page_up();
2422        assert_eq!(virt.scroll_offset(), 0);
2423    }
2424
2425    // ========================================================================
2426    // Performance invariant tests (bd-uo6v)
2427    // ========================================================================
2428
2429    #[test]
2430    fn test_render_scales_with_visible_not_total() {
2431        use ftui_render::grapheme_pool::GraphemePool;
2432        use std::time::Instant;
2433
2434        // Setup: VirtualizedList with 1K items
2435        let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
2436        let small_list = VirtualizedList::new(&small_items);
2437        let mut small_state = VirtualizedListState::new();
2438
2439        let area = Rect::new(0, 0, 80, 24);
2440        let mut pool = GraphemePool::new();
2441        let mut frame = Frame::new(80, 24, &mut pool);
2442
2443        // Warm up
2444        small_list.render(area, &mut frame, &mut small_state);
2445
2446        let start = Instant::now();
2447        for _ in 0..100 {
2448            frame.buffer.clear();
2449            small_list.render(area, &mut frame, &mut small_state);
2450        }
2451        let small_time = start.elapsed();
2452
2453        // Setup: VirtualizedList with 100K items
2454        let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
2455        let large_list = VirtualizedList::new(&large_items);
2456        let mut large_state = VirtualizedListState::new();
2457
2458        // Warm up
2459        large_list.render(area, &mut frame, &mut large_state);
2460
2461        let start = Instant::now();
2462        for _ in 0..100 {
2463            frame.buffer.clear();
2464            large_list.render(area, &mut frame, &mut large_state);
2465        }
2466        let large_time = start.elapsed();
2467
2468        // 100K should be within 3x of 1K (both render ~24 items)
2469        assert!(
2470            large_time < small_time * 3,
2471            "Render does not scale O(visible): 1K={:?}, 100K={:?}",
2472            small_time,
2473            large_time
2474        );
2475    }
2476
2477    #[test]
2478    fn test_scroll_is_constant_time() {
2479        use std::time::Instant;
2480
2481        let mut small: Virtualized<i32> = Virtualized::new(1_000);
2482        for i in 0..1_000 {
2483            small.push(i);
2484        }
2485        small.set_visible_count(24);
2486
2487        let mut large: Virtualized<i32> = Virtualized::new(100_000);
2488        for i in 0..100_000 {
2489            large.push(i);
2490        }
2491        large.set_visible_count(24);
2492
2493        let iterations = 10_000;
2494
2495        // Warm up both paths so the timed runs are not skewed by first-touch
2496        // page faults / branch predictor / cache warming.
2497        for _ in 0..iterations {
2498            small.scroll(1);
2499            small.scroll(-1);
2500            large.scroll(1);
2501            large.scroll(-1);
2502        }
2503
2504        // Take the best (minimum) of several timed runs for each list. The
2505        // minimum is the measurement least contaminated by scheduling jitter,
2506        // GC of other processes, and CI load — exactly the noise that made the
2507        // old single-shot comparison flaky.
2508        let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
2509            let runs = 5;
2510            let mut best = std::time::Duration::MAX;
2511            for _ in 0..runs {
2512                let start = Instant::now();
2513                for _ in 0..iterations {
2514                    v.scroll(1);
2515                    v.scroll(-1);
2516                }
2517                best = best.min(start.elapsed());
2518            }
2519            best
2520        };
2521
2522        let small_time = measure(&mut small);
2523        let large_time = measure(&mut large);
2524
2525        // The real signal we care about is "scroll cost does NOT grow with list
2526        // size" (i.e. it is O(1), not O(n)). With n differing by 100x, a truly
2527        // O(n) scroll would make `large_time` ~100x `small_time`. A generous
2528        // constant-factor ceiling distinguishes O(1) from O(n) without flaking
2529        // on scheduling jitter, so we allow a wide multiplier here.
2530        let ceiling = small_time
2531            .checked_mul(10)
2532            .unwrap_or(std::time::Duration::MAX);
2533        assert!(
2534            large_time < ceiling,
2535            "Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
2536            small_time,
2537            large_time
2538        );
2539    }
2540
2541    #[test]
2542    fn render_partially_offscreen_top_skips_item() {
2543        use ftui_render::grapheme_pool::GraphemePool;
2544
2545        // Items with height 2, each rendering its index as a character
2546        struct IndexedItem(usize);
2547        impl RenderItem for IndexedItem {
2548            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2549                let ch = char::from_digit(self.0 as u32, 10).unwrap();
2550                for y in area.y..area.bottom() {
2551                    frame.buffer.set(area.x, y, Cell::from_char(ch));
2552                }
2553            }
2554            fn height(&self) -> u16 {
2555                2
2556            }
2557        }
2558
2559        // Need 4+ items so scroll_offset=1 is valid:
2560        // items_per_viewport = 5/2 = 2, max_offset = 4-2 = 2
2561        let items = vec![
2562            IndexedItem(0),
2563            IndexedItem(1),
2564            IndexedItem(2),
2565            IndexedItem(3),
2566        ];
2567        let list = VirtualizedList::new(&items).fixed_height(2);
2568
2569        // Scroll so item 1 is at top, item 0 is in overscan (above viewport)
2570        let mut state = VirtualizedListState::new().with_overscan(1);
2571        state.scroll_offset = 1; // Item 1 is top visible. Item 0 is in overscan.
2572
2573        let mut pool = GraphemePool::new();
2574        let mut frame = Frame::new(10, 5, &mut pool);
2575
2576        // Render at y=0 (terminal top edge)
2577        list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
2578
2579        // With scroll_offset=1 and overscan=1:
2580        // - render_start = 1 - 1 = 0 (include item 0 in overscan)
2581        // - Item 0 would render at y_offset = (0-1)*2 = -2
2582        // - area.y + y_offset = 0 + (-2) = -2 < 0, so item 0 must be SKIPPED
2583        // - Item 1 renders at y_offset = (1-1)*2 = 0
2584        //
2585        // Row 0 should be '1' (from Item 1), NOT '0' (from Item 0 ghosting)
2586        let cell = frame.buffer.get(0, 0).unwrap();
2587        assert_eq!(cell.content.as_char(), Some('1'));
2588    }
2589
2590    #[test]
2591    fn render_bottom_boundary_clips_partial_item() {
2592        use ftui_render::grapheme_pool::GraphemePool;
2593
2594        struct IndexedItem(u16);
2595        impl RenderItem for IndexedItem {
2596            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2597                let ch = char::from_digit(self.0 as u32, 10).unwrap();
2598                for y in area.y..area.bottom() {
2599                    frame.buffer.set(area.x, y, Cell::from_char(ch));
2600                }
2601            }
2602            fn height(&self) -> u16 {
2603                2
2604            }
2605        }
2606
2607        let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
2608        let list = VirtualizedList::new(&items)
2609            .fixed_height(2)
2610            .show_scrollbar(false);
2611        let mut state = VirtualizedListState::new();
2612
2613        let mut pool = GraphemePool::new();
2614        let mut frame = Frame::new(4, 4, &mut pool);
2615
2616        // Viewport height 3 means the second item is only partially visible.
2617        list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
2618
2619        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2620        assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
2621        assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
2622        // Row outside the viewport should remain empty.
2623        assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
2624    }
2625
2626    #[test]
2627    fn render_after_fling_advances_visible_rows() {
2628        use ftui_render::grapheme_pool::GraphemePool;
2629
2630        struct IndexedItem(u16);
2631        impl RenderItem for IndexedItem {
2632            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2633                let ch = char::from_digit(self.0 as u32, 10).unwrap();
2634                for y in area.y..area.bottom() {
2635                    frame.buffer.set(area.x, y, Cell::from_char(ch));
2636                }
2637            }
2638        }
2639
2640        let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
2641        let list = VirtualizedList::new(&items)
2642            .fixed_height(1)
2643            .show_scrollbar(false);
2644        let mut state = VirtualizedListState::new();
2645
2646        let mut pool = GraphemePool::new();
2647        let mut frame = Frame::new(4, 3, &mut pool);
2648        let area = Rect::new(0, 0, 4, 3);
2649
2650        // Initial render establishes visible_count and baseline top row.
2651        list.render(area, &mut frame, &mut state);
2652        assert_eq!(state.scroll_offset(), 0);
2653        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2654
2655        // Momentum scroll: 40.0 * 0.1s = 4 rows.
2656        state.fling(40.0);
2657        state.tick(Duration::from_millis(100), items.len());
2658        assert_eq!(state.scroll_offset(), 4);
2659
2660        frame.buffer.clear();
2661        list.render(area, &mut frame, &mut state);
2662        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
2663    }
2664
2665    #[test]
2666    fn render_empty_virtualized_list_clears_stale_viewport() {
2667        use ftui_render::grapheme_pool::GraphemePool;
2668
2669        let items: Vec<String> = Vec::new();
2670        let list = VirtualizedList::new(&items).show_scrollbar(false);
2671        let mut state = VirtualizedListState::new();
2672        let mut pool = GraphemePool::new();
2673        let mut frame = Frame::new(6, 3, &mut pool);
2674        let area = Rect::new(0, 0, 6, 3);
2675        frame.buffer.fill(area, Cell::from_char('X'));
2676
2677        list.render(area, &mut frame, &mut state);
2678
2679        assert_eq!(raw_row_text(&frame, 0), "      ");
2680        assert_eq!(raw_row_text(&frame, 1), "      ");
2681        assert_eq!(raw_row_text(&frame, 2), "      ");
2682    }
2683
2684    #[test]
2685    fn render_shorter_virtualized_row_clears_stale_suffix() {
2686        use ftui_render::grapheme_pool::GraphemePool;
2687
2688        let long_items = vec!["Hello".to_string()];
2689        let short_items = vec!["Hi".to_string()];
2690        let area = Rect::new(0, 0, 6, 1);
2691        let mut state = VirtualizedListState::new();
2692        let mut pool = GraphemePool::new();
2693        let mut frame = Frame::new(6, 1, &mut pool);
2694
2695        VirtualizedList::new(&long_items)
2696            .show_scrollbar(false)
2697            .render(area, &mut frame, &mut state);
2698        VirtualizedList::new(&short_items)
2699            .show_scrollbar(false)
2700            .render(area, &mut frame, &mut state);
2701
2702        assert_eq!(raw_row_text(&frame, 0), "Hi    ");
2703    }
2704
2705    #[test]
2706    fn test_memory_bounded_by_ring_capacity() {
2707        use crate::log_ring::LogRing;
2708
2709        let mut ring: LogRing<String> = LogRing::new(1_000);
2710
2711        // Add 100K items
2712        for i in 0..100_000 {
2713            ring.push(format!("Line {}", i));
2714        }
2715
2716        // Only 1K in memory
2717        assert_eq!(ring.len(), 1_000);
2718        assert_eq!(ring.total_count(), 100_000);
2719        assert_eq!(ring.first_index(), 99_000);
2720
2721        // Can still access recent items
2722        assert!(ring.get(99_999).is_some());
2723        assert!(ring.get(99_000).is_some());
2724        // Old items evicted
2725        assert!(ring.get(0).is_none());
2726        assert!(ring.get(98_999).is_none());
2727    }
2728
2729    #[test]
2730    fn test_visible_range_constant_regardless_of_total() {
2731        let mut small: Virtualized<i32> = Virtualized::new(100);
2732        for i in 0..100 {
2733            small.push(i);
2734        }
2735        let small_range = small.visible_range(24);
2736
2737        let mut large: Virtualized<i32> = Virtualized::new(100_000);
2738        for i in 0..100_000 {
2739            large.push(i);
2740        }
2741        let large_range = large.visible_range(24);
2742
2743        // Both should return exactly 24 visible items
2744        assert_eq!(small_range.end - small_range.start, 24);
2745        assert_eq!(large_range.end - large_range.start, 24);
2746    }
2747
2748    #[test]
2749    fn test_virtualized_list_state_page_up_down() {
2750        let mut state = VirtualizedListState::new();
2751        state.visible_count = 10;
2752
2753        // Page down
2754        state.page_down(50);
2755        assert_eq!(state.scroll_offset(), 9);
2756
2757        // Page down again
2758        state.page_down(50);
2759        assert_eq!(state.scroll_offset(), 18);
2760
2761        // Page up
2762        state.page_up(50);
2763        assert_eq!(state.scroll_offset(), 9);
2764
2765        // Page up again
2766        state.page_up(50);
2767        assert_eq!(state.scroll_offset(), 0);
2768    }
2769
2770    // ========================================================================
2771    // VariableHeightsFenwick tests (bd-2zbk.7)
2772    // ========================================================================
2773
2774    #[test]
2775    fn test_variable_heights_fenwick_new() {
2776        let tracker = VariableHeightsFenwick::new(2, 10);
2777        assert_eq!(tracker.len(), 10);
2778        assert!(!tracker.is_empty());
2779        assert_eq!(tracker.default_height(), 2);
2780    }
2781
2782    #[test]
2783    fn test_variable_heights_fenwick_empty() {
2784        let tracker = VariableHeightsFenwick::new(1, 0);
2785        assert!(tracker.is_empty());
2786        assert_eq!(tracker.total_height(), 0);
2787    }
2788
2789    #[test]
2790    fn test_variable_heights_fenwick_from_heights() {
2791        let heights = vec![3, 2, 5, 1, 4];
2792        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2793
2794        assert_eq!(tracker.len(), 5);
2795        assert_eq!(tracker.get(0), 3);
2796        assert_eq!(tracker.get(1), 2);
2797        assert_eq!(tracker.get(2), 5);
2798        assert_eq!(tracker.get(3), 1);
2799        assert_eq!(tracker.get(4), 4);
2800        assert_eq!(tracker.total_height(), 15);
2801    }
2802
2803    #[test]
2804    fn test_variable_heights_fenwick_offset_of_item() {
2805        // Heights: [3, 2, 5, 1, 4] -> offsets: [0, 3, 5, 10, 11]
2806        let heights = vec![3, 2, 5, 1, 4];
2807        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2808
2809        assert_eq!(tracker.offset_of_item(0), 0);
2810        assert_eq!(tracker.offset_of_item(1), 3);
2811        assert_eq!(tracker.offset_of_item(2), 5);
2812        assert_eq!(tracker.offset_of_item(3), 10);
2813        assert_eq!(tracker.offset_of_item(4), 11);
2814        assert_eq!(tracker.offset_of_item(5), 15); // beyond end
2815    }
2816
2817    #[test]
2818    fn test_variable_heights_fenwick_find_item_at_offset() {
2819        // Heights: [3, 2, 5, 1, 4] -> cumulative: [3, 5, 10, 11, 15]
2820        let heights = vec![3, 2, 5, 1, 4];
2821        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2822
2823        // Offset 0 should be item 0
2824        assert_eq!(tracker.find_item_at_offset(0), 0);
2825        // Offset 1 should be item 0 (within first item)
2826        assert_eq!(tracker.find_item_at_offset(1), 0);
2827        // Offset 3 should be item 1 (starts at offset 3)
2828        assert_eq!(tracker.find_item_at_offset(3), 1);
2829        // Offset 5 should be item 2
2830        assert_eq!(tracker.find_item_at_offset(5), 2);
2831        // Offset 10 should be item 3
2832        assert_eq!(tracker.find_item_at_offset(10), 3);
2833        // Offset 11 should be item 4
2834        assert_eq!(tracker.find_item_at_offset(11), 4);
2835        // Offset 15 should be end (beyond all items)
2836        assert_eq!(tracker.find_item_at_offset(15), 5);
2837    }
2838
2839    #[test]
2840    fn fenwick_large_height_totals_do_not_wrap() {
2841        let heights = vec![u16::MAX; 131_072];
2842        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2843        let offset = 4_294_836_224_u32;
2844        assert_eq!(
2845            tracker.find_item_at_offset(offset),
2846            (u64::from(offset) / u64::from(u16::MAX)) as usize,
2847            "a wrapped root aggregate must not skip the entire list"
2848        );
2849        assert_eq!(tracker.total_height(), u32::MAX);
2850        assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
2851    }
2852
2853    #[test]
2854    #[should_panic(expected = "height index exceeds usize")]
2855    fn fenwick_rejects_unrepresentable_index() {
2856        VariableHeightsFenwick::default().set(usize::MAX, 1);
2857    }
2858
2859    #[test]
2860    fn fenwick_large_updates_and_resize_match_u64_oracle() {
2861        fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
2862            let mut prefixes = Vec::with_capacity(heights.len() + 1);
2863            prefixes.push(0u64);
2864            for &height in heights {
2865                prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
2866            }
2867            let total = prefixes.last().copied().unwrap();
2868            assert_eq!(tracker.len(), heights.len());
2869            assert_eq!(tracker.total_height_exact(), total);
2870            assert_eq!(
2871                tracker.total_height(),
2872                total.min(u64::from(u32::MAX)) as u32
2873            );
2874            let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
2875            for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
2876                assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
2877                assert_eq!(
2878                    tracker.offset_of_item(idx),
2879                    prefixes[idx].min(u64::from(u32::MAX)) as u32
2880                );
2881                queries.extend([
2882                    prefixes[idx].saturating_sub(1),
2883                    prefixes[idx],
2884                    prefixes[idx] + 1,
2885                ]);
2886            }
2887            for offset in queries {
2888                let expected = if offset == 0 {
2889                    0
2890                } else {
2891                    prefixes[1..].partition_point(|&prefix| prefix <= offset)
2892                };
2893                assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
2894                if let Ok(offset) = u32::try_from(offset) {
2895                    assert_eq!(tracker.find_item_at_offset(offset), expected);
2896                }
2897            }
2898        }
2899
2900        // The middle length totals exactly u32::MAX; neighboring lengths
2901        // exercise both sides of the public saturation boundary.
2902        for len in [65_536, 65_537, 65_538, 131_072] {
2903            let mut heights = vec![u16::MAX; len];
2904            let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
2905            check(&tracker, &heights);
2906            for idx in [0, 1, 32_768, 65_535, len - 1] {
2907                tracker.set(idx, 0);
2908                heights[idx] = 0;
2909                assert_eq!(tracker.get(idx), 0);
2910            }
2911            check(&tracker, &heights);
2912            tracker.set(0, u16::MAX);
2913            heights[0] = u16::MAX;
2914            tracker.resize(65_536);
2915            heights.truncate(65_536);
2916            check(&tracker, &heights);
2917            tracker.resize(65_540);
2918            heights.resize(65_540, u16::MAX);
2919            check(&tracker, &heights);
2920        }
2921
2922        // Deterministic varied heights and repeated signed updates exercise
2923        // aggregate values that uniform-height arithmetic alone cannot cover.
2924        let mut seed = 0xa076_1d64_78bd_642fu64;
2925        let mut heights: Vec<u16> = (0..131_072)
2926            .map(|_| {
2927                seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
2928                32_768 + ((seed >> 48) as u16 / 2)
2929            })
2930            .collect();
2931        let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2932        for idx in (0..heights.len()).step_by(997) {
2933            heights[idx] = (idx % 65_536) as u16;
2934            tracker.set(idx, heights[idx]);
2935            assert_eq!(tracker.get(idx), heights[idx]);
2936        }
2937        check(&tracker, &heights);
2938        tracker.drop_front(3);
2939        check(&tracker, &heights[3..]);
2940        heights.fill(u16::MAX);
2941        tracker.rebuild(&heights);
2942        check(&tracker, &heights);
2943        tracker.clear();
2944        check(&tracker, &[]);
2945        tracker.resize(4);
2946        check(&tracker, &[1; 4]);
2947    }
2948
2949    #[test]
2950    fn fenwick_large_visible_range_keeps_tail_reachable() {
2951        let len = 65_548;
2952        let mut virt: Virtualized<()> =
2953            Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
2954        for idx in 65_538..len {
2955            virt.observe_height(idx, 1);
2956        }
2957        virt.scroll_to_bottom();
2958        assert_eq!(virt.visible_range(5), len - 5..len);
2959        virt.scroll_to(len - 8);
2960        assert_eq!(virt.visible_range(5), len - 8..len - 3);
2961    }
2962
2963    #[test]
2964    fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
2965        fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
2966            let scrollbar =
2967                Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
2968            let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
2969            let mut frame = Frame::new(1, 21, &mut pool);
2970            scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
2971            (0..21)
2972                .filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
2973                .collect()
2974        }
2975
2976        // Execute the production scaling helper and real scrollbar renderer
2977        // with a simulated 32-bit capacity; this is not a wasm execution.
2978        let capacity = u32::MAX as usize;
2979        let total = 131_072 * u64::from(u16::MAX);
2980        let viewport = 20;
2981        let max_position = total - u64::from(viewport);
2982        for (position, expected_row) in [
2983            (0, 0),
2984            (max_position / 4, 5),
2985            (max_position / 2, 10),
2986            (max_position / 4 * 3, 15),
2987            (max_position, 20),
2988            (total, 20),
2989        ] {
2990            let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
2991            assert_eq!(scaled.content_length, capacity);
2992            assert!(scaled.viewport_length > 0);
2993            assert_eq!(thumb_rows(scaled), vec![expected_row]);
2994        }
2995
2996        let position = u64::from(u32::MAX) + u64::from(u16::MAX);
2997        let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
2998        assert_eq!(thumb_rows(scaled), vec![10]);
2999        // The former independent saturation gives the wrong actual geometry.
3000        let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
3001        assert_eq!(thumb_rows(saturated), vec![20]);
3002
3003        for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
3004            let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
3005            assert_eq!(exact.content_length, total as usize);
3006            assert_eq!(exact.position, position as usize);
3007            assert_eq!(exact.viewport_length, usize::from(viewport));
3008        }
3009        if usize::BITS > 32 {
3010            let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
3011            assert_eq!(exact.content_length as u64, total);
3012            assert_eq!(exact.position as u64, position);
3013            assert_eq!(exact.viewport_length, usize::from(viewport));
3014        }
3015    }
3016
3017    #[test]
3018    fn test_variable_heights_fenwick_visible_count() {
3019        // Heights: [3, 2, 5, 1, 4]
3020        let heights = vec![3, 2, 5, 1, 4];
3021        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3022
3023        // Viewport 5: items 0 (h=3) + 1 (h=2) = 5 exactly
3024        assert_eq!(tracker.visible_count(0, 5), 2);
3025
3026        // Viewport 4: item 0 fits and item 1 is partially visible.
3027        assert_eq!(tracker.visible_count(0, 4), 2);
3028
3029        // Viewport 10: items 0+1+2 = 10 exactly
3030        assert_eq!(tracker.visible_count(0, 10), 3);
3031
3032        // From item 2, viewport 6: item 2 (h=5) + item 3 (h=1) = 6
3033        assert_eq!(tracker.visible_count(2, 6), 2);
3034    }
3035
3036    #[test]
3037    fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
3038        let heights = vec![1, 1, 1];
3039        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3040
3041        // Viewport extends past the end: must never overcount.
3042        assert_eq!(tracker.visible_count(0, 10), 3);
3043        assert_eq!(tracker.visible_count(1, 10), 2);
3044        assert_eq!(tracker.visible_count(2, 10), 1);
3045    }
3046
3047    #[test]
3048    fn test_variable_heights_fenwick_set() {
3049        let mut tracker = VariableHeightsFenwick::new(1, 5);
3050
3051        // All items should start with default height
3052        assert_eq!(tracker.get(0), 1);
3053        assert_eq!(tracker.total_height(), 5);
3054
3055        // Set item 2 to height 10
3056        tracker.set(2, 10);
3057        assert_eq!(tracker.get(2), 10);
3058        assert_eq!(tracker.total_height(), 14); // 1+1+10+1+1
3059    }
3060
3061    #[test]
3062    fn test_variable_heights_fenwick_resize() {
3063        let mut tracker = VariableHeightsFenwick::new(2, 3);
3064        assert_eq!(tracker.len(), 3);
3065        assert_eq!(tracker.total_height(), 6);
3066
3067        // Grow
3068        tracker.resize(5);
3069        assert_eq!(tracker.len(), 5);
3070        assert_eq!(tracker.total_height(), 10);
3071        assert_eq!(tracker.get(4), 2);
3072
3073        // Shrink
3074        tracker.resize(2);
3075        assert_eq!(tracker.len(), 2);
3076        assert_eq!(tracker.total_height(), 4);
3077    }
3078
3079    #[test]
3080    fn test_variable_heights_fenwick_point_update_and_range_query() {
3081        fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
3082            tracker
3083                .offset_of_item(right.saturating_add(1))
3084                .saturating_sub(tracker.offset_of_item(left))
3085        }
3086
3087        let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
3088        let mut naive = [2_u32, 4, 1, 3, 5, 2];
3089
3090        tracker.set(2, 7);
3091        naive[2] = 7;
3092        tracker.set(5, 1);
3093        naive[5] = 1;
3094        tracker.set(0, 6);
3095        naive[0] = 6;
3096
3097        let mut running = 0u32;
3098        for (i, value) in naive.iter().enumerate() {
3099            running = running.saturating_add(*value);
3100            assert_eq!(tracker.offset_of_item(i + 1), running);
3101        }
3102
3103        let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
3104        assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
3105        assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
3106        assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
3107    }
3108
3109    proptest! {
3110        #![proptest_config(ProptestConfig::with_cases(96))]
3111
3112        #[test]
3113        fn property_variable_heights_fenwick_prefix_sums_match_naive(
3114            heights in proptest::collection::vec(1u16..=32u16, 1..160)
3115        ) {
3116            let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3117
3118            let mut naive_prefix = 0u32;
3119            prop_assert_eq!(tracker.offset_of_item(0), 0);
3120            for (i, height) in heights.iter().enumerate() {
3121                naive_prefix = naive_prefix.saturating_add(u32::from(*height));
3122                prop_assert_eq!(
3123                    tracker.offset_of_item(i + 1),
3124                    naive_prefix,
3125                    "prefix mismatch at index {} for heights {:?}",
3126                    i,
3127                    heights
3128                );
3129            }
3130        }
3131
3132        #[test]
3133        fn property_variable_heights_fenwick_visible_count_matches_naive(
3134            heights in proptest::collection::vec(1u16..=24u16, 1..128),
3135            start_idx in 0usize..192usize,
3136            viewport_height in 1u16..=120u16
3137        ) {
3138            fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
3139                if heights.is_empty() || viewport_height == 0 {
3140                    return 0;
3141                }
3142                let start = start_idx.min(heights.len());
3143                if start >= heights.len() {
3144                    return 0;
3145                }
3146
3147                let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
3148                let end_offset = start_offset.saturating_add(u32::from(viewport_height));
3149                let mut count = 0usize;
3150                let mut cursor = start_offset;
3151                for &height in &heights[start..] {
3152                    if cursor >= end_offset {
3153                        break;
3154                    }
3155                    count = count.saturating_add(1);
3156                    cursor = cursor.saturating_add(u32::from(height));
3157                }
3158
3159                if count == 0 { 1 } else { count }
3160            }
3161
3162            let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3163            let expected = naive_visible_count(&heights, start_idx, viewport_height);
3164            let actual = tracker.visible_count(start_idx, viewport_height);
3165            prop_assert_eq!(
3166                actual,
3167                expected,
3168                "visible_count mismatch for start={} viewport={} heights={:?}",
3169                start_idx,
3170                viewport_height,
3171                heights
3172            );
3173        }
3174    }
3175
3176    /// With a predictor attached, unmeasured slots follow the posterior mean
3177    /// of the measured rows (Normal-Normal update, prior κ₀=2 at μ₀=1) instead
3178    /// of the constant default, and measured slots are never touched.
3179    #[test]
3180    fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
3181        let config = PredictorConfig {
3182            default_height: 1,
3183            prior_mean: 1.0,
3184            prior_strength: 2.0,
3185            ..PredictorConfig::default()
3186        };
3187        let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
3188        assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
3189        assert_eq!(tracker.unmeasured_count(), 10);
3190        assert_eq!(tracker.total_height(), 10);
3191
3192        // Three rows measure 3 tall: posterior mean (2·1 + 3·3) / 5 = 2.2 → 2.
3193        for idx in 0..3 {
3194            tracker.set(idx, 3);
3195        }
3196        assert_eq!(tracker.predicted_height(), 2);
3197        assert_eq!(tracker.unmeasured_count(), 7);
3198        assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
3199        assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
3200        assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
3201        assert_eq!(tracker.offset_of_item(4), 9 + 2);
3202
3203        // Three more: (2·1 + 6·3) / 8 = 2.5 → 3; the unmeasured tail is refilled.
3204        for idx in 3..6 {
3205            tracker.set(idx, 3);
3206        }
3207        assert_eq!(tracker.predicted_height(), 3);
3208        assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
3209        assert!(tracker.is_measured(5) && !tracker.is_measured(6));
3210        assert_eq!(
3211            tracker.predictor().map(HeightPredictor::total_measurements),
3212            Some(6)
3213        );
3214
3215        // Growth uses the prediction, not the constructor default.
3216        tracker.resize(12);
3217        assert_eq!(tracker.get(11), 3);
3218        assert_eq!(tracker.unmeasured_count(), 6);
3219        assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
3220
3221        // Shrinking below measured rows keeps the bookkeeping consistent.
3222        tracker.resize(4);
3223        assert_eq!(tracker.unmeasured_count(), 0);
3224        tracker.resize(6);
3225        assert_eq!(tracker.unmeasured_count(), 2);
3226        assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
3227
3228        // Rebuild trains on every provided height and marks all as measured.
3229        tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
3230        assert_eq!(tracker.unmeasured_count(), 0);
3231        assert_eq!(tracker.total_height(), 40);
3232        assert!(
3233            tracker.predicted_height() >= 4,
3234            "posterior pulled toward the taller rows"
3235        );
3236
3237        // Without a predictor nothing changes: unmeasured slots stay at the default.
3238        let mut plain = VariableHeightsFenwick::new(2, 4);
3239        plain.set(0, 9);
3240        assert_eq!(plain.predicted_height(), 2);
3241        assert_eq!(plain.get(3), 2);
3242        assert_eq!(plain.unmeasured_count(), 3);
3243        assert!(plain.predictor().is_none());
3244    }
3245
3246    /// `Virtualized::with_height_prediction` switches to the Fenwick tracker
3247    /// and `observe_height` trains the model; fixed heights ignore it.
3248    #[test]
3249    fn virtualized_height_prediction_observe_height_trains_the_model() {
3250        let mut virt: Virtualized<i32> = Virtualized::new(100)
3251            .with_fixed_height(1)
3252            .with_height_prediction(PredictorConfig::default());
3253        assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
3254        assert_eq!(virt.unmeasured_item_height(), 1);
3255
3256        // Four rows of height 4: (2·1 + 4·4) / 6 = 3.
3257        for idx in 0..4 {
3258            virt.observe_height(idx, 4);
3259        }
3260        assert_eq!(virt.unmeasured_item_height(), 3);
3261        let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
3262            panic!("expected the Fenwick tracker");
3263        };
3264        assert_eq!(tracker.get(0), 4);
3265        assert_eq!(tracker.len(), 4);
3266        assert_eq!(
3267            tracker.get(40),
3268            3,
3269            "beyond the tracked length: the prediction"
3270        );
3271
3272        let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
3273        fixed.observe_height(0, 9);
3274        assert_eq!(
3275            fixed.unmeasured_item_height(),
3276            2,
3277            "fixed heights ignore observations"
3278        );
3279
3280        let mut linear: Virtualized<i32> =
3281            Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
3282        linear.observe_height(1, 5);
3283        assert_eq!(linear.unmeasured_item_height(), 2);
3284        let ItemHeight::Variable(cache) = linear.item_height() else {
3285            panic!("expected the linear cache");
3286        };
3287        assert_eq!(cache.get(1), 5);
3288    }
3289
3290    #[test]
3291    fn test_virtualized_with_variable_heights_fenwick() {
3292        let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
3293
3294        for i in 0..10 {
3295            virt.push(i);
3296        }
3297
3298        // All items height 2, viewport 6 -> 3 items visible
3299        let range = virt.visible_range(6);
3300        assert_eq!(range.end - range.start, 3);
3301    }
3302
3303    #[test]
3304    fn test_variable_heights_fenwick_performance() {
3305        use std::time::Instant;
3306
3307        // Create large tracker
3308        let n = 100_000;
3309        let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
3310        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3311
3312        // Warm up
3313        let _ = tracker.find_item_at_offset(500_000);
3314        let _ = tracker.offset_of_item(50_000);
3315
3316        // Benchmark find_item_at_offset (O(log n))
3317        let start = Instant::now();
3318        let mut _sink = 0usize;
3319        for i in 0..10_000 {
3320            _sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
3321        }
3322        let find_time = start.elapsed();
3323
3324        // Benchmark offset_of_item (O(log n))
3325        let start = Instant::now();
3326        let mut _sink2 = 0u32;
3327        for i in 0..10_000 {
3328            _sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
3329        }
3330        let offset_time = start.elapsed();
3331
3332        eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
3333        eprintln!("10k find_item_at_offset: {:?}", find_time);
3334        eprintln!("10k offset_of_item:      {:?}", offset_time);
3335
3336        // Both should be under 50ms for 10k operations
3337        assert!(
3338            find_time < std::time::Duration::from_millis(50),
3339            "find_item_at_offset too slow: {:?}",
3340            find_time
3341        );
3342        assert!(
3343            offset_time < std::time::Duration::from_millis(50),
3344            "offset_of_item too slow: {:?}",
3345            offset_time
3346        );
3347    }
3348
3349    #[test]
3350    fn test_variable_heights_fenwick_scales_logarithmically() {
3351        use std::time::Instant;
3352
3353        // Small dataset
3354        let small_n = 1_000;
3355        let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
3356        let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
3357
3358        // Large dataset
3359        let large_n = 100_000;
3360        let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
3361        let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
3362
3363        let iterations = 5_000;
3364
3365        // Time small
3366        let start = Instant::now();
3367        for i in 0..iterations {
3368            let _ = small_tracker.find_item_at_offset((i * 2) as u32);
3369        }
3370        let small_time = start.elapsed();
3371
3372        // Time large
3373        let start = Instant::now();
3374        for i in 0..iterations {
3375            let _ = large_tracker.find_item_at_offset((i * 200) as u32);
3376        }
3377        let large_time = start.elapsed();
3378
3379        // Large should be within 10x of small (O(log n) vs O(n) would be 100x).
3380        // Use a generous bound to avoid flakiness on loaded CI workers.
3381        assert!(
3382            large_time < small_time * 10,
3383            "Not O(log n): small={:?}, large={:?}",
3384            small_time,
3385            large_time
3386        );
3387    }
3388
3389    // ========================================================================
3390    // Edge-case tests (bd-2f15w)
3391    // ========================================================================
3392
3393    // ── Virtualized: construction & empty state ─────────────────────────
3394
3395    #[test]
3396    fn new_zero_capacity() {
3397        let virt: Virtualized<i32> = Virtualized::new(0);
3398        assert_eq!(virt.len(), 0);
3399        assert!(virt.is_empty());
3400        assert_eq!(virt.scroll_offset(), 0);
3401        assert_eq!(virt.visible_count(), 0);
3402        assert!(!virt.follow_mode());
3403    }
3404
3405    #[test]
3406    fn external_zero_len_zero_cache() {
3407        let virt: Virtualized<i32> = Virtualized::external(0, 0);
3408        assert_eq!(virt.len(), 0);
3409        assert!(virt.is_empty());
3410    }
3411
3412    #[test]
3413    fn external_storage_returns_none_for_get() {
3414        let virt: Virtualized<i32> = Virtualized::external(100, 10);
3415        assert_eq!(virt.get(0), None);
3416        assert_eq!(virt.get(50), None);
3417    }
3418
3419    #[test]
3420    fn external_storage_returns_none_for_get_mut() {
3421        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3422        assert!(virt.get_mut(0).is_none());
3423    }
3424
3425    #[test]
3426    fn push_on_external_is_noop() {
3427        let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
3428        virt.push(42);
3429        // Length unchanged because push only works on Owned
3430        assert_eq!(virt.len(), 5);
3431    }
3432
3433    #[test]
3434    fn iter_on_external_is_empty() {
3435        let virt: Virtualized<i32> = Virtualized::external(100, 10);
3436        assert_eq!(virt.iter().count(), 0);
3437    }
3438
3439    #[test]
3440    fn set_external_len_on_owned_is_noop() {
3441        let mut virt: Virtualized<i32> = Virtualized::new(100);
3442        virt.push(1);
3443        virt.set_external_len(999);
3444        assert_eq!(virt.len(), 1); // unchanged
3445    }
3446
3447    // ── Virtualized: visible_range edge cases ───────────────────────────
3448
3449    #[test]
3450    fn visible_range_zero_viewport() {
3451        let mut virt: Virtualized<i32> = Virtualized::new(100);
3452        virt.push(1);
3453        let range = virt.visible_range(0);
3454        assert_eq!(range, 0..0);
3455        assert_eq!(virt.visible_count(), 0);
3456    }
3457
3458    #[test]
3459    fn visible_range_empty_container() {
3460        let virt: Virtualized<i32> = Virtualized::new(100);
3461        let range = virt.visible_range(24);
3462        assert_eq!(range, 0..0);
3463    }
3464
3465    #[test]
3466    fn visible_range_fixed_height_zero() {
3467        // Fixed(0) should not divide by zero; falls through to viewport_height items
3468        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
3469        for i in 0..10 {
3470            virt.push(i);
3471        }
3472        let range = virt.visible_range(5);
3473        // ItemHeight::Fixed(0) → viewport_height as usize = 5
3474        assert_eq!(range, 0..5);
3475    }
3476
3477    #[test]
3478    fn visible_range_fewer_items_than_viewport() {
3479        let mut virt: Virtualized<i32> = Virtualized::new(100);
3480        for i in 0..3 {
3481            virt.push(i);
3482        }
3483        let range = virt.visible_range(24);
3484        // Only 3 items, viewport fits 24
3485        assert_eq!(range, 0..3);
3486    }
3487
3488    #[test]
3489    fn visible_range_single_item() {
3490        let mut virt: Virtualized<i32> = Virtualized::new(100);
3491        virt.push(42);
3492        let range = virt.visible_range(1);
3493        assert_eq!(range, 0..1);
3494    }
3495
3496    // ── Virtualized: render_range edge cases ────────────────────────────
3497
3498    #[test]
3499    fn render_range_at_start_clamps_overscan() {
3500        let mut virt: Virtualized<i32> =
3501            Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3502        for i in 0..20 {
3503            virt.push(i);
3504        }
3505        // At scroll_offset=0, start.saturating_sub(5) = 0
3506        let range = virt.render_range(10);
3507        assert_eq!(range.start, 0);
3508    }
3509
3510    #[test]
3511    fn render_range_at_end_clamps_overscan() {
3512        let mut virt: Virtualized<i32> =
3513            Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3514        for i in 0..20 {
3515            virt.push(i);
3516        }
3517        virt.set_visible_count(10);
3518        virt.scroll_to(10); // offset=10, visible 10..20
3519        let range = virt.render_range(10);
3520        // end = min(20 + 5, 20) = 20
3521        assert_eq!(range.end, 20);
3522    }
3523
3524    #[test]
3525    fn render_range_zero_overscan() {
3526        let mut virt: Virtualized<i32> =
3527            Virtualized::new(100).with_fixed_height(1).with_overscan(0);
3528        for i in 0..20 {
3529            virt.push(i);
3530        }
3531        virt.set_visible_count(10);
3532        virt.scroll_to(5);
3533        let range = virt.render_range(10);
3534        // No overscan: render_range == visible_range
3535        let visible = virt.visible_range(10);
3536        assert_eq!(range, visible);
3537    }
3538
3539    // ── Virtualized: scroll edge cases ──────────────────────────────────
3540
3541    #[test]
3542    fn scroll_on_empty_is_noop() {
3543        let mut virt: Virtualized<i32> = Virtualized::new(100);
3544        virt.scroll(10);
3545        assert_eq!(virt.scroll_offset(), 0);
3546    }
3547
3548    #[test]
3549    fn scroll_delta_zero_does_not_disable_follow() {
3550        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3551        virt.push(1);
3552        virt.scroll(0);
3553        // delta=0 doesn't disable follow_mode
3554        assert!(virt.follow_mode());
3555    }
3556
3557    #[test]
3558    fn scroll_negative_beyond_start() {
3559        let mut virt: Virtualized<i32> = Virtualized::new(100);
3560        for i in 0..10 {
3561            virt.push(i);
3562        }
3563        virt.scroll(-1);
3564        assert_eq!(virt.scroll_offset(), 0);
3565    }
3566
3567    #[test]
3568    fn scroll_to_on_empty() {
3569        let mut virt: Virtualized<i32> = Virtualized::new(100);
3570        // scroll_to on empty: idx.min(0.saturating_sub(1)) = idx.min(0) = 0
3571        virt.scroll_to(100);
3572        assert_eq!(virt.scroll_offset(), 0);
3573    }
3574
3575    #[test]
3576    fn scroll_to_top_already_at_top() {
3577        let mut virt: Virtualized<i32> = Virtualized::new(100);
3578        virt.push(1);
3579        virt.scroll_to_top();
3580        assert_eq!(virt.scroll_offset(), 0);
3581    }
3582
3583    #[test]
3584    fn scroll_to_bottom_fewer_items_than_visible() {
3585        let mut virt: Virtualized<i32> = Virtualized::new(100);
3586        virt.set_visible_count(10);
3587        for i in 0..3 {
3588            virt.push(i);
3589        }
3590        virt.scroll_to_bottom();
3591        // len (3) <= visible_count (10), so offset = 0
3592        assert_eq!(virt.scroll_offset(), 0);
3593    }
3594
3595    #[test]
3596    fn scroll_to_bottom_visible_count_zero() {
3597        let mut virt: Virtualized<i32> = Virtualized::new(100);
3598        for i in 0..20 {
3599            virt.push(i);
3600        }
3601        // visible_count=0 (default), scroll_to_bottom stores a sentinel internally.
3602        virt.scroll_to_bottom();
3603        // Internal field stores MAX sentinel…
3604        assert_eq!(virt.scroll_offset, usize::MAX);
3605        // …but public API clamps to last valid index.
3606        assert_eq!(virt.scroll_offset(), 19);
3607    }
3608
3609    // ── Virtualized: page navigation edge cases ─────────────────────────
3610
3611    #[test]
3612    fn page_up_visible_count_zero_is_noop() {
3613        let mut virt: Virtualized<i32> = Virtualized::new(100);
3614        for i in 0..20 {
3615            virt.push(i);
3616        }
3617        virt.scroll_to(10);
3618        // visible_count=0, page_up is no-op
3619        virt.page_up();
3620        assert_eq!(virt.scroll_offset(), 10);
3621    }
3622
3623    #[test]
3624    fn page_down_visible_count_zero_is_noop() {
3625        let mut virt: Virtualized<i32> = Virtualized::new(100);
3626        for i in 0..20 {
3627            virt.push(i);
3628        }
3629        // visible_count=0, page_down is no-op
3630        virt.page_down();
3631        assert_eq!(virt.scroll_offset(), 0);
3632    }
3633
3634    // ── Virtualized: is_at_bottom edge cases ────────────────────────────
3635
3636    #[test]
3637    fn is_at_bottom_fewer_items_than_visible() {
3638        let mut virt: Virtualized<i32> = Virtualized::new(100);
3639        virt.set_visible_count(10);
3640        for i in 0..3 {
3641            virt.push(i);
3642        }
3643        assert!(virt.is_at_bottom());
3644    }
3645
3646    #[test]
3647    fn is_at_bottom_empty() {
3648        let virt: Virtualized<i32> = Virtualized::new(100);
3649        // len=0 <= visible_count=0, so true
3650        assert!(virt.is_at_bottom());
3651    }
3652
3653    // ── Virtualized: trim_front edge cases ──────────────────────────────
3654
3655    #[test]
3656    fn trim_front_under_max_returns_zero() {
3657        let mut virt: Virtualized<i32> = Virtualized::new(100);
3658        for i in 0..5 {
3659            virt.push(i);
3660        }
3661        let removed = virt.trim_front(10);
3662        assert_eq!(removed, 0);
3663        assert_eq!(virt.len(), 5);
3664    }
3665
3666    #[test]
3667    fn trim_front_adjusts_scroll_offset() {
3668        let mut virt: Virtualized<i32> = Virtualized::new(100);
3669        for i in 0..20 {
3670            virt.push(i);
3671        }
3672        virt.scroll_to(10);
3673        let removed = virt.trim_front(15);
3674        assert_eq!(removed, 5);
3675        assert_eq!(virt.len(), 15);
3676        // scroll_offset adjusted: 10 - 5 = 5
3677        assert_eq!(virt.scroll_offset(), 5);
3678    }
3679
3680    #[test]
3681    fn trim_front_scroll_offset_saturates_to_zero() {
3682        let mut virt: Virtualized<i32> = Virtualized::new(100);
3683        for i in 0..20 {
3684            virt.push(i);
3685        }
3686        virt.scroll_to(2);
3687        let removed = virt.trim_front(10);
3688        assert_eq!(removed, 10);
3689        // scroll_offset 2 - 10 saturates to 0
3690        assert_eq!(virt.scroll_offset(), 0);
3691    }
3692
3693    #[test]
3694    fn trim_front_on_external_returns_zero() {
3695        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3696        let removed = virt.trim_front(5);
3697        assert_eq!(removed, 0);
3698    }
3699
3700    #[test]
3701    fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
3702        let mut virt: Virtualized<i32> = Virtualized::new(100);
3703        for i in 0..20 {
3704            virt.push(i);
3705        }
3706
3707        // Before rendering, visible_count is 0.
3708        // scroll_to_bottom should set MAX instead of 0.
3709        virt.scroll_to_bottom();
3710        assert_eq!(virt.scroll_offset, usize::MAX);
3711
3712        // Render (simulate by calling visible_range with height 10)
3713        // Should clamp start to 20 - 10 = 10.
3714        let range = virt.visible_range(10);
3715        assert_eq!(range, 10..20);
3716        assert_eq!(virt.visible_count(), 10);
3717    }
3718
3719    // ── Virtualized: clear edge cases ───────────────────────────────────
3720
3721    #[test]
3722    fn clear_on_external_resets_scroll() {
3723        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3724        virt.scroll_to(50);
3725        virt.clear();
3726        assert_eq!(virt.scroll_offset(), 0);
3727        // External len unchanged since clear only clears Owned
3728        assert_eq!(virt.len(), 100);
3729    }
3730
3731    // ── Virtualized: momentum scrolling edge cases ──────────────────────
3732
3733    #[test]
3734    fn tick_zero_velocity_is_noop() {
3735        let mut virt: Virtualized<i32> = Virtualized::new(100);
3736        for i in 0..20 {
3737            virt.push(i);
3738        }
3739        virt.tick(Duration::from_millis(100));
3740        assert_eq!(virt.scroll_offset(), 0);
3741    }
3742
3743    #[test]
3744    fn tick_below_threshold_stops_momentum() {
3745        let mut virt: Virtualized<i32> = Virtualized::new(100);
3746        for i in 0..20 {
3747            virt.push(i);
3748        }
3749        virt.fling(0.05); // below 0.1 threshold
3750        virt.tick(Duration::from_millis(100));
3751        // velocity <= 0.1, so it's zeroed out
3752        assert_eq!(virt.scroll_offset(), 0);
3753    }
3754
3755    #[test]
3756    fn tick_zero_duration_no_scroll() {
3757        let mut virt: Virtualized<i32> = Virtualized::new(100);
3758        for i in 0..50 {
3759            virt.push(i);
3760        }
3761        virt.fling(100.0);
3762        virt.tick(Duration::ZERO);
3763        // delta = (100.0 * 0.0) as i32 = 0, no scroll
3764        assert_eq!(virt.scroll_offset(), 0);
3765    }
3766
3767    #[test]
3768    fn fling_negative_scrolls_up() {
3769        let mut virt: Virtualized<i32> = Virtualized::new(100);
3770        for i in 0..50 {
3771            virt.push(i);
3772        }
3773        virt.scroll(20);
3774        let before = virt.scroll_offset();
3775        virt.fling(-50.0);
3776        virt.tick(Duration::from_millis(100));
3777        assert!(virt.scroll_offset() < before);
3778    }
3779
3780    // ── Virtualized: follow mode edge cases ─────────────────────────────
3781
3782    #[test]
3783    fn follow_mode_auto_scrolls_on_push() {
3784        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3785        virt.set_visible_count(5);
3786        for i in 0..20 {
3787            virt.push(i);
3788        }
3789        // With follow mode, should be at bottom
3790        assert!(virt.is_at_bottom());
3791        assert_eq!(virt.scroll_offset(), 15); // 20 - 5
3792    }
3793
3794    #[test]
3795    fn set_follow_false_does_not_scroll() {
3796        let mut virt: Virtualized<i32> = Virtualized::new(100);
3797        virt.set_visible_count(5);
3798        for i in 0..20 {
3799            virt.push(i);
3800        }
3801        virt.scroll_to(5);
3802        virt.set_follow(false);
3803        assert_eq!(virt.scroll_offset(), 5); // unchanged
3804    }
3805
3806    #[test]
3807    fn scroll_to_start_disables_follow() {
3808        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3809        virt.set_visible_count(5);
3810        for i in 0..20 {
3811            virt.push(i);
3812        }
3813        virt.scroll_to_start();
3814        assert!(!virt.follow_mode());
3815        assert_eq!(virt.scroll_offset(), 0);
3816    }
3817
3818    #[test]
3819    fn scroll_to_end_enables_follow() {
3820        let mut virt: Virtualized<i32> = Virtualized::new(100);
3821        virt.set_visible_count(5);
3822        for i in 0..20 {
3823            virt.push(i);
3824        }
3825        assert!(!virt.follow_mode());
3826        virt.scroll_to_end();
3827        assert!(virt.follow_mode());
3828        assert!(virt.is_at_bottom());
3829    }
3830
3831    #[test]
3832    fn external_follow_mode_scrolls_on_set_external_len() {
3833        let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
3834        virt.set_visible_count(5);
3835        virt.set_external_len(20);
3836        assert_eq!(virt.len(), 20);
3837        assert!(virt.is_at_bottom());
3838    }
3839
3840    // ── Virtualized: builder chain ──────────────────────────────────────
3841
3842    #[test]
3843    fn builder_chain_all_options() {
3844        let virt: Virtualized<i32> = Virtualized::new(100)
3845            .with_fixed_height(3)
3846            .with_overscan(5)
3847            .with_follow(true);
3848        assert!(virt.follow_mode());
3849        // Verify visible_range uses height=3
3850        // (no items, so empty range regardless)
3851        let range = virt.visible_range(9);
3852        assert_eq!(range, 0..0);
3853    }
3854
3855    // ── HeightCache edge cases ──────────────────────────────────────────
3856
3857    #[test]
3858    fn height_cache_default() {
3859        let cache = HeightCache::default();
3860        assert_eq!(cache.get(0), 1); // default_height=1
3861        assert_eq!(cache.capacity, 1000);
3862    }
3863
3864    #[test]
3865    fn height_cache_get_before_base_offset() {
3866        let mut cache = HeightCache::new(5, 100);
3867        // Set something to push base_offset forward
3868        cache.set(200, 10); // This resets window since 200 > capacity
3869        // Index 0 < base_offset, returns default
3870        assert_eq!(cache.get(0), 5);
3871    }
3872
3873    #[test]
3874    fn height_cache_set_before_base_offset_ignored() {
3875        let mut cache = HeightCache::new(5, 100);
3876        cache.set(200, 10);
3877        let base = cache.base_offset;
3878        cache.set(0, 99); // before base_offset, should be ignored
3879        assert_eq!(cache.get(0), 5); // still default
3880        assert_eq!(cache.base_offset, base); // unchanged
3881    }
3882
3883    #[test]
3884    fn height_cache_capacity_zero_ignores_all_sets() {
3885        let mut cache = HeightCache::new(3, 0);
3886        cache.set(0, 10);
3887        cache.set(5, 20);
3888        // Everything returns default since capacity=0
3889        assert_eq!(cache.get(0), 3);
3890        assert_eq!(cache.get(5), 3);
3891    }
3892
3893    #[test]
3894    fn height_cache_clear_resets_base() {
3895        let mut cache = HeightCache::new(1, 100);
3896        cache.set(50, 10);
3897        cache.clear();
3898        assert_eq!(cache.base_offset, 0);
3899        assert_eq!(cache.get(50), 1); // back to default
3900    }
3901
3902    #[test]
3903    fn height_cache_eviction_trims_oldest() {
3904        let mut cache = HeightCache::new(1, 4);
3905        // Set indices 0..6 to fill and trigger eviction
3906        for i in 0..6 {
3907            cache.set(i, (i + 10) as u16);
3908        }
3909        // Cache capacity=4, so indices 0-1 should be evicted
3910        assert!(cache.cache.len() <= cache.capacity);
3911        // Recent indices should be accessible
3912        assert_eq!(cache.get(5), 15);
3913        assert_eq!(cache.get(4), 14);
3914        assert_eq!(cache.get(3), 13);
3915        assert_eq!(cache.get(2), 12);
3916        // Old indices return default
3917        assert_eq!(cache.get(1), 1);
3918        assert_eq!(cache.get(0), 1);
3919    }
3920
3921    // ── VariableHeightsFenwick edge cases ───────────────────────────────
3922
3923    #[test]
3924    fn fenwick_default_is_empty() {
3925        let tracker = VariableHeightsFenwick::default();
3926        assert!(tracker.is_empty());
3927        assert_eq!(tracker.len(), 0);
3928        assert_eq!(tracker.total_height(), 0);
3929        assert_eq!(tracker.default_height(), 1);
3930    }
3931
3932    #[test]
3933    fn fenwick_get_beyond_len_returns_default() {
3934        let tracker = VariableHeightsFenwick::new(3, 5);
3935        assert_eq!(tracker.get(5), 3); // beyond len
3936        assert_eq!(tracker.get(100), 3);
3937    }
3938
3939    #[test]
3940    fn fenwick_set_beyond_len_resizes() {
3941        let mut tracker = VariableHeightsFenwick::new(2, 3);
3942        assert_eq!(tracker.len(), 3);
3943        tracker.set(10, 7);
3944        assert!(tracker.len() > 10);
3945        assert_eq!(tracker.get(10), 7);
3946    }
3947
3948    #[test]
3949    fn fenwick_offset_of_item_zero_always_zero() {
3950        let tracker = VariableHeightsFenwick::new(5, 10);
3951        assert_eq!(tracker.offset_of_item(0), 0);
3952
3953        let empty = VariableHeightsFenwick::new(5, 0);
3954        assert_eq!(empty.offset_of_item(0), 0);
3955    }
3956
3957    #[test]
3958    fn fenwick_find_item_at_offset_empty() {
3959        let tracker = VariableHeightsFenwick::new(1, 0);
3960        assert_eq!(tracker.find_item_at_offset(0), 0);
3961        assert_eq!(tracker.find_item_at_offset(100), 0);
3962    }
3963
3964    #[test]
3965    fn fenwick_visible_count_zero_viewport() {
3966        let tracker = VariableHeightsFenwick::new(2, 10);
3967        assert_eq!(tracker.visible_count(0, 0), 0);
3968    }
3969
3970    #[test]
3971    fn fenwick_visible_count_start_beyond_len() {
3972        let tracker = VariableHeightsFenwick::new(2, 5);
3973        // start_idx clamped to len
3974        let count = tracker.visible_count(100, 10);
3975        // start=5 (clamped), offset=total, no items visible
3976        assert_eq!(count, 0);
3977    }
3978
3979    #[test]
3980    fn fenwick_clear_then_operations() {
3981        let mut tracker = VariableHeightsFenwick::new(3, 5);
3982        assert_eq!(tracker.total_height(), 15);
3983        tracker.clear();
3984        assert_eq!(tracker.len(), 0);
3985        assert_eq!(tracker.total_height(), 0);
3986        assert_eq!(tracker.find_item_at_offset(0), 0);
3987    }
3988
3989    #[test]
3990    fn fenwick_rebuild_replaces_data() {
3991        let mut tracker = VariableHeightsFenwick::new(1, 10);
3992        assert_eq!(tracker.total_height(), 10);
3993        tracker.rebuild(&[5, 3, 2]);
3994        assert_eq!(tracker.len(), 3);
3995        assert_eq!(tracker.total_height(), 10);
3996        assert_eq!(tracker.get(0), 5);
3997        assert_eq!(tracker.get(1), 3);
3998        assert_eq!(tracker.get(2), 2);
3999    }
4000
4001    #[test]
4002    fn fenwick_resize_same_size_is_noop() {
4003        let mut tracker = VariableHeightsFenwick::new(2, 5);
4004        tracker.set(2, 10);
4005        tracker.resize(5);
4006        // Item 2 still has custom height
4007        assert_eq!(tracker.get(2), 10);
4008        assert_eq!(tracker.len(), 5);
4009    }
4010
4011    // ── VirtualizedListState edge cases ─────────────────────────────────
4012
4013    #[test]
4014    fn list_state_default_matches_new() {
4015        let d = VirtualizedListState::default();
4016        let n = VirtualizedListState::new();
4017        assert_eq!(d.selected, n.selected);
4018        assert_eq!(d.scroll_offset(), n.scroll_offset());
4019        assert_eq!(d.visible_count(), n.visible_count());
4020        assert_eq!(d.follow_mode(), n.follow_mode());
4021    }
4022
4023    #[test]
4024    fn list_state_select_next_on_empty() {
4025        let mut state = VirtualizedListState::new();
4026        state.select_next(0);
4027        assert_eq!(state.selected, None);
4028    }
4029
4030    #[test]
4031    fn list_state_select_previous_on_empty() {
4032        let mut state = VirtualizedListState::new();
4033        state.select_previous(0);
4034        assert_eq!(state.selected, None);
4035    }
4036
4037    #[test]
4038    fn list_state_select_previous_from_none() {
4039        let mut state = VirtualizedListState::new();
4040        state.select_previous(10);
4041        assert_eq!(state.selected, Some(0));
4042    }
4043
4044    #[test]
4045    fn list_state_select_next_from_none() {
4046        let mut state = VirtualizedListState::new();
4047        state.select_next(10);
4048        assert_eq!(state.selected, Some(0));
4049    }
4050
4051    #[test]
4052    fn list_state_scroll_zero_items() {
4053        let mut state = VirtualizedListState::new();
4054        state.scroll(10, 0);
4055        assert_eq!(state.scroll_offset(), 0);
4056    }
4057
4058    #[test]
4059    fn list_state_scroll_to_clamps() {
4060        let mut state = VirtualizedListState::new();
4061        state.scroll_to(100, 10);
4062        assert_eq!(state.scroll_offset(), 9);
4063    }
4064
4065    #[test]
4066    fn list_state_scroll_to_bottom_zero_items() {
4067        let mut state = VirtualizedListState::new();
4068        state.scroll_to_bottom(0);
4069        assert_eq!(state.scroll_offset(), 0);
4070    }
4071
4072    #[test]
4073    fn list_state_is_at_bottom_zero_items() {
4074        let state = VirtualizedListState::new();
4075        assert!(state.is_at_bottom(0));
4076    }
4077
4078    #[test]
4079    fn list_state_page_up_visible_count_zero() {
4080        let mut state = VirtualizedListState::new();
4081        state.scroll_offset = 5;
4082        state.page_up(20);
4083        // visible_count=0, no-op
4084        assert_eq!(state.scroll_offset(), 5);
4085    }
4086
4087    #[test]
4088    fn list_state_page_down_visible_count_zero() {
4089        let mut state = VirtualizedListState::new();
4090        state.page_down(20);
4091        // visible_count=0, no-op
4092        assert_eq!(state.scroll_offset(), 0);
4093    }
4094
4095    #[test]
4096    fn list_state_set_follow_false_no_scroll() {
4097        let mut state = VirtualizedListState::new();
4098        state.scroll_offset = 5;
4099        state.set_follow(false, 20);
4100        assert_eq!(state.scroll_offset(), 5); // unchanged
4101        assert!(!state.follow_mode());
4102    }
4103
4104    #[test]
4105    fn list_state_persistence_id() {
4106        let state = VirtualizedListState::new().with_persistence_id("my-list");
4107        assert_eq!(state.persistence_id(), Some("my-list"));
4108    }
4109
4110    #[test]
4111    fn list_state_persistence_id_none() {
4112        let state = VirtualizedListState::new();
4113        assert_eq!(state.persistence_id(), None);
4114    }
4115
4116    #[test]
4117    fn list_state_momentum_tick_zero_items() {
4118        let mut state = VirtualizedListState::new();
4119        state.fling(50.0);
4120        state.tick(Duration::from_millis(100), 0);
4121        // total_items=0, scroll is no-op
4122        assert_eq!(state.scroll_offset(), 0);
4123    }
4124
4125    // ── VirtualizedListPersistState edge cases ──────────────────────────
4126
4127    #[test]
4128    fn persist_state_default() {
4129        let ps = VirtualizedListPersistState::default();
4130        assert_eq!(ps.selected, None);
4131        assert_eq!(ps.scroll_offset, 0);
4132        assert!(!ps.follow_mode);
4133    }
4134
4135    #[test]
4136    fn persist_state_eq() {
4137        let a = VirtualizedListPersistState {
4138            selected: Some(5),
4139            scroll_offset: 10,
4140            follow_mode: true,
4141        };
4142        let b = a.clone();
4143        assert_eq!(a, b);
4144    }
4145
4146    // ── Stateful trait impl edge cases ──────────────────────────────────
4147
4148    #[test]
4149    fn stateful_state_key_with_persistence_id() {
4150        use crate::stateful::Stateful;
4151        let state = VirtualizedListState::new().with_persistence_id("logs");
4152        let key = state.state_key();
4153        assert_eq!(key.widget_type, "VirtualizedList");
4154        assert_eq!(key.instance_id, "logs");
4155    }
4156
4157    #[test]
4158    fn stateful_state_key_default_instance() {
4159        use crate::stateful::Stateful;
4160        let state = VirtualizedListState::new();
4161        let key = state.state_key();
4162        assert_eq!(key.instance_id, "default");
4163    }
4164
4165    #[test]
4166    fn stateful_save_restore_roundtrip() {
4167        use crate::stateful::Stateful;
4168        let mut state = VirtualizedListState::new();
4169        state.selected = Some(7);
4170        state.scroll_offset = 15;
4171        state.follow_mode = true;
4172        state.scroll_velocity = 42.0; // transient — not persisted
4173
4174        let saved = state.save_state();
4175        assert_eq!(saved.selected, Some(7));
4176        assert_eq!(saved.scroll_offset, 15);
4177        assert!(saved.follow_mode);
4178
4179        let mut restored = VirtualizedListState::new();
4180        restored.scroll_velocity = 99.0;
4181        restored.restore_state(saved);
4182        assert_eq!(restored.selected, Some(7));
4183        assert_eq!(restored.scroll_offset, 15);
4184        assert!(restored.follow_mode);
4185        // velocity reset to 0 on restore
4186        assert_eq!(restored.scroll_velocity, 0.0);
4187    }
4188
4189    // ── VirtualizedList widget edge cases ───────────────────────────────
4190
4191    #[test]
4192    fn virtualized_list_builder() {
4193        let items: Vec<String> = vec!["a".into()];
4194        let list = VirtualizedList::new(&items)
4195            .style(Style::default())
4196            .highlight_style(Style::default())
4197            .show_scrollbar(false)
4198            .fixed_height(3);
4199        assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
4200        assert!(!list.show_scrollbar);
4201        assert_eq!(
4202            VirtualizedList::new(&items)
4203                .variable_heights()
4204                .height_mode(),
4205            ListHeightMode::Variable
4206        );
4207    }
4208
4209    /// `with_variable_heights` selects the Fenwick tracker sized to the
4210    /// list: offsets are exact before any measurement, offset/index queries
4211    /// round-trip, scrolling to the end computes the last screenful, and a
4212    /// measurement shifts every later offset.
4213    #[test]
4214    fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
4215        let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
4216        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4217            panic!("expected the Fenwick tracker, got {:?}", v.item_height());
4218        };
4219        assert_eq!(tracker.len(), 10_000);
4220        assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
4221        for k in 0..100u32 {
4222            let offset = k * 297;
4223            let idx = tracker.find_item_at_offset(offset);
4224            let start = tracker.offset_of_item(idx);
4225            assert!(
4226                start <= offset && offset < start + u32::from(tracker.get(idx)),
4227                "offset {offset} must land inside item {idx} [{start}, +{})",
4228                tracker.get(idx)
4229            );
4230        }
4231
4232        v.scroll_to(9_999);
4233        let range = v.visible_range(24);
4234        assert_eq!(range.end, 10_000);
4235        assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
4236
4237        v.observe_height(5, 7);
4238        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4239            unreachable!()
4240        };
4241        assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
4242        assert!(tracker.is_measured(5));
4243        assert_eq!(v.unmeasured_item_height(), 3);
4244    }
4245
4246    /// The tracker follows the item count through push, trim_front and
4247    /// clear, keeping measured heights aligned with their items.
4248    #[test]
4249    fn variable_height_tracker_follows_owned_storage() {
4250        let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
4251        for i in 0..5 {
4252            v.push(format!("row {i}"));
4253        }
4254        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4255            unreachable!()
4256        };
4257        assert_eq!(tracker.len(), 5);
4258        assert_eq!(tracker.total_height(), 10);
4259
4260        v.observe_height(0, 5);
4261        v.observe_height(3, 4);
4262        assert_eq!(v.trim_front(3), 2);
4263        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4264            unreachable!()
4265        };
4266        assert_eq!(tracker.len(), 3);
4267        // Old item 3 (height 4) is now item 1; the others are unmeasured (2).
4268        assert!(!tracker.is_measured(0));
4269        assert!(tracker.is_measured(1));
4270        assert_eq!(tracker.get(1), 4);
4271        assert_eq!(tracker.total_height(), 2 + 4 + 2);
4272
4273        v.clear();
4274        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4275            unreachable!()
4276        };
4277        assert_eq!(tracker.len(), 0);
4278        assert_eq!(tracker.total_height(), 0);
4279    }
4280
4281    /// A variable-height `VirtualizedList` lays rows out by
4282    /// `RenderItem::height`, measures them into the state, keeps the
4283    /// selection visible and clamps to the last item-aligned screenful.
4284    #[test]
4285    fn virtualized_list_variable_heights_renders_by_item_height() {
4286        struct Tall(u16);
4287        impl RenderItem for Tall {
4288            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4289                let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
4290                for row in 0..area.height {
4291                    frame
4292                        .buffer
4293                        .set(area.x, area.y + row, Cell::from_char(glyph));
4294                }
4295            }
4296            fn height(&self) -> u16 {
4297                self.0
4298            }
4299        }
4300        let column = |frame: &Frame| -> String {
4301            (0..frame.buffer.height())
4302                .map(|y| {
4303                    frame
4304                        .buffer
4305                        .get(0, y)
4306                        .and_then(|cell| cell.content.as_char())
4307                        .unwrap_or(' ')
4308                })
4309                .collect()
4310        };
4311
4312        let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
4313        let list = VirtualizedList::new(&items)
4314            .variable_heights()
4315            .show_scrollbar(false);
4316        let mut state = VirtualizedListState::new();
4317        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4318
4319        let mut frame = Frame::new(4, 5, &mut pool);
4320        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4321        // item0 (1 row), item1 (2 rows), item2 (3 rows, cut to the 2 left).
4322        assert_eq!(column(&frame), "12233");
4323        assert_eq!(state.visible_count(), 3);
4324        let heights = state.heights().expect("tracker created by render");
4325        assert_eq!(heights.get(1), 2);
4326        assert!(heights.is_measured(2));
4327        assert!(!heights.is_measured(4), "off-screen rows stay unmeasured");
4328        drop(frame);
4329
4330        // Selecting the last item scrolls so it is visible; the clamp keeps
4331        // the first visible row item-aligned (item3 at the top).
4332        state.select(Some(4));
4333        let mut frame = Frame::new(4, 5, &mut pool);
4334        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4335        assert_eq!(state.scroll_offset(), 3);
4336        assert_eq!(column(&frame), "122  ");
4337        assert_eq!(state.visible_count(), 2);
4338        let heights = state.heights().expect("tracker");
4339        assert_eq!(heights.total_height(), 9);
4340        assert_eq!(heights.offset_of_item(4), 7);
4341        drop(frame);
4342
4343        // A manual measurement moves later offsets.
4344        state.measure(0, 3);
4345        assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
4346
4347        // With the scrollbar on, the thumb works in rows.
4348        let list = VirtualizedList::new(&items).variable_heights();
4349        let mut state = VirtualizedListState::new();
4350        let mut frame = Frame::new(4, 5, &mut pool);
4351        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4352        assert!(
4353            frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
4354            "the last column belongs to the scrollbar"
4355        );
4356        assert_eq!(column(&frame), "12233");
4357    }
4358
4359    #[test]
4360    fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
4361        #[derive(Clone, Copy)]
4362        struct Row(u16, char);
4363        impl RenderItem for Row {
4364            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4365                for y in area.y..area.bottom() {
4366                    frame.buffer.set(area.x, y, Cell::from_char(self.1));
4367                }
4368            }
4369
4370            fn height(&self) -> u16 {
4371                self.0
4372            }
4373        }
4374
4375        let mut items = vec![Row(u16::MAX, 'X'); 65_538];
4376        items.extend([Row(1, '.'); 9]);
4377        items.push(Row(1, 'Z'));
4378        let list = VirtualizedList::new(&items).variable_heights();
4379        let mut state = VirtualizedListState::new();
4380        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4381        {
4382            let mut frame = Frame::new(4, 5, &mut pool);
4383            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4384            assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
4385        }
4386        // Populate off-screen measurements through the real list-state API.
4387        for (idx, row) in items.iter().enumerate() {
4388            state.measure(idx, row.height());
4389        }
4390        assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
4391        state.select(Some(items.len() - 1));
4392        {
4393            let mut frame = Frame::new(4, 5, &mut pool);
4394            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4395            assert_eq!(state.scroll_offset(), items.len() - 5);
4396            assert_eq!(state.visible_count(), 5);
4397            let column: String = (0..5)
4398                .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
4399                .collect();
4400            assert_eq!(column, "....Z");
4401            assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
4402        }
4403        state.select(None);
4404        state.scroll_to_top();
4405        {
4406            let mut frame = Frame::new(4, 5, &mut pool);
4407            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4408            assert_eq!(state.scroll_offset(), 0);
4409            assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
4410        }
4411        state.scroll_to_bottom(items.len());
4412        let mut frame = Frame::new(4, 5, &mut pool);
4413        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4414        assert_eq!(state.scroll_offset(), items.len() - 5);
4415        assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
4416    }
4417
4418    // ── VirtualizedStorage Debug/Clone ───────────────────────────────────
4419
4420    #[test]
4421    fn virtualized_storage_debug() {
4422        let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
4423        let dbg = format!("{:?}", storage);
4424        assert!(dbg.contains("Owned"));
4425
4426        let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
4427            len: 100,
4428            cache_capacity: 10,
4429        };
4430        let dbg = format!("{:?}", ext);
4431        assert!(dbg.contains("External"));
4432    }
4433
4434    #[test]
4435    fn test_virtualized_list_handle_mouse_drag_smooth() {
4436        use crate::scrollbar::SCROLLBAR_PART_THUMB;
4437        use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
4438        use ftui_render::frame::{HitId, HitRegion};
4439
4440        let mut state = VirtualizedListState::new();
4441        let scrollbar_hit_id = HitId::new(1);
4442        let total_items = 100;
4443        let viewport_height = 10;
4444        let fixed_height = 1;
4445
4446        // Simulate click on thumb.
4447        // Track length 10. Thumb size 1. Content 100.
4448        // Thumb at top (pos 0).
4449        // Click at track_pos 0 (top of thumb).
4450        // Hit data: [8: part] [28: len] [28: pos]
4451        let track_len = 10u64;
4452        let track_pos = 0u64;
4453        let hit_data = (SCROLLBAR_PART_THUMB << 56)
4454            | ((track_len & 0x0FFF_FFFF) << 28)
4455            | (track_pos & 0x0FFF_FFFF);
4456
4457        let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
4458        let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
4459
4460        state.handle_mouse(
4461            &down_event,
4462            hit,
4463            scrollbar_hit_id,
4464            total_items,
4465            viewport_height,
4466            fixed_height,
4467        );
4468
4469        assert!(
4470            state.scrollbar_drag_anchor.is_some(),
4471            "Drag anchor should be set on down"
4472        );
4473        assert_eq!(
4474            state.scrollbar_drag_anchor.unwrap(),
4475            0,
4476            "Anchor should be 0 (clicked top of thumb)"
4477        );
4478
4479        // Drag down by 1 cell.
4480        // track_pos = 1. anchor = 0. target thumb top = 1.
4481        // available = 9. max_pos = 90.
4482        // pos = (1 * 90) / 9 = 10.
4483        let drag_pos = 1u64;
4484        let drag_data = (SCROLLBAR_PART_THUMB << 56)
4485            | ((track_len & 0x0FFF_FFFF) << 28)
4486            | (drag_pos & 0x0FFF_FFFF);
4487        let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
4488        let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
4489
4490        state.handle_mouse(
4491            &drag_event,
4492            drag_hit,
4493            scrollbar_hit_id,
4494            total_items,
4495            viewport_height,
4496            fixed_height,
4497        );
4498
4499        assert_eq!(
4500            state.scroll_offset, 10,
4501            "Scroll offset should update smoothly"
4502        );
4503    }
4504}