1#![forbid(unsafe_code)]
2
3use std::cell::Cell as StdCell;
34use std::collections::VecDeque;
35use std::ops::Range;
36use std::time::Duration;
37
38use crate::scrollbar::{Scrollbar, ScrollbarOrientation, ScrollbarState};
39use crate::{StatefulWidget, clear_text_area};
40use ftui_core::geometry::Rect;
41use ftui_render::cell::Cell;
42use ftui_render::frame::Frame;
43use ftui_style::Style;
44
45#[derive(Debug, Clone)]
54pub struct Virtualized<T> {
55 storage: VirtualizedStorage<T>,
57 scroll_offset: usize,
59 visible_count: StdCell<usize>,
61 overscan: usize,
63 item_height: ItemHeight,
65 follow_mode: bool,
67 scroll_velocity: f32,
69}
70
71#[derive(Debug, Clone)]
73pub enum VirtualizedStorage<T> {
74 Owned(VecDeque<T>),
76 External {
79 len: usize,
81 cache_capacity: usize,
83 },
84}
85
86#[derive(Debug, Clone)]
88pub enum ItemHeight {
89 Fixed(u16),
91 Variable(HeightCache),
96 VariableFenwick(VariableHeightsFenwick),
99}
100
101#[derive(Debug, Clone)]
103pub struct HeightCache {
104 cache: Vec<Option<u16>>,
106 base_offset: usize,
108 default_height: u16,
110 capacity: usize,
112}
113
114impl<T> Virtualized<T> {
115 #[must_use]
120 pub fn new(capacity: usize) -> Self {
121 Self {
122 storage: VirtualizedStorage::Owned(VecDeque::with_capacity(capacity.min(1024))),
123 scroll_offset: 0,
124 visible_count: StdCell::new(0),
125 overscan: 2,
126 item_height: ItemHeight::Fixed(1),
127 follow_mode: false,
128 scroll_velocity: 0.0,
129 }
130 }
131
132 #[must_use]
134 pub fn external(len: usize, cache_capacity: usize) -> Self {
135 Self {
136 storage: VirtualizedStorage::External {
137 len,
138 cache_capacity,
139 },
140 scroll_offset: 0,
141 visible_count: StdCell::new(0),
142 overscan: 2,
143 item_height: ItemHeight::Fixed(1),
144 follow_mode: false,
145 scroll_velocity: 0.0,
146 }
147 }
148
149 #[must_use]
151 pub fn with_item_height(mut self, height: ItemHeight) -> Self {
152 self.item_height = height;
153 self
154 }
155
156 #[must_use]
158 pub fn with_fixed_height(mut self, height: u16) -> Self {
159 self.item_height = ItemHeight::Fixed(height);
160 self
161 }
162
163 #[must_use]
171 pub fn with_height_prediction(mut self, config: PredictorConfig) -> Self {
172 let len = self.len();
173 let current = std::mem::replace(&mut self.item_height, ItemHeight::Fixed(1));
174 self.item_height = ItemHeight::VariableFenwick(match current {
175 ItemHeight::VariableFenwick(tracker) => tracker.with_predictor(config),
176 ItemHeight::Fixed(height) => {
177 VariableHeightsFenwick::new(height.max(1), len).with_predictor(config)
178 }
179 ItemHeight::Variable(cache) => {
180 VariableHeightsFenwick::new(cache.default_height, len).with_predictor(config)
181 }
182 });
183 self
184 }
185
186 pub fn observe_height(&mut self, idx: usize, height: u16) {
192 match &mut self.item_height {
193 ItemHeight::Fixed(_) => {}
194 ItemHeight::Variable(cache) => cache.set(idx, height),
195 ItemHeight::VariableFenwick(tracker) => tracker.set(idx, height),
196 }
197 }
198
199 #[must_use]
203 pub fn unmeasured_item_height(&self) -> u16 {
204 match &self.item_height {
205 ItemHeight::Fixed(height) => *height,
206 ItemHeight::Variable(cache) => cache.default_height,
207 ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
208 }
209 }
210
211 #[must_use]
219 pub fn with_variable_heights(mut self, default_height: u16) -> Self {
220 let len = self.len();
221 self.item_height =
222 ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
223 self
224 }
225
226 #[must_use]
231 pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
232 self.item_height =
233 ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
234 self
235 }
236
237 fn sync_height_tracker(&mut self, exact: bool) {
242 let len = self.len();
243 if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
244 && (tracker.len() < len || (exact && tracker.len() != len))
245 {
246 tracker.resize(len);
247 }
248 }
249
250 #[must_use]
252 pub fn with_overscan(mut self, overscan: usize) -> Self {
253 self.overscan = overscan;
254 self
255 }
256
257 #[must_use]
259 pub fn with_follow(mut self, follow: bool) -> Self {
260 self.follow_mode = follow;
261 self
262 }
263
264 #[must_use]
266 pub fn len(&self) -> usize {
267 match &self.storage {
268 VirtualizedStorage::Owned(items) => items.len(),
269 VirtualizedStorage::External { len, .. } => *len,
270 }
271 }
272
273 #[must_use]
275 pub fn is_empty(&self) -> bool {
276 self.len() == 0
277 }
278
279 #[must_use]
284 pub fn scroll_offset(&self) -> usize {
285 self.scroll_offset.min(self.len().saturating_sub(1))
286 }
287
288 #[must_use]
290 pub fn visible_count(&self) -> usize {
291 self.visible_count.get()
292 }
293
294 #[must_use]
296 pub fn follow_mode(&self) -> bool {
297 self.follow_mode
298 }
299
300 #[must_use]
302 pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
303 if self.is_empty() || viewport_height == 0 {
304 self.visible_count.set(0);
305 return 0..0;
306 }
307
308 let items_visible = match &self.item_height {
309 ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
311 ItemHeight::Fixed(_) => viewport_height as usize,
312 ItemHeight::Variable(cache) => {
313 let len = self.len();
315 let start = self.scroll_offset.min(len.saturating_sub(1));
316 let mut count = 0;
317 let mut total_height = 0u16;
318 while start + count < len {
319 let next = cache.get(start + count);
320
321 total_height = total_height.saturating_add(next);
323 count += 1;
324
325 if total_height >= viewport_height {
327 break;
328 }
329 }
330 if total_height < viewport_height && start > 0 {
331 count = 0;
337 total_height = 0;
338 while count < len {
339 let next = cache.get(len - 1 - count);
340 total_height = total_height.saturating_add(next);
341 count += 1;
342 if total_height >= viewport_height {
343 break;
344 }
345 }
346 }
347 count
348 }
349 ItemHeight::VariableFenwick(tracker) => {
350 let len = self.len();
352 let start = self.scroll_offset.min(len.saturating_sub(1));
353 let total = tracker.total_height_exact();
354 let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
355 if suffix < u64::from(viewport_height) {
356 let anchor = total.saturating_sub(u64::from(viewport_height));
360 len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
361 .max(1)
362 } else {
363 tracker.visible_count(start, viewport_height).max(1)
364 }
365 }
366 };
367
368 let max_offset = self.len().saturating_sub(items_visible);
369 let start = self.scroll_offset.min(max_offset);
370 let end = start.saturating_add(items_visible).min(self.len());
371 self.visible_count.set(items_visible);
372 start..end
373 }
374
375 #[must_use]
377 pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
378 let visible = self.visible_range(viewport_height);
379 let start = visible.start.saturating_sub(self.overscan);
380 let end = visible.end.saturating_add(self.overscan).min(self.len());
381 start..end
382 }
383
384 pub fn scroll(&mut self, delta: i32) {
386 if self.is_empty() {
387 return;
388 }
389 let visible_count = self.visible_count.get();
390 let max_offset = if visible_count > 0 {
391 self.len().saturating_sub(visible_count)
392 } else {
393 self.len().saturating_sub(1)
394 };
395 let clamped_current = self.scroll_offset.min(max_offset);
397 let new_offset = clamped_current
398 .saturating_add_signed(delta as isize)
399 .min(max_offset);
400 self.scroll_offset = new_offset;
401
402 if delta != 0 {
404 self.follow_mode = false;
405 }
406 }
407
408 pub fn scroll_to(&mut self, idx: usize) {
410 self.scroll_offset = idx.min(self.len().saturating_sub(1));
411 self.follow_mode = false;
412 }
413
414 pub fn scroll_to_bottom(&mut self) {
416 if self.is_empty() {
417 self.scroll_offset = 0;
418 return;
419 }
420
421 let visible_count = self.visible_count.get();
422 if visible_count == 0 {
423 self.scroll_offset = usize::MAX;
425 } else if self.len() > visible_count {
426 self.scroll_offset = self.len().saturating_sub(visible_count);
427 } else {
428 self.scroll_offset = 0;
429 }
430 }
431
432 pub fn scroll_to_top(&mut self) {
434 self.scroll_offset = 0;
435 self.follow_mode = false;
436 }
437
438 pub fn scroll_to_start(&mut self) {
440 self.scroll_to_top();
441 }
442
443 pub fn scroll_to_end(&mut self) {
445 self.scroll_to_bottom();
446 self.follow_mode = true;
447 }
448
449 pub fn page_up(&mut self) {
451 let visible_count = self.visible_count.get();
452 if visible_count > 0 {
453 let step = if visible_count > 1 {
454 visible_count - 1
455 } else {
456 1
457 };
458 let delta = i32::try_from(step).unwrap_or(i32::MAX);
459 self.scroll(-delta);
460 }
461 }
462
463 pub fn page_down(&mut self) {
465 let visible_count = self.visible_count.get();
466 if visible_count > 0 {
467 let step = if visible_count > 1 {
468 visible_count - 1
469 } else {
470 1
471 };
472 let delta = i32::try_from(step).unwrap_or(i32::MAX);
473 self.scroll(delta);
474 }
475 }
476
477 pub fn set_follow(&mut self, follow: bool) {
479 self.follow_mode = follow;
480 if follow {
481 self.scroll_to_bottom();
482 }
483 }
484
485 #[must_use]
487 pub fn is_at_bottom(&self) -> bool {
488 let visible_count = self.visible_count.get();
489 if self.len() <= visible_count {
490 true
491 } else {
492 self.scroll_offset >= self.len().saturating_sub(visible_count)
493 }
494 }
495
496 pub fn fling(&mut self, velocity: f32) {
498 self.scroll_velocity = velocity;
499 }
500
501 pub fn tick(&mut self, dt: Duration) {
503 if self.scroll_velocity.abs() > 0.1 {
504 let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
505 if delta != 0 {
506 self.scroll(delta);
507 }
508 self.scroll_velocity *= 0.95;
510 } else {
511 self.scroll_velocity = 0.0;
512 }
513 }
514
515 pub fn set_visible_count(&self, count: usize) {
517 self.visible_count.set(count);
518 }
519
520 #[must_use]
522 pub fn item_height(&self) -> &ItemHeight {
523 &self.item_height
524 }
525
526 pub fn item_height_mut(&mut self) -> &mut ItemHeight {
531 &mut self.item_height
532 }
533}
534
535impl<T> Virtualized<T> {
536 pub fn push(&mut self, item: T) {
538 if let VirtualizedStorage::Owned(items) = &mut self.storage {
539 items.push_back(item);
540 self.sync_height_tracker(false);
541 if self.follow_mode {
542 self.scroll_to_bottom();
543 }
544 }
545 }
546
547 #[must_use = "use the returned item (if any)"]
549 pub fn get(&self, idx: usize) -> Option<&T> {
550 if let VirtualizedStorage::Owned(items) = &self.storage {
551 items.get(idx)
552 } else {
553 None
554 }
555 }
556
557 #[must_use = "use the returned item (if any)"]
559 pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
560 if let VirtualizedStorage::Owned(items) = &mut self.storage {
561 items.get_mut(idx)
562 } else {
563 None
564 }
565 }
566
567 pub fn clear(&mut self) {
569 if let VirtualizedStorage::Owned(items) = &mut self.storage {
570 items.clear();
571 if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
572 tracker.clear();
573 }
574 }
575 self.scroll_offset = 0;
576 }
577
578 pub fn trim_front(&mut self, max: usize) -> usize {
582 if let VirtualizedStorage::Owned(items) = &mut self.storage
583 && items.len() > max
584 {
585 let to_remove = items.len() - max;
586 items.drain(..to_remove);
587 if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
588 tracker.drop_front(to_remove);
589 }
590 self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
592 return to_remove;
593 }
594 0
595 }
596
597 pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
600 match &self.storage {
601 VirtualizedStorage::Owned(items) => Box::new(items.iter()),
602 VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
603 }
604 }
605
606 pub fn set_external_len(&mut self, len: usize) {
608 if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
609 *l = len;
610 self.sync_height_tracker(true);
611 if self.follow_mode {
612 self.scroll_to_bottom();
613 }
614 }
615 }
616}
617
618impl Default for HeightCache {
619 fn default() -> Self {
620 Self::new(1, 1000)
621 }
622}
623
624impl HeightCache {
625 #[must_use]
627 pub fn new(default_height: u16, capacity: usize) -> Self {
628 Self {
629 cache: Vec::new(),
630 base_offset: 0,
631 default_height,
632 capacity,
633 }
634 }
635
636 #[must_use]
638 pub fn get(&self, idx: usize) -> u16 {
639 if idx < self.base_offset {
640 return self.default_height;
641 }
642 let local = idx - self.base_offset;
643 self.cache
644 .get(local)
645 .and_then(|h| *h)
646 .unwrap_or(self.default_height)
647 }
648
649 pub fn set(&mut self, idx: usize, height: u16) {
651 if self.capacity == 0 {
652 return;
653 }
654 if idx < self.base_offset {
655 return;
657 }
658 let mut local = idx - self.base_offset;
659
660 if local + 1 >= self.cache.len() + self.capacity {
663 self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
664 self.cache.clear();
665 local = idx - self.base_offset;
666 }
667
668 if local >= self.cache.len() {
669 self.cache.resize(local + 1, None);
670 }
671 self.cache[local] = Some(height);
672
673 if self.cache.len() > self.capacity {
675 let to_remove = self.cache.len() - self.capacity;
676 self.cache.drain(0..to_remove);
677 self.base_offset += to_remove;
678 }
679 }
680
681 pub fn clear(&mut self) {
683 self.cache.clear();
684 self.base_offset = 0;
685 }
686}
687
688use crate::height_predictor::{HeightPredictor, PredictorConfig};
693
694#[derive(Debug, Clone)]
715pub struct VariableHeightsFenwick {
716 tree: Vec<u64>,
718 default_height: u16,
720 len: usize,
722 measured: Vec<bool>,
724 unmeasured: usize,
726 predictor: Option<HeightPredictor>,
728 fill_height: u16,
731}
732
733impl Default for VariableHeightsFenwick {
734 fn default() -> Self {
735 Self::new(1, 0)
736 }
737}
738
739impl VariableHeightsFenwick {
740 #[must_use]
742 pub fn new(default_height: u16, capacity: usize) -> Self {
743 let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
744 Self {
745 tree,
746 default_height,
747 len: capacity,
748 measured: vec![false; capacity],
749 unmeasured: capacity,
750 predictor: None,
751 fill_height: default_height,
752 }
753 }
754
755 #[must_use]
757 pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
758 Self {
759 tree: Self::build_height_tree(heights.iter().copied()),
760 default_height,
761 len: heights.len(),
762 measured: vec![true; heights.len()],
763 unmeasured: 0,
764 predictor: None,
765 fill_height: default_height,
766 }
767 }
768
769 fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
772 let len = heights.len();
773 assert!(
774 u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
775 "too many items for exact height aggregates"
776 );
777 let mut tree = vec![0; len + 1];
778 for (slot, height) in tree[1..].iter_mut().zip(heights) {
779 *slot = u64::from(height);
780 }
781 for idx in 1..=len {
782 let parent = idx + idx.isolate_lowest_one();
783 if parent <= len {
784 tree[parent] += tree[idx];
785 }
786 }
787 tree
788 }
789
790 fn set_tracked_height(&mut self, idx: usize, height: u16) {
791 let old = self.get(idx);
792 let mut node = idx + 1;
793 while node <= self.len {
794 if height >= old {
795 self.tree[node] += u64::from(height - old);
796 } else {
797 self.tree[node] -= u64::from(old - height);
798 }
799 node += node.isolate_lowest_one();
800 }
801 }
802
803 fn offset_of_item_exact(&self, idx: usize) -> u64 {
804 let mut node = idx.min(self.len);
805 let mut sum = 0;
806 while node > 0 {
807 sum += self.tree[node];
808 node &= node - 1;
809 }
810 sum
811 }
812
813 fn total_height_exact(&self) -> u64 {
814 self.offset_of_item_exact(self.len)
815 }
816
817 fn find_item_at_offset_exact(&self, offset: u64) -> usize {
818 if self.len == 0 || offset == 0 {
820 return 0;
821 }
822 let mut idx = 0;
823 let mut sum = 0;
824 let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
825 while step > 0 {
826 if step <= self.len - idx {
827 let next = idx + step;
828 let prefix = sum + self.tree[next];
829 if prefix <= offset {
830 idx = next;
831 sum = prefix;
832 }
833 }
834 step >>= 1;
835 }
836 idx
837 }
838
839 #[must_use]
849 pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
850 let predictor = HeightPredictor::new(config);
851 self.fill_height = predictor.predict(0).predicted.max(1);
852 self.predictor = Some(predictor);
853 self.refill_unmeasured();
854 self
855 }
856
857 #[must_use]
859 pub fn predictor(&self) -> Option<&HeightPredictor> {
860 self.predictor.as_ref()
861 }
862
863 #[must_use]
866 pub fn predicted_height(&self) -> u16 {
867 self.fill_height
868 }
869
870 #[must_use]
872 pub fn unmeasured_count(&self) -> usize {
873 self.unmeasured
874 }
875
876 #[must_use]
878 pub fn is_measured(&self, idx: usize) -> bool {
879 self.measured.get(idx).copied().unwrap_or(false)
880 }
881
882 fn refill_unmeasured(&mut self) -> usize {
885 let mut rewritten = 0;
886 for idx in 0..self.len {
887 if !self.measured[idx] {
888 self.set_tracked_height(idx, self.fill_height);
889 rewritten += 1;
890 }
891 }
892 rewritten
893 }
894
895 #[must_use]
897 pub fn len(&self) -> usize {
898 self.len
899 }
900
901 #[must_use]
903 pub fn is_empty(&self) -> bool {
904 self.len == 0
905 }
906
907 #[must_use]
909 pub fn default_height(&self) -> u16 {
910 self.default_height
911 }
912
913 #[must_use]
918 pub fn get(&self, idx: usize) -> u16 {
919 if idx >= self.len {
920 return self.fill_height;
921 }
922 (self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
923 }
924
925 pub fn set(&mut self, idx: usize, height: u16) {
929 if idx >= self.len {
930 self.resize(idx.checked_add(1).expect("height index exceeds usize"));
932 }
933 self.set_tracked_height(idx, height);
934 if !self.measured[idx] {
935 self.measured[idx] = true;
936 self.unmeasured -= 1;
937 }
938 if let Some(predictor) = self.predictor.as_mut() {
939 predictor.observe(0, height);
940 let next = predictor.predict(0).predicted.max(1);
941 if next != self.fill_height {
942 self.fill_height = next;
943 self.refill_unmeasured();
944 }
945 }
946 }
947
948 #[must_use]
953 pub fn offset_of_item(&self, idx: usize) -> u32 {
954 self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
955 }
956
957 #[must_use]
967 pub fn find_item_at_offset(&self, offset: u32) -> usize {
968 self.find_item_at_offset_exact(u64::from(offset))
969 }
970
971 #[must_use]
979 pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
980 if self.len == 0 || viewport_height == 0 {
981 return 0;
982 }
983 let start = start_idx.min(self.len);
984 let start_offset = self.offset_of_item_exact(start);
985 let end_offset = start_offset.saturating_add(u64::from(viewport_height));
986
987 let end_idx = self.find_item_at_offset_exact(end_offset);
989
990 if end_idx > start {
992 if end_idx >= self.len {
995 return self.len.saturating_sub(start);
996 }
997 let end_item_start = self.offset_of_item_exact(end_idx);
999 if end_offset > end_item_start {
1000 end_idx - start + 1
1001 } else {
1002 end_idx - start
1003 }
1004 } else {
1005 if viewport_height > 0 && start < self.len {
1007 1
1008 } else {
1009 0
1010 }
1011 }
1012 }
1013
1014 #[must_use]
1016 pub fn total_height(&self) -> u32 {
1017 self.total_height_exact().min(u64::from(u32::MAX)) as u32
1018 }
1019
1020 pub fn resize(&mut self, new_len: usize) {
1025 if new_len == self.len {
1026 return;
1027 }
1028 self.tree = Self::build_height_tree((0..new_len).map(|idx| self.get(idx)));
1029 if new_len > self.len {
1030 self.unmeasured += new_len - self.len;
1031 self.measured.resize(new_len, false);
1032 } else {
1033 let dropped_unmeasured = self.measured[new_len..].iter().filter(|m| !**m).count();
1034 self.unmeasured -= dropped_unmeasured;
1035 self.measured.truncate(new_len);
1036 }
1037 self.len = new_len;
1038 }
1039
1040 pub fn drop_front(&mut self, n: usize) {
1044 if n == 0 {
1045 return;
1046 }
1047 if n >= self.len {
1048 self.clear();
1049 return;
1050 }
1051 let kept: Vec<(u16, bool)> = (n..self.len)
1052 .map(|idx| (self.get(idx), self.is_measured(idx)))
1053 .collect();
1054 self.clear();
1055 self.resize(kept.len());
1056 for (idx, (height, measured)) in kept.into_iter().enumerate() {
1057 if measured {
1058 self.set(idx, height);
1059 }
1060 }
1061 }
1062
1063 pub fn clear(&mut self) {
1065 self.tree = vec![0];
1066 self.len = 0;
1067 self.measured.clear();
1068 self.unmeasured = 0;
1069 }
1070
1071 pub fn rebuild(&mut self, heights: &[u16]) {
1074 self.tree = Self::build_height_tree(heights.iter().copied());
1075 self.len = heights.len();
1076 self.measured = vec![true; heights.len()];
1077 self.unmeasured = 0;
1078 if let Some(predictor) = self.predictor.as_mut() {
1079 for &height in heights {
1080 predictor.observe(0, height);
1081 }
1082 self.fill_height = predictor.predict(0).predicted.max(1);
1083 }
1084 }
1085}
1086
1087pub trait RenderItem {
1095 fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
1105
1106 fn height(&self) -> u16 {
1108 1
1109 }
1110}
1111
1112#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1114pub enum ListHeightMode {
1115 Fixed(u16),
1117 Variable,
1122}
1123
1124#[derive(Debug, Clone)]
1126pub struct VirtualizedListState {
1127 pub selected: Option<usize>,
1129 scroll_offset: usize,
1131 visible_count: usize,
1133 overscan: usize,
1135 follow_mode: bool,
1137 scroll_velocity: f32,
1139 scrollbar_drag_anchor: Option<usize>,
1141 persistence_id: Option<String>,
1143 heights: Option<VariableHeightsFenwick>,
1146}
1147
1148impl Default for VirtualizedListState {
1149 fn default() -> Self {
1150 Self::new()
1151 }
1152}
1153
1154impl VirtualizedListState {
1155 #[must_use]
1157 pub fn new() -> Self {
1158 Self {
1159 selected: None,
1160 scroll_offset: 0,
1161 visible_count: 0,
1162 overscan: 2,
1163 follow_mode: false,
1164 scroll_velocity: 0.0,
1165 scrollbar_drag_anchor: None,
1166 persistence_id: None,
1167 heights: None,
1168 }
1169 }
1170
1171 pub fn measure(&mut self, idx: usize, height: u16) {
1176 if let Some(heights) = self.heights.as_mut()
1177 && idx < heights.len()
1178 {
1179 heights.set(idx, height.max(1));
1180 }
1181 }
1182
1183 #[must_use]
1185 pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
1186 self.heights.as_ref()
1187 }
1188
1189 #[must_use]
1191 pub fn with_overscan(mut self, overscan: usize) -> Self {
1192 self.overscan = overscan;
1193 self
1194 }
1195
1196 #[must_use]
1198 pub fn with_follow(mut self, follow: bool) -> Self {
1199 self.follow_mode = follow;
1200 self
1201 }
1202
1203 #[must_use]
1205 pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
1206 self.persistence_id = Some(id.into());
1207 self
1208 }
1209
1210 #[must_use = "use the persistence id (if any)"]
1212 pub fn persistence_id(&self) -> Option<&str> {
1213 self.persistence_id.as_deref()
1214 }
1215
1216 #[must_use]
1223 pub fn scroll_offset(&self) -> usize {
1224 self.scroll_offset
1225 }
1226
1227 #[must_use]
1232 pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
1233 if total_items == 0 {
1234 return 0;
1235 }
1236 self.scroll_offset.min(total_items.saturating_sub(1))
1237 }
1238
1239 #[must_use]
1241 pub fn visible_count(&self) -> usize {
1242 self.visible_count
1243 }
1244
1245 pub fn scroll(&mut self, delta: i32, total_items: usize) {
1247 if total_items == 0 {
1248 return;
1249 }
1250 let max_offset = if self.visible_count > 0 {
1251 total_items.saturating_sub(self.visible_count)
1252 } else {
1253 total_items.saturating_sub(1)
1254 };
1255 let clamped_current = self.scroll_offset.min(max_offset);
1257 let new_offset = clamped_current
1258 .saturating_add_signed(delta as isize)
1259 .min(max_offset);
1260 self.scroll_offset = new_offset;
1261
1262 if delta != 0 {
1263 self.follow_mode = false;
1264 }
1265 }
1266
1267 pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
1269 self.scroll_offset = idx.min(total_items.saturating_sub(1));
1270 self.follow_mode = false;
1271 }
1272
1273 pub fn scroll_to_top(&mut self) {
1275 self.scroll_offset = 0;
1276 self.follow_mode = false;
1277 }
1278
1279 pub fn scroll_to_bottom(&mut self, total_items: usize) {
1281 if total_items == 0 {
1282 self.scroll_offset = 0;
1283 } else {
1284 self.scroll_offset = usize::MAX;
1287 }
1288 }
1289
1290 pub fn page_up(&mut self, total_items: usize) {
1292 if self.visible_count > 0 {
1293 let step = if self.visible_count > 1 {
1294 self.visible_count - 1
1295 } else {
1296 1
1297 };
1298 let delta = i32::try_from(step).unwrap_or(i32::MAX);
1299 self.scroll(-delta, total_items);
1300 }
1301 }
1302
1303 pub fn page_down(&mut self, total_items: usize) {
1305 if self.visible_count > 0 {
1306 let step = if self.visible_count > 1 {
1307 self.visible_count - 1
1308 } else {
1309 1
1310 };
1311 let delta = i32::try_from(step).unwrap_or(i32::MAX);
1312 self.scroll(delta, total_items);
1313 }
1314 }
1315
1316 pub fn select(&mut self, index: Option<usize>) {
1318 self.selected = index;
1319 }
1320
1321 pub fn select_previous(&mut self, total_items: usize) {
1323 if total_items == 0 {
1324 self.selected = None;
1325 return;
1326 }
1327 self.selected = Some(match self.selected {
1328 Some(i) if i > 0 => i - 1,
1329 Some(_) => 0,
1330 None => 0,
1331 });
1332 }
1333
1334 pub fn select_next(&mut self, total_items: usize) {
1336 if total_items == 0 {
1337 self.selected = None;
1338 return;
1339 }
1340 self.selected = Some(match self.selected {
1341 Some(i) if i < total_items - 1 => i + 1,
1342 Some(i) => i,
1343 None => 0,
1344 });
1345 }
1346
1347 #[must_use]
1349 pub fn is_at_bottom(&self, total_items: usize) -> bool {
1350 if total_items <= self.visible_count {
1351 true
1352 } else {
1353 self.scroll_offset >= total_items - self.visible_count
1354 }
1355 }
1356
1357 pub fn set_follow(&mut self, follow: bool, total_items: usize) {
1359 self.follow_mode = follow;
1360 if follow {
1361 self.scroll_to_bottom(total_items);
1362 }
1363 }
1364
1365 #[must_use]
1367 pub fn follow_mode(&self) -> bool {
1368 self.follow_mode
1369 }
1370
1371 pub fn fling(&mut self, velocity: f32) {
1373 self.scroll_velocity = velocity;
1374 }
1375
1376 pub fn tick(&mut self, dt: Duration, total_items: usize) {
1378 if self.scroll_velocity.abs() > 0.1 {
1379 let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
1380 if delta != 0 {
1381 self.scroll(delta, total_items);
1382 }
1383 self.scroll_velocity *= 0.95;
1384 } else {
1385 self.scroll_velocity = 0.0;
1386 }
1387 }
1388
1389 pub fn handle_mouse(
1394 &mut self,
1395 event: &ftui_core::event::MouseEvent,
1396 hit: Option<(
1397 ftui_render::frame::HitId,
1398 ftui_render::frame::HitRegion,
1399 u64,
1400 )>,
1401 scrollbar_hit_id: ftui_render::frame::HitId,
1402 total_items: usize,
1403 viewport_height: u16,
1404 fixed_item_height: u16,
1405 ) -> crate::mouse::MouseResult {
1406 let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
1408 let mut scrollbar_state =
1409 ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
1410
1411 scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
1413
1414 let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
1415
1416 self.scroll_offset = scrollbar_state.position;
1418 self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
1419
1420 if result == crate::mouse::MouseResult::Scrolled {
1421 self.follow_mode = false;
1422 }
1423
1424 result
1425 }
1426}
1427
1428#[derive(Clone, Debug, Default, PartialEq)]
1437#[cfg_attr(
1438 feature = "state-persistence",
1439 derive(serde::Serialize, serde::Deserialize)
1440)]
1441pub struct VirtualizedListPersistState {
1442 pub selected: Option<usize>,
1444 pub scroll_offset: usize,
1446 pub follow_mode: bool,
1448}
1449
1450impl crate::stateful::Stateful for VirtualizedListState {
1451 type State = VirtualizedListPersistState;
1452
1453 fn state_key(&self) -> crate::stateful::StateKey {
1454 crate::stateful::StateKey::new(
1455 "VirtualizedList",
1456 self.persistence_id.as_deref().unwrap_or("default"),
1457 )
1458 }
1459
1460 fn save_state(&self) -> VirtualizedListPersistState {
1461 VirtualizedListPersistState {
1462 selected: self.selected,
1463 scroll_offset: self.scroll_offset,
1464 follow_mode: self.follow_mode,
1465 }
1466 }
1467
1468 fn restore_state(&mut self, state: VirtualizedListPersistState) {
1469 self.selected = state.selected;
1470 self.scroll_offset = state.scroll_offset;
1471 self.follow_mode = state.follow_mode;
1472 self.scroll_velocity = 0.0;
1474 self.scrollbar_drag_anchor = None;
1475 }
1476}
1477
1478#[derive(Debug)]
1489pub struct VirtualizedList<'a, T> {
1490 items: &'a [T],
1492 style: Style,
1494 highlight_style: Style,
1496 show_scrollbar: bool,
1498 height_mode: ListHeightMode,
1500 hit_id: Option<ftui_render::frame::HitId>,
1502}
1503
1504impl<'a, T> VirtualizedList<'a, T> {
1505 #[must_use]
1507 pub fn new(items: &'a [T]) -> Self {
1508 Self {
1509 items,
1510 style: Style::default(),
1511 highlight_style: Style::default(),
1512 show_scrollbar: true,
1513 height_mode: ListHeightMode::Fixed(1),
1514 hit_id: None,
1515 }
1516 }
1517
1518 #[must_use]
1520 pub fn style(mut self, style: Style) -> Self {
1521 self.style = style;
1522 self
1523 }
1524
1525 #[must_use]
1527 pub fn highlight_style(mut self, style: Style) -> Self {
1528 self.highlight_style = style;
1529 self
1530 }
1531
1532 #[must_use]
1534 pub fn show_scrollbar(mut self, show: bool) -> Self {
1535 self.show_scrollbar = show;
1536 self
1537 }
1538
1539 #[must_use]
1541 pub fn fixed_height(mut self, height: u16) -> Self {
1542 self.height_mode = ListHeightMode::Fixed(height);
1543 self
1544 }
1545
1546 #[must_use]
1549 pub fn variable_heights(mut self) -> Self {
1550 self.height_mode = ListHeightMode::Variable;
1551 self
1552 }
1553
1554 #[must_use]
1556 pub fn height_mode(&self) -> ListHeightMode {
1557 self.height_mode
1558 }
1559
1560 #[must_use]
1562 pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
1563 self.hit_id = Some(id);
1564 self
1565 }
1566}
1567
1568impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
1569 type State = VirtualizedListState;
1570
1571 fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
1572 #[cfg(feature = "tracing")]
1573 let _span = tracing::debug_span!(
1574 "widget_render",
1575 widget = "VirtualizedList",
1576 x = area.x,
1577 y = area.y,
1578 w = area.width,
1579 h = area.height,
1580 items = self.items.len()
1581 )
1582 .entered();
1583
1584 if area.is_empty() {
1585 return;
1586 }
1587
1588 clear_text_area(frame, area, self.style);
1591
1592 let total_items = self.items.len();
1593 if total_items == 0 {
1594 return;
1595 }
1596
1597 let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
1598 self.render_variable(area, frame, state);
1599 return;
1600 };
1601
1602 let fixed_h = fixed_h.max(1);
1604 let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
1606 let fully_visible_items = (area.height / fixed_h) as usize;
1607 let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
1608 let content_width = if needs_scrollbar {
1609 area.width.saturating_sub(1)
1610 } else {
1611 area.width
1612 };
1613
1614 if let Some(selected) = state.selected
1616 && selected >= total_items
1617 {
1618 state.selected = if total_items > 0 {
1620 Some(total_items - 1)
1621 } else {
1622 None
1623 };
1624 }
1625
1626 if let Some(selected) = state.selected {
1628 let vis_count = fully_visible_items.max(1);
1629 if selected >= state.scroll_offset.saturating_add(vis_count) {
1630 state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
1631 } else if selected < state.scroll_offset {
1632 state.scroll_offset = selected;
1633 }
1634 }
1635
1636 let max_offset = if fully_visible_items > 0 {
1638 total_items.saturating_sub(fully_visible_items)
1639 } else {
1640 total_items.saturating_sub(1)
1641 };
1642 state.scroll_offset = state.scroll_offset.min(max_offset);
1643
1644 state.visible_count = fully_visible_items.max(1).min(total_items);
1648
1649 let render_start = state.scroll_offset.saturating_sub(state.overscan);
1651 let render_end = state
1652 .scroll_offset
1653 .saturating_add(items_per_viewport)
1654 .saturating_add(state.overscan)
1655 .min(total_items);
1656
1657 for idx in render_start..render_end {
1659 let relative_idx = if idx >= state.scroll_offset {
1662 i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
1663 } else {
1664 -(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
1666 };
1667
1668 let height_i32 = i32::from(fixed_h);
1669 let y_offset = relative_idx.saturating_mul(height_i32);
1670
1671 if y_offset.saturating_add(height_i32) <= 0 {
1678 continue;
1679 }
1680
1681 if y_offset >= i32::from(area.height) {
1683 break;
1684 }
1685
1686 let skip_rows = if y_offset < 0 {
1689 y_offset.unsigned_abs() as u16
1690 } else {
1691 0
1692 };
1693
1694 let y = i32::from(area.y)
1697 .saturating_add(y_offset)
1698 .clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
1699
1700 if y >= area.bottom() {
1701 break;
1702 }
1703
1704 let visible_height = fixed_h
1705 .saturating_sub(skip_rows)
1706 .min(area.bottom().saturating_sub(y));
1707
1708 if visible_height == 0 {
1709 continue;
1710 }
1711
1712 let row_area = Rect::new(area.x, y, content_width, visible_height);
1713
1714 let is_selected = state.selected == Some(idx);
1715
1716 let row_style = if is_selected {
1717 self.highlight_style.merge(&self.style)
1718 } else {
1719 self.style
1720 };
1721 clear_text_area(frame, row_area, row_style);
1722
1723 self.items[idx].render(row_area, frame, is_selected, skip_rows);
1725 }
1726
1727 if needs_scrollbar {
1729 let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
1730
1731 let mut scrollbar_state =
1732 ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
1733
1734 scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
1736
1737 let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
1738 if let Some(id) = self.hit_id {
1739 scrollbar = scrollbar.hit_id(id);
1740 }
1741 scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
1742 }
1743 }
1744}
1745
1746fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
1750 let mut idx = heights.find_item_at_offset_exact(offset);
1751 if heights.offset_of_item_exact(idx) < offset {
1752 idx += 1;
1753 }
1754 idx.min(heights.len().saturating_sub(1))
1755}
1756
1757fn scrollbar_state_for_rows(
1763 total: u64,
1764 position: u64,
1765 viewport: u16,
1766 capacity: usize,
1767) -> ScrollbarState {
1768 let limit = capacity as u64;
1769 if total <= limit {
1770 return ScrollbarState::new(
1771 total as usize,
1772 position.min(total) as usize,
1773 viewport.into(),
1774 );
1775 }
1776 let scaled_viewport = (u128::from(viewport) * u128::from(limit))
1777 .div_ceil(u128::from(total))
1778 .min(u128::from(limit)) as usize;
1779 let max_position = total.saturating_sub(u64::from(viewport));
1780 let scaled_position = if max_position == 0 {
1781 0
1782 } else {
1783 (u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
1784 / u128::from(max_position)) as usize
1785 };
1786 ScrollbarState::new(capacity, scaled_position, scaled_viewport)
1787}
1788
1789impl<T: RenderItem> VirtualizedList<'_, T> {
1790 fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
1797 let total_items = self.items.len();
1798 let viewport = area.height;
1799 let heights = state
1800 .heights
1801 .get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
1802 if heights.len() != total_items {
1803 heights.resize(total_items);
1804 }
1805
1806 let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
1807 let height = self.items[idx].height().max(1);
1808 if !heights.is_measured(idx) || heights.get(idx) != height {
1809 heights.set(idx, height);
1810 }
1811 };
1812 let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
1815 let mut rows = 0u16;
1816 let mut idx = start;
1817 while idx < total_items && rows < viewport {
1818 measure(heights, idx);
1819 rows = rows.saturating_add(heights.get(idx));
1820 idx += 1;
1821 }
1822 (idx - start).max(1)
1823 };
1824
1825 if let Some(selected) = state.selected
1827 && selected >= total_items
1828 {
1829 state.selected = Some(total_items - 1);
1830 }
1831 if let Some(selected) = state.selected {
1832 measure(heights, selected);
1833 if selected < state.scroll_offset {
1834 state.scroll_offset = selected;
1835 } else {
1836 measure_screenful(heights, state.scroll_offset);
1837 let top = heights.offset_of_item_exact(state.scroll_offset);
1838 let bottom = heights.offset_of_item_exact(selected + 1);
1839 if bottom.saturating_sub(top) > u64::from(viewport) {
1840 let anchor = bottom.saturating_sub(u64::from(viewport));
1841 state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
1842 }
1843 }
1844 }
1845
1846 let total_height = heights.total_height_exact();
1848 let max_start = if total_height > u64::from(viewport) {
1849 first_item_from_offset(heights, total_height - u64::from(viewport))
1850 } else {
1851 0
1852 };
1853 state.scroll_offset = state.scroll_offset.min(max_start);
1854
1855 let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
1856 state.visible_count = visible;
1857
1858 let total_height = heights.total_height_exact();
1859 let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
1860 let content_width = if needs_scrollbar {
1861 area.width.saturating_sub(1)
1862 } else {
1863 area.width
1864 };
1865
1866 let mut y = 0u16;
1867 for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
1868 {
1869 if y >= viewport {
1870 break;
1871 }
1872 let row_h = heights.get(idx).min(viewport - y);
1873 if row_h == 0 {
1874 continue;
1875 }
1876 let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
1877 let is_selected = state.selected == Some(idx);
1878 let row_style = if is_selected {
1879 self.highlight_style.merge(&self.style)
1880 } else {
1881 self.style
1882 };
1883 clear_text_area(frame, row_area, row_style);
1884 self.items[idx].render(row_area, frame, is_selected, 0);
1885 y = y.saturating_add(row_h);
1886 }
1887
1888 if needs_scrollbar {
1889 let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
1890 let mut scrollbar_state = scrollbar_state_for_rows(
1891 total_height,
1892 heights.offset_of_item_exact(state.scroll_offset),
1893 viewport,
1894 usize::MAX,
1895 );
1896 scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
1897 let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
1898 if let Some(id) = self.hit_id {
1899 scrollbar = scrollbar.hit_id(id);
1900 }
1901 scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
1902 }
1903 }
1904}
1905
1906impl RenderItem for String {
1911 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
1912 if area.is_empty() {
1913 return;
1914 }
1915 let max_chars = area.width as usize;
1916 if skip_rows > 0 {
1921 return;
1922 }
1923 for (i, ch) in self.chars().take(max_chars).enumerate() {
1924 frame
1925 .buffer
1926 .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
1927 }
1928 }
1929}
1930
1931impl RenderItem for &str {
1932 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
1933 if area.is_empty() {
1934 return;
1935 }
1936 if skip_rows > 0 {
1937 return;
1938 }
1939 let max_chars = area.width as usize;
1940 for (i, ch) in self.chars().take(max_chars).enumerate() {
1941 frame
1942 .buffer
1943 .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
1944 }
1945 }
1946}
1947
1948#[cfg(test)]
1949mod tests {
1950 use super::*;
1951 use proptest::prelude::*;
1952
1953 fn raw_row_text(frame: &Frame, y: u16) -> String {
1954 let width = frame.buffer.width();
1955 let mut actual = String::new();
1956 for x in 0..width {
1957 let ch = frame
1958 .buffer
1959 .get(x, y)
1960 .and_then(|cell| cell.content.as_char())
1961 .unwrap_or(' ');
1962 actual.push(ch);
1963 }
1964 actual
1965 }
1966
1967 #[test]
1968 fn test_new_virtualized() {
1969 let virt: Virtualized<String> = Virtualized::new(100);
1970 assert_eq!(virt.len(), 0);
1971 assert!(virt.is_empty());
1972 }
1973
1974 #[test]
1975 fn test_push_and_len() {
1976 let mut virt: Virtualized<i32> = Virtualized::new(100);
1977 virt.push(1);
1978 virt.push(2);
1979 virt.push(3);
1980 assert_eq!(virt.len(), 3);
1981 assert!(!virt.is_empty());
1982 }
1983
1984 #[test]
1985 fn test_visible_range_fixed_height() {
1986 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
1987 for i in 0..20 {
1988 virt.push(i);
1989 }
1990 let range = virt.visible_range(20);
1992 assert_eq!(range, 0..10);
1993 }
1994
1995 #[test]
1996 fn test_visible_range_variable_height_clamps() {
1997 let mut cache = HeightCache::new(1, 16);
1998 cache.set(0, 3);
1999 cache.set(1, 3);
2000 cache.set(2, 3);
2001 let mut virt: Virtualized<i32> =
2002 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2003 for i in 0..3 {
2004 virt.push(i);
2005 }
2006 let range = virt.visible_range(5);
2007 assert_eq!(range, 0..2);
2009 }
2010
2011 #[test]
2012 fn test_visible_range_variable_height_exact_fit() {
2013 let mut cache = HeightCache::new(1, 16);
2014 cache.set(0, 2);
2015 cache.set(1, 3);
2016 let mut virt: Virtualized<i32> =
2017 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2018 for i in 0..2 {
2019 virt.push(i);
2020 }
2021 let range = virt.visible_range(5);
2022 assert_eq!(range, 0..2);
2023 }
2024
2025 #[test]
2026 fn test_visible_range_with_scroll() {
2027 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
2028 for i in 0..50 {
2029 virt.push(i);
2030 }
2031 virt.scroll(10);
2032 let range = virt.visible_range(10);
2033 assert_eq!(range, 10..20);
2034 }
2035
2036 #[test]
2037 fn test_visible_range_variable_height_excludes_partial() {
2038 let mut cache = HeightCache::new(1, 16);
2039 cache.set(0, 6);
2040 cache.set(1, 6);
2041 let mut virt: Virtualized<i32> =
2042 Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2043 virt.push(1);
2044 virt.push(2);
2045 virt.push(3);
2046
2047 let range = virt.visible_range(10);
2048 assert_eq!(range, 0..2);
2050 }
2051
2052 #[test]
2053 fn test_visible_range_variable_height_exact_fit_larger() {
2054 let mut cache = HeightCache::new(1, 16);
2055 cache.set(0, 4);
2056 cache.set(1, 6);
2057 let mut virt: Virtualized<i32> =
2058 Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2059 virt.push(1);
2060 virt.push(2);
2061 virt.push(3);
2062
2063 let range = virt.visible_range(10);
2064 assert_eq!(range, 0..2);
2065 }
2066
2067 #[test]
2068 fn test_visible_range_variable_height_default_for_unmeasured() {
2069 let cache = HeightCache::new(2, 16);
2070 let mut virt: Virtualized<i32> =
2071 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2072 for i in 0..3 {
2073 virt.push(i);
2074 }
2075
2076 let range = virt.visible_range(5);
2078 assert_eq!(range, 0..3);
2080 }
2081
2082 #[test]
2083 fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
2084 let mut virt: Virtualized<i32> =
2085 Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2086 for i in 0..20 {
2087 virt.push(i);
2088 }
2089 virt.scroll_to_bottom();
2092 assert_eq!(virt.visible_range(10), 15..20);
2093 }
2094
2095 #[test]
2096 fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
2097 let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
2098 for i in 0..20 {
2099 virt.push(i);
2100 }
2101 virt.scroll_to_bottom();
2104 assert_eq!(virt.visible_range(10), 15..20);
2105 }
2106
2107 #[test]
2108 fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
2109 let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
2112 let mut virt: Virtualized<i32> =
2113 Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
2114 for i in 0..5 {
2115 virt.push(i);
2116 }
2117 virt.scroll_to_bottom();
2118 assert_eq!(virt.visible_range(5), 3..5);
2119 virt.scroll_to_bottom();
2120 assert_eq!(virt.visible_range(6), 2..5);
2121 }
2122
2123 #[test]
2124 fn test_visible_range_variable_near_end_clamps_like_fixed() {
2125 let mut virt: Virtualized<i32> =
2128 Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2129 for i in 0..20 {
2130 virt.push(i);
2131 }
2132 virt.scroll_to(18);
2133 assert_eq!(virt.visible_range(10), 15..20);
2134 }
2135
2136 #[test]
2137 fn test_render_range_with_overscan() {
2138 let mut virt: Virtualized<i32> =
2139 Virtualized::new(100).with_fixed_height(1).with_overscan(2);
2140 for i in 0..50 {
2141 virt.push(i);
2142 }
2143 virt.scroll(10);
2144 let range = virt.render_range(10);
2145 assert_eq!(range, 8..22);
2148 }
2149
2150 #[test]
2151 fn test_scroll_bounds() {
2152 let mut virt: Virtualized<i32> = Virtualized::new(100);
2153 for i in 0..10 {
2154 virt.push(i);
2155 }
2156
2157 virt.scroll(-100);
2159 assert_eq!(virt.scroll_offset(), 0);
2160
2161 virt.scroll(100);
2163 assert_eq!(virt.scroll_offset(), 9);
2164 }
2165
2166 #[test]
2167 fn test_scroll_to() {
2168 let mut virt: Virtualized<i32> = Virtualized::new(100);
2169 for i in 0..20 {
2170 virt.push(i);
2171 }
2172
2173 virt.scroll_to(15);
2174 assert_eq!(virt.scroll_offset(), 15);
2175
2176 virt.scroll_to(100);
2178 assert_eq!(virt.scroll_offset(), 19);
2179 }
2180
2181 #[test]
2182 fn test_follow_mode() {
2183 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
2184 virt.set_visible_count(5);
2185
2186 for i in 0..10 {
2187 virt.push(i);
2188 }
2189
2190 assert!(virt.is_at_bottom());
2192
2193 virt.scroll(-5);
2195 assert!(!virt.follow_mode());
2196 }
2197
2198 #[test]
2199 fn test_scroll_to_start_and_end() {
2200 let mut virt: Virtualized<i32> = Virtualized::new(100);
2201 virt.set_visible_count(5);
2202 for i in 0..20 {
2203 virt.push(i);
2204 }
2205
2206 virt.scroll_to(10);
2208 virt.set_follow(true);
2209 virt.scroll_to_start();
2210 assert_eq!(virt.scroll_offset(), 0);
2211 assert!(!virt.follow_mode());
2212
2213 virt.scroll_to_end();
2215 assert!(virt.is_at_bottom());
2216 assert!(virt.follow_mode());
2217 }
2218
2219 #[test]
2220 fn test_virtualized_page_navigation() {
2221 let mut virt: Virtualized<i32> = Virtualized::new(100);
2222 virt.set_visible_count(5);
2223 for i in 0..30 {
2224 virt.push(i);
2225 }
2226
2227 virt.scroll_to(15);
2228 virt.page_up();
2229 assert_eq!(virt.scroll_offset(), 11);
2231
2232 virt.page_down();
2233 assert_eq!(virt.scroll_offset(), 15);
2234
2235 virt.scroll_to(2);
2237 virt.page_up();
2238 assert_eq!(virt.scroll_offset(), 0);
2239 }
2240
2241 #[test]
2242 fn test_height_cache() {
2243 let mut cache = HeightCache::new(1, 100);
2244
2245 assert_eq!(cache.get(0), 1);
2247 assert_eq!(cache.get(50), 1);
2248
2249 cache.set(5, 3);
2251 assert_eq!(cache.get(5), 3);
2252
2253 assert_eq!(cache.get(4), 1);
2255 assert_eq!(cache.get(6), 1);
2256 }
2257
2258 #[test]
2259 fn test_height_cache_large_index_window() {
2260 let mut cache = HeightCache::new(1, 8);
2261 cache.set(10_000, 4);
2262 assert_eq!(cache.get(10_000), 4);
2263 assert_eq!(cache.get(0), 1);
2264 assert!(cache.cache.len() <= cache.capacity);
2265 }
2266
2267 #[test]
2268 fn test_clear() {
2269 let mut virt: Virtualized<i32> = Virtualized::new(100);
2270 for i in 0..10 {
2271 virt.push(i);
2272 }
2273 virt.scroll(5);
2274
2275 virt.clear();
2276 assert_eq!(virt.len(), 0);
2277 assert_eq!(virt.scroll_offset(), 0);
2278 }
2279
2280 #[test]
2281 fn test_get_item() {
2282 let mut virt: Virtualized<String> = Virtualized::new(100);
2283 virt.push("hello".to_string());
2284 virt.push("world".to_string());
2285
2286 assert_eq!(virt.get(0), Some(&"hello".to_string()));
2287 assert_eq!(virt.get(1), Some(&"world".to_string()));
2288 assert_eq!(virt.get(2), None);
2289 }
2290
2291 #[test]
2292 fn test_external_storage_len() {
2293 let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
2294 assert_eq!(virt.len(), 1000);
2295
2296 virt.set_external_len(2000);
2297 assert_eq!(virt.len(), 2000);
2298 }
2299
2300 #[test]
2301 fn test_momentum_scrolling() {
2302 let mut virt: Virtualized<i32> = Virtualized::new(100);
2303 for i in 0..50 {
2304 virt.push(i);
2305 }
2306
2307 virt.fling(10.0);
2308
2309 virt.tick(Duration::from_millis(100));
2311
2312 assert!(virt.scroll_offset() > 0);
2314 }
2315
2316 #[test]
2321 fn test_virtualized_list_state_new() {
2322 let state = VirtualizedListState::new();
2323 assert_eq!(state.selected, None);
2324 assert_eq!(state.scroll_offset(), 0);
2325 assert_eq!(state.visible_count(), 0);
2326 }
2327
2328 #[test]
2329 fn test_virtualized_list_state_select_next() {
2330 let mut state = VirtualizedListState::new();
2331
2332 state.select_next(10);
2333 assert_eq!(state.selected, Some(0));
2334
2335 state.select_next(10);
2336 assert_eq!(state.selected, Some(1));
2337
2338 state.selected = Some(9);
2340 state.select_next(10);
2341 assert_eq!(state.selected, Some(9));
2342 }
2343
2344 #[test]
2345 fn test_virtualized_list_state_select_previous() {
2346 let mut state = VirtualizedListState::new();
2347 state.selected = Some(5);
2348
2349 state.select_previous(10);
2350 assert_eq!(state.selected, Some(4));
2351
2352 state.selected = Some(0);
2353 state.select_previous(10);
2354 assert_eq!(state.selected, Some(0));
2355 }
2356
2357 #[test]
2358 fn test_virtualized_list_state_scroll() {
2359 let mut state = VirtualizedListState::new();
2360
2361 state.scroll(5, 20);
2362 assert_eq!(state.scroll_offset(), 5);
2363
2364 state.scroll(-3, 20);
2365 assert_eq!(state.scroll_offset(), 2);
2366
2367 state.scroll(-100, 20);
2369 assert_eq!(state.scroll_offset(), 0);
2370
2371 state.scroll(100, 20);
2373 assert_eq!(state.scroll_offset(), 19);
2374 }
2375
2376 #[test]
2377 fn test_virtualized_list_state_follow_mode() {
2378 let mut state = VirtualizedListState::new().with_follow(true);
2379 assert!(state.follow_mode());
2380
2381 state.scroll(5, 20);
2383 assert!(!state.follow_mode());
2384 }
2385
2386 #[test]
2387 fn test_render_item_string() {
2388 let s = String::from("hello");
2390 assert_eq!(s.height(), 1);
2391 }
2392
2393 #[test]
2394 fn test_page_up_down() {
2395 let mut virt: Virtualized<i32> = Virtualized::new(100);
2396 for i in 0..50 {
2397 virt.push(i);
2398 }
2399 virt.set_visible_count(10);
2400
2401 assert_eq!(virt.scroll_offset(), 0);
2403
2404 virt.page_down();
2406 assert_eq!(virt.scroll_offset(), 9);
2407
2408 virt.page_down();
2410 assert_eq!(virt.scroll_offset(), 18);
2411
2412 virt.page_up();
2414 assert_eq!(virt.scroll_offset(), 9);
2415
2416 virt.page_up();
2418 assert_eq!(virt.scroll_offset(), 0);
2419
2420 virt.page_up();
2422 assert_eq!(virt.scroll_offset(), 0);
2423 }
2424
2425 #[test]
2430 fn test_render_scales_with_visible_not_total() {
2431 use ftui_render::grapheme_pool::GraphemePool;
2432 use std::time::Instant;
2433
2434 let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
2436 let small_list = VirtualizedList::new(&small_items);
2437 let mut small_state = VirtualizedListState::new();
2438
2439 let area = Rect::new(0, 0, 80, 24);
2440 let mut pool = GraphemePool::new();
2441 let mut frame = Frame::new(80, 24, &mut pool);
2442
2443 small_list.render(area, &mut frame, &mut small_state);
2445
2446 let start = Instant::now();
2447 for _ in 0..100 {
2448 frame.buffer.clear();
2449 small_list.render(area, &mut frame, &mut small_state);
2450 }
2451 let small_time = start.elapsed();
2452
2453 let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
2455 let large_list = VirtualizedList::new(&large_items);
2456 let mut large_state = VirtualizedListState::new();
2457
2458 large_list.render(area, &mut frame, &mut large_state);
2460
2461 let start = Instant::now();
2462 for _ in 0..100 {
2463 frame.buffer.clear();
2464 large_list.render(area, &mut frame, &mut large_state);
2465 }
2466 let large_time = start.elapsed();
2467
2468 assert!(
2470 large_time < small_time * 3,
2471 "Render does not scale O(visible): 1K={:?}, 100K={:?}",
2472 small_time,
2473 large_time
2474 );
2475 }
2476
2477 #[test]
2478 fn test_scroll_is_constant_time() {
2479 use std::time::Instant;
2480
2481 let mut small: Virtualized<i32> = Virtualized::new(1_000);
2482 for i in 0..1_000 {
2483 small.push(i);
2484 }
2485 small.set_visible_count(24);
2486
2487 let mut large: Virtualized<i32> = Virtualized::new(100_000);
2488 for i in 0..100_000 {
2489 large.push(i);
2490 }
2491 large.set_visible_count(24);
2492
2493 let iterations = 10_000;
2494
2495 for _ in 0..iterations {
2498 small.scroll(1);
2499 small.scroll(-1);
2500 large.scroll(1);
2501 large.scroll(-1);
2502 }
2503
2504 let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
2509 let runs = 5;
2510 let mut best = std::time::Duration::MAX;
2511 for _ in 0..runs {
2512 let start = Instant::now();
2513 for _ in 0..iterations {
2514 v.scroll(1);
2515 v.scroll(-1);
2516 }
2517 best = best.min(start.elapsed());
2518 }
2519 best
2520 };
2521
2522 let small_time = measure(&mut small);
2523 let large_time = measure(&mut large);
2524
2525 let ceiling = small_time
2531 .checked_mul(10)
2532 .unwrap_or(std::time::Duration::MAX);
2533 assert!(
2534 large_time < ceiling,
2535 "Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
2536 small_time,
2537 large_time
2538 );
2539 }
2540
2541 #[test]
2542 fn render_partially_offscreen_top_skips_item() {
2543 use ftui_render::grapheme_pool::GraphemePool;
2544
2545 struct IndexedItem(usize);
2547 impl RenderItem for IndexedItem {
2548 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2549 let ch = char::from_digit(self.0 as u32, 10).unwrap();
2550 for y in area.y..area.bottom() {
2551 frame.buffer.set(area.x, y, Cell::from_char(ch));
2552 }
2553 }
2554 fn height(&self) -> u16 {
2555 2
2556 }
2557 }
2558
2559 let items = vec![
2562 IndexedItem(0),
2563 IndexedItem(1),
2564 IndexedItem(2),
2565 IndexedItem(3),
2566 ];
2567 let list = VirtualizedList::new(&items).fixed_height(2);
2568
2569 let mut state = VirtualizedListState::new().with_overscan(1);
2571 state.scroll_offset = 1; let mut pool = GraphemePool::new();
2574 let mut frame = Frame::new(10, 5, &mut pool);
2575
2576 list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
2578
2579 let cell = frame.buffer.get(0, 0).unwrap();
2587 assert_eq!(cell.content.as_char(), Some('1'));
2588 }
2589
2590 #[test]
2591 fn render_bottom_boundary_clips_partial_item() {
2592 use ftui_render::grapheme_pool::GraphemePool;
2593
2594 struct IndexedItem(u16);
2595 impl RenderItem for IndexedItem {
2596 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2597 let ch = char::from_digit(self.0 as u32, 10).unwrap();
2598 for y in area.y..area.bottom() {
2599 frame.buffer.set(area.x, y, Cell::from_char(ch));
2600 }
2601 }
2602 fn height(&self) -> u16 {
2603 2
2604 }
2605 }
2606
2607 let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
2608 let list = VirtualizedList::new(&items)
2609 .fixed_height(2)
2610 .show_scrollbar(false);
2611 let mut state = VirtualizedListState::new();
2612
2613 let mut pool = GraphemePool::new();
2614 let mut frame = Frame::new(4, 4, &mut pool);
2615
2616 list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
2618
2619 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2620 assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
2621 assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
2622 assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
2624 }
2625
2626 #[test]
2627 fn render_after_fling_advances_visible_rows() {
2628 use ftui_render::grapheme_pool::GraphemePool;
2629
2630 struct IndexedItem(u16);
2631 impl RenderItem for IndexedItem {
2632 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2633 let ch = char::from_digit(self.0 as u32, 10).unwrap();
2634 for y in area.y..area.bottom() {
2635 frame.buffer.set(area.x, y, Cell::from_char(ch));
2636 }
2637 }
2638 }
2639
2640 let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
2641 let list = VirtualizedList::new(&items)
2642 .fixed_height(1)
2643 .show_scrollbar(false);
2644 let mut state = VirtualizedListState::new();
2645
2646 let mut pool = GraphemePool::new();
2647 let mut frame = Frame::new(4, 3, &mut pool);
2648 let area = Rect::new(0, 0, 4, 3);
2649
2650 list.render(area, &mut frame, &mut state);
2652 assert_eq!(state.scroll_offset(), 0);
2653 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2654
2655 state.fling(40.0);
2657 state.tick(Duration::from_millis(100), items.len());
2658 assert_eq!(state.scroll_offset(), 4);
2659
2660 frame.buffer.clear();
2661 list.render(area, &mut frame, &mut state);
2662 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
2663 }
2664
2665 #[test]
2666 fn render_empty_virtualized_list_clears_stale_viewport() {
2667 use ftui_render::grapheme_pool::GraphemePool;
2668
2669 let items: Vec<String> = Vec::new();
2670 let list = VirtualizedList::new(&items).show_scrollbar(false);
2671 let mut state = VirtualizedListState::new();
2672 let mut pool = GraphemePool::new();
2673 let mut frame = Frame::new(6, 3, &mut pool);
2674 let area = Rect::new(0, 0, 6, 3);
2675 frame.buffer.fill(area, Cell::from_char('X'));
2676
2677 list.render(area, &mut frame, &mut state);
2678
2679 assert_eq!(raw_row_text(&frame, 0), " ");
2680 assert_eq!(raw_row_text(&frame, 1), " ");
2681 assert_eq!(raw_row_text(&frame, 2), " ");
2682 }
2683
2684 #[test]
2685 fn render_shorter_virtualized_row_clears_stale_suffix() {
2686 use ftui_render::grapheme_pool::GraphemePool;
2687
2688 let long_items = vec!["Hello".to_string()];
2689 let short_items = vec!["Hi".to_string()];
2690 let area = Rect::new(0, 0, 6, 1);
2691 let mut state = VirtualizedListState::new();
2692 let mut pool = GraphemePool::new();
2693 let mut frame = Frame::new(6, 1, &mut pool);
2694
2695 VirtualizedList::new(&long_items)
2696 .show_scrollbar(false)
2697 .render(area, &mut frame, &mut state);
2698 VirtualizedList::new(&short_items)
2699 .show_scrollbar(false)
2700 .render(area, &mut frame, &mut state);
2701
2702 assert_eq!(raw_row_text(&frame, 0), "Hi ");
2703 }
2704
2705 #[test]
2706 fn test_memory_bounded_by_ring_capacity() {
2707 use crate::log_ring::LogRing;
2708
2709 let mut ring: LogRing<String> = LogRing::new(1_000);
2710
2711 for i in 0..100_000 {
2713 ring.push(format!("Line {}", i));
2714 }
2715
2716 assert_eq!(ring.len(), 1_000);
2718 assert_eq!(ring.total_count(), 100_000);
2719 assert_eq!(ring.first_index(), 99_000);
2720
2721 assert!(ring.get(99_999).is_some());
2723 assert!(ring.get(99_000).is_some());
2724 assert!(ring.get(0).is_none());
2726 assert!(ring.get(98_999).is_none());
2727 }
2728
2729 #[test]
2730 fn test_visible_range_constant_regardless_of_total() {
2731 let mut small: Virtualized<i32> = Virtualized::new(100);
2732 for i in 0..100 {
2733 small.push(i);
2734 }
2735 let small_range = small.visible_range(24);
2736
2737 let mut large: Virtualized<i32> = Virtualized::new(100_000);
2738 for i in 0..100_000 {
2739 large.push(i);
2740 }
2741 let large_range = large.visible_range(24);
2742
2743 assert_eq!(small_range.end - small_range.start, 24);
2745 assert_eq!(large_range.end - large_range.start, 24);
2746 }
2747
2748 #[test]
2749 fn test_virtualized_list_state_page_up_down() {
2750 let mut state = VirtualizedListState::new();
2751 state.visible_count = 10;
2752
2753 state.page_down(50);
2755 assert_eq!(state.scroll_offset(), 9);
2756
2757 state.page_down(50);
2759 assert_eq!(state.scroll_offset(), 18);
2760
2761 state.page_up(50);
2763 assert_eq!(state.scroll_offset(), 9);
2764
2765 state.page_up(50);
2767 assert_eq!(state.scroll_offset(), 0);
2768 }
2769
2770 #[test]
2775 fn test_variable_heights_fenwick_new() {
2776 let tracker = VariableHeightsFenwick::new(2, 10);
2777 assert_eq!(tracker.len(), 10);
2778 assert!(!tracker.is_empty());
2779 assert_eq!(tracker.default_height(), 2);
2780 }
2781
2782 #[test]
2783 fn test_variable_heights_fenwick_empty() {
2784 let tracker = VariableHeightsFenwick::new(1, 0);
2785 assert!(tracker.is_empty());
2786 assert_eq!(tracker.total_height(), 0);
2787 }
2788
2789 #[test]
2790 fn test_variable_heights_fenwick_from_heights() {
2791 let heights = vec![3, 2, 5, 1, 4];
2792 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2793
2794 assert_eq!(tracker.len(), 5);
2795 assert_eq!(tracker.get(0), 3);
2796 assert_eq!(tracker.get(1), 2);
2797 assert_eq!(tracker.get(2), 5);
2798 assert_eq!(tracker.get(3), 1);
2799 assert_eq!(tracker.get(4), 4);
2800 assert_eq!(tracker.total_height(), 15);
2801 }
2802
2803 #[test]
2804 fn test_variable_heights_fenwick_offset_of_item() {
2805 let heights = vec![3, 2, 5, 1, 4];
2807 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2808
2809 assert_eq!(tracker.offset_of_item(0), 0);
2810 assert_eq!(tracker.offset_of_item(1), 3);
2811 assert_eq!(tracker.offset_of_item(2), 5);
2812 assert_eq!(tracker.offset_of_item(3), 10);
2813 assert_eq!(tracker.offset_of_item(4), 11);
2814 assert_eq!(tracker.offset_of_item(5), 15); }
2816
2817 #[test]
2818 fn test_variable_heights_fenwick_find_item_at_offset() {
2819 let heights = vec![3, 2, 5, 1, 4];
2821 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2822
2823 assert_eq!(tracker.find_item_at_offset(0), 0);
2825 assert_eq!(tracker.find_item_at_offset(1), 0);
2827 assert_eq!(tracker.find_item_at_offset(3), 1);
2829 assert_eq!(tracker.find_item_at_offset(5), 2);
2831 assert_eq!(tracker.find_item_at_offset(10), 3);
2833 assert_eq!(tracker.find_item_at_offset(11), 4);
2835 assert_eq!(tracker.find_item_at_offset(15), 5);
2837 }
2838
2839 #[test]
2840 fn fenwick_large_height_totals_do_not_wrap() {
2841 let heights = vec![u16::MAX; 131_072];
2842 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2843 let offset = 4_294_836_224_u32;
2844 assert_eq!(
2845 tracker.find_item_at_offset(offset),
2846 (u64::from(offset) / u64::from(u16::MAX)) as usize,
2847 "a wrapped root aggregate must not skip the entire list"
2848 );
2849 assert_eq!(tracker.total_height(), u32::MAX);
2850 assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
2851 }
2852
2853 #[test]
2854 #[should_panic(expected = "height index exceeds usize")]
2855 fn fenwick_rejects_unrepresentable_index() {
2856 VariableHeightsFenwick::default().set(usize::MAX, 1);
2857 }
2858
2859 #[test]
2860 fn fenwick_large_updates_and_resize_match_u64_oracle() {
2861 fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
2862 let mut prefixes = Vec::with_capacity(heights.len() + 1);
2863 prefixes.push(0u64);
2864 for &height in heights {
2865 prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
2866 }
2867 let total = prefixes.last().copied().unwrap();
2868 assert_eq!(tracker.len(), heights.len());
2869 assert_eq!(tracker.total_height_exact(), total);
2870 assert_eq!(
2871 tracker.total_height(),
2872 total.min(u64::from(u32::MAX)) as u32
2873 );
2874 let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
2875 for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
2876 assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
2877 assert_eq!(
2878 tracker.offset_of_item(idx),
2879 prefixes[idx].min(u64::from(u32::MAX)) as u32
2880 );
2881 queries.extend([
2882 prefixes[idx].saturating_sub(1),
2883 prefixes[idx],
2884 prefixes[idx] + 1,
2885 ]);
2886 }
2887 for offset in queries {
2888 let expected = if offset == 0 {
2889 0
2890 } else {
2891 prefixes[1..].partition_point(|&prefix| prefix <= offset)
2892 };
2893 assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
2894 if let Ok(offset) = u32::try_from(offset) {
2895 assert_eq!(tracker.find_item_at_offset(offset), expected);
2896 }
2897 }
2898 }
2899
2900 for len in [65_536, 65_537, 65_538, 131_072] {
2903 let mut heights = vec![u16::MAX; len];
2904 let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
2905 check(&tracker, &heights);
2906 for idx in [0, 1, 32_768, 65_535, len - 1] {
2907 tracker.set(idx, 0);
2908 heights[idx] = 0;
2909 assert_eq!(tracker.get(idx), 0);
2910 }
2911 check(&tracker, &heights);
2912 tracker.set(0, u16::MAX);
2913 heights[0] = u16::MAX;
2914 tracker.resize(65_536);
2915 heights.truncate(65_536);
2916 check(&tracker, &heights);
2917 tracker.resize(65_540);
2918 heights.resize(65_540, u16::MAX);
2919 check(&tracker, &heights);
2920 }
2921
2922 let mut seed = 0xa076_1d64_78bd_642fu64;
2925 let mut heights: Vec<u16> = (0..131_072)
2926 .map(|_| {
2927 seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
2928 32_768 + ((seed >> 48) as u16 / 2)
2929 })
2930 .collect();
2931 let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
2932 for idx in (0..heights.len()).step_by(997) {
2933 heights[idx] = (idx % 65_536) as u16;
2934 tracker.set(idx, heights[idx]);
2935 assert_eq!(tracker.get(idx), heights[idx]);
2936 }
2937 check(&tracker, &heights);
2938 tracker.drop_front(3);
2939 check(&tracker, &heights[3..]);
2940 heights.fill(u16::MAX);
2941 tracker.rebuild(&heights);
2942 check(&tracker, &heights);
2943 tracker.clear();
2944 check(&tracker, &[]);
2945 tracker.resize(4);
2946 check(&tracker, &[1; 4]);
2947 }
2948
2949 #[test]
2950 fn fenwick_large_visible_range_keeps_tail_reachable() {
2951 let len = 65_548;
2952 let mut virt: Virtualized<()> =
2953 Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
2954 for idx in 65_538..len {
2955 virt.observe_height(idx, 1);
2956 }
2957 virt.scroll_to_bottom();
2958 assert_eq!(virt.visible_range(5), len - 5..len);
2959 virt.scroll_to(len - 8);
2960 assert_eq!(virt.visible_range(5), len - 8..len - 3);
2961 }
2962
2963 #[test]
2964 fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
2965 fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
2966 let scrollbar =
2967 Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
2968 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
2969 let mut frame = Frame::new(1, 21, &mut pool);
2970 scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
2971 (0..21)
2972 .filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
2973 .collect()
2974 }
2975
2976 let capacity = u32::MAX as usize;
2979 let total = 131_072 * u64::from(u16::MAX);
2980 let viewport = 20;
2981 let max_position = total - u64::from(viewport);
2982 for (position, expected_row) in [
2983 (0, 0),
2984 (max_position / 4, 5),
2985 (max_position / 2, 10),
2986 (max_position / 4 * 3, 15),
2987 (max_position, 20),
2988 (total, 20),
2989 ] {
2990 let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
2991 assert_eq!(scaled.content_length, capacity);
2992 assert!(scaled.viewport_length > 0);
2993 assert_eq!(thumb_rows(scaled), vec![expected_row]);
2994 }
2995
2996 let position = u64::from(u32::MAX) + u64::from(u16::MAX);
2997 let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
2998 assert_eq!(thumb_rows(scaled), vec![10]);
2999 let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
3001 assert_eq!(thumb_rows(saturated), vec![20]);
3002
3003 for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
3004 let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
3005 assert_eq!(exact.content_length, total as usize);
3006 assert_eq!(exact.position, position as usize);
3007 assert_eq!(exact.viewport_length, usize::from(viewport));
3008 }
3009 if usize::BITS > 32 {
3010 let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
3011 assert_eq!(exact.content_length as u64, total);
3012 assert_eq!(exact.position as u64, position);
3013 assert_eq!(exact.viewport_length, usize::from(viewport));
3014 }
3015 }
3016
3017 #[test]
3018 fn test_variable_heights_fenwick_visible_count() {
3019 let heights = vec![3, 2, 5, 1, 4];
3021 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3022
3023 assert_eq!(tracker.visible_count(0, 5), 2);
3025
3026 assert_eq!(tracker.visible_count(0, 4), 2);
3028
3029 assert_eq!(tracker.visible_count(0, 10), 3);
3031
3032 assert_eq!(tracker.visible_count(2, 6), 2);
3034 }
3035
3036 #[test]
3037 fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
3038 let heights = vec![1, 1, 1];
3039 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3040
3041 assert_eq!(tracker.visible_count(0, 10), 3);
3043 assert_eq!(tracker.visible_count(1, 10), 2);
3044 assert_eq!(tracker.visible_count(2, 10), 1);
3045 }
3046
3047 #[test]
3048 fn test_variable_heights_fenwick_set() {
3049 let mut tracker = VariableHeightsFenwick::new(1, 5);
3050
3051 assert_eq!(tracker.get(0), 1);
3053 assert_eq!(tracker.total_height(), 5);
3054
3055 tracker.set(2, 10);
3057 assert_eq!(tracker.get(2), 10);
3058 assert_eq!(tracker.total_height(), 14); }
3060
3061 #[test]
3062 fn test_variable_heights_fenwick_resize() {
3063 let mut tracker = VariableHeightsFenwick::new(2, 3);
3064 assert_eq!(tracker.len(), 3);
3065 assert_eq!(tracker.total_height(), 6);
3066
3067 tracker.resize(5);
3069 assert_eq!(tracker.len(), 5);
3070 assert_eq!(tracker.total_height(), 10);
3071 assert_eq!(tracker.get(4), 2);
3072
3073 tracker.resize(2);
3075 assert_eq!(tracker.len(), 2);
3076 assert_eq!(tracker.total_height(), 4);
3077 }
3078
3079 #[test]
3080 fn test_variable_heights_fenwick_point_update_and_range_query() {
3081 fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
3082 tracker
3083 .offset_of_item(right.saturating_add(1))
3084 .saturating_sub(tracker.offset_of_item(left))
3085 }
3086
3087 let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
3088 let mut naive = [2_u32, 4, 1, 3, 5, 2];
3089
3090 tracker.set(2, 7);
3091 naive[2] = 7;
3092 tracker.set(5, 1);
3093 naive[5] = 1;
3094 tracker.set(0, 6);
3095 naive[0] = 6;
3096
3097 let mut running = 0u32;
3098 for (i, value) in naive.iter().enumerate() {
3099 running = running.saturating_add(*value);
3100 assert_eq!(tracker.offset_of_item(i + 1), running);
3101 }
3102
3103 let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
3104 assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
3105 assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
3106 assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
3107 }
3108
3109 proptest! {
3110 #![proptest_config(ProptestConfig::with_cases(96))]
3111
3112 #[test]
3113 fn property_variable_heights_fenwick_prefix_sums_match_naive(
3114 heights in proptest::collection::vec(1u16..=32u16, 1..160)
3115 ) {
3116 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3117
3118 let mut naive_prefix = 0u32;
3119 prop_assert_eq!(tracker.offset_of_item(0), 0);
3120 for (i, height) in heights.iter().enumerate() {
3121 naive_prefix = naive_prefix.saturating_add(u32::from(*height));
3122 prop_assert_eq!(
3123 tracker.offset_of_item(i + 1),
3124 naive_prefix,
3125 "prefix mismatch at index {} for heights {:?}",
3126 i,
3127 heights
3128 );
3129 }
3130 }
3131
3132 #[test]
3133 fn property_variable_heights_fenwick_visible_count_matches_naive(
3134 heights in proptest::collection::vec(1u16..=24u16, 1..128),
3135 start_idx in 0usize..192usize,
3136 viewport_height in 1u16..=120u16
3137 ) {
3138 fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
3139 if heights.is_empty() || viewport_height == 0 {
3140 return 0;
3141 }
3142 let start = start_idx.min(heights.len());
3143 if start >= heights.len() {
3144 return 0;
3145 }
3146
3147 let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
3148 let end_offset = start_offset.saturating_add(u32::from(viewport_height));
3149 let mut count = 0usize;
3150 let mut cursor = start_offset;
3151 for &height in &heights[start..] {
3152 if cursor >= end_offset {
3153 break;
3154 }
3155 count = count.saturating_add(1);
3156 cursor = cursor.saturating_add(u32::from(height));
3157 }
3158
3159 if count == 0 { 1 } else { count }
3160 }
3161
3162 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3163 let expected = naive_visible_count(&heights, start_idx, viewport_height);
3164 let actual = tracker.visible_count(start_idx, viewport_height);
3165 prop_assert_eq!(
3166 actual,
3167 expected,
3168 "visible_count mismatch for start={} viewport={} heights={:?}",
3169 start_idx,
3170 viewport_height,
3171 heights
3172 );
3173 }
3174 }
3175
3176 #[test]
3180 fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
3181 let config = PredictorConfig {
3182 default_height: 1,
3183 prior_mean: 1.0,
3184 prior_strength: 2.0,
3185 ..PredictorConfig::default()
3186 };
3187 let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
3188 assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
3189 assert_eq!(tracker.unmeasured_count(), 10);
3190 assert_eq!(tracker.total_height(), 10);
3191
3192 for idx in 0..3 {
3194 tracker.set(idx, 3);
3195 }
3196 assert_eq!(tracker.predicted_height(), 2);
3197 assert_eq!(tracker.unmeasured_count(), 7);
3198 assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
3199 assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
3200 assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
3201 assert_eq!(tracker.offset_of_item(4), 9 + 2);
3202
3203 for idx in 3..6 {
3205 tracker.set(idx, 3);
3206 }
3207 assert_eq!(tracker.predicted_height(), 3);
3208 assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
3209 assert!(tracker.is_measured(5) && !tracker.is_measured(6));
3210 assert_eq!(
3211 tracker.predictor().map(HeightPredictor::total_measurements),
3212 Some(6)
3213 );
3214
3215 tracker.resize(12);
3217 assert_eq!(tracker.get(11), 3);
3218 assert_eq!(tracker.unmeasured_count(), 6);
3219 assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
3220
3221 tracker.resize(4);
3223 assert_eq!(tracker.unmeasured_count(), 0);
3224 tracker.resize(6);
3225 assert_eq!(tracker.unmeasured_count(), 2);
3226 assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
3227
3228 tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
3230 assert_eq!(tracker.unmeasured_count(), 0);
3231 assert_eq!(tracker.total_height(), 40);
3232 assert!(
3233 tracker.predicted_height() >= 4,
3234 "posterior pulled toward the taller rows"
3235 );
3236
3237 let mut plain = VariableHeightsFenwick::new(2, 4);
3239 plain.set(0, 9);
3240 assert_eq!(plain.predicted_height(), 2);
3241 assert_eq!(plain.get(3), 2);
3242 assert_eq!(plain.unmeasured_count(), 3);
3243 assert!(plain.predictor().is_none());
3244 }
3245
3246 #[test]
3249 fn virtualized_height_prediction_observe_height_trains_the_model() {
3250 let mut virt: Virtualized<i32> = Virtualized::new(100)
3251 .with_fixed_height(1)
3252 .with_height_prediction(PredictorConfig::default());
3253 assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
3254 assert_eq!(virt.unmeasured_item_height(), 1);
3255
3256 for idx in 0..4 {
3258 virt.observe_height(idx, 4);
3259 }
3260 assert_eq!(virt.unmeasured_item_height(), 3);
3261 let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
3262 panic!("expected the Fenwick tracker");
3263 };
3264 assert_eq!(tracker.get(0), 4);
3265 assert_eq!(tracker.len(), 4);
3266 assert_eq!(
3267 tracker.get(40),
3268 3,
3269 "beyond the tracked length: the prediction"
3270 );
3271
3272 let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
3273 fixed.observe_height(0, 9);
3274 assert_eq!(
3275 fixed.unmeasured_item_height(),
3276 2,
3277 "fixed heights ignore observations"
3278 );
3279
3280 let mut linear: Virtualized<i32> =
3281 Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
3282 linear.observe_height(1, 5);
3283 assert_eq!(linear.unmeasured_item_height(), 2);
3284 let ItemHeight::Variable(cache) = linear.item_height() else {
3285 panic!("expected the linear cache");
3286 };
3287 assert_eq!(cache.get(1), 5);
3288 }
3289
3290 #[test]
3291 fn test_virtualized_with_variable_heights_fenwick() {
3292 let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
3293
3294 for i in 0..10 {
3295 virt.push(i);
3296 }
3297
3298 let range = virt.visible_range(6);
3300 assert_eq!(range.end - range.start, 3);
3301 }
3302
3303 #[test]
3304 fn test_variable_heights_fenwick_performance() {
3305 use std::time::Instant;
3306
3307 let n = 100_000;
3309 let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
3310 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3311
3312 let _ = tracker.find_item_at_offset(500_000);
3314 let _ = tracker.offset_of_item(50_000);
3315
3316 let start = Instant::now();
3318 let mut _sink = 0usize;
3319 for i in 0..10_000 {
3320 _sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
3321 }
3322 let find_time = start.elapsed();
3323
3324 let start = Instant::now();
3326 let mut _sink2 = 0u32;
3327 for i in 0..10_000 {
3328 _sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
3329 }
3330 let offset_time = start.elapsed();
3331
3332 eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
3333 eprintln!("10k find_item_at_offset: {:?}", find_time);
3334 eprintln!("10k offset_of_item: {:?}", offset_time);
3335
3336 assert!(
3338 find_time < std::time::Duration::from_millis(50),
3339 "find_item_at_offset too slow: {:?}",
3340 find_time
3341 );
3342 assert!(
3343 offset_time < std::time::Duration::from_millis(50),
3344 "offset_of_item too slow: {:?}",
3345 offset_time
3346 );
3347 }
3348
3349 #[test]
3350 fn test_variable_heights_fenwick_scales_logarithmically() {
3351 use std::time::Instant;
3352
3353 let small_n = 1_000;
3355 let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
3356 let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
3357
3358 let large_n = 100_000;
3360 let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
3361 let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
3362
3363 let iterations = 5_000;
3364
3365 let start = Instant::now();
3367 for i in 0..iterations {
3368 let _ = small_tracker.find_item_at_offset((i * 2) as u32);
3369 }
3370 let small_time = start.elapsed();
3371
3372 let start = Instant::now();
3374 for i in 0..iterations {
3375 let _ = large_tracker.find_item_at_offset((i * 200) as u32);
3376 }
3377 let large_time = start.elapsed();
3378
3379 assert!(
3382 large_time < small_time * 10,
3383 "Not O(log n): small={:?}, large={:?}",
3384 small_time,
3385 large_time
3386 );
3387 }
3388
3389 #[test]
3396 fn new_zero_capacity() {
3397 let virt: Virtualized<i32> = Virtualized::new(0);
3398 assert_eq!(virt.len(), 0);
3399 assert!(virt.is_empty());
3400 assert_eq!(virt.scroll_offset(), 0);
3401 assert_eq!(virt.visible_count(), 0);
3402 assert!(!virt.follow_mode());
3403 }
3404
3405 #[test]
3406 fn external_zero_len_zero_cache() {
3407 let virt: Virtualized<i32> = Virtualized::external(0, 0);
3408 assert_eq!(virt.len(), 0);
3409 assert!(virt.is_empty());
3410 }
3411
3412 #[test]
3413 fn external_storage_returns_none_for_get() {
3414 let virt: Virtualized<i32> = Virtualized::external(100, 10);
3415 assert_eq!(virt.get(0), None);
3416 assert_eq!(virt.get(50), None);
3417 }
3418
3419 #[test]
3420 fn external_storage_returns_none_for_get_mut() {
3421 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3422 assert!(virt.get_mut(0).is_none());
3423 }
3424
3425 #[test]
3426 fn push_on_external_is_noop() {
3427 let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
3428 virt.push(42);
3429 assert_eq!(virt.len(), 5);
3431 }
3432
3433 #[test]
3434 fn iter_on_external_is_empty() {
3435 let virt: Virtualized<i32> = Virtualized::external(100, 10);
3436 assert_eq!(virt.iter().count(), 0);
3437 }
3438
3439 #[test]
3440 fn set_external_len_on_owned_is_noop() {
3441 let mut virt: Virtualized<i32> = Virtualized::new(100);
3442 virt.push(1);
3443 virt.set_external_len(999);
3444 assert_eq!(virt.len(), 1); }
3446
3447 #[test]
3450 fn visible_range_zero_viewport() {
3451 let mut virt: Virtualized<i32> = Virtualized::new(100);
3452 virt.push(1);
3453 let range = virt.visible_range(0);
3454 assert_eq!(range, 0..0);
3455 assert_eq!(virt.visible_count(), 0);
3456 }
3457
3458 #[test]
3459 fn visible_range_empty_container() {
3460 let virt: Virtualized<i32> = Virtualized::new(100);
3461 let range = virt.visible_range(24);
3462 assert_eq!(range, 0..0);
3463 }
3464
3465 #[test]
3466 fn visible_range_fixed_height_zero() {
3467 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
3469 for i in 0..10 {
3470 virt.push(i);
3471 }
3472 let range = virt.visible_range(5);
3473 assert_eq!(range, 0..5);
3475 }
3476
3477 #[test]
3478 fn visible_range_fewer_items_than_viewport() {
3479 let mut virt: Virtualized<i32> = Virtualized::new(100);
3480 for i in 0..3 {
3481 virt.push(i);
3482 }
3483 let range = virt.visible_range(24);
3484 assert_eq!(range, 0..3);
3486 }
3487
3488 #[test]
3489 fn visible_range_single_item() {
3490 let mut virt: Virtualized<i32> = Virtualized::new(100);
3491 virt.push(42);
3492 let range = virt.visible_range(1);
3493 assert_eq!(range, 0..1);
3494 }
3495
3496 #[test]
3499 fn render_range_at_start_clamps_overscan() {
3500 let mut virt: Virtualized<i32> =
3501 Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3502 for i in 0..20 {
3503 virt.push(i);
3504 }
3505 let range = virt.render_range(10);
3507 assert_eq!(range.start, 0);
3508 }
3509
3510 #[test]
3511 fn render_range_at_end_clamps_overscan() {
3512 let mut virt: Virtualized<i32> =
3513 Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3514 for i in 0..20 {
3515 virt.push(i);
3516 }
3517 virt.set_visible_count(10);
3518 virt.scroll_to(10); let range = virt.render_range(10);
3520 assert_eq!(range.end, 20);
3522 }
3523
3524 #[test]
3525 fn render_range_zero_overscan() {
3526 let mut virt: Virtualized<i32> =
3527 Virtualized::new(100).with_fixed_height(1).with_overscan(0);
3528 for i in 0..20 {
3529 virt.push(i);
3530 }
3531 virt.set_visible_count(10);
3532 virt.scroll_to(5);
3533 let range = virt.render_range(10);
3534 let visible = virt.visible_range(10);
3536 assert_eq!(range, visible);
3537 }
3538
3539 #[test]
3542 fn scroll_on_empty_is_noop() {
3543 let mut virt: Virtualized<i32> = Virtualized::new(100);
3544 virt.scroll(10);
3545 assert_eq!(virt.scroll_offset(), 0);
3546 }
3547
3548 #[test]
3549 fn scroll_delta_zero_does_not_disable_follow() {
3550 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3551 virt.push(1);
3552 virt.scroll(0);
3553 assert!(virt.follow_mode());
3555 }
3556
3557 #[test]
3558 fn scroll_negative_beyond_start() {
3559 let mut virt: Virtualized<i32> = Virtualized::new(100);
3560 for i in 0..10 {
3561 virt.push(i);
3562 }
3563 virt.scroll(-1);
3564 assert_eq!(virt.scroll_offset(), 0);
3565 }
3566
3567 #[test]
3568 fn scroll_to_on_empty() {
3569 let mut virt: Virtualized<i32> = Virtualized::new(100);
3570 virt.scroll_to(100);
3572 assert_eq!(virt.scroll_offset(), 0);
3573 }
3574
3575 #[test]
3576 fn scroll_to_top_already_at_top() {
3577 let mut virt: Virtualized<i32> = Virtualized::new(100);
3578 virt.push(1);
3579 virt.scroll_to_top();
3580 assert_eq!(virt.scroll_offset(), 0);
3581 }
3582
3583 #[test]
3584 fn scroll_to_bottom_fewer_items_than_visible() {
3585 let mut virt: Virtualized<i32> = Virtualized::new(100);
3586 virt.set_visible_count(10);
3587 for i in 0..3 {
3588 virt.push(i);
3589 }
3590 virt.scroll_to_bottom();
3591 assert_eq!(virt.scroll_offset(), 0);
3593 }
3594
3595 #[test]
3596 fn scroll_to_bottom_visible_count_zero() {
3597 let mut virt: Virtualized<i32> = Virtualized::new(100);
3598 for i in 0..20 {
3599 virt.push(i);
3600 }
3601 virt.scroll_to_bottom();
3603 assert_eq!(virt.scroll_offset, usize::MAX);
3605 assert_eq!(virt.scroll_offset(), 19);
3607 }
3608
3609 #[test]
3612 fn page_up_visible_count_zero_is_noop() {
3613 let mut virt: Virtualized<i32> = Virtualized::new(100);
3614 for i in 0..20 {
3615 virt.push(i);
3616 }
3617 virt.scroll_to(10);
3618 virt.page_up();
3620 assert_eq!(virt.scroll_offset(), 10);
3621 }
3622
3623 #[test]
3624 fn page_down_visible_count_zero_is_noop() {
3625 let mut virt: Virtualized<i32> = Virtualized::new(100);
3626 for i in 0..20 {
3627 virt.push(i);
3628 }
3629 virt.page_down();
3631 assert_eq!(virt.scroll_offset(), 0);
3632 }
3633
3634 #[test]
3637 fn is_at_bottom_fewer_items_than_visible() {
3638 let mut virt: Virtualized<i32> = Virtualized::new(100);
3639 virt.set_visible_count(10);
3640 for i in 0..3 {
3641 virt.push(i);
3642 }
3643 assert!(virt.is_at_bottom());
3644 }
3645
3646 #[test]
3647 fn is_at_bottom_empty() {
3648 let virt: Virtualized<i32> = Virtualized::new(100);
3649 assert!(virt.is_at_bottom());
3651 }
3652
3653 #[test]
3656 fn trim_front_under_max_returns_zero() {
3657 let mut virt: Virtualized<i32> = Virtualized::new(100);
3658 for i in 0..5 {
3659 virt.push(i);
3660 }
3661 let removed = virt.trim_front(10);
3662 assert_eq!(removed, 0);
3663 assert_eq!(virt.len(), 5);
3664 }
3665
3666 #[test]
3667 fn trim_front_adjusts_scroll_offset() {
3668 let mut virt: Virtualized<i32> = Virtualized::new(100);
3669 for i in 0..20 {
3670 virt.push(i);
3671 }
3672 virt.scroll_to(10);
3673 let removed = virt.trim_front(15);
3674 assert_eq!(removed, 5);
3675 assert_eq!(virt.len(), 15);
3676 assert_eq!(virt.scroll_offset(), 5);
3678 }
3679
3680 #[test]
3681 fn trim_front_scroll_offset_saturates_to_zero() {
3682 let mut virt: Virtualized<i32> = Virtualized::new(100);
3683 for i in 0..20 {
3684 virt.push(i);
3685 }
3686 virt.scroll_to(2);
3687 let removed = virt.trim_front(10);
3688 assert_eq!(removed, 10);
3689 assert_eq!(virt.scroll_offset(), 0);
3691 }
3692
3693 #[test]
3694 fn trim_front_on_external_returns_zero() {
3695 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3696 let removed = virt.trim_front(5);
3697 assert_eq!(removed, 0);
3698 }
3699
3700 #[test]
3701 fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
3702 let mut virt: Virtualized<i32> = Virtualized::new(100);
3703 for i in 0..20 {
3704 virt.push(i);
3705 }
3706
3707 virt.scroll_to_bottom();
3710 assert_eq!(virt.scroll_offset, usize::MAX);
3711
3712 let range = virt.visible_range(10);
3715 assert_eq!(range, 10..20);
3716 assert_eq!(virt.visible_count(), 10);
3717 }
3718
3719 #[test]
3722 fn clear_on_external_resets_scroll() {
3723 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3724 virt.scroll_to(50);
3725 virt.clear();
3726 assert_eq!(virt.scroll_offset(), 0);
3727 assert_eq!(virt.len(), 100);
3729 }
3730
3731 #[test]
3734 fn tick_zero_velocity_is_noop() {
3735 let mut virt: Virtualized<i32> = Virtualized::new(100);
3736 for i in 0..20 {
3737 virt.push(i);
3738 }
3739 virt.tick(Duration::from_millis(100));
3740 assert_eq!(virt.scroll_offset(), 0);
3741 }
3742
3743 #[test]
3744 fn tick_below_threshold_stops_momentum() {
3745 let mut virt: Virtualized<i32> = Virtualized::new(100);
3746 for i in 0..20 {
3747 virt.push(i);
3748 }
3749 virt.fling(0.05); virt.tick(Duration::from_millis(100));
3751 assert_eq!(virt.scroll_offset(), 0);
3753 }
3754
3755 #[test]
3756 fn tick_zero_duration_no_scroll() {
3757 let mut virt: Virtualized<i32> = Virtualized::new(100);
3758 for i in 0..50 {
3759 virt.push(i);
3760 }
3761 virt.fling(100.0);
3762 virt.tick(Duration::ZERO);
3763 assert_eq!(virt.scroll_offset(), 0);
3765 }
3766
3767 #[test]
3768 fn fling_negative_scrolls_up() {
3769 let mut virt: Virtualized<i32> = Virtualized::new(100);
3770 for i in 0..50 {
3771 virt.push(i);
3772 }
3773 virt.scroll(20);
3774 let before = virt.scroll_offset();
3775 virt.fling(-50.0);
3776 virt.tick(Duration::from_millis(100));
3777 assert!(virt.scroll_offset() < before);
3778 }
3779
3780 #[test]
3783 fn follow_mode_auto_scrolls_on_push() {
3784 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3785 virt.set_visible_count(5);
3786 for i in 0..20 {
3787 virt.push(i);
3788 }
3789 assert!(virt.is_at_bottom());
3791 assert_eq!(virt.scroll_offset(), 15); }
3793
3794 #[test]
3795 fn set_follow_false_does_not_scroll() {
3796 let mut virt: Virtualized<i32> = Virtualized::new(100);
3797 virt.set_visible_count(5);
3798 for i in 0..20 {
3799 virt.push(i);
3800 }
3801 virt.scroll_to(5);
3802 virt.set_follow(false);
3803 assert_eq!(virt.scroll_offset(), 5); }
3805
3806 #[test]
3807 fn scroll_to_start_disables_follow() {
3808 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3809 virt.set_visible_count(5);
3810 for i in 0..20 {
3811 virt.push(i);
3812 }
3813 virt.scroll_to_start();
3814 assert!(!virt.follow_mode());
3815 assert_eq!(virt.scroll_offset(), 0);
3816 }
3817
3818 #[test]
3819 fn scroll_to_end_enables_follow() {
3820 let mut virt: Virtualized<i32> = Virtualized::new(100);
3821 virt.set_visible_count(5);
3822 for i in 0..20 {
3823 virt.push(i);
3824 }
3825 assert!(!virt.follow_mode());
3826 virt.scroll_to_end();
3827 assert!(virt.follow_mode());
3828 assert!(virt.is_at_bottom());
3829 }
3830
3831 #[test]
3832 fn external_follow_mode_scrolls_on_set_external_len() {
3833 let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
3834 virt.set_visible_count(5);
3835 virt.set_external_len(20);
3836 assert_eq!(virt.len(), 20);
3837 assert!(virt.is_at_bottom());
3838 }
3839
3840 #[test]
3843 fn builder_chain_all_options() {
3844 let virt: Virtualized<i32> = Virtualized::new(100)
3845 .with_fixed_height(3)
3846 .with_overscan(5)
3847 .with_follow(true);
3848 assert!(virt.follow_mode());
3849 let range = virt.visible_range(9);
3852 assert_eq!(range, 0..0);
3853 }
3854
3855 #[test]
3858 fn height_cache_default() {
3859 let cache = HeightCache::default();
3860 assert_eq!(cache.get(0), 1); assert_eq!(cache.capacity, 1000);
3862 }
3863
3864 #[test]
3865 fn height_cache_get_before_base_offset() {
3866 let mut cache = HeightCache::new(5, 100);
3867 cache.set(200, 10); assert_eq!(cache.get(0), 5);
3871 }
3872
3873 #[test]
3874 fn height_cache_set_before_base_offset_ignored() {
3875 let mut cache = HeightCache::new(5, 100);
3876 cache.set(200, 10);
3877 let base = cache.base_offset;
3878 cache.set(0, 99); assert_eq!(cache.get(0), 5); assert_eq!(cache.base_offset, base); }
3882
3883 #[test]
3884 fn height_cache_capacity_zero_ignores_all_sets() {
3885 let mut cache = HeightCache::new(3, 0);
3886 cache.set(0, 10);
3887 cache.set(5, 20);
3888 assert_eq!(cache.get(0), 3);
3890 assert_eq!(cache.get(5), 3);
3891 }
3892
3893 #[test]
3894 fn height_cache_clear_resets_base() {
3895 let mut cache = HeightCache::new(1, 100);
3896 cache.set(50, 10);
3897 cache.clear();
3898 assert_eq!(cache.base_offset, 0);
3899 assert_eq!(cache.get(50), 1); }
3901
3902 #[test]
3903 fn height_cache_eviction_trims_oldest() {
3904 let mut cache = HeightCache::new(1, 4);
3905 for i in 0..6 {
3907 cache.set(i, (i + 10) as u16);
3908 }
3909 assert!(cache.cache.len() <= cache.capacity);
3911 assert_eq!(cache.get(5), 15);
3913 assert_eq!(cache.get(4), 14);
3914 assert_eq!(cache.get(3), 13);
3915 assert_eq!(cache.get(2), 12);
3916 assert_eq!(cache.get(1), 1);
3918 assert_eq!(cache.get(0), 1);
3919 }
3920
3921 #[test]
3924 fn fenwick_default_is_empty() {
3925 let tracker = VariableHeightsFenwick::default();
3926 assert!(tracker.is_empty());
3927 assert_eq!(tracker.len(), 0);
3928 assert_eq!(tracker.total_height(), 0);
3929 assert_eq!(tracker.default_height(), 1);
3930 }
3931
3932 #[test]
3933 fn fenwick_get_beyond_len_returns_default() {
3934 let tracker = VariableHeightsFenwick::new(3, 5);
3935 assert_eq!(tracker.get(5), 3); assert_eq!(tracker.get(100), 3);
3937 }
3938
3939 #[test]
3940 fn fenwick_set_beyond_len_resizes() {
3941 let mut tracker = VariableHeightsFenwick::new(2, 3);
3942 assert_eq!(tracker.len(), 3);
3943 tracker.set(10, 7);
3944 assert!(tracker.len() > 10);
3945 assert_eq!(tracker.get(10), 7);
3946 }
3947
3948 #[test]
3949 fn fenwick_offset_of_item_zero_always_zero() {
3950 let tracker = VariableHeightsFenwick::new(5, 10);
3951 assert_eq!(tracker.offset_of_item(0), 0);
3952
3953 let empty = VariableHeightsFenwick::new(5, 0);
3954 assert_eq!(empty.offset_of_item(0), 0);
3955 }
3956
3957 #[test]
3958 fn fenwick_find_item_at_offset_empty() {
3959 let tracker = VariableHeightsFenwick::new(1, 0);
3960 assert_eq!(tracker.find_item_at_offset(0), 0);
3961 assert_eq!(tracker.find_item_at_offset(100), 0);
3962 }
3963
3964 #[test]
3965 fn fenwick_visible_count_zero_viewport() {
3966 let tracker = VariableHeightsFenwick::new(2, 10);
3967 assert_eq!(tracker.visible_count(0, 0), 0);
3968 }
3969
3970 #[test]
3971 fn fenwick_visible_count_start_beyond_len() {
3972 let tracker = VariableHeightsFenwick::new(2, 5);
3973 let count = tracker.visible_count(100, 10);
3975 assert_eq!(count, 0);
3977 }
3978
3979 #[test]
3980 fn fenwick_clear_then_operations() {
3981 let mut tracker = VariableHeightsFenwick::new(3, 5);
3982 assert_eq!(tracker.total_height(), 15);
3983 tracker.clear();
3984 assert_eq!(tracker.len(), 0);
3985 assert_eq!(tracker.total_height(), 0);
3986 assert_eq!(tracker.find_item_at_offset(0), 0);
3987 }
3988
3989 #[test]
3990 fn fenwick_rebuild_replaces_data() {
3991 let mut tracker = VariableHeightsFenwick::new(1, 10);
3992 assert_eq!(tracker.total_height(), 10);
3993 tracker.rebuild(&[5, 3, 2]);
3994 assert_eq!(tracker.len(), 3);
3995 assert_eq!(tracker.total_height(), 10);
3996 assert_eq!(tracker.get(0), 5);
3997 assert_eq!(tracker.get(1), 3);
3998 assert_eq!(tracker.get(2), 2);
3999 }
4000
4001 #[test]
4002 fn fenwick_resize_same_size_is_noop() {
4003 let mut tracker = VariableHeightsFenwick::new(2, 5);
4004 tracker.set(2, 10);
4005 tracker.resize(5);
4006 assert_eq!(tracker.get(2), 10);
4008 assert_eq!(tracker.len(), 5);
4009 }
4010
4011 #[test]
4014 fn list_state_default_matches_new() {
4015 let d = VirtualizedListState::default();
4016 let n = VirtualizedListState::new();
4017 assert_eq!(d.selected, n.selected);
4018 assert_eq!(d.scroll_offset(), n.scroll_offset());
4019 assert_eq!(d.visible_count(), n.visible_count());
4020 assert_eq!(d.follow_mode(), n.follow_mode());
4021 }
4022
4023 #[test]
4024 fn list_state_select_next_on_empty() {
4025 let mut state = VirtualizedListState::new();
4026 state.select_next(0);
4027 assert_eq!(state.selected, None);
4028 }
4029
4030 #[test]
4031 fn list_state_select_previous_on_empty() {
4032 let mut state = VirtualizedListState::new();
4033 state.select_previous(0);
4034 assert_eq!(state.selected, None);
4035 }
4036
4037 #[test]
4038 fn list_state_select_previous_from_none() {
4039 let mut state = VirtualizedListState::new();
4040 state.select_previous(10);
4041 assert_eq!(state.selected, Some(0));
4042 }
4043
4044 #[test]
4045 fn list_state_select_next_from_none() {
4046 let mut state = VirtualizedListState::new();
4047 state.select_next(10);
4048 assert_eq!(state.selected, Some(0));
4049 }
4050
4051 #[test]
4052 fn list_state_scroll_zero_items() {
4053 let mut state = VirtualizedListState::new();
4054 state.scroll(10, 0);
4055 assert_eq!(state.scroll_offset(), 0);
4056 }
4057
4058 #[test]
4059 fn list_state_scroll_to_clamps() {
4060 let mut state = VirtualizedListState::new();
4061 state.scroll_to(100, 10);
4062 assert_eq!(state.scroll_offset(), 9);
4063 }
4064
4065 #[test]
4066 fn list_state_scroll_to_bottom_zero_items() {
4067 let mut state = VirtualizedListState::new();
4068 state.scroll_to_bottom(0);
4069 assert_eq!(state.scroll_offset(), 0);
4070 }
4071
4072 #[test]
4073 fn list_state_is_at_bottom_zero_items() {
4074 let state = VirtualizedListState::new();
4075 assert!(state.is_at_bottom(0));
4076 }
4077
4078 #[test]
4079 fn list_state_page_up_visible_count_zero() {
4080 let mut state = VirtualizedListState::new();
4081 state.scroll_offset = 5;
4082 state.page_up(20);
4083 assert_eq!(state.scroll_offset(), 5);
4085 }
4086
4087 #[test]
4088 fn list_state_page_down_visible_count_zero() {
4089 let mut state = VirtualizedListState::new();
4090 state.page_down(20);
4091 assert_eq!(state.scroll_offset(), 0);
4093 }
4094
4095 #[test]
4096 fn list_state_set_follow_false_no_scroll() {
4097 let mut state = VirtualizedListState::new();
4098 state.scroll_offset = 5;
4099 state.set_follow(false, 20);
4100 assert_eq!(state.scroll_offset(), 5); assert!(!state.follow_mode());
4102 }
4103
4104 #[test]
4105 fn list_state_persistence_id() {
4106 let state = VirtualizedListState::new().with_persistence_id("my-list");
4107 assert_eq!(state.persistence_id(), Some("my-list"));
4108 }
4109
4110 #[test]
4111 fn list_state_persistence_id_none() {
4112 let state = VirtualizedListState::new();
4113 assert_eq!(state.persistence_id(), None);
4114 }
4115
4116 #[test]
4117 fn list_state_momentum_tick_zero_items() {
4118 let mut state = VirtualizedListState::new();
4119 state.fling(50.0);
4120 state.tick(Duration::from_millis(100), 0);
4121 assert_eq!(state.scroll_offset(), 0);
4123 }
4124
4125 #[test]
4128 fn persist_state_default() {
4129 let ps = VirtualizedListPersistState::default();
4130 assert_eq!(ps.selected, None);
4131 assert_eq!(ps.scroll_offset, 0);
4132 assert!(!ps.follow_mode);
4133 }
4134
4135 #[test]
4136 fn persist_state_eq() {
4137 let a = VirtualizedListPersistState {
4138 selected: Some(5),
4139 scroll_offset: 10,
4140 follow_mode: true,
4141 };
4142 let b = a.clone();
4143 assert_eq!(a, b);
4144 }
4145
4146 #[test]
4149 fn stateful_state_key_with_persistence_id() {
4150 use crate::stateful::Stateful;
4151 let state = VirtualizedListState::new().with_persistence_id("logs");
4152 let key = state.state_key();
4153 assert_eq!(key.widget_type, "VirtualizedList");
4154 assert_eq!(key.instance_id, "logs");
4155 }
4156
4157 #[test]
4158 fn stateful_state_key_default_instance() {
4159 use crate::stateful::Stateful;
4160 let state = VirtualizedListState::new();
4161 let key = state.state_key();
4162 assert_eq!(key.instance_id, "default");
4163 }
4164
4165 #[test]
4166 fn stateful_save_restore_roundtrip() {
4167 use crate::stateful::Stateful;
4168 let mut state = VirtualizedListState::new();
4169 state.selected = Some(7);
4170 state.scroll_offset = 15;
4171 state.follow_mode = true;
4172 state.scroll_velocity = 42.0; let saved = state.save_state();
4175 assert_eq!(saved.selected, Some(7));
4176 assert_eq!(saved.scroll_offset, 15);
4177 assert!(saved.follow_mode);
4178
4179 let mut restored = VirtualizedListState::new();
4180 restored.scroll_velocity = 99.0;
4181 restored.restore_state(saved);
4182 assert_eq!(restored.selected, Some(7));
4183 assert_eq!(restored.scroll_offset, 15);
4184 assert!(restored.follow_mode);
4185 assert_eq!(restored.scroll_velocity, 0.0);
4187 }
4188
4189 #[test]
4192 fn virtualized_list_builder() {
4193 let items: Vec<String> = vec!["a".into()];
4194 let list = VirtualizedList::new(&items)
4195 .style(Style::default())
4196 .highlight_style(Style::default())
4197 .show_scrollbar(false)
4198 .fixed_height(3);
4199 assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
4200 assert!(!list.show_scrollbar);
4201 assert_eq!(
4202 VirtualizedList::new(&items)
4203 .variable_heights()
4204 .height_mode(),
4205 ListHeightMode::Variable
4206 );
4207 }
4208
4209 #[test]
4214 fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
4215 let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
4216 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4217 panic!("expected the Fenwick tracker, got {:?}", v.item_height());
4218 };
4219 assert_eq!(tracker.len(), 10_000);
4220 assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
4221 for k in 0..100u32 {
4222 let offset = k * 297;
4223 let idx = tracker.find_item_at_offset(offset);
4224 let start = tracker.offset_of_item(idx);
4225 assert!(
4226 start <= offset && offset < start + u32::from(tracker.get(idx)),
4227 "offset {offset} must land inside item {idx} [{start}, +{})",
4228 tracker.get(idx)
4229 );
4230 }
4231
4232 v.scroll_to(9_999);
4233 let range = v.visible_range(24);
4234 assert_eq!(range.end, 10_000);
4235 assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
4236
4237 v.observe_height(5, 7);
4238 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4239 unreachable!()
4240 };
4241 assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
4242 assert!(tracker.is_measured(5));
4243 assert_eq!(v.unmeasured_item_height(), 3);
4244 }
4245
4246 #[test]
4249 fn variable_height_tracker_follows_owned_storage() {
4250 let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
4251 for i in 0..5 {
4252 v.push(format!("row {i}"));
4253 }
4254 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4255 unreachable!()
4256 };
4257 assert_eq!(tracker.len(), 5);
4258 assert_eq!(tracker.total_height(), 10);
4259
4260 v.observe_height(0, 5);
4261 v.observe_height(3, 4);
4262 assert_eq!(v.trim_front(3), 2);
4263 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4264 unreachable!()
4265 };
4266 assert_eq!(tracker.len(), 3);
4267 assert!(!tracker.is_measured(0));
4269 assert!(tracker.is_measured(1));
4270 assert_eq!(tracker.get(1), 4);
4271 assert_eq!(tracker.total_height(), 2 + 4 + 2);
4272
4273 v.clear();
4274 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4275 unreachable!()
4276 };
4277 assert_eq!(tracker.len(), 0);
4278 assert_eq!(tracker.total_height(), 0);
4279 }
4280
4281 #[test]
4285 fn virtualized_list_variable_heights_renders_by_item_height() {
4286 struct Tall(u16);
4287 impl RenderItem for Tall {
4288 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4289 let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
4290 for row in 0..area.height {
4291 frame
4292 .buffer
4293 .set(area.x, area.y + row, Cell::from_char(glyph));
4294 }
4295 }
4296 fn height(&self) -> u16 {
4297 self.0
4298 }
4299 }
4300 let column = |frame: &Frame| -> String {
4301 (0..frame.buffer.height())
4302 .map(|y| {
4303 frame
4304 .buffer
4305 .get(0, y)
4306 .and_then(|cell| cell.content.as_char())
4307 .unwrap_or(' ')
4308 })
4309 .collect()
4310 };
4311
4312 let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
4313 let list = VirtualizedList::new(&items)
4314 .variable_heights()
4315 .show_scrollbar(false);
4316 let mut state = VirtualizedListState::new();
4317 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4318
4319 let mut frame = Frame::new(4, 5, &mut pool);
4320 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4321 assert_eq!(column(&frame), "12233");
4323 assert_eq!(state.visible_count(), 3);
4324 let heights = state.heights().expect("tracker created by render");
4325 assert_eq!(heights.get(1), 2);
4326 assert!(heights.is_measured(2));
4327 assert!(!heights.is_measured(4), "off-screen rows stay unmeasured");
4328 drop(frame);
4329
4330 state.select(Some(4));
4333 let mut frame = Frame::new(4, 5, &mut pool);
4334 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4335 assert_eq!(state.scroll_offset(), 3);
4336 assert_eq!(column(&frame), "122 ");
4337 assert_eq!(state.visible_count(), 2);
4338 let heights = state.heights().expect("tracker");
4339 assert_eq!(heights.total_height(), 9);
4340 assert_eq!(heights.offset_of_item(4), 7);
4341 drop(frame);
4342
4343 state.measure(0, 3);
4345 assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
4346
4347 let list = VirtualizedList::new(&items).variable_heights();
4349 let mut state = VirtualizedListState::new();
4350 let mut frame = Frame::new(4, 5, &mut pool);
4351 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4352 assert!(
4353 frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
4354 "the last column belongs to the scrollbar"
4355 );
4356 assert_eq!(column(&frame), "12233");
4357 }
4358
4359 #[test]
4360 fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
4361 #[derive(Clone, Copy)]
4362 struct Row(u16, char);
4363 impl RenderItem for Row {
4364 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4365 for y in area.y..area.bottom() {
4366 frame.buffer.set(area.x, y, Cell::from_char(self.1));
4367 }
4368 }
4369
4370 fn height(&self) -> u16 {
4371 self.0
4372 }
4373 }
4374
4375 let mut items = vec![Row(u16::MAX, 'X'); 65_538];
4376 items.extend([Row(1, '.'); 9]);
4377 items.push(Row(1, 'Z'));
4378 let list = VirtualizedList::new(&items).variable_heights();
4379 let mut state = VirtualizedListState::new();
4380 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4381 {
4382 let mut frame = Frame::new(4, 5, &mut pool);
4383 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4384 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
4385 }
4386 for (idx, row) in items.iter().enumerate() {
4388 state.measure(idx, row.height());
4389 }
4390 assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
4391 state.select(Some(items.len() - 1));
4392 {
4393 let mut frame = Frame::new(4, 5, &mut pool);
4394 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4395 assert_eq!(state.scroll_offset(), items.len() - 5);
4396 assert_eq!(state.visible_count(), 5);
4397 let column: String = (0..5)
4398 .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
4399 .collect();
4400 assert_eq!(column, "....Z");
4401 assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
4402 }
4403 state.select(None);
4404 state.scroll_to_top();
4405 {
4406 let mut frame = Frame::new(4, 5, &mut pool);
4407 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4408 assert_eq!(state.scroll_offset(), 0);
4409 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
4410 }
4411 state.scroll_to_bottom(items.len());
4412 let mut frame = Frame::new(4, 5, &mut pool);
4413 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4414 assert_eq!(state.scroll_offset(), items.len() - 5);
4415 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
4416 }
4417
4418 #[test]
4421 fn virtualized_storage_debug() {
4422 let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
4423 let dbg = format!("{:?}", storage);
4424 assert!(dbg.contains("Owned"));
4425
4426 let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
4427 len: 100,
4428 cache_capacity: 10,
4429 };
4430 let dbg = format!("{:?}", ext);
4431 assert!(dbg.contains("External"));
4432 }
4433
4434 #[test]
4435 fn test_virtualized_list_handle_mouse_drag_smooth() {
4436 use crate::scrollbar::SCROLLBAR_PART_THUMB;
4437 use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
4438 use ftui_render::frame::{HitId, HitRegion};
4439
4440 let mut state = VirtualizedListState::new();
4441 let scrollbar_hit_id = HitId::new(1);
4442 let total_items = 100;
4443 let viewport_height = 10;
4444 let fixed_height = 1;
4445
4446 let track_len = 10u64;
4452 let track_pos = 0u64;
4453 let hit_data = (SCROLLBAR_PART_THUMB << 56)
4454 | ((track_len & 0x0FFF_FFFF) << 28)
4455 | (track_pos & 0x0FFF_FFFF);
4456
4457 let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
4458 let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
4459
4460 state.handle_mouse(
4461 &down_event,
4462 hit,
4463 scrollbar_hit_id,
4464 total_items,
4465 viewport_height,
4466 fixed_height,
4467 );
4468
4469 assert!(
4470 state.scrollbar_drag_anchor.is_some(),
4471 "Drag anchor should be set on down"
4472 );
4473 assert_eq!(
4474 state.scrollbar_drag_anchor.unwrap(),
4475 0,
4476 "Anchor should be 0 (clicked top of thumb)"
4477 );
4478
4479 let drag_pos = 1u64;
4484 let drag_data = (SCROLLBAR_PART_THUMB << 56)
4485 | ((track_len & 0x0FFF_FFFF) << 28)
4486 | (drag_pos & 0x0FFF_FFFF);
4487 let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
4488 let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
4489
4490 state.handle_mouse(
4491 &drag_event,
4492 drag_hit,
4493 scrollbar_hit_id,
4494 total_items,
4495 viewport_height,
4496 fixed_height,
4497 );
4498
4499 assert_eq!(
4500 state.scroll_offset, 10,
4501 "Scroll offset should update smoothly"
4502 );
4503 }
4504}