1#![forbid(unsafe_code)]
2
3use std::cell::Cell as StdCell;
38use std::collections::VecDeque;
39use std::ops::Range;
40use std::time::Duration;
41
42use crate::scrollbar::{Scrollbar, ScrollbarOrientation, ScrollbarState};
43use crate::{StatefulWidget, clear_text_area};
44use ftui_core::geometry::Rect;
45pub use ftui_core::voi::{BetaPosterior, beta_voi};
46use ftui_render::cell::Cell;
47use ftui_render::frame::{Frame, RemeasureRequest};
48use ftui_style::Style;
49
50#[derive(Debug, Clone, Copy, PartialEq)]
52pub struct RemeasureDecision {
53 pub voi: f64,
55 pub cost: f64,
57}
58
59#[derive(Debug, Clone, PartialEq)]
66pub struct RemeasurePolicy {
67 pub posterior: BetaPosterior,
69 pub sample_cost: f64,
71 pub min_interval_frames: u32,
73 pub last_sample_frame: u64,
75}
76
77impl Default for RemeasurePolicy {
78 fn default() -> Self {
79 Self {
80 posterior: BetaPosterior::new(1.0, 9.0),
81 sample_cost: 0.08,
82 min_interval_frames: 6,
83 last_sample_frame: u64::MAX,
84 }
85 }
86}
87
88impl RemeasurePolicy {
89 #[must_use]
91 pub const fn new(posterior: BetaPosterior, sample_cost: f64, min_interval_frames: u32) -> Self {
92 Self {
93 posterior,
94 sample_cost,
95 min_interval_frames,
96 last_sample_frame: u64::MAX,
97 }
98 }
99
100 pub fn should_sample(&mut self, frame_idx: u64) -> Option<RemeasureDecision> {
103 if self.last_sample_frame != u64::MAX
104 && frame_idx.saturating_sub(self.last_sample_frame)
105 < u64::from(self.min_interval_frames)
106 {
107 return None;
108 }
109 let voi = self.posterior.voi();
110 if voi >= self.sample_cost {
111 self.last_sample_frame = frame_idx;
112 Some(RemeasureDecision {
113 voi,
114 cost: self.sample_cost,
115 })
116 } else {
117 None
118 }
119 }
120
121 pub fn should_remeasure(
124 &mut self,
125 frame_idx: u64,
126 violation_observed: bool,
127 ) -> Option<RemeasureDecision> {
128 let cooldown_ok = self.last_sample_frame == u64::MAX
129 || frame_idx.saturating_sub(self.last_sample_frame)
130 >= u64::from(self.min_interval_frames);
131 let decision = self.should_sample(frame_idx).or_else(|| {
132 if violation_observed && cooldown_ok {
133 self.last_sample_frame = frame_idx;
134 Some(RemeasureDecision {
135 voi: self.posterior.voi(),
136 cost: self.sample_cost,
137 })
138 } else {
139 None
140 }
141 });
142 self.observe(violation_observed);
143 decision
144 }
145
146 #[inline]
149 pub fn observe(&mut self, violation_observed: bool) {
150 self.posterior.observe(violation_observed);
151 }
152}
153
154#[derive(Debug, Clone)]
163pub struct Virtualized<T> {
164 storage: VirtualizedStorage<T>,
166 scroll_offset: usize,
168 visible_count: StdCell<usize>,
170 overscan: usize,
172 item_height: ItemHeight,
174 follow_mode: bool,
176 scroll_velocity: f32,
178 remeasure_policy: Option<RemeasurePolicy>,
180}
181
182#[derive(Debug, Clone)]
184pub enum VirtualizedStorage<T> {
185 Owned(VecDeque<T>),
187 External {
190 len: usize,
192 cache_capacity: usize,
194 },
195}
196
197#[derive(Debug, Clone)]
199pub enum ItemHeight {
200 Fixed(u16),
202 Variable(HeightCache),
207 VariableFenwick(VariableHeightsFenwick),
210}
211
212#[derive(Debug, Clone)]
214pub struct HeightCache {
215 cache: Vec<Option<u16>>,
217 base_offset: usize,
219 default_height: u16,
221 capacity: usize,
223}
224
225impl<T> Virtualized<T> {
226 #[must_use]
231 pub fn new(capacity: usize) -> Self {
232 Self {
233 storage: VirtualizedStorage::Owned(VecDeque::with_capacity(capacity.min(1024))),
234 scroll_offset: 0,
235 visible_count: StdCell::new(0),
236 overscan: 2,
237 item_height: ItemHeight::Fixed(1),
238 follow_mode: false,
239 scroll_velocity: 0.0,
240 remeasure_policy: None,
241 }
242 }
243
244 #[must_use]
246 pub fn external(len: usize, cache_capacity: usize) -> Self {
247 Self {
248 storage: VirtualizedStorage::External {
249 len,
250 cache_capacity,
251 },
252 scroll_offset: 0,
253 visible_count: StdCell::new(0),
254 overscan: 2,
255 item_height: ItemHeight::Fixed(1),
256 follow_mode: false,
257 scroll_velocity: 0.0,
258 remeasure_policy: None,
259 }
260 }
261
262 #[must_use]
264 pub fn with_remeasure_policy(mut self, policy: RemeasurePolicy) -> Self {
265 self.remeasure_policy = Some(policy);
266 self
267 }
268
269 #[must_use]
271 pub fn remeasure_policy(&self) -> Option<&RemeasurePolicy> {
272 self.remeasure_policy.as_ref()
273 }
274
275 pub fn remeasure_policy_mut(&mut self) -> Option<&mut RemeasurePolicy> {
277 self.remeasure_policy.as_mut()
278 }
279
280 pub fn invalidate(&mut self, idx: usize) {
283 match &mut self.item_height {
284 ItemHeight::Fixed(_) => {}
285 ItemHeight::Variable(cache) => cache.invalidate(idx),
286 ItemHeight::VariableFenwick(tracker) => tracker.invalidate(idx),
287 }
288 }
289
290 #[must_use]
292 pub fn with_item_height(mut self, height: ItemHeight) -> Self {
293 self.item_height = height;
294 self
295 }
296
297 #[must_use]
299 pub fn with_fixed_height(mut self, height: u16) -> Self {
300 self.item_height = ItemHeight::Fixed(height);
301 self
302 }
303
304 #[must_use]
312 pub fn with_height_prediction(mut self, config: PredictorConfig) -> Self {
313 let len = self.len();
314 let current = std::mem::replace(&mut self.item_height, ItemHeight::Fixed(1));
315 self.item_height = ItemHeight::VariableFenwick(match current {
316 ItemHeight::VariableFenwick(tracker) => tracker.with_predictor(config),
317 ItemHeight::Fixed(height) => {
318 VariableHeightsFenwick::new(height.max(1), len).with_predictor(config)
319 }
320 ItemHeight::Variable(cache) => {
321 VariableHeightsFenwick::new(cache.default_height, len).with_predictor(config)
322 }
323 });
324 self
325 }
326
327 #[must_use]
329 pub fn with_height_predictor(self, config: PredictorConfig) -> Self {
330 self.with_height_prediction(config)
331 }
332
333 pub fn observe_height(&mut self, idx: usize, height: u16) {
339 self.observe_height_in_category(idx, height, 0);
340 }
341
342 pub fn observe_height_in_category(&mut self, idx: usize, height: u16, category: usize) {
345 match &mut self.item_height {
346 ItemHeight::Fixed(_) => {}
347 ItemHeight::Variable(cache) => cache.set(idx, height),
348 ItemHeight::VariableFenwick(tracker) => tracker.set_in_category(idx, height, category),
349 }
350 }
351
352 #[must_use]
354 pub fn offset_of_item(&self, idx: usize) -> u32 {
355 let clamped = idx.min(self.len());
356 match &self.item_height {
357 ItemHeight::Fixed(h) => (clamped as u64)
358 .saturating_mul(u64::from(*h))
359 .min(u64::from(u32::MAX)) as u32,
360 ItemHeight::Variable(cache) => (0..clamped)
361 .fold(0u64, |acc, i| acc + u64::from(cache.get(i)))
362 .min(u64::from(u32::MAX)) as u32,
363 ItemHeight::VariableFenwick(tracker) => tracker.offset_of_item(clamped),
364 }
365 }
366
367 #[must_use]
369 pub fn find_item_at_offset(&self, offset: u32) -> usize {
370 let len = self.len();
371 match &self.item_height {
372 ItemHeight::Fixed(h) => {
373 let h = u32::from((*h).max(1));
374 ((offset / h) as usize).min(len)
375 }
376 ItemHeight::Variable(cache) => {
377 let mut acc = 0u64;
378 for i in 0..len {
379 let next = acc + u64::from(cache.get(i).max(1));
380 if u64::from(offset) < next {
381 return i;
382 }
383 acc = next;
384 }
385 len
386 }
387 ItemHeight::VariableFenwick(tracker) => tracker.find_item_at_offset(offset),
388 }
389 }
390
391 #[must_use]
393 pub fn predicted_height(&self, category: usize) -> u16 {
394 if let ItemHeight::VariableFenwick(tracker) = &self.item_height
395 && let Some(predictor) = tracker.predictor()
396 {
397 return predictor.predict(category).predicted.max(1);
398 }
399 self.unmeasured_item_height()
400 }
401
402 #[must_use]
404 pub fn predictor_stats(&self) -> Option<PredictorStats> {
405 match &self.item_height {
406 ItemHeight::VariableFenwick(tracker) => tracker.predictor().map(HeightPredictor::stats),
407 _ => None,
408 }
409 }
410
411 #[must_use]
415 pub fn unmeasured_item_height(&self) -> u16 {
416 match &self.item_height {
417 ItemHeight::Fixed(height) => *height,
418 ItemHeight::Variable(cache) => cache.default_height,
419 ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
420 }
421 }
422
423 #[must_use]
431 pub fn with_variable_heights(mut self, default_height: u16) -> Self {
432 let len = self.len();
433 self.item_height =
434 ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
435 self
436 }
437
438 #[must_use]
443 pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
444 self.item_height =
445 ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
446 self
447 }
448
449 fn sync_height_tracker(&mut self, exact: bool) {
454 let len = self.len();
455 if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
456 && (tracker.len() < len || (exact && tracker.len() != len))
457 {
458 tracker.resize(len);
459 }
460 }
461
462 #[must_use]
464 pub fn with_overscan(mut self, overscan: usize) -> Self {
465 self.overscan = overscan;
466 self
467 }
468
469 #[must_use]
471 pub fn with_follow(mut self, follow: bool) -> Self {
472 self.follow_mode = follow;
473 self
474 }
475
476 #[must_use]
478 pub fn len(&self) -> usize {
479 match &self.storage {
480 VirtualizedStorage::Owned(items) => items.len(),
481 VirtualizedStorage::External { len, .. } => *len,
482 }
483 }
484
485 #[must_use]
487 pub fn is_empty(&self) -> bool {
488 self.len() == 0
489 }
490
491 #[must_use]
496 pub fn scroll_offset(&self) -> usize {
497 self.scroll_offset.min(self.len().saturating_sub(1))
498 }
499
500 #[must_use]
502 pub fn visible_count(&self) -> usize {
503 self.visible_count.get()
504 }
505
506 #[must_use]
508 pub fn follow_mode(&self) -> bool {
509 self.follow_mode
510 }
511
512 #[must_use]
514 pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
515 if self.is_empty() || viewport_height == 0 {
516 self.visible_count.set(0);
517 return 0..0;
518 }
519
520 let items_visible = match &self.item_height {
521 ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
523 ItemHeight::Fixed(_) => viewport_height as usize,
524 ItemHeight::Variable(cache) => {
525 let len = self.len();
527 let start = self.scroll_offset.min(len.saturating_sub(1));
528 let mut count = 0;
529 let mut total_height = 0u16;
530 while start + count < len {
531 let next = cache.get(start + count);
532
533 total_height = total_height.saturating_add(next);
535 count += 1;
536
537 if total_height >= viewport_height {
539 break;
540 }
541 }
542 if total_height < viewport_height && start > 0 {
543 count = 0;
549 total_height = 0;
550 while count < len {
551 let next = cache.get(len - 1 - count);
552 total_height = total_height.saturating_add(next);
553 count += 1;
554 if total_height >= viewport_height {
555 break;
556 }
557 }
558 }
559 count
560 }
561 ItemHeight::VariableFenwick(tracker) => {
562 let len = self.len();
564 let start = self.scroll_offset.min(len.saturating_sub(1));
565 let total = tracker.total_height_exact();
566 let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
567 if suffix < u64::from(viewport_height) {
568 let anchor = total.saturating_sub(u64::from(viewport_height));
572 len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
573 .max(1)
574 } else {
575 tracker.visible_count(start, viewport_height).max(1)
576 }
577 }
578 };
579
580 let max_offset = self.len().saturating_sub(items_visible);
581 let start = self.scroll_offset.min(max_offset);
582 let end = start.saturating_add(items_visible).min(self.len());
583 self.visible_count.set(items_visible);
584 start..end
585 }
586
587 #[must_use]
589 pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
590 let visible = self.visible_range(viewport_height);
591 let start = visible.start.saturating_sub(self.overscan);
592 let end = visible.end.saturating_add(self.overscan).min(self.len());
593 start..end
594 }
595
596 pub fn scroll(&mut self, delta: i32) {
598 if self.is_empty() {
599 return;
600 }
601 let visible_count = self.visible_count.get();
612 let max_offset = match self.item_height {
613 ItemHeight::Fixed(_) if visible_count > 0 => self.len().saturating_sub(visible_count),
614 _ => self.len().saturating_sub(1),
615 };
616 let clamped_current = self.scroll_offset.min(max_offset);
618 let new_offset = clamped_current
619 .saturating_add_signed(delta as isize)
620 .min(max_offset);
621 self.scroll_offset = new_offset;
622
623 if delta != 0 {
625 self.follow_mode = false;
626 }
627 }
628
629 pub fn scroll_to(&mut self, idx: usize) {
631 if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
632 tracker.refresh_category_predictions();
633 }
634 self.scroll_offset = idx.min(self.len().saturating_sub(1));
635 self.follow_mode = false;
636 }
637
638 pub fn scroll_to_bottom(&mut self) {
640 if self.is_empty() {
641 self.scroll_offset = 0;
642 return;
643 }
644
645 if !matches!(self.item_height, ItemHeight::Fixed(_)) {
657 self.scroll_offset = usize::MAX;
658 return;
659 }
660
661 let visible_count = self.visible_count.get();
662 if visible_count == 0 {
663 self.scroll_offset = usize::MAX;
665 } else if self.len() > visible_count {
666 self.scroll_offset = self.len().saturating_sub(visible_count);
667 } else {
668 self.scroll_offset = 0;
669 }
670 }
671
672 pub fn scroll_to_top(&mut self) {
674 self.scroll_offset = 0;
675 self.follow_mode = false;
676 }
677
678 pub fn scroll_to_start(&mut self) {
680 self.scroll_to_top();
681 }
682
683 pub fn scroll_to_end(&mut self) {
685 self.scroll_to_bottom();
686 self.follow_mode = true;
687 }
688
689 pub fn page_up(&mut self) {
691 let visible_count = self.visible_count.get();
692 if visible_count > 0 {
693 let step = if visible_count > 1 {
694 visible_count - 1
695 } else {
696 1
697 };
698 let delta = i32::try_from(step).unwrap_or(i32::MAX);
699 self.scroll(-delta);
700 }
701 }
702
703 pub fn page_down(&mut self) {
705 let visible_count = self.visible_count.get();
706 if visible_count > 0 {
707 let step = if visible_count > 1 {
708 visible_count - 1
709 } else {
710 1
711 };
712 let delta = i32::try_from(step).unwrap_or(i32::MAX);
713 self.scroll(delta);
714 }
715 }
716
717 pub fn set_follow(&mut self, follow: bool) {
719 self.follow_mode = follow;
720 if follow {
721 self.scroll_to_bottom();
722 }
723 }
724
725 #[must_use]
727 pub fn is_at_bottom(&self) -> bool {
728 let visible_count = self.visible_count.get();
729 if self.len() <= visible_count {
730 true
731 } else {
732 self.scroll_offset >= self.len().saturating_sub(visible_count)
733 }
734 }
735
736 pub fn fling(&mut self, velocity: f32) {
738 self.scroll_velocity = velocity;
739 }
740
741 pub fn tick(&mut self, dt: Duration) {
743 if self.scroll_velocity.abs() > 0.1 {
744 let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
745 if delta != 0 {
746 self.scroll(delta);
747 }
748 self.scroll_velocity *= 0.95;
750 } else {
751 self.scroll_velocity = 0.0;
752 }
753 }
754
755 pub fn set_visible_count(&self, count: usize) {
757 self.visible_count.set(count);
758 }
759
760 #[must_use]
762 pub fn item_height(&self) -> &ItemHeight {
763 &self.item_height
764 }
765
766 pub fn item_height_mut(&mut self) -> &mut ItemHeight {
771 &mut self.item_height
772 }
773}
774
775impl<T> Virtualized<T> {
776 pub fn push(&mut self, item: T) {
778 if let VirtualizedStorage::Owned(items) = &mut self.storage {
779 items.push_back(item);
780 self.sync_height_tracker(false);
781 if self.follow_mode {
782 self.scroll_to_bottom();
783 }
784 }
785 }
786
787 #[must_use = "use the returned item (if any)"]
789 pub fn get(&self, idx: usize) -> Option<&T> {
790 if let VirtualizedStorage::Owned(items) = &self.storage {
791 items.get(idx)
792 } else {
793 None
794 }
795 }
796
797 #[must_use = "use the returned item (if any)"]
799 pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
800 if let VirtualizedStorage::Owned(items) = &mut self.storage {
801 items.get_mut(idx)
802 } else {
803 None
804 }
805 }
806
807 pub fn clear(&mut self) {
809 if let VirtualizedStorage::Owned(items) = &mut self.storage {
810 items.clear();
811 match &mut self.item_height {
812 ItemHeight::Fixed(_) => {}
813 ItemHeight::Variable(cache) => cache.clear(),
814 ItemHeight::VariableFenwick(tracker) => tracker.clear(),
815 }
816 }
817 self.scroll_offset = 0;
818 }
819
820 pub fn trim_front(&mut self, max: usize) -> usize {
824 if let VirtualizedStorage::Owned(items) = &mut self.storage
825 && items.len() > max
826 {
827 let to_remove = items.len() - max;
828 items.drain(..to_remove);
829 match &mut self.item_height {
833 ItemHeight::Fixed(_) => {}
834 ItemHeight::Variable(cache) => cache.drop_front(to_remove),
835 ItemHeight::VariableFenwick(tracker) => tracker.drop_front(to_remove),
836 }
837 self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
839 return to_remove;
840 }
841 0
842 }
843
844 pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
847 match &self.storage {
848 VirtualizedStorage::Owned(items) => Box::new(items.iter()),
849 VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
850 }
851 }
852
853 pub fn set_external_len(&mut self, len: usize) {
855 if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
856 *l = len;
857 self.sync_height_tracker(true);
858 if self.follow_mode {
859 self.scroll_to_bottom();
860 }
861 }
862 }
863}
864
865impl Default for HeightCache {
866 fn default() -> Self {
867 Self::new(1, 1000)
868 }
869}
870
871impl HeightCache {
872 #[must_use]
874 pub fn new(default_height: u16, capacity: usize) -> Self {
875 Self {
876 cache: Vec::new(),
877 base_offset: 0,
878 default_height,
879 capacity,
880 }
881 }
882
883 #[must_use]
885 pub fn get(&self, idx: usize) -> u16 {
886 if idx < self.base_offset {
887 return self.default_height;
888 }
889 let local = idx - self.base_offset;
890 self.cache
891 .get(local)
892 .and_then(|h| *h)
893 .unwrap_or(self.default_height)
894 }
895
896 pub fn set(&mut self, idx: usize, height: u16) {
898 if self.capacity == 0 {
899 return;
900 }
901 if idx < self.base_offset {
902 return;
904 }
905 let mut local = idx - self.base_offset;
906
907 if local + 1 >= self.cache.len() + self.capacity {
910 self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
911 self.cache.clear();
912 local = idx - self.base_offset;
913 }
914
915 if local >= self.cache.len() {
916 self.cache.resize(local + 1, None);
917 }
918 self.cache[local] = Some(height);
919
920 if self.cache.len() > self.capacity {
922 let to_remove = self.cache.len() - self.capacity;
923 self.cache.drain(0..to_remove);
924 self.base_offset += to_remove;
925 }
926 }
927
928 pub fn drop_front(&mut self, count: usize) {
934 if count == 0 {
935 return;
936 }
937 if let Some(base) = self.base_offset.checked_sub(count) {
938 self.base_offset = base;
940 return;
941 }
942 let dropped = count - self.base_offset;
943 if dropped >= self.cache.len() {
944 self.cache.clear();
945 } else {
946 self.cache.drain(0..dropped);
947 }
948 self.base_offset = 0;
949 }
950
951 pub fn clear(&mut self) {
953 self.cache.clear();
954 self.base_offset = 0;
955 }
956
957 pub fn invalidate(&mut self, idx: usize) {
959 if idx < self.base_offset {
960 return;
961 }
962 let local = idx - self.base_offset;
963 if let Some(slot) = self.cache.get_mut(local) {
964 *slot = None;
965 }
966 }
967}
968
969use crate::height_predictor::{HeightPredictor, PredictorConfig, PredictorStats};
974
975#[derive(Debug, Clone)]
996pub struct VariableHeightsFenwick {
997 tree: Vec<u64>,
999 default_height: u16,
1001 len: usize,
1003 measured: Vec<u64>,
1005 unmeasured: usize,
1007 predictor: Option<HeightPredictor>,
1009 fill_height: u16,
1012 categories: Vec<u16>,
1014 cat_fill_heights: Vec<u16>,
1016 categories_synced_len: usize,
1018 last_violation: bool,
1021}
1022
1023impl Default for VariableHeightsFenwick {
1024 fn default() -> Self {
1025 Self::new(1, 0)
1026 }
1027}
1028
1029impl VariableHeightsFenwick {
1030 #[must_use]
1032 pub fn new(default_height: u16, capacity: usize) -> Self {
1033 let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
1034 Self {
1035 tree,
1036 default_height,
1037 len: capacity,
1038 measured: vec![0; capacity.div_ceil(64)],
1039 unmeasured: capacity,
1040 predictor: None,
1041 fill_height: default_height,
1042 categories: vec![0; capacity],
1043 cat_fill_heights: vec![default_height],
1044 categories_synced_len: 0,
1045 last_violation: false,
1046 }
1047 }
1048
1049 #[must_use]
1051 pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
1052 Self {
1053 tree: Self::build_height_tree(heights.iter().copied()),
1054 default_height,
1055 len: heights.len(),
1056 measured: Self::all_measured_bits(heights.len()),
1057 unmeasured: 0,
1058 predictor: None,
1059 fill_height: default_height,
1060 categories: vec![0; heights.len()],
1061 cat_fill_heights: vec![default_height],
1062 categories_synced_len: 0,
1063 last_violation: false,
1064 }
1065 }
1066
1067 fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
1070 let len = heights.len();
1071 assert!(
1072 u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
1073 "too many items for exact height aggregates"
1074 );
1075 let mut tree = vec![0; len + 1];
1076 for (slot, height) in tree[1..].iter_mut().zip(heights) {
1077 *slot = u64::from(height);
1078 }
1079 for idx in 1..=len {
1080 let parent = idx + idx.isolate_lowest_one();
1081 if parent <= len {
1082 tree[parent] += tree[idx];
1083 }
1084 }
1085 tree
1086 }
1087
1088 fn all_measured_bits(len: usize) -> Vec<u64> {
1089 let mut bits = vec![u64::MAX; len.div_ceil(64)];
1090 if !len.is_multiple_of(64) {
1091 *bits.last_mut().expect("partial word exists") = (1_u64 << (len % 64)) - 1;
1092 }
1093 bits
1094 }
1095
1096 fn mark_measured(&mut self, idx: usize) {
1097 if !self.is_measured(idx) {
1098 self.measured[idx / 64] |= 1_u64 << (idx % 64);
1099 self.unmeasured -= 1;
1100 }
1101 }
1102
1103 #[inline]
1104 fn fill_height_for_category(&self, category: usize) -> u16 {
1105 self.cat_fill_heights
1106 .get(category)
1107 .copied()
1108 .unwrap_or(self.fill_height)
1109 }
1110
1111 pub fn set_categories(&mut self, categories: impl IntoIterator<Item = usize>) {
1114 self.categories.clear();
1115 self.categories.extend(
1116 categories
1117 .into_iter()
1118 .take(self.len)
1119 .map(|c| u16::try_from(c).unwrap_or(u16::MAX)),
1120 );
1121 self.categories.resize(self.len, 0);
1122 self.categories_synced_len = self.len;
1123 for idx in 0..self.len {
1124 if !self.is_measured(idx) {
1125 let cat = self.categories[idx] as usize;
1126 let h = self.fill_height_for_category(cat);
1127 if self.get(idx) != h {
1128 self.set_tracked_height(idx, h);
1129 }
1130 }
1131 }
1132 }
1133
1134 pub fn invalidate(&mut self, idx: usize) {
1137 if idx < self.len && self.is_measured(idx) {
1138 self.measured[idx / 64] &= !(1_u64 << (idx % 64));
1139 self.unmeasured += 1;
1140 let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
1141 self.set_tracked_height(idx, self.fill_height_for_category(cat));
1142 }
1143 }
1144
1145 #[inline]
1147 pub fn take_last_violation(&mut self) -> bool {
1148 std::mem::replace(&mut self.last_violation, false)
1149 }
1150
1151 fn set_tracked_height(&mut self, idx: usize, height: u16) {
1152 let old = self.get(idx);
1153 let mut node = idx + 1;
1154 while node <= self.len {
1155 if height >= old {
1156 self.tree[node] += u64::from(height - old);
1157 } else {
1158 self.tree[node] -= u64::from(old - height);
1159 }
1160 node += node.isolate_lowest_one();
1161 }
1162 }
1163
1164 fn offset_of_item_exact(&self, idx: usize) -> u64 {
1165 let mut node = idx.min(self.len);
1166 let mut sum = 0;
1167 while node > 0 {
1168 sum += self.tree[node];
1169 node &= node - 1;
1170 }
1171 sum
1172 }
1173
1174 fn total_height_exact(&self) -> u64 {
1175 self.offset_of_item_exact(self.len)
1176 }
1177
1178 fn find_item_at_offset_exact(&self, offset: u64) -> usize {
1179 if self.len == 0 || offset == 0 {
1181 return 0;
1182 }
1183 let mut idx = 0;
1184 let mut sum = 0;
1185 let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
1186 while step > 0 {
1187 if step <= self.len - idx {
1188 let next = idx + step;
1189 let prefix = sum + self.tree[next];
1190 if prefix <= offset {
1191 idx = next;
1192 sum = prefix;
1193 }
1194 }
1195 step >>= 1;
1196 }
1197 idx
1198 }
1199
1200 #[must_use]
1210 pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
1211 let predictor = HeightPredictor::new(config);
1212 self.fill_height = predictor.predict(0).predicted.max(1);
1213 self.cat_fill_heights.fill(self.fill_height);
1214 if self.cat_fill_heights.is_empty() {
1215 self.cat_fill_heights.push(self.fill_height);
1216 }
1217 self.predictor = Some(predictor);
1218 self.refill_unmeasured();
1219 self
1220 }
1221
1222 #[must_use]
1224 pub fn predictor(&self) -> Option<&HeightPredictor> {
1225 self.predictor.as_ref()
1226 }
1227
1228 #[must_use]
1231 pub fn predicted_height(&self) -> u16 {
1232 self.fill_height
1233 }
1234
1235 #[must_use]
1237 pub fn unmeasured_count(&self) -> usize {
1238 self.unmeasured
1239 }
1240
1241 #[must_use]
1243 pub fn is_measured(&self, idx: usize) -> bool {
1244 idx < self.len && self.measured[idx / 64] & (1_u64 << (idx % 64)) != 0
1245 }
1246
1247 fn refill_unmeasured(&mut self) -> usize {
1250 let mut rewritten = 0;
1251 for idx in 0..self.len {
1252 if !self.is_measured(idx) {
1253 let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
1254 let h = self.fill_height_for_category(cat);
1255 self.set_tracked_height(idx, h);
1256 rewritten += 1;
1257 }
1258 }
1259 rewritten
1260 }
1261
1262 #[must_use]
1264 pub fn len(&self) -> usize {
1265 self.len
1266 }
1267
1268 #[must_use]
1270 pub fn is_empty(&self) -> bool {
1271 self.len == 0
1272 }
1273
1274 #[must_use]
1276 pub fn default_height(&self) -> u16 {
1277 self.default_height
1278 }
1279
1280 #[must_use]
1285 pub fn get(&self, idx: usize) -> u16 {
1286 if idx >= self.len {
1287 return self.fill_height;
1288 }
1289 (self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
1290 }
1291
1292 pub fn set(&mut self, idx: usize, height: u16) {
1296 self.set_in_category(idx, height, 0);
1297 }
1298
1299 pub fn refresh_category_predictions(&mut self) {
1302 let Some(predictor) = self.predictor.as_ref() else {
1303 return;
1304 };
1305 if self.unmeasured == 0 || self.categories_synced_len == 0 {
1306 return;
1307 }
1308 let cat_count = predictor.category_count().max(1);
1309 if self.cat_fill_heights.len() < cat_count {
1310 self.cat_fill_heights.resize(cat_count, self.fill_height);
1311 }
1312 let mut any_changed = false;
1313 for cat in 0..cat_count {
1314 let next = predictor.predict(cat).predicted.max(1);
1315 if cat == 0 {
1316 self.fill_height = next;
1317 }
1318 if self.cat_fill_heights[cat] != next {
1319 self.cat_fill_heights[cat] = next;
1320 any_changed = true;
1321 }
1322 }
1323 if !any_changed {
1324 return;
1325 }
1326 for idx in 0..self.len {
1327 if !self.is_measured(idx) {
1328 let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
1329 let h = self.fill_height_for_category(cat);
1330 self.set_tracked_height(idx, h);
1331 }
1332 }
1333 }
1334
1335 pub fn set_in_category(&mut self, idx: usize, height: u16, category: usize) {
1338 if idx >= self.len {
1339 self.resize(idx.checked_add(1).expect("height index exceeds usize"));
1341 }
1342 let cat_u16 = u16::try_from(category).unwrap_or(u16::MAX);
1343 self.categories[idx] = cat_u16;
1344 let was_measured = self.is_measured(idx);
1345 let old_height = self.get(idx);
1346 self.set_tracked_height(idx, height);
1347 self.mark_measured(idx);
1348 if was_measured && old_height != height {
1349 self.last_violation = true;
1350 }
1351 if let Some(predictor) = self.predictor.as_mut() {
1352 let within_bounds = predictor.observe(category, height);
1353 if !within_bounds {
1354 self.last_violation = true;
1355 }
1356 let next = predictor.predict(category).predicted.max(1);
1357 if self.cat_fill_heights.len() <= category {
1358 self.cat_fill_heights.resize(category + 1, self.fill_height);
1359 }
1360 if category == 0 {
1361 self.fill_height = next;
1362 }
1363 if self.categories_synced_len == 0 && category == 0 && self.cat_fill_heights[0] != next
1364 {
1365 self.cat_fill_heights[0] = next;
1366 self.refill_unmeasured();
1367 }
1368 }
1369 }
1370
1371 #[must_use]
1376 pub fn offset_of_item(&self, idx: usize) -> u32 {
1377 self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
1378 }
1379
1380 #[must_use]
1390 pub fn find_item_at_offset(&self, offset: u32) -> usize {
1391 self.find_item_at_offset_exact(u64::from(offset))
1392 }
1393
1394 #[must_use]
1402 pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
1403 if self.len == 0 || viewport_height == 0 {
1404 return 0;
1405 }
1406 let start = start_idx.min(self.len);
1407 let start_offset = self.offset_of_item_exact(start);
1408 let end_offset = start_offset.saturating_add(u64::from(viewport_height));
1409
1410 let end_idx = self.find_item_at_offset_exact(end_offset);
1412
1413 if end_idx > start {
1415 if end_idx >= self.len {
1418 return self.len.saturating_sub(start);
1419 }
1420 let end_item_start = self.offset_of_item_exact(end_idx);
1422 if end_offset > end_item_start {
1423 end_idx - start + 1
1424 } else {
1425 end_idx - start
1426 }
1427 } else {
1428 if viewport_height > 0 && start < self.len {
1430 1
1431 } else {
1432 0
1433 }
1434 }
1435 }
1436
1437 #[must_use]
1439 pub fn total_height(&self) -> u32 {
1440 self.total_height_exact().min(u64::from(u32::MAX)) as u32
1441 }
1442
1443 pub fn resize(&mut self, new_len: usize) {
1448 if new_len == self.len {
1449 return;
1450 }
1451 assert!(
1452 u64::try_from(new_len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
1453 "too many items for exact height aggregates"
1454 );
1455 if new_len > self.len {
1456 self.tree.reserve(new_len + 1 - self.tree.len());
1457 let fill = u64::from(self.fill_height);
1458 for node in (self.len + 1)..=new_len {
1459 let mut sum = fill;
1460 let tz = node.trailing_zeros();
1461 for k in 0..tz {
1462 sum += self.tree[node - (1usize << k)];
1463 }
1464 self.tree.push(sum);
1465 }
1466 self.unmeasured += new_len - self.len;
1467 self.measured.resize(new_len.div_ceil(64), 0);
1468 } else {
1469 let dropped_unmeasured = (new_len..self.len)
1470 .filter(|&idx| !self.is_measured(idx))
1471 .count();
1472 self.unmeasured -= dropped_unmeasured;
1473 self.tree.truncate(new_len + 1);
1474 self.measured.truncate(new_len.div_ceil(64));
1475 if !new_len.is_multiple_of(64) {
1476 *self.measured.last_mut().expect("partial word exists") &=
1477 (1_u64 << (new_len % 64)) - 1;
1478 }
1479 }
1480 self.categories.resize(new_len, 0);
1481 self.len = new_len;
1482 }
1483
1484 pub fn drop_front(&mut self, n: usize) {
1488 if n == 0 {
1489 return;
1490 }
1491 if n >= self.len {
1492 self.clear();
1493 return;
1494 }
1495 let kept: Vec<(u16, bool, u16)> = (n..self.len)
1496 .map(|idx| (self.get(idx), self.is_measured(idx), self.categories[idx]))
1497 .collect();
1498 self.tree = Self::build_height_tree(kept.iter().map(|&(height, _, _)| height));
1499 self.len = kept.len();
1500 self.measured = vec![0; self.len.div_ceil(64)];
1501 self.categories = kept.iter().map(|&(_, _, cat)| cat).collect();
1502 self.categories_synced_len = self.categories_synced_len.saturating_sub(n);
1503 self.unmeasured = self.len;
1504 for (idx, (_, measured, _)) in kept.into_iter().enumerate() {
1505 if measured {
1506 self.mark_measured(idx);
1507 }
1508 }
1509 }
1510
1511 pub fn clear(&mut self) {
1513 self.tree = vec![0];
1514 self.len = 0;
1515 self.measured.clear();
1516 self.categories.clear();
1517 self.categories_synced_len = 0;
1518 self.unmeasured = 0;
1519 self.last_violation = false;
1520 }
1521
1522 pub fn rebuild(&mut self, heights: &[u16]) {
1525 self.tree = Self::build_height_tree(heights.iter().copied());
1526 self.len = heights.len();
1527 self.measured = Self::all_measured_bits(heights.len());
1528 self.categories.resize(heights.len(), 0);
1529 self.unmeasured = 0;
1530 if let Some(predictor) = self.predictor.as_mut() {
1531 for &height in heights {
1532 predictor.observe(0, height);
1533 }
1534 self.fill_height = predictor.predict(0).predicted.max(1);
1535 if !self.cat_fill_heights.is_empty() {
1536 self.cat_fill_heights[0] = self.fill_height;
1537 }
1538 }
1539 }
1540}
1541
1542pub trait RenderItem {
1550 fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
1560
1561 fn height(&self) -> u16 {
1563 1
1564 }
1565
1566 fn category(&self) -> usize {
1569 0
1570 }
1571}
1572
1573impl<T: RenderItem> Virtualized<T> {
1574 pub fn sync_item_categories(&mut self) {
1577 if let (VirtualizedStorage::Owned(items), ItemHeight::VariableFenwick(tracker)) =
1578 (&self.storage, &mut self.item_height)
1579 && tracker.categories_synced_len != items.len()
1580 {
1581 tracker.set_categories(items.iter().map(RenderItem::category));
1582 }
1583 }
1584
1585 pub fn measure(&mut self, idx: usize, height: u16) {
1589 self.sync_item_categories();
1590 let category = self.get(idx).map_or(0, RenderItem::category);
1591 self.observe_height_in_category(idx, height, category);
1592 }
1593}
1594
1595#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1597pub enum ListHeightMode {
1598 Fixed(u16),
1600 Variable,
1605}
1606
1607#[derive(Debug, Clone)]
1609pub struct VirtualizedListState {
1610 pub selected: Option<usize>,
1612 scroll_offset: usize,
1614 visible_count: usize,
1616 overscan: usize,
1618 follow_mode: bool,
1620 scroll_velocity: f32,
1622 scrollbar_drag_anchor: Option<usize>,
1624 persistence_id: Option<String>,
1626 heights: Option<VariableHeightsFenwick>,
1629 remeasure_policy: Option<RemeasurePolicy>,
1631 render_frame_idx: u64,
1633}
1634
1635impl Default for VirtualizedListState {
1636 fn default() -> Self {
1637 Self::new()
1638 }
1639}
1640
1641impl VirtualizedListState {
1642 #[must_use]
1644 pub fn new() -> Self {
1645 Self {
1646 selected: None,
1647 scroll_offset: 0,
1648 visible_count: 0,
1649 overscan: 2,
1650 follow_mode: false,
1651 scroll_velocity: 0.0,
1652 scrollbar_drag_anchor: None,
1653 persistence_id: None,
1654 heights: None,
1655 remeasure_policy: None,
1656 render_frame_idx: 0,
1657 }
1658 }
1659
1660 #[must_use]
1662 pub fn variable(default_height: u16) -> Self {
1663 Self {
1664 heights: Some(VariableHeightsFenwick::new(default_height.max(1), 0)),
1665 ..Self::new()
1666 }
1667 }
1668
1669 #[must_use]
1672 pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
1673 self.heights = Some(
1674 self.heights
1675 .take()
1676 .unwrap_or_default()
1677 .with_predictor(config),
1678 );
1679 self
1680 }
1681
1682 #[must_use]
1684 pub fn with_remeasure_policy(mut self, policy: RemeasurePolicy) -> Self {
1685 self.remeasure_policy = Some(policy);
1686 self
1687 }
1688
1689 #[must_use]
1691 pub fn remeasure_policy(&self) -> Option<&RemeasurePolicy> {
1692 self.remeasure_policy.as_ref()
1693 }
1694
1695 pub fn remeasure_policy_mut(&mut self) -> Option<&mut RemeasurePolicy> {
1697 self.remeasure_policy.as_mut()
1698 }
1699
1700 pub fn invalidate(&mut self, idx: usize) {
1703 if let Some(heights) = self.heights.as_mut() {
1704 heights.invalidate(idx);
1705 }
1706 }
1707
1708 pub fn remeasure_tick(&mut self, frame_idx: u64, widget_id: u64) -> Option<RemeasureRequest> {
1712 let violation_observed = self
1713 .heights
1714 .as_mut()
1715 .is_some_and(VariableHeightsFenwick::take_last_violation);
1716 let policy = self.remeasure_policy.as_mut()?;
1717 let alpha = policy.posterior.alpha;
1718 let beta = policy.posterior.beta;
1719 let decision = policy.should_remeasure(frame_idx, violation_observed)?;
1720 let index = self.scroll_offset;
1721 if let Some(heights) = self.heights.as_mut() {
1722 heights.invalidate(index);
1723 }
1724 Some(RemeasureRequest {
1725 widget_id,
1726 index,
1727 voi: decision.voi,
1728 cost: decision.cost,
1729 alpha,
1730 beta,
1731 })
1732 }
1733
1734 #[must_use]
1736 pub fn predicted_height(&self, category: usize) -> u16 {
1737 self.heights.as_ref().map_or(1, |heights| {
1738 heights
1739 .predictor()
1740 .map_or(heights.default_height(), |predictor| {
1741 predictor.predict(category).predicted.max(1)
1742 })
1743 })
1744 }
1745
1746 #[must_use]
1748 pub fn predictor_stats(&self) -> Option<PredictorStats> {
1749 self.heights
1750 .as_ref()
1751 .and_then(VariableHeightsFenwick::predictor)
1752 .map(HeightPredictor::stats)
1753 }
1754
1755 pub fn measure(&mut self, idx: usize, height: u16) {
1760 self.measure_in_category(idx, height, 0);
1761 }
1762
1763 pub fn measure_in_category(&mut self, idx: usize, height: u16, category: usize) {
1765 if let Some(heights) = self.heights.as_mut() {
1766 if idx >= heights.len() {
1767 heights.resize(idx + 1);
1768 }
1769 heights.set_in_category(idx, height.max(1), category);
1770 }
1771 }
1772
1773 pub fn resize_heights(&mut self, len: usize) {
1775 if let Some(heights) = self.heights.as_mut()
1776 && heights.len() != len
1777 {
1778 heights.resize(len);
1779 }
1780 }
1781
1782 #[must_use]
1784 pub fn offset_of_item(&self, idx: usize) -> u32 {
1785 self.heights
1786 .as_ref()
1787 .map_or(idx as u32, |h| h.offset_of_item(idx))
1788 }
1789
1790 #[must_use]
1792 pub fn find_item_at_offset(&self, offset: u32) -> usize {
1793 self.heights
1794 .as_ref()
1795 .map_or(offset as usize, |h| h.find_item_at_offset(offset))
1796 }
1797
1798 #[must_use]
1800 pub fn selected(&self) -> Option<usize> {
1801 self.selected
1802 }
1803
1804 #[must_use]
1806 pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
1807 self.heights.as_ref()
1808 }
1809
1810 #[must_use]
1812 pub fn with_overscan(mut self, overscan: usize) -> Self {
1813 self.overscan = overscan;
1814 self
1815 }
1816
1817 #[must_use]
1819 pub fn with_follow(mut self, follow: bool) -> Self {
1820 self.follow_mode = follow;
1821 self
1822 }
1823
1824 #[must_use]
1827 pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
1828 self.persistence_id = Some(id.into());
1829 self
1830 }
1831
1832 #[must_use = "use the persistence id (if any)"]
1834 pub fn persistence_id(&self) -> Option<&str> {
1835 self.persistence_id.as_deref()
1836 }
1837
1838 #[must_use]
1845 pub fn scroll_offset(&self) -> usize {
1846 self.scroll_offset
1847 }
1848
1849 #[must_use]
1854 pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
1855 if total_items == 0 {
1856 return 0;
1857 }
1858 self.scroll_offset.min(total_items.saturating_sub(1))
1859 }
1860
1861 #[must_use]
1863 pub fn visible_count(&self) -> usize {
1864 self.visible_count
1865 }
1866
1867 pub fn scroll(&mut self, delta: i32, total_items: usize) {
1869 if total_items == 0 {
1870 return;
1871 }
1872 let max_offset = if self.visible_count > 0 {
1873 total_items.saturating_sub(self.visible_count)
1874 } else {
1875 total_items.saturating_sub(1)
1876 };
1877 let clamped_current = self.scroll_offset.min(max_offset);
1879 let new_offset = clamped_current
1880 .saturating_add_signed(delta as isize)
1881 .min(max_offset);
1882 self.scroll_offset = new_offset;
1883
1884 if delta != 0 {
1885 self.follow_mode = false;
1886 }
1887 }
1888
1889 pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
1891 self.scroll_offset = idx.min(total_items.saturating_sub(1));
1892 self.follow_mode = false;
1893 }
1894
1895 pub fn scroll_to_top(&mut self) {
1897 self.scroll_offset = 0;
1898 self.follow_mode = false;
1899 }
1900
1901 pub fn scroll_to_bottom(&mut self, total_items: usize) {
1903 if total_items == 0 {
1904 self.scroll_offset = 0;
1905 } else {
1906 self.scroll_offset = usize::MAX;
1909 }
1910 }
1911
1912 pub fn page_up(&mut self, total_items: usize) {
1914 if self.visible_count > 0 {
1915 let step = if self.visible_count > 1 {
1916 self.visible_count - 1
1917 } else {
1918 1
1919 };
1920 let delta = i32::try_from(step).unwrap_or(i32::MAX);
1921 self.scroll(-delta, total_items);
1922 }
1923 }
1924
1925 pub fn page_down(&mut self, total_items: usize) {
1927 if self.visible_count > 0 {
1928 let step = if self.visible_count > 1 {
1929 self.visible_count - 1
1930 } else {
1931 1
1932 };
1933 let delta = i32::try_from(step).unwrap_or(i32::MAX);
1934 self.scroll(delta, total_items);
1935 }
1936 }
1937
1938 pub fn select(&mut self, index: Option<usize>) {
1940 self.selected = index;
1941 }
1942
1943 pub fn select_previous(&mut self, total_items: usize) {
1945 if total_items == 0 {
1946 self.selected = None;
1947 return;
1948 }
1949 self.selected = Some(match self.selected {
1950 Some(i) if i > 0 => i - 1,
1951 Some(_) => 0,
1952 None => 0,
1953 });
1954 }
1955
1956 pub fn select_next(&mut self, total_items: usize) {
1958 if total_items == 0 {
1959 self.selected = None;
1960 return;
1961 }
1962 self.selected = Some(match self.selected {
1963 Some(i) if i < total_items - 1 => i + 1,
1964 Some(i) => i,
1965 None => 0,
1966 });
1967 }
1968
1969 #[must_use]
1971 pub fn is_at_bottom(&self, total_items: usize) -> bool {
1972 if total_items <= self.visible_count {
1973 true
1974 } else {
1975 self.scroll_offset >= total_items - self.visible_count
1976 }
1977 }
1978
1979 pub fn set_follow(&mut self, follow: bool, total_items: usize) {
1981 self.follow_mode = follow;
1982 if follow {
1983 self.scroll_to_bottom(total_items);
1984 }
1985 }
1986
1987 #[must_use]
1989 pub fn follow_mode(&self) -> bool {
1990 self.follow_mode
1991 }
1992
1993 pub fn fling(&mut self, velocity: f32) {
1995 self.scroll_velocity = velocity;
1996 }
1997
1998 pub fn tick(&mut self, dt: Duration, total_items: usize) {
2000 if self.scroll_velocity.abs() > 0.1 {
2001 let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
2002 if delta != 0 {
2003 self.scroll(delta, total_items);
2004 }
2005 self.scroll_velocity *= 0.95;
2006 } else {
2007 self.scroll_velocity = 0.0;
2008 }
2009 }
2010
2011 pub fn handle_mouse(
2021 &mut self,
2022 event: &ftui_core::event::MouseEvent,
2023 hit: Option<(
2024 ftui_render::frame::HitId,
2025 ftui_render::frame::HitRegion,
2026 u64,
2027 )>,
2028 scrollbar_hit_id: ftui_render::frame::HitId,
2029 total_items: usize,
2030 viewport_height: u16,
2031 fixed_item_height: u16,
2032 ) -> crate::mouse::MouseResult {
2033 if let Some(heights) = self.heights.as_ref()
2034 && heights.len() == total_items
2035 && total_items > 0
2036 {
2037 let old_item = self.scroll_offset.min(total_items - 1);
2038 let old_row = heights.offset_of_item_exact(old_item);
2039 let mut scrollbar_state = scrollbar_state_for_rows(
2040 heights.total_height_exact(),
2041 old_row,
2042 viewport_height,
2043 usize::MAX,
2044 );
2045 scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
2046 let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
2047 self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
2048
2049 let total_rows = heights.total_height_exact();
2053 let row = scrollbar_state.position as u64;
2054 let mut item = heights.find_item_at_offset_exact(row);
2055 let start = heights.offset_of_item_exact(item);
2056 if row + u64::from(viewport_height) >= total_rows {
2057 item = total_items - 1;
2058 } else if row.saturating_sub(start) * 2 > u64::from(heights.get(item)) {
2059 item += 1;
2060 }
2061 if row > old_row && item <= old_item {
2063 item = old_item + 1;
2064 } else if row < old_row && item >= old_item {
2065 item = old_item.saturating_sub(1);
2066 }
2067 self.scroll_offset = item.min(total_items - 1);
2068
2069 if result == crate::mouse::MouseResult::Scrolled {
2070 self.follow_mode = false;
2071 }
2072 return result;
2073 }
2074
2075 let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
2077 let mut scrollbar_state =
2078 ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
2079
2080 scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
2082
2083 let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
2084
2085 self.scroll_offset = scrollbar_state.position;
2087 self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
2088
2089 if result == crate::mouse::MouseResult::Scrolled {
2090 self.follow_mode = false;
2091 }
2092
2093 result
2094 }
2095}
2096
2097#[derive(Clone, Debug, Default, PartialEq)]
2106#[cfg_attr(
2107 feature = "state-persistence",
2108 derive(serde::Serialize, serde::Deserialize)
2109)]
2110pub struct VirtualizedListPersistState {
2111 pub selected: Option<usize>,
2113 pub scroll_offset: usize,
2115 pub follow_mode: bool,
2117}
2118
2119impl crate::stateful::Stateful for VirtualizedListState {
2120 type State = VirtualizedListPersistState;
2121
2122 fn state_key(&self) -> Option<crate::stateful::StateKey> {
2123 self.persistence_id
2125 .as_deref()
2126 .map(|id| crate::stateful::StateKey::new("VirtualizedList", id))
2127 }
2128
2129 fn save_state(&self) -> VirtualizedListPersistState {
2130 VirtualizedListPersistState {
2131 selected: self.selected,
2132 scroll_offset: self.scroll_offset,
2133 follow_mode: self.follow_mode,
2134 }
2135 }
2136
2137 fn restore_state(&mut self, state: VirtualizedListPersistState) {
2138 self.selected = state.selected;
2139 self.scroll_offset = state.scroll_offset;
2140 self.follow_mode = state.follow_mode;
2141 self.scroll_velocity = 0.0;
2143 self.scrollbar_drag_anchor = None;
2144 }
2145}
2146
2147#[derive(Debug)]
2160pub struct VirtualizedList<'a, T> {
2161 items: &'a [T],
2163 style: Style,
2165 highlight_style: Style,
2167 show_scrollbar: bool,
2169 height_mode: ListHeightMode,
2171 hit_id: Option<ftui_render::frame::HitId>,
2173}
2174
2175impl<'a, T> VirtualizedList<'a, T> {
2176 #[must_use]
2178 pub fn new(items: &'a [T]) -> Self {
2179 Self {
2180 items,
2181 style: Style::default(),
2182 highlight_style: Style::default(),
2183 show_scrollbar: true,
2184 height_mode: ListHeightMode::Fixed(1),
2185 hit_id: None,
2186 }
2187 }
2188
2189 #[must_use]
2191 pub fn style(mut self, style: Style) -> Self {
2192 self.style = style;
2193 self
2194 }
2195
2196 #[must_use]
2198 pub fn highlight_style(mut self, style: Style) -> Self {
2199 self.highlight_style = style;
2200 self
2201 }
2202
2203 #[must_use]
2205 pub fn show_scrollbar(mut self, show: bool) -> Self {
2206 self.show_scrollbar = show;
2207 self
2208 }
2209
2210 #[must_use]
2212 pub fn fixed_height(mut self, height: u16) -> Self {
2213 self.height_mode = ListHeightMode::Fixed(height);
2214 self
2215 }
2216
2217 #[must_use]
2220 pub fn variable_heights(mut self) -> Self {
2221 self.height_mode = ListHeightMode::Variable;
2222 self
2223 }
2224
2225 #[must_use]
2227 pub fn height_mode(&self) -> ListHeightMode {
2228 self.height_mode
2229 }
2230
2231 #[must_use]
2233 pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
2234 self.hit_id = Some(id);
2235 self
2236 }
2237}
2238
2239impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
2240 type State = VirtualizedListState;
2241
2242 fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
2243 #[cfg(feature = "tracing")]
2244 let _span = tracing::debug_span!(
2245 "widget_render",
2246 widget = "VirtualizedList",
2247 x = area.x,
2248 y = area.y,
2249 w = area.width,
2250 h = area.height,
2251 items = self.items.len(),
2252 height_mode = ?self.height_mode
2253 )
2254 .entered();
2255
2256 if area.is_empty() {
2257 return;
2258 }
2259
2260 clear_text_area(frame, area, self.style);
2263
2264 let total_items = self.items.len();
2265 if total_items == 0 {
2266 state.visible_count = 0;
2267 state.scroll_offset = 0;
2268 if let Some(heights) = state.heights.as_mut() {
2269 heights.clear();
2270 }
2271 return;
2272 }
2273
2274 let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
2275 self.render_variable(area, frame, state);
2276 return;
2277 };
2278
2279 let fixed_h = fixed_h.max(1);
2281 let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
2283 let fully_visible_items = (area.height / fixed_h) as usize;
2284 let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
2285 let content_width = if needs_scrollbar {
2286 area.width.saturating_sub(1)
2287 } else {
2288 area.width
2289 };
2290
2291 if let Some(selected) = state.selected
2293 && selected >= total_items
2294 {
2295 state.selected = if total_items > 0 {
2297 Some(total_items - 1)
2298 } else {
2299 None
2300 };
2301 }
2302
2303 if let Some(selected) = state.selected {
2305 let vis_count = fully_visible_items.max(1);
2306 if selected >= state.scroll_offset.saturating_add(vis_count) {
2307 state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
2308 } else if selected < state.scroll_offset {
2309 state.scroll_offset = selected;
2310 }
2311 }
2312
2313 let max_offset = if fully_visible_items > 0 {
2315 total_items.saturating_sub(fully_visible_items)
2316 } else {
2317 total_items.saturating_sub(1)
2318 };
2319 state.scroll_offset = state.scroll_offset.min(max_offset);
2320
2321 state.visible_count = fully_visible_items.max(1).min(total_items);
2325
2326 let render_start = state.scroll_offset.saturating_sub(state.overscan);
2328 let render_end = state
2329 .scroll_offset
2330 .saturating_add(items_per_viewport)
2331 .saturating_add(state.overscan)
2332 .min(total_items);
2333
2334 for idx in render_start..render_end {
2336 let relative_idx = if idx >= state.scroll_offset {
2339 i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
2340 } else {
2341 -(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
2343 };
2344
2345 let height_i32 = i32::from(fixed_h);
2346 let y_offset = relative_idx.saturating_mul(height_i32);
2347
2348 if y_offset.saturating_add(height_i32) <= 0 {
2355 continue;
2356 }
2357
2358 if y_offset >= i32::from(area.height) {
2360 break;
2361 }
2362
2363 let skip_rows = if y_offset < 0 {
2366 y_offset.unsigned_abs() as u16
2367 } else {
2368 0
2369 };
2370
2371 let y = i32::from(area.y)
2374 .saturating_add(y_offset)
2375 .clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
2376
2377 if y >= area.bottom() {
2378 break;
2379 }
2380
2381 let visible_height = fixed_h
2382 .saturating_sub(skip_rows)
2383 .min(area.bottom().saturating_sub(y));
2384
2385 if visible_height == 0 {
2386 continue;
2387 }
2388
2389 let row_area = Rect::new(area.x, y, content_width, visible_height);
2390
2391 let is_selected = state.selected == Some(idx);
2392
2393 let row_style = if is_selected {
2394 self.highlight_style.merge(&self.style)
2395 } else {
2396 self.style
2397 };
2398 clear_text_area(frame, row_area, row_style);
2399
2400 self.items[idx].render(row_area, frame, is_selected, skip_rows);
2402 }
2403
2404 if needs_scrollbar {
2406 let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
2407
2408 let mut scrollbar_state =
2409 ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
2410
2411 scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
2413
2414 let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
2415 if let Some(id) = self.hit_id {
2416 scrollbar = scrollbar.hit_id(id);
2417 }
2418 scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
2419 }
2420 }
2421}
2422
2423fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
2427 let mut idx = heights.find_item_at_offset_exact(offset);
2428 if heights.offset_of_item_exact(idx) < offset {
2429 idx += 1;
2430 }
2431 idx.min(heights.len().saturating_sub(1))
2432}
2433
2434fn scrollbar_state_for_rows(
2440 total: u64,
2441 position: u64,
2442 viewport: u16,
2443 capacity: usize,
2444) -> ScrollbarState {
2445 let limit = capacity as u64;
2446 if total <= limit {
2447 return ScrollbarState::new(
2448 total as usize,
2449 position.min(total) as usize,
2450 viewport.into(),
2451 );
2452 }
2453 let scaled_viewport = (u128::from(viewport) * u128::from(limit))
2454 .div_ceil(u128::from(total))
2455 .min(u128::from(limit)) as usize;
2456 let max_position = total.saturating_sub(u64::from(viewport));
2457 let scaled_position = if max_position == 0 {
2458 0
2459 } else {
2460 (u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
2461 / u128::from(max_position)) as usize
2462 };
2463 ScrollbarState::new(capacity, scaled_position, scaled_viewport)
2464}
2465
2466impl<T: RenderItem> VirtualizedList<'_, T> {
2467 fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
2475 let total_items = self.items.len();
2476 let viewport = area.height;
2477 let heights = state
2478 .heights
2479 .get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
2480 if heights.len() != total_items {
2481 heights.resize(total_items);
2482 }
2483 if heights.categories_synced_len != total_items {
2484 heights.set_categories(self.items.iter().map(RenderItem::category));
2485 }
2486
2487 let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
2488 let height = self.items[idx].height().max(1);
2489 if !heights.is_measured(idx) || heights.get(idx) != height {
2490 heights.set_in_category(idx, height, self.items[idx].category());
2491 }
2492 };
2493 let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
2496 let mut rows = 0u16;
2497 let mut idx = start;
2498 while idx < total_items && rows < viewport {
2499 measure(heights, idx);
2500 rows = rows.saturating_add(heights.get(idx));
2501 idx += 1;
2502 }
2503 (idx - start).max(1)
2504 };
2505
2506 if let Some(selected) = state.selected
2508 && selected >= total_items
2509 {
2510 state.selected = Some(total_items - 1);
2511 }
2512 if let Some(selected) = state.selected {
2513 measure(heights, selected);
2514 if selected < state.scroll_offset {
2515 state.scroll_offset = selected;
2516 } else {
2517 measure_screenful(heights, state.scroll_offset);
2518 let mut sel_rows = 0u16;
2519 for idx in (0..=selected).rev() {
2520 if sel_rows >= viewport {
2521 break;
2522 }
2523 measure(heights, idx);
2524 sel_rows = sel_rows.saturating_add(heights.get(idx));
2525 }
2526 heights.refresh_category_predictions();
2527 let top = heights.offset_of_item_exact(state.scroll_offset);
2528 let bottom = heights.offset_of_item_exact(selected + 1);
2529 if bottom.saturating_sub(top) > u64::from(viewport) {
2530 let anchor = bottom.saturating_sub(u64::from(viewport));
2531 state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
2532 }
2533 }
2534 }
2535
2536 let mut tail_rows = 0u16;
2540 for idx in (0..total_items).rev() {
2541 if tail_rows >= viewport {
2542 break;
2543 }
2544 measure(heights, idx);
2545 tail_rows = tail_rows.saturating_add(heights.get(idx));
2546 }
2547 heights.refresh_category_predictions();
2548 let total_height = heights.total_height_exact();
2549 let max_start = if total_height > u64::from(viewport) {
2550 first_item_from_offset(heights, total_height - u64::from(viewport))
2551 } else {
2552 0
2553 };
2554 state.scroll_offset = state.scroll_offset.min(max_start);
2555
2556 let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
2557 heights.refresh_category_predictions();
2558 state.visible_count = visible;
2559
2560 let total_height = heights.total_height_exact();
2561 let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
2562 let content_width = if needs_scrollbar {
2563 area.width.saturating_sub(1)
2564 } else {
2565 area.width
2566 };
2567
2568 let mut y = 0u16;
2569 for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
2570 {
2571 if y >= viewport {
2572 break;
2573 }
2574 let row_h = heights.get(idx).min(viewport - y);
2575 if row_h == 0 {
2576 continue;
2577 }
2578 let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
2579 let is_selected = state.selected == Some(idx);
2580 let row_style = if is_selected {
2581 self.highlight_style.merge(&self.style)
2582 } else {
2583 self.style
2584 };
2585 clear_text_area(frame, row_area, row_style);
2586 self.items[idx].render(row_area, frame, is_selected, 0);
2587 y = y.saturating_add(row_h);
2588 }
2589
2590 if needs_scrollbar {
2591 let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
2592 let mut scrollbar_state = scrollbar_state_for_rows(
2593 total_height,
2594 heights.offset_of_item_exact(state.scroll_offset),
2595 viewport,
2596 usize::MAX,
2597 );
2598 scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
2599 let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
2600 if let Some(id) = self.hit_id {
2601 scrollbar = scrollbar.hit_id(id);
2602 }
2603 scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
2604 }
2605
2606 let widget_id = self.hit_id.map_or_else(
2607 || ftui_a11y::node::A11yNodeInfo::stable_id_for(ftui_a11y::node::A11yRole::List, area),
2608 |id| u64::from(id.id()),
2609 );
2610 let frame_idx = state.render_frame_idx;
2611 state.render_frame_idx = state.render_frame_idx.wrapping_add(1);
2612 if let Some(req) = state.remeasure_tick(frame_idx, widget_id) {
2613 frame.push_remeasure_request(req);
2614 }
2615 }
2616}
2617
2618impl RenderItem for String {
2623 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2624 if area.is_empty() {
2625 return;
2626 }
2627 let max_chars = area.width as usize;
2628 if skip_rows > 0 {
2633 return;
2634 }
2635 for (i, ch) in self.chars().take(max_chars).enumerate() {
2636 frame
2637 .buffer
2638 .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2639 }
2640 }
2641}
2642
2643impl RenderItem for &str {
2644 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2645 if area.is_empty() {
2646 return;
2647 }
2648 if skip_rows > 0 {
2649 return;
2650 }
2651 let max_chars = area.width as usize;
2652 for (i, ch) in self.chars().take(max_chars).enumerate() {
2653 frame
2654 .buffer
2655 .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2656 }
2657 }
2658}
2659
2660#[cfg(test)]
2661mod tests {
2662 use super::*;
2663 use proptest::prelude::*;
2664
2665 fn raw_row_text(frame: &Frame, y: u16) -> String {
2666 let width = frame.buffer.width();
2667 let mut actual = String::new();
2668 for x in 0..width {
2669 let ch = frame
2670 .buffer
2671 .get(x, y)
2672 .and_then(|cell| cell.content.as_char())
2673 .unwrap_or(' ');
2674 actual.push(ch);
2675 }
2676 actual
2677 }
2678
2679 #[test]
2680 fn test_new_virtualized() {
2681 let virt: Virtualized<String> = Virtualized::new(100);
2682 assert_eq!(virt.len(), 0);
2683 assert!(virt.is_empty());
2684 }
2685
2686 #[test]
2687 fn test_push_and_len() {
2688 let mut virt: Virtualized<i32> = Virtualized::new(100);
2689 virt.push(1);
2690 virt.push(2);
2691 virt.push(3);
2692 assert_eq!(virt.len(), 3);
2693 assert!(!virt.is_empty());
2694 }
2695
2696 #[test]
2697 fn test_visible_range_fixed_height() {
2698 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
2699 for i in 0..20 {
2700 virt.push(i);
2701 }
2702 let range = virt.visible_range(20);
2704 assert_eq!(range, 0..10);
2705 }
2706
2707 #[test]
2708 fn test_visible_range_variable_height_clamps() {
2709 let mut cache = HeightCache::new(1, 16);
2710 cache.set(0, 3);
2711 cache.set(1, 3);
2712 cache.set(2, 3);
2713 let mut virt: Virtualized<i32> =
2714 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2715 for i in 0..3 {
2716 virt.push(i);
2717 }
2718 let range = virt.visible_range(5);
2719 assert_eq!(range, 0..2);
2721 }
2722
2723 #[test]
2724 fn test_visible_range_variable_height_exact_fit() {
2725 let mut cache = HeightCache::new(1, 16);
2726 cache.set(0, 2);
2727 cache.set(1, 3);
2728 let mut virt: Virtualized<i32> =
2729 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2730 for i in 0..2 {
2731 virt.push(i);
2732 }
2733 let range = virt.visible_range(5);
2734 assert_eq!(range, 0..2);
2735 }
2736
2737 #[test]
2738 fn test_visible_range_with_scroll() {
2739 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
2740 for i in 0..50 {
2741 virt.push(i);
2742 }
2743 virt.scroll(10);
2744 let range = virt.visible_range(10);
2745 assert_eq!(range, 10..20);
2746 }
2747
2748 #[test]
2749 fn test_visible_range_variable_height_excludes_partial() {
2750 let mut cache = HeightCache::new(1, 16);
2751 cache.set(0, 6);
2752 cache.set(1, 6);
2753 let mut virt: Virtualized<i32> =
2754 Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2755 virt.push(1);
2756 virt.push(2);
2757 virt.push(3);
2758
2759 let range = virt.visible_range(10);
2760 assert_eq!(range, 0..2);
2762 }
2763
2764 #[test]
2765 fn test_visible_range_variable_height_exact_fit_larger() {
2766 let mut cache = HeightCache::new(1, 16);
2767 cache.set(0, 4);
2768 cache.set(1, 6);
2769 let mut virt: Virtualized<i32> =
2770 Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2771 virt.push(1);
2772 virt.push(2);
2773 virt.push(3);
2774
2775 let range = virt.visible_range(10);
2776 assert_eq!(range, 0..2);
2777 }
2778
2779 #[test]
2780 fn test_visible_range_variable_height_default_for_unmeasured() {
2781 let cache = HeightCache::new(2, 16);
2782 let mut virt: Virtualized<i32> =
2783 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2784 for i in 0..3 {
2785 virt.push(i);
2786 }
2787
2788 let range = virt.visible_range(5);
2790 assert_eq!(range, 0..3);
2792 }
2793
2794 #[test]
2795 fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
2796 let mut virt: Virtualized<i32> =
2797 Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2798 for i in 0..20 {
2799 virt.push(i);
2800 }
2801 virt.scroll_to_bottom();
2804 assert_eq!(virt.visible_range(10), 15..20);
2805 }
2806
2807 #[test]
2808 fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
2809 let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
2810 for i in 0..20 {
2811 virt.push(i);
2812 }
2813 virt.scroll_to_bottom();
2816 assert_eq!(virt.visible_range(10), 15..20);
2817 }
2818
2819 #[test]
2820 fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
2821 let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
2824 let mut virt: Virtualized<i32> =
2825 Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
2826 for i in 0..5 {
2827 virt.push(i);
2828 }
2829 virt.scroll_to_bottom();
2830 assert_eq!(virt.visible_range(5), 3..5);
2831 virt.scroll_to_bottom();
2832 assert_eq!(virt.visible_range(6), 2..5);
2833 }
2834
2835 #[test]
2836 fn test_visible_range_variable_near_end_clamps_like_fixed() {
2837 let mut virt: Virtualized<i32> =
2840 Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2841 for i in 0..20 {
2842 virt.push(i);
2843 }
2844 virt.scroll_to(18);
2845 assert_eq!(virt.visible_range(10), 15..20);
2846 }
2847
2848 #[test]
2849 fn test_render_range_with_overscan() {
2850 let mut virt: Virtualized<i32> =
2851 Virtualized::new(100).with_fixed_height(1).with_overscan(2);
2852 for i in 0..50 {
2853 virt.push(i);
2854 }
2855 virt.scroll(10);
2856 let range = virt.render_range(10);
2857 assert_eq!(range, 8..22);
2860 }
2861
2862 #[test]
2863 fn test_scroll_bounds() {
2864 let mut virt: Virtualized<i32> = Virtualized::new(100);
2865 for i in 0..10 {
2866 virt.push(i);
2867 }
2868
2869 virt.scroll(-100);
2871 assert_eq!(virt.scroll_offset(), 0);
2872
2873 virt.scroll(100);
2875 assert_eq!(virt.scroll_offset(), 9);
2876 }
2877
2878 #[test]
2879 fn test_scroll_to() {
2880 let mut virt: Virtualized<i32> = Virtualized::new(100);
2881 for i in 0..20 {
2882 virt.push(i);
2883 }
2884
2885 virt.scroll_to(15);
2886 assert_eq!(virt.scroll_offset(), 15);
2887
2888 virt.scroll_to(100);
2890 assert_eq!(virt.scroll_offset(), 19);
2891 }
2892
2893 #[test]
2894 fn test_follow_mode() {
2895 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
2896 virt.set_visible_count(5);
2897
2898 for i in 0..10 {
2899 virt.push(i);
2900 }
2901
2902 assert!(virt.is_at_bottom());
2904
2905 virt.scroll(-5);
2907 assert!(!virt.follow_mode());
2908 }
2909
2910 #[test]
2911 fn test_scroll_to_start_and_end() {
2912 let mut virt: Virtualized<i32> = Virtualized::new(100);
2913 virt.set_visible_count(5);
2914 for i in 0..20 {
2915 virt.push(i);
2916 }
2917
2918 virt.scroll_to(10);
2920 virt.set_follow(true);
2921 virt.scroll_to_start();
2922 assert_eq!(virt.scroll_offset(), 0);
2923 assert!(!virt.follow_mode());
2924
2925 virt.scroll_to_end();
2927 assert!(virt.is_at_bottom());
2928 assert!(virt.follow_mode());
2929 }
2930
2931 #[test]
2932 fn test_virtualized_page_navigation() {
2933 let mut virt: Virtualized<i32> = Virtualized::new(100);
2934 virt.set_visible_count(5);
2935 for i in 0..30 {
2936 virt.push(i);
2937 }
2938
2939 virt.scroll_to(15);
2940 virt.page_up();
2941 assert_eq!(virt.scroll_offset(), 11);
2943
2944 virt.page_down();
2945 assert_eq!(virt.scroll_offset(), 15);
2946
2947 virt.scroll_to(2);
2949 virt.page_up();
2950 assert_eq!(virt.scroll_offset(), 0);
2951 }
2952
2953 #[test]
2954 fn test_height_cache() {
2955 let mut cache = HeightCache::new(1, 100);
2956
2957 assert_eq!(cache.get(0), 1);
2959 assert_eq!(cache.get(50), 1);
2960
2961 cache.set(5, 3);
2963 assert_eq!(cache.get(5), 3);
2964
2965 assert_eq!(cache.get(4), 1);
2967 assert_eq!(cache.get(6), 1);
2968 }
2969
2970 #[test]
2971 fn test_height_cache_large_index_window() {
2972 let mut cache = HeightCache::new(1, 8);
2973 cache.set(10_000, 4);
2974 assert_eq!(cache.get(10_000), 4);
2975 assert_eq!(cache.get(0), 1);
2976 assert!(cache.cache.len() <= cache.capacity);
2977 }
2978
2979 #[test]
2980 fn test_clear() {
2981 let mut virt: Virtualized<i32> = Virtualized::new(100);
2982 for i in 0..10 {
2983 virt.push(i);
2984 }
2985 virt.scroll(5);
2986
2987 virt.clear();
2988 assert_eq!(virt.len(), 0);
2989 assert_eq!(virt.scroll_offset(), 0);
2990 }
2991
2992 #[test]
2993 fn test_get_item() {
2994 let mut virt: Virtualized<String> = Virtualized::new(100);
2995 virt.push("hello".to_string());
2996 virt.push("world".to_string());
2997
2998 assert_eq!(virt.get(0), Some(&"hello".to_string()));
2999 assert_eq!(virt.get(1), Some(&"world".to_string()));
3000 assert_eq!(virt.get(2), None);
3001 }
3002
3003 #[test]
3004 fn test_external_storage_len() {
3005 let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
3006 assert_eq!(virt.len(), 1000);
3007
3008 virt.set_external_len(2000);
3009 assert_eq!(virt.len(), 2000);
3010 }
3011
3012 #[test]
3013 fn test_momentum_scrolling() {
3014 let mut virt: Virtualized<i32> = Virtualized::new(100);
3015 for i in 0..50 {
3016 virt.push(i);
3017 }
3018
3019 virt.fling(10.0);
3020
3021 virt.tick(Duration::from_millis(100));
3023
3024 assert!(virt.scroll_offset() > 0);
3026 }
3027
3028 #[test]
3033 fn test_virtualized_list_state_new() {
3034 let state = VirtualizedListState::new();
3035 assert_eq!(state.selected, None);
3036 assert_eq!(state.scroll_offset(), 0);
3037 assert_eq!(state.visible_count(), 0);
3038 }
3039
3040 #[test]
3041 fn test_virtualized_list_state_select_next() {
3042 let mut state = VirtualizedListState::new();
3043
3044 state.select_next(10);
3045 assert_eq!(state.selected, Some(0));
3046
3047 state.select_next(10);
3048 assert_eq!(state.selected, Some(1));
3049
3050 state.selected = Some(9);
3052 state.select_next(10);
3053 assert_eq!(state.selected, Some(9));
3054 }
3055
3056 #[test]
3057 fn test_virtualized_list_state_select_previous() {
3058 let mut state = VirtualizedListState::new();
3059 state.selected = Some(5);
3060
3061 state.select_previous(10);
3062 assert_eq!(state.selected, Some(4));
3063
3064 state.selected = Some(0);
3065 state.select_previous(10);
3066 assert_eq!(state.selected, Some(0));
3067 }
3068
3069 #[test]
3070 fn test_virtualized_list_state_scroll() {
3071 let mut state = VirtualizedListState::new();
3072
3073 state.scroll(5, 20);
3074 assert_eq!(state.scroll_offset(), 5);
3075
3076 state.scroll(-3, 20);
3077 assert_eq!(state.scroll_offset(), 2);
3078
3079 state.scroll(-100, 20);
3081 assert_eq!(state.scroll_offset(), 0);
3082
3083 state.scroll(100, 20);
3085 assert_eq!(state.scroll_offset(), 19);
3086 }
3087
3088 #[test]
3089 fn test_virtualized_list_state_follow_mode() {
3090 let mut state = VirtualizedListState::new().with_follow(true);
3091 assert!(state.follow_mode());
3092
3093 state.scroll(5, 20);
3095 assert!(!state.follow_mode());
3096 }
3097
3098 #[test]
3099 fn test_render_item_string() {
3100 let s = String::from("hello");
3102 assert_eq!(s.height(), 1);
3103 }
3104
3105 #[test]
3106 fn test_page_up_down() {
3107 let mut virt: Virtualized<i32> = Virtualized::new(100);
3108 for i in 0..50 {
3109 virt.push(i);
3110 }
3111 virt.set_visible_count(10);
3112
3113 assert_eq!(virt.scroll_offset(), 0);
3115
3116 virt.page_down();
3118 assert_eq!(virt.scroll_offset(), 9);
3119
3120 virt.page_down();
3122 assert_eq!(virt.scroll_offset(), 18);
3123
3124 virt.page_up();
3126 assert_eq!(virt.scroll_offset(), 9);
3127
3128 virt.page_up();
3130 assert_eq!(virt.scroll_offset(), 0);
3131
3132 virt.page_up();
3134 assert_eq!(virt.scroll_offset(), 0);
3135 }
3136
3137 #[test]
3142 fn test_render_scales_with_visible_not_total() {
3143 use ftui_render::grapheme_pool::GraphemePool;
3144 use std::time::Instant;
3145
3146 let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
3148 let small_list = VirtualizedList::new(&small_items);
3149 let mut small_state = VirtualizedListState::new();
3150
3151 let area = Rect::new(0, 0, 80, 24);
3152 let mut pool = GraphemePool::new();
3153 let mut frame = Frame::new(80, 24, &mut pool);
3154
3155 small_list.render(area, &mut frame, &mut small_state);
3157
3158 let start = Instant::now();
3159 for _ in 0..100 {
3160 frame.buffer.clear();
3161 small_list.render(area, &mut frame, &mut small_state);
3162 }
3163 let small_time = start.elapsed();
3164
3165 let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
3167 let large_list = VirtualizedList::new(&large_items);
3168 let mut large_state = VirtualizedListState::new();
3169
3170 large_list.render(area, &mut frame, &mut large_state);
3172
3173 let start = Instant::now();
3174 for _ in 0..100 {
3175 frame.buffer.clear();
3176 large_list.render(area, &mut frame, &mut large_state);
3177 }
3178 let large_time = start.elapsed();
3179
3180 assert!(
3182 large_time < small_time * 3,
3183 "Render does not scale O(visible): 1K={:?}, 100K={:?}",
3184 small_time,
3185 large_time
3186 );
3187 }
3188
3189 #[test]
3190 fn test_scroll_is_constant_time() {
3191 use std::time::Instant;
3192
3193 let mut small: Virtualized<i32> = Virtualized::new(1_000);
3194 for i in 0..1_000 {
3195 small.push(i);
3196 }
3197 small.set_visible_count(24);
3198
3199 let mut large: Virtualized<i32> = Virtualized::new(100_000);
3200 for i in 0..100_000 {
3201 large.push(i);
3202 }
3203 large.set_visible_count(24);
3204
3205 let iterations = 10_000;
3206
3207 for _ in 0..iterations {
3210 small.scroll(1);
3211 small.scroll(-1);
3212 large.scroll(1);
3213 large.scroll(-1);
3214 }
3215
3216 let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
3221 let runs = 5;
3222 let mut best = std::time::Duration::MAX;
3223 for _ in 0..runs {
3224 let start = Instant::now();
3225 for _ in 0..iterations {
3226 v.scroll(1);
3227 v.scroll(-1);
3228 }
3229 best = best.min(start.elapsed());
3230 }
3231 best
3232 };
3233
3234 let small_time = measure(&mut small);
3235 let large_time = measure(&mut large);
3236
3237 let ceiling = small_time
3243 .checked_mul(10)
3244 .unwrap_or(std::time::Duration::MAX);
3245 assert!(
3246 large_time < ceiling,
3247 "Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
3248 small_time,
3249 large_time
3250 );
3251 }
3252
3253 #[test]
3254 fn render_partially_offscreen_top_skips_item() {
3255 use ftui_render::grapheme_pool::GraphemePool;
3256
3257 struct IndexedItem(usize);
3259 impl RenderItem for IndexedItem {
3260 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
3261 let ch = char::from_digit(self.0 as u32, 10).unwrap();
3262 for y in area.y..area.bottom() {
3263 frame.buffer.set(area.x, y, Cell::from_char(ch));
3264 }
3265 }
3266 fn height(&self) -> u16 {
3267 2
3268 }
3269 }
3270
3271 let items = vec![
3274 IndexedItem(0),
3275 IndexedItem(1),
3276 IndexedItem(2),
3277 IndexedItem(3),
3278 ];
3279 let list = VirtualizedList::new(&items).fixed_height(2);
3280
3281 let mut state = VirtualizedListState::new().with_overscan(1);
3283 state.scroll_offset = 1; let mut pool = GraphemePool::new();
3286 let mut frame = Frame::new(10, 5, &mut pool);
3287
3288 list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
3290
3291 let cell = frame.buffer.get(0, 0).unwrap();
3299 assert_eq!(cell.content.as_char(), Some('1'));
3300 }
3301
3302 #[test]
3303 fn render_bottom_boundary_clips_partial_item() {
3304 use ftui_render::grapheme_pool::GraphemePool;
3305
3306 struct IndexedItem(u16);
3307 impl RenderItem for IndexedItem {
3308 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
3309 let ch = char::from_digit(self.0 as u32, 10).unwrap();
3310 for y in area.y..area.bottom() {
3311 frame.buffer.set(area.x, y, Cell::from_char(ch));
3312 }
3313 }
3314 fn height(&self) -> u16 {
3315 2
3316 }
3317 }
3318
3319 let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
3320 let list = VirtualizedList::new(&items)
3321 .fixed_height(2)
3322 .show_scrollbar(false);
3323 let mut state = VirtualizedListState::new();
3324
3325 let mut pool = GraphemePool::new();
3326 let mut frame = Frame::new(4, 4, &mut pool);
3327
3328 list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
3330
3331 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
3332 assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
3333 assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
3334 assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
3336 }
3337
3338 #[test]
3339 fn render_after_fling_advances_visible_rows() {
3340 use ftui_render::grapheme_pool::GraphemePool;
3341
3342 struct IndexedItem(u16);
3343 impl RenderItem for IndexedItem {
3344 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
3345 let ch = char::from_digit(self.0 as u32, 10).unwrap();
3346 for y in area.y..area.bottom() {
3347 frame.buffer.set(area.x, y, Cell::from_char(ch));
3348 }
3349 }
3350 }
3351
3352 let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
3353 let list = VirtualizedList::new(&items)
3354 .fixed_height(1)
3355 .show_scrollbar(false);
3356 let mut state = VirtualizedListState::new();
3357
3358 let mut pool = GraphemePool::new();
3359 let mut frame = Frame::new(4, 3, &mut pool);
3360 let area = Rect::new(0, 0, 4, 3);
3361
3362 list.render(area, &mut frame, &mut state);
3364 assert_eq!(state.scroll_offset(), 0);
3365 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
3366
3367 state.fling(40.0);
3369 state.tick(Duration::from_millis(100), items.len());
3370 assert_eq!(state.scroll_offset(), 4);
3371
3372 frame.buffer.clear();
3373 list.render(area, &mut frame, &mut state);
3374 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
3375 }
3376
3377 #[test]
3378 fn render_empty_virtualized_list_clears_stale_viewport() {
3379 use ftui_render::grapheme_pool::GraphemePool;
3380
3381 let items: Vec<String> = Vec::new();
3382 let list = VirtualizedList::new(&items).show_scrollbar(false);
3383 let mut state = VirtualizedListState::new();
3384 let mut pool = GraphemePool::new();
3385 let mut frame = Frame::new(6, 3, &mut pool);
3386 let area = Rect::new(0, 0, 6, 3);
3387 frame.buffer.fill(area, Cell::from_char('X'));
3388
3389 list.render(area, &mut frame, &mut state);
3390
3391 assert_eq!(raw_row_text(&frame, 0), " ");
3392 assert_eq!(raw_row_text(&frame, 1), " ");
3393 assert_eq!(raw_row_text(&frame, 2), " ");
3394 }
3395
3396 #[test]
3397 fn render_shorter_virtualized_row_clears_stale_suffix() {
3398 use ftui_render::grapheme_pool::GraphemePool;
3399
3400 let long_items = vec!["Hello".to_string()];
3401 let short_items = vec!["Hi".to_string()];
3402 let area = Rect::new(0, 0, 6, 1);
3403 let mut state = VirtualizedListState::new();
3404 let mut pool = GraphemePool::new();
3405 let mut frame = Frame::new(6, 1, &mut pool);
3406
3407 VirtualizedList::new(&long_items)
3408 .show_scrollbar(false)
3409 .render(area, &mut frame, &mut state);
3410 VirtualizedList::new(&short_items)
3411 .show_scrollbar(false)
3412 .render(area, &mut frame, &mut state);
3413
3414 assert_eq!(raw_row_text(&frame, 0), "Hi ");
3415 }
3416
3417 #[test]
3418 fn test_memory_bounded_by_ring_capacity() {
3419 use crate::log_ring::LogRing;
3420
3421 let mut ring: LogRing<String> = LogRing::new(1_000);
3422
3423 for i in 0..100_000 {
3425 ring.push(format!("Line {}", i));
3426 }
3427
3428 assert_eq!(ring.len(), 1_000);
3430 assert_eq!(ring.total_count(), 100_000);
3431 assert_eq!(ring.first_index(), 99_000);
3432
3433 assert!(ring.get(99_999).is_some());
3435 assert!(ring.get(99_000).is_some());
3436 assert!(ring.get(0).is_none());
3438 assert!(ring.get(98_999).is_none());
3439 }
3440
3441 #[test]
3442 fn test_visible_range_constant_regardless_of_total() {
3443 let mut small: Virtualized<i32> = Virtualized::new(100);
3444 for i in 0..100 {
3445 small.push(i);
3446 }
3447 let small_range = small.visible_range(24);
3448
3449 let mut large: Virtualized<i32> = Virtualized::new(100_000);
3450 for i in 0..100_000 {
3451 large.push(i);
3452 }
3453 let large_range = large.visible_range(24);
3454
3455 assert_eq!(small_range.end - small_range.start, 24);
3457 assert_eq!(large_range.end - large_range.start, 24);
3458 }
3459
3460 #[test]
3461 fn test_virtualized_list_state_page_up_down() {
3462 let mut state = VirtualizedListState::new();
3463 state.visible_count = 10;
3464
3465 state.page_down(50);
3467 assert_eq!(state.scroll_offset(), 9);
3468
3469 state.page_down(50);
3471 assert_eq!(state.scroll_offset(), 18);
3472
3473 state.page_up(50);
3475 assert_eq!(state.scroll_offset(), 9);
3476
3477 state.page_up(50);
3479 assert_eq!(state.scroll_offset(), 0);
3480 }
3481
3482 #[test]
3487 fn test_variable_heights_fenwick_new() {
3488 let tracker = VariableHeightsFenwick::new(2, 10);
3489 assert_eq!(tracker.len(), 10);
3490 assert!(!tracker.is_empty());
3491 assert_eq!(tracker.default_height(), 2);
3492 }
3493
3494 #[test]
3495 fn test_variable_heights_fenwick_empty() {
3496 let tracker = VariableHeightsFenwick::new(1, 0);
3497 assert!(tracker.is_empty());
3498 assert_eq!(tracker.total_height(), 0);
3499 }
3500
3501 #[test]
3502 fn test_variable_heights_fenwick_from_heights() {
3503 let heights = vec![3, 2, 5, 1, 4];
3504 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3505
3506 assert_eq!(tracker.len(), 5);
3507 assert_eq!(tracker.get(0), 3);
3508 assert_eq!(tracker.get(1), 2);
3509 assert_eq!(tracker.get(2), 5);
3510 assert_eq!(tracker.get(3), 1);
3511 assert_eq!(tracker.get(4), 4);
3512 assert_eq!(tracker.total_height(), 15);
3513 }
3514
3515 #[test]
3516 fn test_variable_heights_fenwick_offset_of_item() {
3517 let heights = vec![3, 2, 5, 1, 4];
3519 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3520
3521 assert_eq!(tracker.offset_of_item(0), 0);
3522 assert_eq!(tracker.offset_of_item(1), 3);
3523 assert_eq!(tracker.offset_of_item(2), 5);
3524 assert_eq!(tracker.offset_of_item(3), 10);
3525 assert_eq!(tracker.offset_of_item(4), 11);
3526 assert_eq!(tracker.offset_of_item(5), 15); }
3528
3529 #[test]
3530 fn test_variable_heights_fenwick_find_item_at_offset() {
3531 let heights = vec![3, 2, 5, 1, 4];
3533 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3534
3535 assert_eq!(tracker.find_item_at_offset(0), 0);
3537 assert_eq!(tracker.find_item_at_offset(1), 0);
3539 assert_eq!(tracker.find_item_at_offset(3), 1);
3541 assert_eq!(tracker.find_item_at_offset(5), 2);
3543 assert_eq!(tracker.find_item_at_offset(10), 3);
3545 assert_eq!(tracker.find_item_at_offset(11), 4);
3547 assert_eq!(tracker.find_item_at_offset(15), 5);
3549 }
3550
3551 #[test]
3552 fn fenwick_large_height_totals_do_not_wrap() {
3553 let heights = vec![u16::MAX; 131_072];
3554 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3555 let offset = 4_294_836_224_u32;
3556 assert_eq!(
3557 tracker.find_item_at_offset(offset),
3558 (u64::from(offset) / u64::from(u16::MAX)) as usize,
3559 "a wrapped root aggregate must not skip the entire list"
3560 );
3561 assert_eq!(tracker.total_height(), u32::MAX);
3562 assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
3563 }
3564
3565 #[test]
3566 #[should_panic(expected = "height index exceeds usize")]
3567 fn fenwick_rejects_unrepresentable_index() {
3568 VariableHeightsFenwick::default().set(usize::MAX, 1);
3569 }
3570
3571 #[test]
3572 fn fenwick_large_updates_and_resize_match_u64_oracle() {
3573 fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
3574 let mut prefixes = Vec::with_capacity(heights.len() + 1);
3575 prefixes.push(0u64);
3576 for &height in heights {
3577 prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
3578 }
3579 let total = prefixes.last().copied().unwrap();
3580 assert_eq!(tracker.len(), heights.len());
3581 assert_eq!(tracker.total_height_exact(), total);
3582 assert_eq!(
3583 tracker.total_height(),
3584 total.min(u64::from(u32::MAX)) as u32
3585 );
3586 let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
3587 for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
3588 assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
3589 assert_eq!(
3590 tracker.offset_of_item(idx),
3591 prefixes[idx].min(u64::from(u32::MAX)) as u32
3592 );
3593 queries.extend([
3594 prefixes[idx].saturating_sub(1),
3595 prefixes[idx],
3596 prefixes[idx] + 1,
3597 ]);
3598 }
3599 for offset in queries {
3600 let expected = if offset == 0 {
3601 0
3602 } else {
3603 prefixes[1..].partition_point(|&prefix| prefix <= offset)
3604 };
3605 assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
3606 if let Ok(offset) = u32::try_from(offset) {
3607 assert_eq!(tracker.find_item_at_offset(offset), expected);
3608 }
3609 }
3610 }
3611
3612 for len in [65_536, 65_537, 65_538, 131_072] {
3615 let mut heights = vec![u16::MAX; len];
3616 let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
3617 check(&tracker, &heights);
3618 for idx in [0, 1, 32_768, 65_535, len - 1] {
3619 tracker.set(idx, 0);
3620 heights[idx] = 0;
3621 assert_eq!(tracker.get(idx), 0);
3622 }
3623 check(&tracker, &heights);
3624 tracker.set(0, u16::MAX);
3625 heights[0] = u16::MAX;
3626 tracker.resize(65_536);
3627 heights.truncate(65_536);
3628 check(&tracker, &heights);
3629 tracker.resize(65_540);
3630 heights.resize(65_540, u16::MAX);
3631 check(&tracker, &heights);
3632 }
3633
3634 let mut seed = 0xa076_1d64_78bd_642fu64;
3637 let mut heights: Vec<u16> = (0..131_072)
3638 .map(|_| {
3639 seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
3640 32_768 + ((seed >> 48) as u16 / 2)
3641 })
3642 .collect();
3643 let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3644 for idx in (0..heights.len()).step_by(997) {
3645 heights[idx] = (idx % 65_536) as u16;
3646 tracker.set(idx, heights[idx]);
3647 assert_eq!(tracker.get(idx), heights[idx]);
3648 }
3649 check(&tracker, &heights);
3650 tracker.drop_front(3);
3651 check(&tracker, &heights[3..]);
3652 heights.fill(u16::MAX);
3653 tracker.rebuild(&heights);
3654 check(&tracker, &heights);
3655 tracker.clear();
3656 check(&tracker, &[]);
3657 tracker.resize(4);
3658 check(&tracker, &[1; 4]);
3659 }
3660
3661 #[test]
3662 fn fenwick_large_visible_range_keeps_tail_reachable() {
3663 let len = 65_548;
3664 let mut virt: Virtualized<()> =
3665 Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
3666 for idx in 65_538..len {
3667 virt.observe_height(idx, 1);
3668 }
3669 virt.scroll_to_bottom();
3670 assert_eq!(virt.visible_range(5), len - 5..len);
3671 virt.scroll_to(len - 8);
3672 assert_eq!(virt.visible_range(5), len - 8..len - 3);
3673 }
3674
3675 #[test]
3676 fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
3677 fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
3678 let scrollbar =
3679 Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
3680 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
3681 let mut frame = Frame::new(1, 21, &mut pool);
3682 scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
3683 (0..21)
3684 .filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
3685 .collect()
3686 }
3687
3688 let capacity = u32::MAX as usize;
3691 let total = 131_072 * u64::from(u16::MAX);
3692 let viewport = 20;
3693 let max_position = total - u64::from(viewport);
3694 for (position, expected_row) in [
3695 (0, 0),
3696 (max_position / 4, 5),
3697 (max_position / 2, 10),
3698 (max_position / 4 * 3, 15),
3699 (max_position, 20),
3700 (total, 20),
3701 ] {
3702 let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3703 assert_eq!(scaled.content_length, capacity);
3704 assert!(scaled.viewport_length > 0);
3705 assert_eq!(thumb_rows(scaled), vec![expected_row]);
3706 }
3707
3708 let position = u64::from(u32::MAX) + u64::from(u16::MAX);
3709 let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3710 assert_eq!(thumb_rows(scaled), vec![10]);
3711 let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
3713 assert_eq!(thumb_rows(saturated), vec![20]);
3714
3715 for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
3716 let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
3717 assert_eq!(exact.content_length, total as usize);
3718 assert_eq!(exact.position, position as usize);
3719 assert_eq!(exact.viewport_length, usize::from(viewport));
3720 }
3721 if usize::BITS > 32 {
3722 let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
3723 assert_eq!(exact.content_length as u64, total);
3724 assert_eq!(exact.position as u64, position);
3725 assert_eq!(exact.viewport_length, usize::from(viewport));
3726 }
3727 }
3728
3729 #[test]
3730 fn test_variable_heights_fenwick_visible_count() {
3731 let heights = vec![3, 2, 5, 1, 4];
3733 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3734
3735 assert_eq!(tracker.visible_count(0, 5), 2);
3737
3738 assert_eq!(tracker.visible_count(0, 4), 2);
3740
3741 assert_eq!(tracker.visible_count(0, 10), 3);
3743
3744 assert_eq!(tracker.visible_count(2, 6), 2);
3746 }
3747
3748 #[test]
3749 fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
3750 let heights = vec![1, 1, 1];
3751 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3752
3753 assert_eq!(tracker.visible_count(0, 10), 3);
3755 assert_eq!(tracker.visible_count(1, 10), 2);
3756 assert_eq!(tracker.visible_count(2, 10), 1);
3757 }
3758
3759 #[test]
3760 fn test_variable_heights_fenwick_set() {
3761 let mut tracker = VariableHeightsFenwick::new(1, 5);
3762
3763 assert_eq!(tracker.get(0), 1);
3765 assert_eq!(tracker.total_height(), 5);
3766
3767 tracker.set(2, 10);
3769 assert_eq!(tracker.get(2), 10);
3770 assert_eq!(tracker.total_height(), 14); }
3772
3773 #[test]
3774 fn test_variable_heights_fenwick_resize() {
3775 let mut tracker = VariableHeightsFenwick::new(2, 3);
3776 assert_eq!(tracker.len(), 3);
3777 assert_eq!(tracker.total_height(), 6);
3778
3779 tracker.resize(5);
3781 assert_eq!(tracker.len(), 5);
3782 assert_eq!(tracker.total_height(), 10);
3783 assert_eq!(tracker.get(4), 2);
3784
3785 tracker.resize(2);
3787 assert_eq!(tracker.len(), 2);
3788 assert_eq!(tracker.total_height(), 4);
3789 }
3790
3791 #[test]
3792 fn test_variable_heights_fenwick_point_update_and_range_query() {
3793 fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
3794 tracker
3795 .offset_of_item(right.saturating_add(1))
3796 .saturating_sub(tracker.offset_of_item(left))
3797 }
3798
3799 let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
3800 let mut naive = [2_u32, 4, 1, 3, 5, 2];
3801
3802 tracker.set(2, 7);
3803 naive[2] = 7;
3804 tracker.set(5, 1);
3805 naive[5] = 1;
3806 tracker.set(0, 6);
3807 naive[0] = 6;
3808
3809 let mut running = 0u32;
3810 for (i, value) in naive.iter().enumerate() {
3811 running = running.saturating_add(*value);
3812 assert_eq!(tracker.offset_of_item(i + 1), running);
3813 }
3814
3815 let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
3816 assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
3817 assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
3818 assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
3819 }
3820
3821 proptest! {
3822 #![proptest_config(ProptestConfig::with_cases(96))]
3823
3824 #[test]
3825 fn property_measured_heights_survive_mutations(
3826 operations in proptest::collection::vec((0u8..3, 0usize..150, 1u16..32), 1..80)
3827 ) {
3828 let mut tracker = VariableHeightsFenwick::new(2, 0);
3829 let mut expected: Vec<Option<u16>> = Vec::new();
3830 for (operation, index, height) in operations {
3831 match operation {
3832 0 => {
3833 if index >= expected.len() {
3834 expected.resize(index + 1, None);
3835 }
3836 expected[index] = Some(height);
3837 tracker.set(index, height);
3838 }
3839 1 => {
3840 expected.resize(index, None);
3841 tracker.resize(index);
3842 }
3843 _ => {
3844 expected.drain(..index.min(expected.len()));
3845 tracker.drop_front(index);
3846 }
3847 }
3848 prop_assert_eq!(tracker.len(), expected.len());
3849 prop_assert_eq!(
3850 tracker.unmeasured_count(),
3851 expected.iter().filter(|height| height.is_none()).count()
3852 );
3853 let mut prefix = 0;
3854 for (index, height) in expected.iter().enumerate() {
3855 prop_assert_eq!(tracker.offset_of_item(index), prefix);
3856 prop_assert_eq!(tracker.is_measured(index), height.is_some());
3857 prop_assert_eq!(tracker.get(index), height.unwrap_or(2));
3858 prefix += u32::from(height.unwrap_or(2));
3859 }
3860 prop_assert_eq!(tracker.total_height(), prefix);
3861 }
3862 }
3863
3864 #[test]
3865 fn property_variable_heights_fenwick_prefix_sums_match_naive(
3866 heights in proptest::collection::vec(1u16..=32u16, 1..160)
3867 ) {
3868 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3869
3870 let mut naive_prefix = 0u32;
3871 prop_assert_eq!(tracker.offset_of_item(0), 0);
3872 for (i, height) in heights.iter().enumerate() {
3873 naive_prefix = naive_prefix.saturating_add(u32::from(*height));
3874 prop_assert_eq!(
3875 tracker.offset_of_item(i + 1),
3876 naive_prefix,
3877 "prefix mismatch at index {} for heights {:?}",
3878 i,
3879 heights
3880 );
3881 }
3882 }
3883
3884 #[test]
3885 fn property_variable_heights_fenwick_visible_count_matches_naive(
3886 heights in proptest::collection::vec(1u16..=24u16, 1..128),
3887 start_idx in 0usize..192usize,
3888 viewport_height in 1u16..=120u16
3889 ) {
3890 fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
3891 if heights.is_empty() || viewport_height == 0 {
3892 return 0;
3893 }
3894 let start = start_idx.min(heights.len());
3895 if start >= heights.len() {
3896 return 0;
3897 }
3898
3899 let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
3900 let end_offset = start_offset.saturating_add(u32::from(viewport_height));
3901 let mut count = 0usize;
3902 let mut cursor = start_offset;
3903 for &height in &heights[start..] {
3904 if cursor >= end_offset {
3905 break;
3906 }
3907 count = count.saturating_add(1);
3908 cursor = cursor.saturating_add(u32::from(height));
3909 }
3910
3911 if count == 0 { 1 } else { count }
3912 }
3913
3914 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3915 let expected = naive_visible_count(&heights, start_idx, viewport_height);
3916 let actual = tracker.visible_count(start_idx, viewport_height);
3917 prop_assert_eq!(
3918 actual,
3919 expected,
3920 "visible_count mismatch for start={} viewport={} heights={:?}",
3921 start_idx,
3922 viewport_height,
3923 heights
3924 );
3925 }
3926 }
3927
3928 #[test]
3932 fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
3933 let config = PredictorConfig {
3934 default_height: 1,
3935 prior_mean: 1.0,
3936 prior_strength: 2.0,
3937 ..PredictorConfig::default()
3938 };
3939 let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
3940 assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
3941 assert_eq!(tracker.unmeasured_count(), 10);
3942 assert_eq!(tracker.total_height(), 10);
3943
3944 for idx in 0..3 {
3946 tracker.set(idx, 3);
3947 }
3948 assert_eq!(tracker.predicted_height(), 2);
3949 assert_eq!(tracker.unmeasured_count(), 7);
3950 assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
3951 assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
3952 assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
3953 assert_eq!(tracker.offset_of_item(4), 9 + 2);
3954
3955 for idx in 3..6 {
3957 tracker.set(idx, 3);
3958 }
3959 assert_eq!(tracker.predicted_height(), 3);
3960 assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
3961 assert!(tracker.is_measured(5) && !tracker.is_measured(6));
3962 assert_eq!(
3963 tracker.predictor().map(HeightPredictor::total_measurements),
3964 Some(6)
3965 );
3966
3967 tracker.resize(12);
3969 assert_eq!(tracker.get(11), 3);
3970 assert_eq!(tracker.unmeasured_count(), 6);
3971 assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
3972
3973 tracker.resize(4);
3975 assert_eq!(tracker.unmeasured_count(), 0);
3976 tracker.resize(6);
3977 assert_eq!(tracker.unmeasured_count(), 2);
3978 assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
3979
3980 tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
3982 assert_eq!(tracker.unmeasured_count(), 0);
3983 assert_eq!(tracker.total_height(), 40);
3984 assert!(
3985 tracker.predicted_height() >= 4,
3986 "posterior pulled toward the taller rows"
3987 );
3988
3989 let mut plain = VariableHeightsFenwick::new(2, 4);
3991 plain.set(0, 9);
3992 assert_eq!(plain.predicted_height(), 2);
3993 assert_eq!(plain.get(3), 2);
3994 assert_eq!(plain.unmeasured_count(), 3);
3995 assert!(plain.predictor().is_none());
3996 }
3997
3998 #[test]
4001 fn virtualized_height_prediction_observe_height_trains_the_model() {
4002 let mut virt: Virtualized<i32> = Virtualized::new(100)
4003 .with_fixed_height(1)
4004 .with_height_prediction(PredictorConfig::default());
4005 assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
4006 assert_eq!(virt.unmeasured_item_height(), 1);
4007
4008 for idx in 0..4 {
4010 virt.observe_height(idx, 4);
4011 }
4012 assert_eq!(virt.unmeasured_item_height(), 3);
4013 let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
4014 panic!("expected the Fenwick tracker");
4015 };
4016 assert_eq!(tracker.get(0), 4);
4017 assert_eq!(tracker.len(), 4);
4018 assert_eq!(
4019 tracker.get(40),
4020 3,
4021 "beyond the tracked length: the prediction"
4022 );
4023
4024 let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
4025 fixed.observe_height(0, 9);
4026 assert_eq!(
4027 fixed.unmeasured_item_height(),
4028 2,
4029 "fixed heights ignore observations"
4030 );
4031
4032 let mut linear: Virtualized<i32> =
4033 Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
4034 linear.observe_height(1, 5);
4035 assert_eq!(linear.unmeasured_item_height(), 2);
4036 let ItemHeight::Variable(cache) = linear.item_height() else {
4037 panic!("expected the linear cache");
4038 };
4039 assert_eq!(cache.get(1), 5);
4040 }
4041
4042 #[test]
4043 fn test_virtualized_with_variable_heights_fenwick() {
4044 let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
4045
4046 for i in 0..10 {
4047 virt.push(i);
4048 }
4049
4050 let range = virt.visible_range(6);
4052 assert_eq!(range.end - range.start, 3);
4053 }
4054
4055 proptest! {
4056 #[test]
4062 fn variable_height_implementations_agree(
4063 heights in proptest::collection::vec(1u16..=5, 1..40),
4064 viewport in 1u16..=20,
4065 default_height in 1u16..=4,
4066 offset_seed in 0usize..64,
4067 ) {
4068 let len = heights.len();
4069 let mut cache: Virtualized<usize> = Virtualized::new(len)
4074 .with_item_height(ItemHeight::Variable(HeightCache::new(default_height, len)));
4075 let mut fenwick: Virtualized<usize> =
4076 Virtualized::new(len).with_variable_heights_fenwick(default_height, len);
4077 for i in 0..len {
4078 cache.push(i);
4079 fenwick.push(i);
4080 }
4081 for (idx, height) in heights.iter().enumerate() {
4082 cache.observe_height(idx, *height);
4083 fenwick.observe_height(idx, *height);
4084 }
4085
4086 let offset = offset_seed % len;
4087 cache.scroll_to(offset);
4088 fenwick.scroll_to(offset);
4089 prop_assert_eq!(
4090 cache.visible_range(viewport),
4091 fenwick.visible_range(viewport),
4092 "implementations disagree at len={} viewport={} offset={}",
4093 len,
4094 viewport,
4095 offset
4096 );
4097
4098 cache.scroll_to_bottom();
4100 fenwick.scroll_to_bottom();
4101 let bottom_cache = cache.visible_range(viewport);
4102 let bottom_fenwick = fenwick.visible_range(viewport);
4103 prop_assert_eq!(&bottom_cache, &bottom_fenwick, "bottom anchoring disagrees");
4104 prop_assert!(
4105 bottom_cache.contains(&(len - 1)),
4106 "last item unreachable: range {:?} of {} items",
4107 bottom_cache,
4108 len
4109 );
4110
4111 let keep = 1 + offset_seed % len;
4115 if keep < len {
4116 prop_assert_eq!(cache.trim_front(keep), fenwick.trim_front(keep));
4117 let len = cache.len();
4118 cache.scroll_to_bottom();
4119 fenwick.scroll_to_bottom();
4120 let trimmed_cache = cache.visible_range(viewport);
4121 let trimmed_fenwick = fenwick.visible_range(viewport);
4122 prop_assert_eq!(
4123 &trimmed_cache,
4124 &trimmed_fenwick,
4125 "implementations disagree after trimming to {} items",
4126 keep
4127 );
4128 prop_assert!(
4129 trimmed_cache.contains(&(len - 1)),
4130 "last item unreachable after a trim: range {:?} of {} items",
4131 trimmed_cache,
4132 len
4133 );
4134 }
4135 }
4136 }
4137
4138 #[test]
4139 fn test_variable_heights_fenwick_performance() {
4140 use std::time::Instant;
4141
4142 let n = 100_000;
4144 let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
4145 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
4146
4147 let _ = tracker.find_item_at_offset(500_000);
4149 let _ = tracker.offset_of_item(50_000);
4150
4151 let start = Instant::now();
4153 let mut _sink = 0usize;
4154 for i in 0..10_000 {
4155 _sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
4156 }
4157 let find_time = start.elapsed();
4158
4159 let start = Instant::now();
4161 let mut _sink2 = 0u32;
4162 for i in 0..10_000 {
4163 _sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
4164 }
4165 let offset_time = start.elapsed();
4166
4167 eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
4168 eprintln!("10k find_item_at_offset: {:?}", find_time);
4169 eprintln!("10k offset_of_item: {:?}", offset_time);
4170
4171 assert!(
4173 find_time < std::time::Duration::from_millis(50),
4174 "find_item_at_offset too slow: {:?}",
4175 find_time
4176 );
4177 assert!(
4178 offset_time < std::time::Duration::from_millis(50),
4179 "offset_of_item too slow: {:?}",
4180 offset_time
4181 );
4182 }
4183
4184 #[test]
4185 fn test_variable_heights_fenwick_scales_logarithmically() {
4186 use std::time::Instant;
4187
4188 let small_n = 1_000;
4190 let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
4191 let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
4192
4193 let large_n = 100_000;
4195 let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
4196 let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
4197
4198 let iterations = 5_000;
4199
4200 let start = Instant::now();
4202 for i in 0..iterations {
4203 let _ = small_tracker.find_item_at_offset((i * 2) as u32);
4204 }
4205 let small_time = start.elapsed();
4206
4207 let start = Instant::now();
4209 for i in 0..iterations {
4210 let _ = large_tracker.find_item_at_offset((i * 200) as u32);
4211 }
4212 let large_time = start.elapsed();
4213
4214 assert!(
4217 large_time < small_time * 10,
4218 "Not O(log n): small={:?}, large={:?}",
4219 small_time,
4220 large_time
4221 );
4222 }
4223
4224 #[test]
4231 fn new_zero_capacity() {
4232 let virt: Virtualized<i32> = Virtualized::new(0);
4233 assert_eq!(virt.len(), 0);
4234 assert!(virt.is_empty());
4235 assert_eq!(virt.scroll_offset(), 0);
4236 assert_eq!(virt.visible_count(), 0);
4237 assert!(!virt.follow_mode());
4238 }
4239
4240 #[test]
4241 fn external_zero_len_zero_cache() {
4242 let virt: Virtualized<i32> = Virtualized::external(0, 0);
4243 assert_eq!(virt.len(), 0);
4244 assert!(virt.is_empty());
4245 }
4246
4247 #[test]
4248 fn external_storage_returns_none_for_get() {
4249 let virt: Virtualized<i32> = Virtualized::external(100, 10);
4250 assert_eq!(virt.get(0), None);
4251 assert_eq!(virt.get(50), None);
4252 }
4253
4254 #[test]
4255 fn external_storage_returns_none_for_get_mut() {
4256 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4257 assert!(virt.get_mut(0).is_none());
4258 }
4259
4260 #[test]
4261 fn push_on_external_is_noop() {
4262 let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
4263 virt.push(42);
4264 assert_eq!(virt.len(), 5);
4266 }
4267
4268 #[test]
4269 fn iter_on_external_is_empty() {
4270 let virt: Virtualized<i32> = Virtualized::external(100, 10);
4271 assert_eq!(virt.iter().count(), 0);
4272 }
4273
4274 #[test]
4275 fn set_external_len_on_owned_is_noop() {
4276 let mut virt: Virtualized<i32> = Virtualized::new(100);
4277 virt.push(1);
4278 virt.set_external_len(999);
4279 assert_eq!(virt.len(), 1); }
4281
4282 #[test]
4285 fn visible_range_zero_viewport() {
4286 let mut virt: Virtualized<i32> = Virtualized::new(100);
4287 virt.push(1);
4288 let range = virt.visible_range(0);
4289 assert_eq!(range, 0..0);
4290 assert_eq!(virt.visible_count(), 0);
4291 }
4292
4293 #[test]
4294 fn visible_range_empty_container() {
4295 let virt: Virtualized<i32> = Virtualized::new(100);
4296 let range = virt.visible_range(24);
4297 assert_eq!(range, 0..0);
4298 }
4299
4300 #[test]
4301 fn visible_range_fixed_height_zero() {
4302 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
4304 for i in 0..10 {
4305 virt.push(i);
4306 }
4307 let range = virt.visible_range(5);
4308 assert_eq!(range, 0..5);
4310 }
4311
4312 #[test]
4313 fn visible_range_fewer_items_than_viewport() {
4314 let mut virt: Virtualized<i32> = Virtualized::new(100);
4315 for i in 0..3 {
4316 virt.push(i);
4317 }
4318 let range = virt.visible_range(24);
4319 assert_eq!(range, 0..3);
4321 }
4322
4323 #[test]
4324 fn visible_range_single_item() {
4325 let mut virt: Virtualized<i32> = Virtualized::new(100);
4326 virt.push(42);
4327 let range = virt.visible_range(1);
4328 assert_eq!(range, 0..1);
4329 }
4330
4331 #[test]
4334 fn render_range_at_start_clamps_overscan() {
4335 let mut virt: Virtualized<i32> =
4336 Virtualized::new(100).with_fixed_height(1).with_overscan(5);
4337 for i in 0..20 {
4338 virt.push(i);
4339 }
4340 let range = virt.render_range(10);
4342 assert_eq!(range.start, 0);
4343 }
4344
4345 #[test]
4346 fn render_range_at_end_clamps_overscan() {
4347 let mut virt: Virtualized<i32> =
4348 Virtualized::new(100).with_fixed_height(1).with_overscan(5);
4349 for i in 0..20 {
4350 virt.push(i);
4351 }
4352 virt.set_visible_count(10);
4353 virt.scroll_to(10); let range = virt.render_range(10);
4355 assert_eq!(range.end, 20);
4357 }
4358
4359 #[test]
4360 fn render_range_zero_overscan() {
4361 let mut virt: Virtualized<i32> =
4362 Virtualized::new(100).with_fixed_height(1).with_overscan(0);
4363 for i in 0..20 {
4364 virt.push(i);
4365 }
4366 virt.set_visible_count(10);
4367 virt.scroll_to(5);
4368 let range = virt.render_range(10);
4369 let visible = virt.visible_range(10);
4371 assert_eq!(range, visible);
4372 }
4373
4374 #[test]
4377 fn scroll_on_empty_is_noop() {
4378 let mut virt: Virtualized<i32> = Virtualized::new(100);
4379 virt.scroll(10);
4380 assert_eq!(virt.scroll_offset(), 0);
4381 }
4382
4383 #[test]
4384 fn scroll_delta_zero_does_not_disable_follow() {
4385 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4386 virt.push(1);
4387 virt.scroll(0);
4388 assert!(virt.follow_mode());
4390 }
4391
4392 #[test]
4393 fn scroll_negative_beyond_start() {
4394 let mut virt: Virtualized<i32> = Virtualized::new(100);
4395 for i in 0..10 {
4396 virt.push(i);
4397 }
4398 virt.scroll(-1);
4399 assert_eq!(virt.scroll_offset(), 0);
4400 }
4401
4402 #[test]
4403 fn scroll_to_on_empty() {
4404 let mut virt: Virtualized<i32> = Virtualized::new(100);
4405 virt.scroll_to(100);
4407 assert_eq!(virt.scroll_offset(), 0);
4408 }
4409
4410 #[test]
4411 fn scroll_to_top_already_at_top() {
4412 let mut virt: Virtualized<i32> = Virtualized::new(100);
4413 virt.push(1);
4414 virt.scroll_to_top();
4415 assert_eq!(virt.scroll_offset(), 0);
4416 }
4417
4418 #[test]
4419 fn scroll_to_bottom_fewer_items_than_visible() {
4420 let mut virt: Virtualized<i32> = Virtualized::new(100);
4421 virt.set_visible_count(10);
4422 for i in 0..3 {
4423 virt.push(i);
4424 }
4425 virt.scroll_to_bottom();
4426 assert_eq!(virt.scroll_offset(), 0);
4428 }
4429
4430 #[test]
4431 fn scroll_to_bottom_visible_count_zero() {
4432 let mut virt: Virtualized<i32> = Virtualized::new(100);
4433 for i in 0..20 {
4434 virt.push(i);
4435 }
4436 virt.scroll_to_bottom();
4438 assert_eq!(virt.scroll_offset, usize::MAX);
4440 assert_eq!(virt.scroll_offset(), 19);
4442 }
4443
4444 #[test]
4447 fn page_up_visible_count_zero_is_noop() {
4448 let mut virt: Virtualized<i32> = Virtualized::new(100);
4449 for i in 0..20 {
4450 virt.push(i);
4451 }
4452 virt.scroll_to(10);
4453 virt.page_up();
4455 assert_eq!(virt.scroll_offset(), 10);
4456 }
4457
4458 #[test]
4459 fn page_down_visible_count_zero_is_noop() {
4460 let mut virt: Virtualized<i32> = Virtualized::new(100);
4461 for i in 0..20 {
4462 virt.push(i);
4463 }
4464 virt.page_down();
4466 assert_eq!(virt.scroll_offset(), 0);
4467 }
4468
4469 #[test]
4472 fn is_at_bottom_fewer_items_than_visible() {
4473 let mut virt: Virtualized<i32> = Virtualized::new(100);
4474 virt.set_visible_count(10);
4475 for i in 0..3 {
4476 virt.push(i);
4477 }
4478 assert!(virt.is_at_bottom());
4479 }
4480
4481 #[test]
4482 fn is_at_bottom_empty() {
4483 let virt: Virtualized<i32> = Virtualized::new(100);
4484 assert!(virt.is_at_bottom());
4486 }
4487
4488 #[test]
4491 fn trim_front_under_max_returns_zero() {
4492 let mut virt: Virtualized<i32> = Virtualized::new(100);
4493 for i in 0..5 {
4494 virt.push(i);
4495 }
4496 let removed = virt.trim_front(10);
4497 assert_eq!(removed, 0);
4498 assert_eq!(virt.len(), 5);
4499 }
4500
4501 #[test]
4502 fn trim_front_adjusts_scroll_offset() {
4503 let mut virt: Virtualized<i32> = Virtualized::new(100);
4504 for i in 0..20 {
4505 virt.push(i);
4506 }
4507 virt.scroll_to(10);
4508 let removed = virt.trim_front(15);
4509 assert_eq!(removed, 5);
4510 assert_eq!(virt.len(), 15);
4511 assert_eq!(virt.scroll_offset(), 5);
4513 }
4514
4515 #[test]
4516 fn trim_front_scroll_offset_saturates_to_zero() {
4517 let mut virt: Virtualized<i32> = Virtualized::new(100);
4518 for i in 0..20 {
4519 virt.push(i);
4520 }
4521 virt.scroll_to(2);
4522 let removed = virt.trim_front(10);
4523 assert_eq!(removed, 10);
4524 assert_eq!(virt.scroll_offset(), 0);
4526 }
4527
4528 #[test]
4529 fn trim_front_on_external_returns_zero() {
4530 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4531 let removed = virt.trim_front(5);
4532 assert_eq!(removed, 0);
4533 }
4534
4535 #[test]
4536 fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
4537 let mut virt: Virtualized<i32> = Virtualized::new(100);
4538 for i in 0..20 {
4539 virt.push(i);
4540 }
4541
4542 virt.scroll_to_bottom();
4545 assert_eq!(virt.scroll_offset, usize::MAX);
4546
4547 let range = virt.visible_range(10);
4550 assert_eq!(range, 10..20);
4551 assert_eq!(virt.visible_count(), 10);
4552 }
4553
4554 #[test]
4557 fn clear_on_external_resets_scroll() {
4558 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4559 virt.scroll_to(50);
4560 virt.clear();
4561 assert_eq!(virt.scroll_offset(), 0);
4562 assert_eq!(virt.len(), 100);
4564 }
4565
4566 #[test]
4569 fn tick_zero_velocity_is_noop() {
4570 let mut virt: Virtualized<i32> = Virtualized::new(100);
4571 for i in 0..20 {
4572 virt.push(i);
4573 }
4574 virt.tick(Duration::from_millis(100));
4575 assert_eq!(virt.scroll_offset(), 0);
4576 }
4577
4578 #[test]
4579 fn tick_below_threshold_stops_momentum() {
4580 let mut virt: Virtualized<i32> = Virtualized::new(100);
4581 for i in 0..20 {
4582 virt.push(i);
4583 }
4584 virt.fling(0.05); virt.tick(Duration::from_millis(100));
4586 assert_eq!(virt.scroll_offset(), 0);
4588 }
4589
4590 #[test]
4591 fn tick_zero_duration_no_scroll() {
4592 let mut virt: Virtualized<i32> = Virtualized::new(100);
4593 for i in 0..50 {
4594 virt.push(i);
4595 }
4596 virt.fling(100.0);
4597 virt.tick(Duration::ZERO);
4598 assert_eq!(virt.scroll_offset(), 0);
4600 }
4601
4602 #[test]
4603 fn fling_negative_scrolls_up() {
4604 let mut virt: Virtualized<i32> = Virtualized::new(100);
4605 for i in 0..50 {
4606 virt.push(i);
4607 }
4608 virt.scroll(20);
4609 let before = virt.scroll_offset();
4610 virt.fling(-50.0);
4611 virt.tick(Duration::from_millis(100));
4612 assert!(virt.scroll_offset() < before);
4613 }
4614
4615 #[test]
4618 fn follow_mode_auto_scrolls_on_push() {
4619 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4620 virt.set_visible_count(5);
4621 for i in 0..20 {
4622 virt.push(i);
4623 }
4624 assert!(virt.is_at_bottom());
4626 assert_eq!(virt.scroll_offset(), 15); }
4628
4629 #[test]
4630 fn set_follow_false_does_not_scroll() {
4631 let mut virt: Virtualized<i32> = Virtualized::new(100);
4632 virt.set_visible_count(5);
4633 for i in 0..20 {
4634 virt.push(i);
4635 }
4636 virt.scroll_to(5);
4637 virt.set_follow(false);
4638 assert_eq!(virt.scroll_offset(), 5); }
4640
4641 #[test]
4642 fn scroll_to_start_disables_follow() {
4643 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4644 virt.set_visible_count(5);
4645 for i in 0..20 {
4646 virt.push(i);
4647 }
4648 virt.scroll_to_start();
4649 assert!(!virt.follow_mode());
4650 assert_eq!(virt.scroll_offset(), 0);
4651 }
4652
4653 #[test]
4654 fn scroll_to_end_enables_follow() {
4655 let mut virt: Virtualized<i32> = Virtualized::new(100);
4656 virt.set_visible_count(5);
4657 for i in 0..20 {
4658 virt.push(i);
4659 }
4660 assert!(!virt.follow_mode());
4661 virt.scroll_to_end();
4662 assert!(virt.follow_mode());
4663 assert!(virt.is_at_bottom());
4664 }
4665
4666 #[test]
4667 fn external_follow_mode_scrolls_on_set_external_len() {
4668 let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
4669 virt.set_visible_count(5);
4670 virt.set_external_len(20);
4671 assert_eq!(virt.len(), 20);
4672 assert!(virt.is_at_bottom());
4673 }
4674
4675 #[test]
4678 fn builder_chain_all_options() {
4679 let virt: Virtualized<i32> = Virtualized::new(100)
4680 .with_fixed_height(3)
4681 .with_overscan(5)
4682 .with_follow(true);
4683 assert!(virt.follow_mode());
4684 let range = virt.visible_range(9);
4687 assert_eq!(range, 0..0);
4688 }
4689
4690 #[test]
4693 fn height_cache_default() {
4694 let cache = HeightCache::default();
4695 assert_eq!(cache.get(0), 1); assert_eq!(cache.capacity, 1000);
4697 }
4698
4699 #[test]
4700 fn height_cache_get_before_base_offset() {
4701 let mut cache = HeightCache::new(5, 100);
4702 cache.set(200, 10); assert_eq!(cache.get(0), 5);
4706 }
4707
4708 #[test]
4709 fn height_cache_set_before_base_offset_ignored() {
4710 let mut cache = HeightCache::new(5, 100);
4711 cache.set(200, 10);
4712 let base = cache.base_offset;
4713 cache.set(0, 99); assert_eq!(cache.get(0), 5); assert_eq!(cache.base_offset, base); }
4717
4718 #[test]
4719 fn height_cache_capacity_zero_ignores_all_sets() {
4720 let mut cache = HeightCache::new(3, 0);
4721 cache.set(0, 10);
4722 cache.set(5, 20);
4723 assert_eq!(cache.get(0), 3);
4725 assert_eq!(cache.get(5), 3);
4726 }
4727
4728 #[test]
4729 fn height_cache_clear_resets_base() {
4730 let mut cache = HeightCache::new(1, 100);
4731 cache.set(50, 10);
4732 cache.clear();
4733 assert_eq!(cache.base_offset, 0);
4734 assert_eq!(cache.get(50), 1); }
4736
4737 #[test]
4738 fn height_cache_eviction_trims_oldest() {
4739 let mut cache = HeightCache::new(1, 4);
4740 for i in 0..6 {
4742 cache.set(i, (i + 10) as u16);
4743 }
4744 assert!(cache.cache.len() <= cache.capacity);
4746 assert_eq!(cache.get(5), 15);
4748 assert_eq!(cache.get(4), 14);
4749 assert_eq!(cache.get(3), 13);
4750 assert_eq!(cache.get(2), 12);
4751 assert_eq!(cache.get(1), 1);
4753 assert_eq!(cache.get(0), 1);
4754 }
4755
4756 #[test]
4759 fn fenwick_default_is_empty() {
4760 let tracker = VariableHeightsFenwick::default();
4761 assert!(tracker.is_empty());
4762 assert_eq!(tracker.len(), 0);
4763 assert_eq!(tracker.total_height(), 0);
4764 assert_eq!(tracker.default_height(), 1);
4765 }
4766
4767 #[test]
4768 fn fenwick_get_beyond_len_returns_default() {
4769 let tracker = VariableHeightsFenwick::new(3, 5);
4770 assert_eq!(tracker.get(5), 3); assert_eq!(tracker.get(100), 3);
4772 }
4773
4774 #[test]
4775 fn fenwick_set_beyond_len_resizes() {
4776 let mut tracker = VariableHeightsFenwick::new(2, 3);
4777 assert_eq!(tracker.len(), 3);
4778 tracker.set(10, 7);
4779 assert!(tracker.len() > 10);
4780 assert_eq!(tracker.get(10), 7);
4781 }
4782
4783 #[test]
4784 fn fenwick_offset_of_item_zero_always_zero() {
4785 let tracker = VariableHeightsFenwick::new(5, 10);
4786 assert_eq!(tracker.offset_of_item(0), 0);
4787
4788 let empty = VariableHeightsFenwick::new(5, 0);
4789 assert_eq!(empty.offset_of_item(0), 0);
4790 }
4791
4792 #[test]
4793 fn fenwick_find_item_at_offset_empty() {
4794 let tracker = VariableHeightsFenwick::new(1, 0);
4795 assert_eq!(tracker.find_item_at_offset(0), 0);
4796 assert_eq!(tracker.find_item_at_offset(100), 0);
4797 }
4798
4799 #[test]
4800 fn fenwick_visible_count_zero_viewport() {
4801 let tracker = VariableHeightsFenwick::new(2, 10);
4802 assert_eq!(tracker.visible_count(0, 0), 0);
4803 }
4804
4805 #[test]
4806 fn fenwick_visible_count_start_beyond_len() {
4807 let tracker = VariableHeightsFenwick::new(2, 5);
4808 let count = tracker.visible_count(100, 10);
4810 assert_eq!(count, 0);
4812 }
4813
4814 #[test]
4815 fn fenwick_clear_then_operations() {
4816 let mut tracker = VariableHeightsFenwick::new(3, 5);
4817 assert_eq!(tracker.total_height(), 15);
4818 tracker.clear();
4819 assert_eq!(tracker.len(), 0);
4820 assert_eq!(tracker.total_height(), 0);
4821 assert_eq!(tracker.find_item_at_offset(0), 0);
4822 }
4823
4824 #[test]
4825 fn fenwick_rebuild_replaces_data() {
4826 let mut tracker = VariableHeightsFenwick::new(1, 10);
4827 assert_eq!(tracker.total_height(), 10);
4828 tracker.rebuild(&[5, 3, 2]);
4829 assert_eq!(tracker.len(), 3);
4830 assert_eq!(tracker.total_height(), 10);
4831 assert_eq!(tracker.get(0), 5);
4832 assert_eq!(tracker.get(1), 3);
4833 assert_eq!(tracker.get(2), 2);
4834 }
4835
4836 #[test]
4837 fn fenwick_resize_same_size_is_noop() {
4838 let mut tracker = VariableHeightsFenwick::new(2, 5);
4839 tracker.set(2, 10);
4840 tracker.resize(5);
4841 assert_eq!(tracker.get(2), 10);
4843 assert_eq!(tracker.len(), 5);
4844 }
4845
4846 #[test]
4849 fn list_state_default_matches_new() {
4850 let d = VirtualizedListState::default();
4851 let n = VirtualizedListState::new();
4852 assert_eq!(d.selected, n.selected);
4853 assert_eq!(d.scroll_offset(), n.scroll_offset());
4854 assert_eq!(d.visible_count(), n.visible_count());
4855 assert_eq!(d.follow_mode(), n.follow_mode());
4856 }
4857
4858 #[test]
4859 fn list_state_select_next_on_empty() {
4860 let mut state = VirtualizedListState::new();
4861 state.select_next(0);
4862 assert_eq!(state.selected, None);
4863 }
4864
4865 #[test]
4866 fn list_state_select_previous_on_empty() {
4867 let mut state = VirtualizedListState::new();
4868 state.select_previous(0);
4869 assert_eq!(state.selected, None);
4870 }
4871
4872 #[test]
4873 fn list_state_select_previous_from_none() {
4874 let mut state = VirtualizedListState::new();
4875 state.select_previous(10);
4876 assert_eq!(state.selected, Some(0));
4877 }
4878
4879 #[test]
4880 fn list_state_select_next_from_none() {
4881 let mut state = VirtualizedListState::new();
4882 state.select_next(10);
4883 assert_eq!(state.selected, Some(0));
4884 }
4885
4886 #[test]
4887 fn list_state_scroll_zero_items() {
4888 let mut state = VirtualizedListState::new();
4889 state.scroll(10, 0);
4890 assert_eq!(state.scroll_offset(), 0);
4891 }
4892
4893 #[test]
4894 fn list_state_scroll_to_clamps() {
4895 let mut state = VirtualizedListState::new();
4896 state.scroll_to(100, 10);
4897 assert_eq!(state.scroll_offset(), 9);
4898 }
4899
4900 #[test]
4901 fn list_state_scroll_to_bottom_zero_items() {
4902 let mut state = VirtualizedListState::new();
4903 state.scroll_to_bottom(0);
4904 assert_eq!(state.scroll_offset(), 0);
4905 }
4906
4907 #[test]
4908 fn list_state_is_at_bottom_zero_items() {
4909 let state = VirtualizedListState::new();
4910 assert!(state.is_at_bottom(0));
4911 }
4912
4913 #[test]
4914 fn list_state_page_up_visible_count_zero() {
4915 let mut state = VirtualizedListState::new();
4916 state.scroll_offset = 5;
4917 state.page_up(20);
4918 assert_eq!(state.scroll_offset(), 5);
4920 }
4921
4922 #[test]
4923 fn list_state_page_down_visible_count_zero() {
4924 let mut state = VirtualizedListState::new();
4925 state.page_down(20);
4926 assert_eq!(state.scroll_offset(), 0);
4928 }
4929
4930 #[test]
4931 fn list_state_set_follow_false_no_scroll() {
4932 let mut state = VirtualizedListState::new();
4933 state.scroll_offset = 5;
4934 state.set_follow(false, 20);
4935 assert_eq!(state.scroll_offset(), 5); assert!(!state.follow_mode());
4937 }
4938
4939 #[test]
4940 fn list_state_persistence_id() {
4941 let state = VirtualizedListState::new().with_persistence_id("my-list");
4942 assert_eq!(state.persistence_id(), Some("my-list"));
4943 }
4944
4945 #[test]
4946 fn list_state_persistence_id_none() {
4947 let state = VirtualizedListState::new();
4948 assert_eq!(state.persistence_id(), None);
4949 }
4950
4951 #[test]
4952 fn list_state_momentum_tick_zero_items() {
4953 let mut state = VirtualizedListState::new();
4954 state.fling(50.0);
4955 state.tick(Duration::from_millis(100), 0);
4956 assert_eq!(state.scroll_offset(), 0);
4958 }
4959
4960 #[test]
4963 fn persist_state_default() {
4964 let ps = VirtualizedListPersistState::default();
4965 assert_eq!(ps.selected, None);
4966 assert_eq!(ps.scroll_offset, 0);
4967 assert!(!ps.follow_mode);
4968 }
4969
4970 #[test]
4971 fn persist_state_eq() {
4972 let a = VirtualizedListPersistState {
4973 selected: Some(5),
4974 scroll_offset: 10,
4975 follow_mode: true,
4976 };
4977 let b = a.clone();
4978 assert_eq!(a, b);
4979 }
4980
4981 #[test]
4984 fn stateful_state_key_with_persistence_id() {
4985 use crate::stateful::Stateful;
4986 let state = VirtualizedListState::new().with_persistence_id("logs");
4987 let key = state.state_key().expect("named list has a key");
4988 assert_eq!(key.widget_type, "VirtualizedList");
4989 assert_eq!(key.instance_id, "logs");
4990 }
4991
4992 #[test]
4993 fn stateful_state_without_id_is_not_persisted() {
4994 use crate::stateful::Stateful;
4995 assert!(VirtualizedListState::new().state_key().is_none());
4996 }
4997
4998 #[test]
4999 fn stateful_save_restore_roundtrip() {
5000 use crate::stateful::Stateful;
5001 let mut state = VirtualizedListState::new();
5002 state.selected = Some(7);
5003 state.scroll_offset = 15;
5004 state.follow_mode = true;
5005 state.scroll_velocity = 42.0; let saved = state.save_state();
5008 assert_eq!(saved.selected, Some(7));
5009 assert_eq!(saved.scroll_offset, 15);
5010 assert!(saved.follow_mode);
5011
5012 let mut restored = VirtualizedListState::new();
5013 restored.scroll_velocity = 99.0;
5014 restored.restore_state(saved);
5015 assert_eq!(restored.selected, Some(7));
5016 assert_eq!(restored.scroll_offset, 15);
5017 assert!(restored.follow_mode);
5018 assert_eq!(restored.scroll_velocity, 0.0);
5020 }
5021
5022 #[test]
5025 fn virtualized_list_builder() {
5026 let items: Vec<String> = vec!["a".into()];
5027 let list = VirtualizedList::new(&items)
5028 .style(Style::default())
5029 .highlight_style(Style::default())
5030 .show_scrollbar(false)
5031 .fixed_height(3);
5032 assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
5033 assert!(!list.show_scrollbar);
5034 assert_eq!(
5035 VirtualizedList::new(&items)
5036 .variable_heights()
5037 .height_mode(),
5038 ListHeightMode::Variable
5039 );
5040 }
5041
5042 #[test]
5047 fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
5048 let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
5049 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5050 panic!("expected the Fenwick tracker, got {:?}", v.item_height());
5051 };
5052 assert_eq!(tracker.len(), 10_000);
5053 assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
5054 for k in 0..100u32 {
5055 let offset = k * 297;
5056 let idx = tracker.find_item_at_offset(offset);
5057 let start = tracker.offset_of_item(idx);
5058 assert!(
5059 start <= offset && offset < start + u32::from(tracker.get(idx)),
5060 "offset {offset} must land inside item {idx} [{start}, +{})",
5061 tracker.get(idx)
5062 );
5063 }
5064
5065 v.scroll_to(9_999);
5066 let range = v.visible_range(24);
5067 assert_eq!(range.end, 10_000);
5068 assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
5069
5070 v.observe_height(5, 7);
5071 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5072 unreachable!()
5073 };
5074 assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
5075 assert!(tracker.is_measured(5));
5076 assert_eq!(v.unmeasured_item_height(), 3);
5077 }
5078
5079 #[test]
5082 fn variable_height_tracker_follows_owned_storage() {
5083 let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
5084 for i in 0..5 {
5085 v.push(format!("row {i}"));
5086 }
5087 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5088 unreachable!()
5089 };
5090 assert_eq!(tracker.len(), 5);
5091 assert_eq!(tracker.total_height(), 10);
5092
5093 v.observe_height(0, 5);
5094 v.observe_height(3, 4);
5095 assert_eq!(v.trim_front(3), 2);
5096 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5097 unreachable!()
5098 };
5099 assert_eq!(tracker.len(), 3);
5100 assert!(!tracker.is_measured(0));
5102 assert!(tracker.is_measured(1));
5103 assert_eq!(tracker.get(1), 4);
5104 assert_eq!(tracker.total_height(), 2 + 4 + 2);
5105
5106 v.clear();
5107 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
5108 unreachable!()
5109 };
5110 assert_eq!(tracker.len(), 0);
5111 assert_eq!(tracker.total_height(), 0);
5112 }
5113
5114 #[test]
5118 fn legacy_height_cache_follows_owned_storage() {
5119 let mut v: Virtualized<String> =
5120 Virtualized::new(8).with_item_height(ItemHeight::Variable(HeightCache::new(1, 64)));
5121 for i in 0..6 {
5122 v.push(format!("row {i}"));
5123 }
5124 v.observe_height(0, 9);
5125 v.observe_height(4, 4);
5126 assert_eq!(v.trim_front(3), 3);
5127
5128 let ItemHeight::Variable(cache) = v.item_height() else {
5129 unreachable!()
5130 };
5131 assert_eq!(cache.get(0), 1);
5133 assert_eq!(cache.get(1), 4);
5134 assert_eq!(v.visible_range(4), 0..2);
5136
5137 v.clear();
5138 for i in 0..3 {
5139 v.push(format!("fresh {i}"));
5140 }
5141 let ItemHeight::Variable(cache) = v.item_height() else {
5142 unreachable!()
5143 };
5144 assert_eq!(cache.get(0), 1);
5145 assert_eq!(cache.get(1), 1);
5146 assert_eq!(v.visible_range(4), 0..3);
5147 }
5148
5149 #[test]
5152 fn height_cache_drop_front_shifts_a_window_past_the_prefix() {
5153 let mut cache = HeightCache::new(1, 4);
5154 for idx in 10..14 {
5155 cache.set(idx, idx as u16);
5156 }
5157 cache.drop_front(10);
5158 for idx in 0..4 {
5159 assert_eq!(cache.get(idx), 10 + idx as u16);
5160 }
5161
5162 cache.drop_front(2);
5164 assert_eq!(cache.get(0), 12);
5165 assert_eq!(cache.get(1), 13);
5166 assert_eq!(cache.get(2), 1);
5167
5168 cache.drop_front(9);
5170 assert_eq!(cache.get(0), 1);
5171 }
5172
5173 #[test]
5174 fn measure_updates_fenwick_and_predictor() {
5175 let mut list: Virtualized<String> = Virtualized::external(10, 0)
5176 .with_variable_heights(3)
5177 .with_height_prediction(PredictorConfig {
5178 default_height: 3,
5179 prior_mean: 3.0,
5180 prior_strength: 100.0,
5181 ..PredictorConfig::default()
5182 });
5183 let ItemHeight::VariableFenwick(before) = list.item_height() else {
5184 panic!("expected Fenwick heights");
5185 };
5186 let offset = before.offset_of_item(6);
5187 list.measure(5, 7);
5188 let ItemHeight::VariableFenwick(after) = list.item_height() else {
5189 panic!("expected Fenwick heights");
5190 };
5191 assert_eq!(after.offset_of_item(6), offset + 4);
5192 assert_eq!(list.predictor_stats().unwrap().measurements, 1);
5193 assert_eq!(list.predicted_height(0), 3);
5194 }
5195
5196 #[test]
5197 fn unmeasured_rows_use_predicted_mean() {
5198 let mut list: Virtualized<String> = Virtualized::external(100, 0)
5199 .with_variable_heights(1)
5200 .with_height_prediction(PredictorConfig::default());
5201 for idx in 0..20 {
5202 list.measure(idx, 4);
5203 }
5204 assert_eq!(list.predicted_height(0), 4);
5205 assert_eq!(list.predictor_stats().unwrap().measurements, 20);
5206 let ItemHeight::VariableFenwick(heights) = list.item_height() else {
5207 panic!("expected Fenwick heights");
5208 };
5209 assert!(!heights.is_measured(99));
5210 assert_eq!(heights.get(99), 4);
5211 assert_eq!(heights.total_height(), 400);
5212 assert_eq!(String::from("uncategorized").category(), 0);
5213 }
5214
5215 #[test]
5216 fn measured_bitset_tracks_word_boundaries_resize_and_rebuild() {
5217 let mut heights = VariableHeightsFenwick::new(2, 130);
5218 for idx in [0, 63, 64, 65, 127, 128, 129] {
5219 heights.set(idx, 3);
5220 }
5221 assert_eq!(heights.unmeasured_count(), 123);
5222 assert_eq!(heights.measured.len(), 3);
5223 heights.resize(65);
5224 assert_eq!(heights.unmeasured_count(), 62);
5225 heights.resize(130);
5226 for idx in 65..130 {
5227 assert!(!heights.is_measured(idx), "stale bit at {idx}");
5228 assert_eq!(heights.get(idx), 2);
5229 }
5230 heights.rebuild(&[4; 65]);
5231 assert_eq!(heights.unmeasured_count(), 0);
5232 assert!(heights.is_measured(64));
5233 assert!(!heights.is_measured(65));
5234 heights.resize(66);
5235 assert!(!heights.is_measured(65));
5236 heights.drop_front(64);
5237 assert!(heights.is_measured(0));
5238 assert!(!heights.is_measured(1));
5239 assert_eq!(heights.get(0), 4);
5240 assert_eq!(heights.get(1), 2);
5241 heights.clear();
5242 assert!(!heights.is_measured(0));
5243 assert_eq!(heights.unmeasured_count(), 0);
5244 assert!(heights.measured.is_empty());
5245 }
5246
5247 #[test]
5248 fn trimming_measured_rows_does_not_retrain_predictor() {
5249 let mut heights =
5250 VariableHeightsFenwick::new(1, 80).with_predictor(PredictorConfig::default());
5251 for idx in 0..70 {
5252 heights.set_in_category(idx, 5, 1);
5253 }
5254 let before = heights.predictor().unwrap().stats();
5255 heights.drop_front(65);
5256 assert_eq!(heights.predictor().unwrap().stats(), before);
5257 assert_eq!(heights.unmeasured_count(), 10);
5258 for idx in 0..5 {
5259 assert!(heights.is_measured(idx));
5260 assert_eq!(heights.get(idx), 5);
5261 }
5262 }
5263
5264 #[test]
5265 fn variable_list_trains_categories_once_per_measurement() {
5266 struct Row {
5267 height: u16,
5268 category: usize,
5269 }
5270 impl RenderItem for Row {
5271 fn render(&self, area: Rect, frame: &mut Frame, _: bool, _: u16) {
5272 for y in area.y..area.bottom() {
5273 frame.buffer.set(area.x, y, Cell::from_char('x'));
5274 }
5275 }
5276
5277 fn height(&self) -> u16 {
5278 self.height
5279 }
5280
5281 fn category(&self) -> usize {
5282 self.category
5283 }
5284 }
5285 let mut items = [
5286 Row {
5287 height: 3,
5288 category: 1,
5289 },
5290 Row {
5291 height: 1,
5292 category: 0,
5293 },
5294 ];
5295 let mut state =
5296 VirtualizedListState::variable(2).with_predictor(PredictorConfig::default());
5297 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5298 let mut frame = Frame::new(10, 5, &mut pool);
5299 let area = Rect::new(0, 0, 10, 5);
5300 VirtualizedList::new(&items)
5301 .variable_heights()
5302 .render(area, &mut frame, &mut state);
5303 assert_eq!(state.predictor_stats().unwrap().measurements, 2);
5304 assert_eq!(state.predictor_stats().unwrap().categories, 2);
5305 let predictor = state.heights().unwrap().predictor().unwrap();
5306 assert_eq!(predictor.category_observations(1), 1);
5307 assert_eq!(predictor.category_observations(0), 1);
5308 assert_eq!(state.heights().unwrap().offset_of_item(1), 3);
5309 assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), Some('x'));
5310 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some(' '));
5311 VirtualizedList::new(&items)
5312 .variable_heights()
5313 .render(area, &mut frame, &mut state);
5314 assert_eq!(state.predictor_stats().unwrap().measurements, 2);
5315 items[0].height = 4;
5316 VirtualizedList::new(&items)
5317 .variable_heights()
5318 .render(area, &mut frame, &mut state);
5319 assert_eq!(state.predictor_stats().unwrap().measurements, 3);
5320 assert_eq!(
5321 state
5322 .heights()
5323 .unwrap()
5324 .predictor()
5325 .unwrap()
5326 .category_observations(1),
5327 2
5328 );
5329
5330 VirtualizedList::new(&items[..0])
5331 .variable_heights()
5332 .render(area, &mut frame, &mut state);
5333 assert_eq!(state.visible_count(), 0);
5334 assert_eq!(state.scroll_offset(), 0);
5335 assert!(state.heights().unwrap().is_empty());
5336 assert_eq!(state.predictor_stats().unwrap().measurements, 3);
5337 VirtualizedList::new(&items)
5338 .variable_heights()
5339 .render(area, &mut frame, &mut state);
5340 assert_eq!(state.predictor_stats().unwrap().measurements, 5);
5341
5342 let mut owned = Virtualized::new(2)
5343 .with_variable_heights(2)
5344 .with_height_prediction(PredictorConfig::default());
5345 owned.push(Row {
5346 height: 4,
5347 category: 1,
5348 });
5349 owned.measure(0, 4);
5350 assert_eq!(owned.predictor_stats().unwrap().categories, 2);
5351 assert_eq!(owned.predictor_stats().unwrap().measurements, 1);
5352 assert!(owned.predicted_height(1) > owned.predicted_height(0));
5353 }
5354
5355 #[test]
5359 fn virtualized_list_variable_heights_renders_by_item_height() {
5360 struct Tall(u16);
5361 impl RenderItem for Tall {
5362 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
5363 let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
5364 for row in 0..area.height {
5365 frame
5366 .buffer
5367 .set(area.x, area.y + row, Cell::from_char(glyph));
5368 }
5369 }
5370 fn height(&self) -> u16 {
5371 self.0
5372 }
5373 }
5374 let column = |frame: &Frame| -> String {
5375 (0..frame.buffer.height())
5376 .map(|y| {
5377 frame
5378 .buffer
5379 .get(0, y)
5380 .and_then(|cell| cell.content.as_char())
5381 .unwrap_or(' ')
5382 })
5383 .collect()
5384 };
5385
5386 let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
5387 let list = VirtualizedList::new(&items)
5388 .variable_heights()
5389 .show_scrollbar(false);
5390 let mut state = VirtualizedListState::new();
5391 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5392
5393 let mut frame = Frame::new(4, 5, &mut pool);
5394 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5395 assert_eq!(column(&frame), "12233");
5397 assert_eq!(state.visible_count(), 3);
5398 let heights = state.heights().expect("tracker created by render");
5399 assert_eq!(heights.get(1), 2);
5400 assert!(heights.is_measured(2));
5401 assert!(heights.is_measured(4) && heights.is_measured(3));
5403 drop(frame);
5404
5405 state.select(Some(4));
5408 let mut frame = Frame::new(4, 5, &mut pool);
5409 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5410 assert_eq!(state.scroll_offset(), 3);
5411 assert_eq!(column(&frame), "122 ");
5412 assert_eq!(state.visible_count(), 2);
5413 let heights = state.heights().expect("tracker");
5414 assert_eq!(heights.total_height(), 9);
5415 assert_eq!(heights.offset_of_item(4), 7);
5416 drop(frame);
5417
5418 state.measure(0, 3);
5420 assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
5421
5422 let list = VirtualizedList::new(&items).variable_heights();
5424 let mut state = VirtualizedListState::new();
5425 let mut frame = Frame::new(4, 5, &mut pool);
5426 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5427 assert!(
5428 frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
5429 "the last column belongs to the scrollbar"
5430 );
5431 assert_eq!(column(&frame), "12233");
5432 }
5433
5434 #[test]
5435 fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
5436 #[derive(Clone, Copy)]
5437 struct Row(u16, char);
5438 impl RenderItem for Row {
5439 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
5440 for y in area.y..area.bottom() {
5441 frame.buffer.set(area.x, y, Cell::from_char(self.1));
5442 }
5443 }
5444
5445 fn height(&self) -> u16 {
5446 self.0
5447 }
5448 }
5449
5450 let mut items = vec![Row(u16::MAX, 'X'); 65_538];
5451 items.extend([Row(1, '.'); 9]);
5452 items.push(Row(1, 'Z'));
5453 let list = VirtualizedList::new(&items).variable_heights();
5454 let mut state = VirtualizedListState::new();
5455 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5456 {
5457 let mut frame = Frame::new(4, 5, &mut pool);
5458 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5459 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
5460 }
5461 for (idx, row) in items.iter().enumerate() {
5463 state.measure(idx, row.height());
5464 }
5465 assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
5466 state.select(Some(items.len() - 1));
5467 {
5468 let mut frame = Frame::new(4, 5, &mut pool);
5469 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5470 assert_eq!(state.scroll_offset(), items.len() - 5);
5471 assert_eq!(state.visible_count(), 5);
5472 let column: String = (0..5)
5473 .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
5474 .collect();
5475 assert_eq!(column, "....Z");
5476 assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
5477 }
5478 state.select(None);
5479 state.scroll_to_top();
5480 {
5481 let mut frame = Frame::new(4, 5, &mut pool);
5482 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5483 assert_eq!(state.scroll_offset(), 0);
5484 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
5485 }
5486 state.scroll_to_bottom(items.len());
5487 let mut frame = Frame::new(4, 5, &mut pool);
5488 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5489 assert_eq!(state.scroll_offset(), items.len() - 5);
5490 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
5491 }
5492
5493 #[test]
5496 fn virtualized_storage_debug() {
5497 let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
5498 let dbg = format!("{:?}", storage);
5499 assert!(dbg.contains("Owned"));
5500
5501 let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
5502 len: 100,
5503 cache_capacity: 10,
5504 };
5505 let dbg = format!("{:?}", ext);
5506 assert!(dbg.contains("External"));
5507 }
5508
5509 #[test]
5510 fn test_virtualized_list_handle_mouse_drag_smooth() {
5511 use crate::scrollbar::SCROLLBAR_PART_THUMB;
5512 use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5513 use ftui_render::frame::{HitId, HitRegion};
5514
5515 let mut state = VirtualizedListState::new();
5516 let scrollbar_hit_id = HitId::new(1);
5517 let total_items = 100;
5518 let viewport_height = 10;
5519 let fixed_height = 1;
5520
5521 let track_len = 10u64;
5527 let track_pos = 0u64;
5528 let hit_data = (SCROLLBAR_PART_THUMB << 56)
5529 | ((track_len & 0x0FFF_FFFF) << 28)
5530 | (track_pos & 0x0FFF_FFFF);
5531
5532 let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
5533 let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
5534
5535 state.handle_mouse(
5536 &down_event,
5537 hit,
5538 scrollbar_hit_id,
5539 total_items,
5540 viewport_height,
5541 fixed_height,
5542 );
5543
5544 assert!(
5545 state.scrollbar_drag_anchor.is_some(),
5546 "Drag anchor should be set on down"
5547 );
5548 assert_eq!(
5549 state.scrollbar_drag_anchor.unwrap(),
5550 0,
5551 "Anchor should be 0 (clicked top of thumb)"
5552 );
5553
5554 let drag_pos = 1u64;
5559 let drag_data = (SCROLLBAR_PART_THUMB << 56)
5560 | ((track_len & 0x0FFF_FFFF) << 28)
5561 | (drag_pos & 0x0FFF_FFFF);
5562 let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
5563 let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
5564
5565 state.handle_mouse(
5566 &drag_event,
5567 drag_hit,
5568 scrollbar_hit_id,
5569 total_items,
5570 viewport_height,
5571 fixed_height,
5572 );
5573
5574 assert_eq!(
5575 state.scroll_offset, 10,
5576 "Scroll offset should update smoothly"
5577 );
5578 }
5579
5580 #[test]
5584 fn variable_height_mouse_scrolls_in_rows() {
5585 use crate::scrollbar::SCROLLBAR_PART_TRACK;
5586 use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5587 use ftui_render::frame::{HitId, HitRegion};
5588
5589 struct Tall;
5590 impl RenderItem for Tall {
5591 fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip: u16) {}
5592 fn height(&self) -> u16 {
5593 6
5594 }
5595 }
5596 let items = [Tall, Tall, Tall, Tall, Tall];
5597 let list = VirtualizedList::new(&items).variable_heights();
5598 let mut state = VirtualizedListState::new();
5599 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5600 let area = Rect::new(0, 0, 4, 5);
5601 let mut frame = Frame::new(4, 5, &mut pool);
5602 StatefulWidget::render(&list, area, &mut frame, &mut state);
5603
5604 let id = HitId::new(1);
5605 let mouse = |state: &mut VirtualizedListState, kind, hit| {
5606 state.handle_mouse(&MouseEvent::new(kind, 3, 4), hit, id, items.len(), 5, 1);
5607 };
5608
5609 mouse(&mut state, MouseEventKind::ScrollDown, None);
5611 assert_eq!(state.scroll_offset(), 1);
5612 mouse(&mut state, MouseEventKind::ScrollUp, None);
5613 assert_eq!(state.scroll_offset(), 0);
5614
5615 let track = (SCROLLBAR_PART_TRACK << 56) | (5 << 28) | 4;
5617 mouse(
5618 &mut state,
5619 MouseEventKind::Down(MouseButton::Left),
5620 Some((id, HitRegion::Scrollbar, track)),
5621 );
5622 assert_eq!(state.scroll_offset(), 4);
5623 StatefulWidget::render(&list, area, &mut frame, &mut state);
5624 assert_eq!(state.scroll_offset(), 4, "render keeps the offset");
5625 }
5626
5627 #[test]
5628 fn remeasure_policy_samples_when_voi_exceeds_cost() {
5629 let mut high_voi = RemeasurePolicy::new(BetaPosterior::new(1.0, 1.0), 0.01, 2);
5630 let decision = high_voi.should_sample(0);
5631 assert!(
5632 decision.is_some(),
5633 "Beta(1,1) VOI (~0.0278) should exceed cost 0.01"
5634 );
5635
5636 let mut low_voi = RemeasurePolicy::new(BetaPosterior::new(1.0, 200.0), 0.08, 2);
5637 assert!(
5638 low_voi.should_sample(0).is_none(),
5639 "Beta(1,200) VOI should fall below cost 0.08"
5640 );
5641 }
5642
5643 #[test]
5644 fn remeasure_policy_respects_min_interval() {
5645 let mut policy = RemeasurePolicy::new(BetaPosterior::new(1.0, 1.0), 0.001, 4);
5646 assert!(policy.should_sample(0).is_some(), "frame 0 should sample");
5647 assert!(
5648 policy.should_sample(1).is_none(),
5649 "frame 1 within min_interval_frames=4 must be skipped"
5650 );
5651 assert!(
5652 policy.should_sample(3).is_none(),
5653 "frame 3 within min_interval_frames=4 must be skipped"
5654 );
5655 assert!(
5656 policy.should_sample(4).is_some(),
5657 "frame 4 at min_interval_frames=4 should sample"
5658 );
5659 }
5660
5661 #[test]
5662 fn invalidate_clears_measured_bit() {
5663 let mut fenwick = VariableHeightsFenwick::new(1, 4);
5664 fenwick.set(2, 5);
5665 assert!(fenwick.is_measured(2));
5666 assert_eq!(fenwick.get(2), 5);
5667 assert_eq!(fenwick.unmeasured_count(), 3);
5668
5669 fenwick.invalidate(2);
5670 assert!(!fenwick.is_measured(2));
5671 assert_eq!(fenwick.get(2), 1);
5672 assert_eq!(fenwick.unmeasured_count(), 4);
5673 }
5674
5675 #[test]
5676 fn variable_heights_defaults_to_fenwick() {
5677 let v: Virtualized<String> = Virtualized::new(16).with_variable_heights(2);
5678 assert!(matches!(v.item_height(), ItemHeight::VariableFenwick(_)));
5679 }
5680
5681 #[test]
5682 fn offset_of_item_is_prefix_sum() {
5683 let heights = [2u16, 5, 1, 4, 3, 6];
5684 let fenwick = VariableHeightsFenwick::from_heights(&heights, 1);
5685 let mut prefix = 0u32;
5686 for (i, &h) in heights.iter().enumerate() {
5687 assert_eq!(fenwick.offset_of_item(i), prefix);
5688 prefix += u32::from(h);
5689 }
5690 assert_eq!(fenwick.total_height(), prefix);
5691 }
5692
5693 #[test]
5694 fn find_item_at_offset_round_trips() {
5695 let heights = [3u16, 1, 4, 2, 5];
5696 let fenwick = VariableHeightsFenwick::from_heights(&heights, 1);
5697 for (i, &h) in heights.iter().enumerate() {
5698 let start = fenwick.offset_of_item(i);
5699 for off in start..start + u32::from(h) {
5700 assert_eq!(fenwick.find_item_at_offset(off), i);
5701 }
5702 }
5703 }
5704
5705 #[test]
5706 fn variable_list_renders_multi_line_items_at_correct_rows() {
5707 #[derive(Clone, Copy)]
5708 struct MultiRow(u16, char);
5709 impl RenderItem for MultiRow {
5710 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip: u16) {
5711 for y in area.y..area.bottom() {
5712 frame.buffer.set(area.x, y, Cell::from_char(self.1));
5713 }
5714 }
5715 fn height(&self) -> u16 {
5716 self.0
5717 }
5718 }
5719 let items = [MultiRow(2, 'A'), MultiRow(3, 'B'), MultiRow(1, 'C')];
5720 let list = VirtualizedList::new(&items)
5721 .variable_heights()
5722 .show_scrollbar(false);
5723 let mut state = VirtualizedListState::new();
5724 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5725 let mut frame = Frame::new(4, 6, &mut pool);
5726 StatefulWidget::render(&list, Rect::new(0, 0, 4, 6), &mut frame, &mut state);
5727 let col: String = (0..6)
5728 .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
5729 .collect();
5730 assert_eq!(col, "AABBBC");
5731 }
5732
5733 #[test]
5734 fn category_default_is_zero() {
5735 assert_eq!(String::from("default").category(), 0);
5736 }
5737
5738 #[test]
5739 fn measured_bitset_tracks_set_and_rebuild() {
5740 let mut fenwick = VariableHeightsFenwick::new(1, 10);
5741 assert_eq!(fenwick.unmeasured_count(), 10);
5742 fenwick.set(3, 4);
5743 assert!(fenwick.is_measured(3));
5744 assert!(!fenwick.is_measured(2));
5745 assert_eq!(fenwick.unmeasured_count(), 9);
5746 fenwick.rebuild(&[2; 10]);
5747 assert_eq!(fenwick.unmeasured_count(), 0);
5748 assert!(fenwick.is_measured(2));
5749 }
5750
5751 mod scroll_stability_proptests {
5752 use super::*;
5753 use proptest::prelude::{ProptestConfig, any, prop_assert, proptest};
5754
5755 #[derive(Clone, Copy, Debug)]
5756 struct CorpusRow {
5757 height: u16,
5758 category: usize,
5759 }
5760
5761 impl RenderItem for CorpusRow {
5762 fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip_rows: u16) {}
5763
5764 fn height(&self) -> u16 {
5765 self.height
5766 }
5767
5768 fn category(&self) -> usize {
5769 self.category
5770 }
5771 }
5772
5773 fn generate_long_tail_corpus(n: usize, seed: u64) -> (Vec<CorpusRow>, Vec<usize>) {
5774 let mut state = seed ^ 0x9E37_79B9_7F4A_7C15;
5775 let mut next_u64 = || -> u64 {
5776 state = state
5777 .wrapping_mul(6364136223846793005)
5778 .wrapping_add(1442695040888963407);
5779 state
5780 };
5781
5782 let mut rows = Vec::with_capacity(n);
5783 for _ in 0..n {
5784 let bucket = (next_u64() >> 32) % 100;
5785 let (height, category) = if bucket < 80 {
5786 (1u16, 0usize)
5787 } else if bucket < 95 {
5788 let r = next_u64();
5789 let h = 2 + (((r >> 32) % 2) + ((r >> 48) % 2)) as u16; (h, 1usize)
5791 } else {
5792 let r = next_u64();
5793 let tier = ((r >> 48) % 3) as usize;
5794 let jitter = (((r & 0xFF) % 3) + (((r >> 8) & 0xFF) % 3)) as u16; let h = match tier {
5796 0 => 6 + jitter, 1 => 15 + jitter, _ => 25 + jitter, };
5800 (h, 2 + tier)
5801 };
5802 rows.push(CorpusRow { height, category });
5803 }
5804
5805 let mut perm: Vec<usize> = (0..n).collect();
5806 for idx in (1..n).rev() {
5807 let swap_idx = (next_u64() as usize) % (idx + 1);
5808 perm.swap(idx, swap_idx);
5809 }
5810
5811 let train_count = (n / 10).max(1);
5814 let mut swap_pos = 0usize;
5815 for target_cat in 1..=4usize {
5816 let mut seen = perm[..train_count]
5817 .iter()
5818 .filter(|&&idx| rows[idx].category == target_cat)
5819 .count();
5820 for pos in train_count..n {
5821 if seen >= 4 || swap_pos >= train_count {
5822 break;
5823 }
5824 if rows[perm[pos]].category == target_cat {
5825 while swap_pos < train_count && rows[perm[swap_pos]].category != 0 {
5826 swap_pos += 1;
5827 }
5828 if swap_pos < train_count {
5829 perm.swap(swap_pos, pos);
5830 seen += 1;
5831 swap_pos += 1;
5832 }
5833 }
5834 }
5835 }
5836
5837 (rows, perm)
5838 }
5839
5840 proptest! {
5841 #![proptest_config(ProptestConfig { cases: 256, ..ProptestConfig::default() })]
5842
5843 #[test]
5844 fn scroll_to_index_is_stable_under_late_measurements(
5845 n in 500usize..5000,
5846 seed in any::<u64>(),
5847 target_frac in 0usize..10_000,
5848 ) {
5849 let min_target = n / 4;
5850 let i = min_target + (target_frac % (n - min_target).max(1));
5851 let (rows, perm) = generate_long_tail_corpus(n, seed);
5852 let total_true_sum: u64 = rows.iter().map(|r| u64::from(r.height)).sum();
5853 let mean_height = ((total_true_sum as f64) / (n as f64)).round().max(1.0) as u16;
5854 let true_offset: u32 = rows[..i].iter().map(|r| u32::from(r.height)).sum();
5855
5856 let mut pred_list: Virtualized<CorpusRow> = Virtualized::new(n)
5857 .with_variable_heights(1)
5858 .with_height_predictor(PredictorConfig::default());
5859 let mut base_list: Virtualized<CorpusRow> = Virtualized::new(n)
5860 .with_variable_heights(mean_height);
5861
5862 for &row in &rows {
5863 pred_list.push(row);
5864 base_list.push(row);
5865 }
5866
5867 let train_count = (n / 10).max(1);
5868 for &idx in &perm[..train_count] {
5869 let h = rows[idx].height;
5870 pred_list.measure(idx, h);
5871 base_list.observe_height(idx, h);
5872 }
5873
5874 pred_list.scroll_to(i);
5875 base_list.scroll_to(i);
5876
5877 let mut prev_pred_offset = pred_list.offset_of_item(i);
5878 let mut prev_base_offset = base_list.offset_of_item(i);
5879 let mut jump_predictor = 0u64;
5880 let mut jump_mean_baseline = 0u64;
5881
5882 for chunk in perm[train_count..].chunks(50) {
5883 for &idx in chunk {
5884 let h = rows[idx].height;
5885 pred_list.measure(idx, h);
5886 base_list.observe_height(idx, h);
5887 }
5888 let next_pred_offset = pred_list.offset_of_item(i);
5889 let next_base_offset = base_list.offset_of_item(i);
5890 jump_predictor += u64::from(next_pred_offset.abs_diff(prev_pred_offset));
5891 jump_mean_baseline += u64::from(next_base_offset.abs_diff(prev_base_offset));
5892 prev_pred_offset = next_pred_offset;
5893 prev_base_offset = next_base_offset;
5894 }
5895
5896 let final_offset = pred_list.offset_of_item(i);
5897 let cat = rows[i].category;
5898 let (lower, upper) = match pred_list.item_height() {
5899 ItemHeight::VariableFenwick(t) => t
5900 .predictor()
5901 .map_or((1, 1), |p| {
5902 let b = p.predict(cat);
5903 (b.lower, b.upper)
5904 }),
5905 _ => (1, 1),
5906 };
5907 let bound_width = u32::from(upper.saturating_sub(lower));
5908
5909 prop_assert!(
5910 final_offset.abs_diff(true_offset) <= bound_width,
5911 "seed={seed} n={n} i={i} final_offset={final_offset} true_offset={true_offset} bounds=[{lower}, {upper}]"
5912 );
5913 prop_assert!(
5914 jump_predictor <= jump_mean_baseline,
5915 "seed={seed} n={n} i={i} jump_predictor={jump_predictor} > jump_mean_baseline={jump_mean_baseline} bounds=[{lower}, {upper}]"
5916 );
5917 }
5918 }
5919 }
5920}