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 self.observe_height_in_category(idx, height, 0);
193 }
194
195 pub fn observe_height_in_category(&mut self, idx: usize, height: u16, category: usize) {
198 match &mut self.item_height {
199 ItemHeight::Fixed(_) => {}
200 ItemHeight::Variable(cache) => cache.set(idx, height),
201 ItemHeight::VariableFenwick(tracker) => tracker.set_in_category(idx, height, category),
202 }
203 }
204
205 #[must_use]
207 pub fn predicted_height(&self, category: usize) -> u16 {
208 if let ItemHeight::VariableFenwick(tracker) = &self.item_height
209 && let Some(predictor) = tracker.predictor()
210 {
211 return predictor.predict(category).predicted.max(1);
212 }
213 self.unmeasured_item_height()
214 }
215
216 #[must_use]
218 pub fn predictor_stats(&self) -> Option<PredictorStats> {
219 match &self.item_height {
220 ItemHeight::VariableFenwick(tracker) => tracker.predictor().map(HeightPredictor::stats),
221 _ => None,
222 }
223 }
224
225 #[must_use]
229 pub fn unmeasured_item_height(&self) -> u16 {
230 match &self.item_height {
231 ItemHeight::Fixed(height) => *height,
232 ItemHeight::Variable(cache) => cache.default_height,
233 ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
234 }
235 }
236
237 #[must_use]
245 pub fn with_variable_heights(mut self, default_height: u16) -> Self {
246 let len = self.len();
247 self.item_height =
248 ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
249 self
250 }
251
252 #[must_use]
257 pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
258 self.item_height =
259 ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
260 self
261 }
262
263 fn sync_height_tracker(&mut self, exact: bool) {
268 let len = self.len();
269 if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
270 && (tracker.len() < len || (exact && tracker.len() != len))
271 {
272 tracker.resize(len);
273 }
274 }
275
276 #[must_use]
278 pub fn with_overscan(mut self, overscan: usize) -> Self {
279 self.overscan = overscan;
280 self
281 }
282
283 #[must_use]
285 pub fn with_follow(mut self, follow: bool) -> Self {
286 self.follow_mode = follow;
287 self
288 }
289
290 #[must_use]
292 pub fn len(&self) -> usize {
293 match &self.storage {
294 VirtualizedStorage::Owned(items) => items.len(),
295 VirtualizedStorage::External { len, .. } => *len,
296 }
297 }
298
299 #[must_use]
301 pub fn is_empty(&self) -> bool {
302 self.len() == 0
303 }
304
305 #[must_use]
310 pub fn scroll_offset(&self) -> usize {
311 self.scroll_offset.min(self.len().saturating_sub(1))
312 }
313
314 #[must_use]
316 pub fn visible_count(&self) -> usize {
317 self.visible_count.get()
318 }
319
320 #[must_use]
322 pub fn follow_mode(&self) -> bool {
323 self.follow_mode
324 }
325
326 #[must_use]
328 pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
329 if self.is_empty() || viewport_height == 0 {
330 self.visible_count.set(0);
331 return 0..0;
332 }
333
334 let items_visible = match &self.item_height {
335 ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
337 ItemHeight::Fixed(_) => viewport_height as usize,
338 ItemHeight::Variable(cache) => {
339 let len = self.len();
341 let start = self.scroll_offset.min(len.saturating_sub(1));
342 let mut count = 0;
343 let mut total_height = 0u16;
344 while start + count < len {
345 let next = cache.get(start + count);
346
347 total_height = total_height.saturating_add(next);
349 count += 1;
350
351 if total_height >= viewport_height {
353 break;
354 }
355 }
356 if total_height < viewport_height && start > 0 {
357 count = 0;
363 total_height = 0;
364 while count < len {
365 let next = cache.get(len - 1 - count);
366 total_height = total_height.saturating_add(next);
367 count += 1;
368 if total_height >= viewport_height {
369 break;
370 }
371 }
372 }
373 count
374 }
375 ItemHeight::VariableFenwick(tracker) => {
376 let len = self.len();
378 let start = self.scroll_offset.min(len.saturating_sub(1));
379 let total = tracker.total_height_exact();
380 let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
381 if suffix < u64::from(viewport_height) {
382 let anchor = total.saturating_sub(u64::from(viewport_height));
386 len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
387 .max(1)
388 } else {
389 tracker.visible_count(start, viewport_height).max(1)
390 }
391 }
392 };
393
394 let max_offset = self.len().saturating_sub(items_visible);
395 let start = self.scroll_offset.min(max_offset);
396 let end = start.saturating_add(items_visible).min(self.len());
397 self.visible_count.set(items_visible);
398 start..end
399 }
400
401 #[must_use]
403 pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
404 let visible = self.visible_range(viewport_height);
405 let start = visible.start.saturating_sub(self.overscan);
406 let end = visible.end.saturating_add(self.overscan).min(self.len());
407 start..end
408 }
409
410 pub fn scroll(&mut self, delta: i32) {
412 if self.is_empty() {
413 return;
414 }
415 let visible_count = self.visible_count.get();
426 let max_offset = match self.item_height {
427 ItemHeight::Fixed(_) if visible_count > 0 => self.len().saturating_sub(visible_count),
428 _ => self.len().saturating_sub(1),
429 };
430 let clamped_current = self.scroll_offset.min(max_offset);
432 let new_offset = clamped_current
433 .saturating_add_signed(delta as isize)
434 .min(max_offset);
435 self.scroll_offset = new_offset;
436
437 if delta != 0 {
439 self.follow_mode = false;
440 }
441 }
442
443 pub fn scroll_to(&mut self, idx: usize) {
445 self.scroll_offset = idx.min(self.len().saturating_sub(1));
446 self.follow_mode = false;
447 }
448
449 pub fn scroll_to_bottom(&mut self) {
451 if self.is_empty() {
452 self.scroll_offset = 0;
453 return;
454 }
455
456 if !matches!(self.item_height, ItemHeight::Fixed(_)) {
468 self.scroll_offset = usize::MAX;
469 return;
470 }
471
472 let visible_count = self.visible_count.get();
473 if visible_count == 0 {
474 self.scroll_offset = usize::MAX;
476 } else if self.len() > visible_count {
477 self.scroll_offset = self.len().saturating_sub(visible_count);
478 } else {
479 self.scroll_offset = 0;
480 }
481 }
482
483 pub fn scroll_to_top(&mut self) {
485 self.scroll_offset = 0;
486 self.follow_mode = false;
487 }
488
489 pub fn scroll_to_start(&mut self) {
491 self.scroll_to_top();
492 }
493
494 pub fn scroll_to_end(&mut self) {
496 self.scroll_to_bottom();
497 self.follow_mode = true;
498 }
499
500 pub fn page_up(&mut self) {
502 let visible_count = self.visible_count.get();
503 if visible_count > 0 {
504 let step = if visible_count > 1 {
505 visible_count - 1
506 } else {
507 1
508 };
509 let delta = i32::try_from(step).unwrap_or(i32::MAX);
510 self.scroll(-delta);
511 }
512 }
513
514 pub fn page_down(&mut self) {
516 let visible_count = self.visible_count.get();
517 if visible_count > 0 {
518 let step = if visible_count > 1 {
519 visible_count - 1
520 } else {
521 1
522 };
523 let delta = i32::try_from(step).unwrap_or(i32::MAX);
524 self.scroll(delta);
525 }
526 }
527
528 pub fn set_follow(&mut self, follow: bool) {
530 self.follow_mode = follow;
531 if follow {
532 self.scroll_to_bottom();
533 }
534 }
535
536 #[must_use]
538 pub fn is_at_bottom(&self) -> bool {
539 let visible_count = self.visible_count.get();
540 if self.len() <= visible_count {
541 true
542 } else {
543 self.scroll_offset >= self.len().saturating_sub(visible_count)
544 }
545 }
546
547 pub fn fling(&mut self, velocity: f32) {
549 self.scroll_velocity = velocity;
550 }
551
552 pub fn tick(&mut self, dt: Duration) {
554 if self.scroll_velocity.abs() > 0.1 {
555 let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
556 if delta != 0 {
557 self.scroll(delta);
558 }
559 self.scroll_velocity *= 0.95;
561 } else {
562 self.scroll_velocity = 0.0;
563 }
564 }
565
566 pub fn set_visible_count(&self, count: usize) {
568 self.visible_count.set(count);
569 }
570
571 #[must_use]
573 pub fn item_height(&self) -> &ItemHeight {
574 &self.item_height
575 }
576
577 pub fn item_height_mut(&mut self) -> &mut ItemHeight {
582 &mut self.item_height
583 }
584}
585
586impl<T> Virtualized<T> {
587 pub fn push(&mut self, item: T) {
589 if let VirtualizedStorage::Owned(items) = &mut self.storage {
590 items.push_back(item);
591 self.sync_height_tracker(false);
592 if self.follow_mode {
593 self.scroll_to_bottom();
594 }
595 }
596 }
597
598 #[must_use = "use the returned item (if any)"]
600 pub fn get(&self, idx: usize) -> Option<&T> {
601 if let VirtualizedStorage::Owned(items) = &self.storage {
602 items.get(idx)
603 } else {
604 None
605 }
606 }
607
608 #[must_use = "use the returned item (if any)"]
610 pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
611 if let VirtualizedStorage::Owned(items) = &mut self.storage {
612 items.get_mut(idx)
613 } else {
614 None
615 }
616 }
617
618 pub fn clear(&mut self) {
620 if let VirtualizedStorage::Owned(items) = &mut self.storage {
621 items.clear();
622 match &mut self.item_height {
623 ItemHeight::Fixed(_) => {}
624 ItemHeight::Variable(cache) => cache.clear(),
625 ItemHeight::VariableFenwick(tracker) => tracker.clear(),
626 }
627 }
628 self.scroll_offset = 0;
629 }
630
631 pub fn trim_front(&mut self, max: usize) -> usize {
635 if let VirtualizedStorage::Owned(items) = &mut self.storage
636 && items.len() > max
637 {
638 let to_remove = items.len() - max;
639 items.drain(..to_remove);
640 match &mut self.item_height {
644 ItemHeight::Fixed(_) => {}
645 ItemHeight::Variable(cache) => cache.drop_front(to_remove),
646 ItemHeight::VariableFenwick(tracker) => tracker.drop_front(to_remove),
647 }
648 self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
650 return to_remove;
651 }
652 0
653 }
654
655 pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
658 match &self.storage {
659 VirtualizedStorage::Owned(items) => Box::new(items.iter()),
660 VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
661 }
662 }
663
664 pub fn set_external_len(&mut self, len: usize) {
666 if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
667 *l = len;
668 self.sync_height_tracker(true);
669 if self.follow_mode {
670 self.scroll_to_bottom();
671 }
672 }
673 }
674}
675
676impl Default for HeightCache {
677 fn default() -> Self {
678 Self::new(1, 1000)
679 }
680}
681
682impl HeightCache {
683 #[must_use]
685 pub fn new(default_height: u16, capacity: usize) -> Self {
686 Self {
687 cache: Vec::new(),
688 base_offset: 0,
689 default_height,
690 capacity,
691 }
692 }
693
694 #[must_use]
696 pub fn get(&self, idx: usize) -> u16 {
697 if idx < self.base_offset {
698 return self.default_height;
699 }
700 let local = idx - self.base_offset;
701 self.cache
702 .get(local)
703 .and_then(|h| *h)
704 .unwrap_or(self.default_height)
705 }
706
707 pub fn set(&mut self, idx: usize, height: u16) {
709 if self.capacity == 0 {
710 return;
711 }
712 if idx < self.base_offset {
713 return;
715 }
716 let mut local = idx - self.base_offset;
717
718 if local + 1 >= self.cache.len() + self.capacity {
721 self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
722 self.cache.clear();
723 local = idx - self.base_offset;
724 }
725
726 if local >= self.cache.len() {
727 self.cache.resize(local + 1, None);
728 }
729 self.cache[local] = Some(height);
730
731 if self.cache.len() > self.capacity {
733 let to_remove = self.cache.len() - self.capacity;
734 self.cache.drain(0..to_remove);
735 self.base_offset += to_remove;
736 }
737 }
738
739 pub fn drop_front(&mut self, count: usize) {
745 if count == 0 {
746 return;
747 }
748 if let Some(base) = self.base_offset.checked_sub(count) {
749 self.base_offset = base;
751 return;
752 }
753 let dropped = count - self.base_offset;
754 if dropped >= self.cache.len() {
755 self.cache.clear();
756 } else {
757 self.cache.drain(0..dropped);
758 }
759 self.base_offset = 0;
760 }
761
762 pub fn clear(&mut self) {
764 self.cache.clear();
765 self.base_offset = 0;
766 }
767}
768
769use crate::height_predictor::{HeightPredictor, PredictorConfig, PredictorStats};
774
775#[derive(Debug, Clone)]
796pub struct VariableHeightsFenwick {
797 tree: Vec<u64>,
799 default_height: u16,
801 len: usize,
803 measured: Vec<u64>,
805 unmeasured: usize,
807 predictor: Option<HeightPredictor>,
809 fill_height: u16,
812}
813
814impl Default for VariableHeightsFenwick {
815 fn default() -> Self {
816 Self::new(1, 0)
817 }
818}
819
820impl VariableHeightsFenwick {
821 #[must_use]
823 pub fn new(default_height: u16, capacity: usize) -> Self {
824 let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
825 Self {
826 tree,
827 default_height,
828 len: capacity,
829 measured: vec![0; capacity.div_ceil(64)],
830 unmeasured: capacity,
831 predictor: None,
832 fill_height: default_height,
833 }
834 }
835
836 #[must_use]
838 pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
839 Self {
840 tree: Self::build_height_tree(heights.iter().copied()),
841 default_height,
842 len: heights.len(),
843 measured: Self::all_measured_bits(heights.len()),
844 unmeasured: 0,
845 predictor: None,
846 fill_height: default_height,
847 }
848 }
849
850 fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
853 let len = heights.len();
854 assert!(
855 u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
856 "too many items for exact height aggregates"
857 );
858 let mut tree = vec![0; len + 1];
859 for (slot, height) in tree[1..].iter_mut().zip(heights) {
860 *slot = u64::from(height);
861 }
862 for idx in 1..=len {
863 let parent = idx + idx.isolate_lowest_one();
864 if parent <= len {
865 tree[parent] += tree[idx];
866 }
867 }
868 tree
869 }
870
871 fn all_measured_bits(len: usize) -> Vec<u64> {
872 let mut bits = vec![u64::MAX; len.div_ceil(64)];
873 if !len.is_multiple_of(64) {
874 *bits.last_mut().expect("partial word exists") = (1_u64 << (len % 64)) - 1;
875 }
876 bits
877 }
878
879 fn mark_measured(&mut self, idx: usize) {
880 if !self.is_measured(idx) {
881 self.measured[idx / 64] |= 1_u64 << (idx % 64);
882 self.unmeasured -= 1;
883 }
884 }
885
886 fn set_tracked_height(&mut self, idx: usize, height: u16) {
887 let old = self.get(idx);
888 let mut node = idx + 1;
889 while node <= self.len {
890 if height >= old {
891 self.tree[node] += u64::from(height - old);
892 } else {
893 self.tree[node] -= u64::from(old - height);
894 }
895 node += node.isolate_lowest_one();
896 }
897 }
898
899 fn offset_of_item_exact(&self, idx: usize) -> u64 {
900 let mut node = idx.min(self.len);
901 let mut sum = 0;
902 while node > 0 {
903 sum += self.tree[node];
904 node &= node - 1;
905 }
906 sum
907 }
908
909 fn total_height_exact(&self) -> u64 {
910 self.offset_of_item_exact(self.len)
911 }
912
913 fn find_item_at_offset_exact(&self, offset: u64) -> usize {
914 if self.len == 0 || offset == 0 {
916 return 0;
917 }
918 let mut idx = 0;
919 let mut sum = 0;
920 let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
921 while step > 0 {
922 if step <= self.len - idx {
923 let next = idx + step;
924 let prefix = sum + self.tree[next];
925 if prefix <= offset {
926 idx = next;
927 sum = prefix;
928 }
929 }
930 step >>= 1;
931 }
932 idx
933 }
934
935 #[must_use]
945 pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
946 let predictor = HeightPredictor::new(config);
947 self.fill_height = predictor.predict(0).predicted.max(1);
948 self.predictor = Some(predictor);
949 self.refill_unmeasured();
950 self
951 }
952
953 #[must_use]
955 pub fn predictor(&self) -> Option<&HeightPredictor> {
956 self.predictor.as_ref()
957 }
958
959 #[must_use]
962 pub fn predicted_height(&self) -> u16 {
963 self.fill_height
964 }
965
966 #[must_use]
968 pub fn unmeasured_count(&self) -> usize {
969 self.unmeasured
970 }
971
972 #[must_use]
974 pub fn is_measured(&self, idx: usize) -> bool {
975 idx < self.len && self.measured[idx / 64] & (1_u64 << (idx % 64)) != 0
976 }
977
978 fn refill_unmeasured(&mut self) -> usize {
981 let mut rewritten = 0;
982 for idx in 0..self.len {
983 if !self.is_measured(idx) {
984 self.set_tracked_height(idx, self.fill_height);
985 rewritten += 1;
986 }
987 }
988 rewritten
989 }
990
991 #[must_use]
993 pub fn len(&self) -> usize {
994 self.len
995 }
996
997 #[must_use]
999 pub fn is_empty(&self) -> bool {
1000 self.len == 0
1001 }
1002
1003 #[must_use]
1005 pub fn default_height(&self) -> u16 {
1006 self.default_height
1007 }
1008
1009 #[must_use]
1014 pub fn get(&self, idx: usize) -> u16 {
1015 if idx >= self.len {
1016 return self.fill_height;
1017 }
1018 (self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
1019 }
1020
1021 pub fn set(&mut self, idx: usize, height: u16) {
1025 self.set_in_category(idx, height, 0);
1026 }
1027
1028 pub fn set_in_category(&mut self, idx: usize, height: u16, category: usize) {
1031 if idx >= self.len {
1032 self.resize(idx.checked_add(1).expect("height index exceeds usize"));
1034 }
1035 self.set_tracked_height(idx, height);
1036 self.mark_measured(idx);
1037 if let Some(predictor) = self.predictor.as_mut() {
1038 predictor.observe(category, height);
1039 let next = predictor.predict(0).predicted.max(1);
1040 if next != self.fill_height {
1041 self.fill_height = next;
1042 self.refill_unmeasured();
1043 }
1044 }
1045 }
1046
1047 #[must_use]
1052 pub fn offset_of_item(&self, idx: usize) -> u32 {
1053 self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
1054 }
1055
1056 #[must_use]
1066 pub fn find_item_at_offset(&self, offset: u32) -> usize {
1067 self.find_item_at_offset_exact(u64::from(offset))
1068 }
1069
1070 #[must_use]
1078 pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
1079 if self.len == 0 || viewport_height == 0 {
1080 return 0;
1081 }
1082 let start = start_idx.min(self.len);
1083 let start_offset = self.offset_of_item_exact(start);
1084 let end_offset = start_offset.saturating_add(u64::from(viewport_height));
1085
1086 let end_idx = self.find_item_at_offset_exact(end_offset);
1088
1089 if end_idx > start {
1091 if end_idx >= self.len {
1094 return self.len.saturating_sub(start);
1095 }
1096 let end_item_start = self.offset_of_item_exact(end_idx);
1098 if end_offset > end_item_start {
1099 end_idx - start + 1
1100 } else {
1101 end_idx - start
1102 }
1103 } else {
1104 if viewport_height > 0 && start < self.len {
1106 1
1107 } else {
1108 0
1109 }
1110 }
1111 }
1112
1113 #[must_use]
1115 pub fn total_height(&self) -> u32 {
1116 self.total_height_exact().min(u64::from(u32::MAX)) as u32
1117 }
1118
1119 pub fn resize(&mut self, new_len: usize) {
1124 if new_len == self.len {
1125 return;
1126 }
1127 self.tree = Self::build_height_tree((0..new_len).map(|idx| self.get(idx)));
1128 if new_len > self.len {
1129 self.unmeasured += new_len - self.len;
1130 self.measured.resize(new_len.div_ceil(64), 0);
1131 } else {
1132 let dropped_unmeasured = (new_len..self.len)
1133 .filter(|&idx| !self.is_measured(idx))
1134 .count();
1135 self.unmeasured -= dropped_unmeasured;
1136 self.measured.truncate(new_len.div_ceil(64));
1137 if !new_len.is_multiple_of(64) {
1138 *self.measured.last_mut().expect("partial word exists") &=
1139 (1_u64 << (new_len % 64)) - 1;
1140 }
1141 }
1142 self.len = new_len;
1143 }
1144
1145 pub fn drop_front(&mut self, n: usize) {
1149 if n == 0 {
1150 return;
1151 }
1152 if n >= self.len {
1153 self.clear();
1154 return;
1155 }
1156 let kept: Vec<(u16, bool)> = (n..self.len)
1157 .map(|idx| (self.get(idx), self.is_measured(idx)))
1158 .collect();
1159 self.tree = Self::build_height_tree(kept.iter().map(|&(height, _)| height));
1160 self.len = kept.len();
1161 self.measured = vec![0; self.len.div_ceil(64)];
1162 self.unmeasured = self.len;
1163 for (idx, (_, measured)) in kept.into_iter().enumerate() {
1164 if measured {
1165 self.mark_measured(idx);
1166 }
1167 }
1168 }
1169
1170 pub fn clear(&mut self) {
1172 self.tree = vec![0];
1173 self.len = 0;
1174 self.measured.clear();
1175 self.unmeasured = 0;
1176 }
1177
1178 pub fn rebuild(&mut self, heights: &[u16]) {
1181 self.tree = Self::build_height_tree(heights.iter().copied());
1182 self.len = heights.len();
1183 self.measured = Self::all_measured_bits(heights.len());
1184 self.unmeasured = 0;
1185 if let Some(predictor) = self.predictor.as_mut() {
1186 for &height in heights {
1187 predictor.observe(0, height);
1188 }
1189 self.fill_height = predictor.predict(0).predicted.max(1);
1190 }
1191 }
1192}
1193
1194pub trait RenderItem {
1202 fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
1212
1213 fn height(&self) -> u16 {
1215 1
1216 }
1217
1218 fn category(&self) -> usize {
1221 0
1222 }
1223}
1224
1225impl<T: RenderItem> Virtualized<T> {
1226 pub fn measure(&mut self, idx: usize, height: u16) {
1230 let category = self.get(idx).map_or(0, RenderItem::category);
1231 self.observe_height_in_category(idx, height, category);
1232 }
1233}
1234
1235#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1237pub enum ListHeightMode {
1238 Fixed(u16),
1240 Variable,
1245}
1246
1247#[derive(Debug, Clone)]
1249pub struct VirtualizedListState {
1250 pub selected: Option<usize>,
1252 scroll_offset: usize,
1254 visible_count: usize,
1256 overscan: usize,
1258 follow_mode: bool,
1260 scroll_velocity: f32,
1262 scrollbar_drag_anchor: Option<usize>,
1264 persistence_id: Option<String>,
1266 heights: Option<VariableHeightsFenwick>,
1269}
1270
1271impl Default for VirtualizedListState {
1272 fn default() -> Self {
1273 Self::new()
1274 }
1275}
1276
1277impl VirtualizedListState {
1278 #[must_use]
1280 pub fn new() -> Self {
1281 Self {
1282 selected: None,
1283 scroll_offset: 0,
1284 visible_count: 0,
1285 overscan: 2,
1286 follow_mode: false,
1287 scroll_velocity: 0.0,
1288 scrollbar_drag_anchor: None,
1289 persistence_id: None,
1290 heights: None,
1291 }
1292 }
1293
1294 #[must_use]
1296 pub fn variable(default_height: u16) -> Self {
1297 Self {
1298 heights: Some(VariableHeightsFenwick::new(default_height.max(1), 0)),
1299 ..Self::new()
1300 }
1301 }
1302
1303 #[must_use]
1306 pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
1307 self.heights = Some(
1308 self.heights
1309 .take()
1310 .unwrap_or_default()
1311 .with_predictor(config),
1312 );
1313 self
1314 }
1315
1316 #[must_use]
1318 pub fn predicted_height(&self, category: usize) -> u16 {
1319 self.heights.as_ref().map_or(1, |heights| {
1320 heights
1321 .predictor()
1322 .map_or(heights.default_height(), |predictor| {
1323 predictor.predict(category).predicted.max(1)
1324 })
1325 })
1326 }
1327
1328 #[must_use]
1330 pub fn predictor_stats(&self) -> Option<PredictorStats> {
1331 self.heights
1332 .as_ref()
1333 .and_then(VariableHeightsFenwick::predictor)
1334 .map(HeightPredictor::stats)
1335 }
1336
1337 pub fn measure(&mut self, idx: usize, height: u16) {
1342 self.measure_in_category(idx, height, 0);
1343 }
1344
1345 pub fn measure_in_category(&mut self, idx: usize, height: u16, category: usize) {
1347 if let Some(heights) = self.heights.as_mut()
1348 && idx < heights.len()
1349 {
1350 heights.set_in_category(idx, height.max(1), category);
1351 }
1352 }
1353
1354 #[must_use]
1356 pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
1357 self.heights.as_ref()
1358 }
1359
1360 #[must_use]
1362 pub fn with_overscan(mut self, overscan: usize) -> Self {
1363 self.overscan = overscan;
1364 self
1365 }
1366
1367 #[must_use]
1369 pub fn with_follow(mut self, follow: bool) -> Self {
1370 self.follow_mode = follow;
1371 self
1372 }
1373
1374 #[must_use]
1377 pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
1378 self.persistence_id = Some(id.into());
1379 self
1380 }
1381
1382 #[must_use = "use the persistence id (if any)"]
1384 pub fn persistence_id(&self) -> Option<&str> {
1385 self.persistence_id.as_deref()
1386 }
1387
1388 #[must_use]
1395 pub fn scroll_offset(&self) -> usize {
1396 self.scroll_offset
1397 }
1398
1399 #[must_use]
1404 pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
1405 if total_items == 0 {
1406 return 0;
1407 }
1408 self.scroll_offset.min(total_items.saturating_sub(1))
1409 }
1410
1411 #[must_use]
1413 pub fn visible_count(&self) -> usize {
1414 self.visible_count
1415 }
1416
1417 pub fn scroll(&mut self, delta: i32, total_items: usize) {
1419 if total_items == 0 {
1420 return;
1421 }
1422 let max_offset = if self.visible_count > 0 {
1423 total_items.saturating_sub(self.visible_count)
1424 } else {
1425 total_items.saturating_sub(1)
1426 };
1427 let clamped_current = self.scroll_offset.min(max_offset);
1429 let new_offset = clamped_current
1430 .saturating_add_signed(delta as isize)
1431 .min(max_offset);
1432 self.scroll_offset = new_offset;
1433
1434 if delta != 0 {
1435 self.follow_mode = false;
1436 }
1437 }
1438
1439 pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
1441 self.scroll_offset = idx.min(total_items.saturating_sub(1));
1442 self.follow_mode = false;
1443 }
1444
1445 pub fn scroll_to_top(&mut self) {
1447 self.scroll_offset = 0;
1448 self.follow_mode = false;
1449 }
1450
1451 pub fn scroll_to_bottom(&mut self, total_items: usize) {
1453 if total_items == 0 {
1454 self.scroll_offset = 0;
1455 } else {
1456 self.scroll_offset = usize::MAX;
1459 }
1460 }
1461
1462 pub fn page_up(&mut self, total_items: usize) {
1464 if self.visible_count > 0 {
1465 let step = if self.visible_count > 1 {
1466 self.visible_count - 1
1467 } else {
1468 1
1469 };
1470 let delta = i32::try_from(step).unwrap_or(i32::MAX);
1471 self.scroll(-delta, total_items);
1472 }
1473 }
1474
1475 pub fn page_down(&mut self, total_items: usize) {
1477 if self.visible_count > 0 {
1478 let step = if self.visible_count > 1 {
1479 self.visible_count - 1
1480 } else {
1481 1
1482 };
1483 let delta = i32::try_from(step).unwrap_or(i32::MAX);
1484 self.scroll(delta, total_items);
1485 }
1486 }
1487
1488 pub fn select(&mut self, index: Option<usize>) {
1490 self.selected = index;
1491 }
1492
1493 pub fn select_previous(&mut self, total_items: usize) {
1495 if total_items == 0 {
1496 self.selected = None;
1497 return;
1498 }
1499 self.selected = Some(match self.selected {
1500 Some(i) if i > 0 => i - 1,
1501 Some(_) => 0,
1502 None => 0,
1503 });
1504 }
1505
1506 pub fn select_next(&mut self, total_items: usize) {
1508 if total_items == 0 {
1509 self.selected = None;
1510 return;
1511 }
1512 self.selected = Some(match self.selected {
1513 Some(i) if i < total_items - 1 => i + 1,
1514 Some(i) => i,
1515 None => 0,
1516 });
1517 }
1518
1519 #[must_use]
1521 pub fn is_at_bottom(&self, total_items: usize) -> bool {
1522 if total_items <= self.visible_count {
1523 true
1524 } else {
1525 self.scroll_offset >= total_items - self.visible_count
1526 }
1527 }
1528
1529 pub fn set_follow(&mut self, follow: bool, total_items: usize) {
1531 self.follow_mode = follow;
1532 if follow {
1533 self.scroll_to_bottom(total_items);
1534 }
1535 }
1536
1537 #[must_use]
1539 pub fn follow_mode(&self) -> bool {
1540 self.follow_mode
1541 }
1542
1543 pub fn fling(&mut self, velocity: f32) {
1545 self.scroll_velocity = velocity;
1546 }
1547
1548 pub fn tick(&mut self, dt: Duration, total_items: usize) {
1550 if self.scroll_velocity.abs() > 0.1 {
1551 let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
1552 if delta != 0 {
1553 self.scroll(delta, total_items);
1554 }
1555 self.scroll_velocity *= 0.95;
1556 } else {
1557 self.scroll_velocity = 0.0;
1558 }
1559 }
1560
1561 pub fn handle_mouse(
1571 &mut self,
1572 event: &ftui_core::event::MouseEvent,
1573 hit: Option<(
1574 ftui_render::frame::HitId,
1575 ftui_render::frame::HitRegion,
1576 u64,
1577 )>,
1578 scrollbar_hit_id: ftui_render::frame::HitId,
1579 total_items: usize,
1580 viewport_height: u16,
1581 fixed_item_height: u16,
1582 ) -> crate::mouse::MouseResult {
1583 if let Some(heights) = self.heights.as_ref()
1584 && heights.len() == total_items
1585 && total_items > 0
1586 {
1587 let old_item = self.scroll_offset.min(total_items - 1);
1588 let old_row = heights.offset_of_item_exact(old_item);
1589 let mut scrollbar_state = scrollbar_state_for_rows(
1590 heights.total_height_exact(),
1591 old_row,
1592 viewport_height,
1593 usize::MAX,
1594 );
1595 scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
1596 let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
1597 self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
1598
1599 let total_rows = heights.total_height_exact();
1603 let row = scrollbar_state.position as u64;
1604 let mut item = heights.find_item_at_offset_exact(row);
1605 let start = heights.offset_of_item_exact(item);
1606 if row + u64::from(viewport_height) >= total_rows {
1607 item = total_items - 1;
1608 } else if row.saturating_sub(start) * 2 > u64::from(heights.get(item)) {
1609 item += 1;
1610 }
1611 if row > old_row && item <= old_item {
1613 item = old_item + 1;
1614 } else if row < old_row && item >= old_item {
1615 item = old_item.saturating_sub(1);
1616 }
1617 self.scroll_offset = item.min(total_items - 1);
1618
1619 if result == crate::mouse::MouseResult::Scrolled {
1620 self.follow_mode = false;
1621 }
1622 return result;
1623 }
1624
1625 let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
1627 let mut scrollbar_state =
1628 ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
1629
1630 scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
1632
1633 let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
1634
1635 self.scroll_offset = scrollbar_state.position;
1637 self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
1638
1639 if result == crate::mouse::MouseResult::Scrolled {
1640 self.follow_mode = false;
1641 }
1642
1643 result
1644 }
1645}
1646
1647#[derive(Clone, Debug, Default, PartialEq)]
1656#[cfg_attr(
1657 feature = "state-persistence",
1658 derive(serde::Serialize, serde::Deserialize)
1659)]
1660pub struct VirtualizedListPersistState {
1661 pub selected: Option<usize>,
1663 pub scroll_offset: usize,
1665 pub follow_mode: bool,
1667}
1668
1669impl crate::stateful::Stateful for VirtualizedListState {
1670 type State = VirtualizedListPersistState;
1671
1672 fn state_key(&self) -> Option<crate::stateful::StateKey> {
1673 self.persistence_id
1675 .as_deref()
1676 .map(|id| crate::stateful::StateKey::new("VirtualizedList", id))
1677 }
1678
1679 fn save_state(&self) -> VirtualizedListPersistState {
1680 VirtualizedListPersistState {
1681 selected: self.selected,
1682 scroll_offset: self.scroll_offset,
1683 follow_mode: self.follow_mode,
1684 }
1685 }
1686
1687 fn restore_state(&mut self, state: VirtualizedListPersistState) {
1688 self.selected = state.selected;
1689 self.scroll_offset = state.scroll_offset;
1690 self.follow_mode = state.follow_mode;
1691 self.scroll_velocity = 0.0;
1693 self.scrollbar_drag_anchor = None;
1694 }
1695}
1696
1697#[derive(Debug)]
1710pub struct VirtualizedList<'a, T> {
1711 items: &'a [T],
1713 style: Style,
1715 highlight_style: Style,
1717 show_scrollbar: bool,
1719 height_mode: ListHeightMode,
1721 hit_id: Option<ftui_render::frame::HitId>,
1723}
1724
1725impl<'a, T> VirtualizedList<'a, T> {
1726 #[must_use]
1728 pub fn new(items: &'a [T]) -> Self {
1729 Self {
1730 items,
1731 style: Style::default(),
1732 highlight_style: Style::default(),
1733 show_scrollbar: true,
1734 height_mode: ListHeightMode::Fixed(1),
1735 hit_id: None,
1736 }
1737 }
1738
1739 #[must_use]
1741 pub fn style(mut self, style: Style) -> Self {
1742 self.style = style;
1743 self
1744 }
1745
1746 #[must_use]
1748 pub fn highlight_style(mut self, style: Style) -> Self {
1749 self.highlight_style = style;
1750 self
1751 }
1752
1753 #[must_use]
1755 pub fn show_scrollbar(mut self, show: bool) -> Self {
1756 self.show_scrollbar = show;
1757 self
1758 }
1759
1760 #[must_use]
1762 pub fn fixed_height(mut self, height: u16) -> Self {
1763 self.height_mode = ListHeightMode::Fixed(height);
1764 self
1765 }
1766
1767 #[must_use]
1770 pub fn variable_heights(mut self) -> Self {
1771 self.height_mode = ListHeightMode::Variable;
1772 self
1773 }
1774
1775 #[must_use]
1777 pub fn height_mode(&self) -> ListHeightMode {
1778 self.height_mode
1779 }
1780
1781 #[must_use]
1783 pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
1784 self.hit_id = Some(id);
1785 self
1786 }
1787}
1788
1789impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
1790 type State = VirtualizedListState;
1791
1792 fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
1793 #[cfg(feature = "tracing")]
1794 let _span = tracing::debug_span!(
1795 "widget_render",
1796 widget = "VirtualizedList",
1797 x = area.x,
1798 y = area.y,
1799 w = area.width,
1800 h = area.height,
1801 items = self.items.len(),
1802 height_mode = ?self.height_mode
1803 )
1804 .entered();
1805
1806 if area.is_empty() {
1807 return;
1808 }
1809
1810 clear_text_area(frame, area, self.style);
1813
1814 let total_items = self.items.len();
1815 if total_items == 0 {
1816 state.visible_count = 0;
1817 state.scroll_offset = 0;
1818 if let Some(heights) = state.heights.as_mut() {
1819 heights.clear();
1820 }
1821 return;
1822 }
1823
1824 let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
1825 self.render_variable(area, frame, state);
1826 return;
1827 };
1828
1829 let fixed_h = fixed_h.max(1);
1831 let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
1833 let fully_visible_items = (area.height / fixed_h) as usize;
1834 let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
1835 let content_width = if needs_scrollbar {
1836 area.width.saturating_sub(1)
1837 } else {
1838 area.width
1839 };
1840
1841 if let Some(selected) = state.selected
1843 && selected >= total_items
1844 {
1845 state.selected = if total_items > 0 {
1847 Some(total_items - 1)
1848 } else {
1849 None
1850 };
1851 }
1852
1853 if let Some(selected) = state.selected {
1855 let vis_count = fully_visible_items.max(1);
1856 if selected >= state.scroll_offset.saturating_add(vis_count) {
1857 state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
1858 } else if selected < state.scroll_offset {
1859 state.scroll_offset = selected;
1860 }
1861 }
1862
1863 let max_offset = if fully_visible_items > 0 {
1865 total_items.saturating_sub(fully_visible_items)
1866 } else {
1867 total_items.saturating_sub(1)
1868 };
1869 state.scroll_offset = state.scroll_offset.min(max_offset);
1870
1871 state.visible_count = fully_visible_items.max(1).min(total_items);
1875
1876 let render_start = state.scroll_offset.saturating_sub(state.overscan);
1878 let render_end = state
1879 .scroll_offset
1880 .saturating_add(items_per_viewport)
1881 .saturating_add(state.overscan)
1882 .min(total_items);
1883
1884 for idx in render_start..render_end {
1886 let relative_idx = if idx >= state.scroll_offset {
1889 i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
1890 } else {
1891 -(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
1893 };
1894
1895 let height_i32 = i32::from(fixed_h);
1896 let y_offset = relative_idx.saturating_mul(height_i32);
1897
1898 if y_offset.saturating_add(height_i32) <= 0 {
1905 continue;
1906 }
1907
1908 if y_offset >= i32::from(area.height) {
1910 break;
1911 }
1912
1913 let skip_rows = if y_offset < 0 {
1916 y_offset.unsigned_abs() as u16
1917 } else {
1918 0
1919 };
1920
1921 let y = i32::from(area.y)
1924 .saturating_add(y_offset)
1925 .clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
1926
1927 if y >= area.bottom() {
1928 break;
1929 }
1930
1931 let visible_height = fixed_h
1932 .saturating_sub(skip_rows)
1933 .min(area.bottom().saturating_sub(y));
1934
1935 if visible_height == 0 {
1936 continue;
1937 }
1938
1939 let row_area = Rect::new(area.x, y, content_width, visible_height);
1940
1941 let is_selected = state.selected == Some(idx);
1942
1943 let row_style = if is_selected {
1944 self.highlight_style.merge(&self.style)
1945 } else {
1946 self.style
1947 };
1948 clear_text_area(frame, row_area, row_style);
1949
1950 self.items[idx].render(row_area, frame, is_selected, skip_rows);
1952 }
1953
1954 if needs_scrollbar {
1956 let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
1957
1958 let mut scrollbar_state =
1959 ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
1960
1961 scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
1963
1964 let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
1965 if let Some(id) = self.hit_id {
1966 scrollbar = scrollbar.hit_id(id);
1967 }
1968 scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
1969 }
1970 }
1971}
1972
1973fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
1977 let mut idx = heights.find_item_at_offset_exact(offset);
1978 if heights.offset_of_item_exact(idx) < offset {
1979 idx += 1;
1980 }
1981 idx.min(heights.len().saturating_sub(1))
1982}
1983
1984fn scrollbar_state_for_rows(
1990 total: u64,
1991 position: u64,
1992 viewport: u16,
1993 capacity: usize,
1994) -> ScrollbarState {
1995 let limit = capacity as u64;
1996 if total <= limit {
1997 return ScrollbarState::new(
1998 total as usize,
1999 position.min(total) as usize,
2000 viewport.into(),
2001 );
2002 }
2003 let scaled_viewport = (u128::from(viewport) * u128::from(limit))
2004 .div_ceil(u128::from(total))
2005 .min(u128::from(limit)) as usize;
2006 let max_position = total.saturating_sub(u64::from(viewport));
2007 let scaled_position = if max_position == 0 {
2008 0
2009 } else {
2010 (u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
2011 / u128::from(max_position)) as usize
2012 };
2013 ScrollbarState::new(capacity, scaled_position, scaled_viewport)
2014}
2015
2016impl<T: RenderItem> VirtualizedList<'_, T> {
2017 fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
2025 let total_items = self.items.len();
2026 let viewport = area.height;
2027 let heights = state
2028 .heights
2029 .get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
2030 if heights.len() != total_items {
2031 heights.resize(total_items);
2032 }
2033
2034 let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
2035 let height = self.items[idx].height().max(1);
2036 if !heights.is_measured(idx) || heights.get(idx) != height {
2037 heights.set_in_category(idx, height, self.items[idx].category());
2038 }
2039 };
2040 let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
2043 let mut rows = 0u16;
2044 let mut idx = start;
2045 while idx < total_items && rows < viewport {
2046 measure(heights, idx);
2047 rows = rows.saturating_add(heights.get(idx));
2048 idx += 1;
2049 }
2050 (idx - start).max(1)
2051 };
2052
2053 if let Some(selected) = state.selected
2055 && selected >= total_items
2056 {
2057 state.selected = Some(total_items - 1);
2058 }
2059 if let Some(selected) = state.selected {
2060 measure(heights, selected);
2061 if selected < state.scroll_offset {
2062 state.scroll_offset = selected;
2063 } else {
2064 measure_screenful(heights, state.scroll_offset);
2065 let top = heights.offset_of_item_exact(state.scroll_offset);
2066 let bottom = heights.offset_of_item_exact(selected + 1);
2067 if bottom.saturating_sub(top) > u64::from(viewport) {
2068 let anchor = bottom.saturating_sub(u64::from(viewport));
2069 state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
2070 }
2071 }
2072 }
2073
2074 let mut tail_rows = 0u16;
2078 for idx in (0..total_items).rev() {
2079 if tail_rows >= viewport {
2080 break;
2081 }
2082 measure(heights, idx);
2083 tail_rows = tail_rows.saturating_add(heights.get(idx));
2084 }
2085 let total_height = heights.total_height_exact();
2086 let max_start = if total_height > u64::from(viewport) {
2087 first_item_from_offset(heights, total_height - u64::from(viewport))
2088 } else {
2089 0
2090 };
2091 state.scroll_offset = state.scroll_offset.min(max_start);
2092
2093 let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
2094 state.visible_count = visible;
2095
2096 let total_height = heights.total_height_exact();
2097 let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
2098 let content_width = if needs_scrollbar {
2099 area.width.saturating_sub(1)
2100 } else {
2101 area.width
2102 };
2103
2104 let mut y = 0u16;
2105 for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
2106 {
2107 if y >= viewport {
2108 break;
2109 }
2110 let row_h = heights.get(idx).min(viewport - y);
2111 if row_h == 0 {
2112 continue;
2113 }
2114 let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
2115 let is_selected = state.selected == Some(idx);
2116 let row_style = if is_selected {
2117 self.highlight_style.merge(&self.style)
2118 } else {
2119 self.style
2120 };
2121 clear_text_area(frame, row_area, row_style);
2122 self.items[idx].render(row_area, frame, is_selected, 0);
2123 y = y.saturating_add(row_h);
2124 }
2125
2126 if needs_scrollbar {
2127 let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
2128 let mut scrollbar_state = scrollbar_state_for_rows(
2129 total_height,
2130 heights.offset_of_item_exact(state.scroll_offset),
2131 viewport,
2132 usize::MAX,
2133 );
2134 scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
2135 let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
2136 if let Some(id) = self.hit_id {
2137 scrollbar = scrollbar.hit_id(id);
2138 }
2139 scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
2140 }
2141 }
2142}
2143
2144impl RenderItem for String {
2149 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2150 if area.is_empty() {
2151 return;
2152 }
2153 let max_chars = area.width as usize;
2154 if skip_rows > 0 {
2159 return;
2160 }
2161 for (i, ch) in self.chars().take(max_chars).enumerate() {
2162 frame
2163 .buffer
2164 .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2165 }
2166 }
2167}
2168
2169impl RenderItem for &str {
2170 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2171 if area.is_empty() {
2172 return;
2173 }
2174 if skip_rows > 0 {
2175 return;
2176 }
2177 let max_chars = area.width as usize;
2178 for (i, ch) in self.chars().take(max_chars).enumerate() {
2179 frame
2180 .buffer
2181 .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2182 }
2183 }
2184}
2185
2186#[cfg(test)]
2187mod tests {
2188 use super::*;
2189 use proptest::prelude::*;
2190
2191 fn raw_row_text(frame: &Frame, y: u16) -> String {
2192 let width = frame.buffer.width();
2193 let mut actual = String::new();
2194 for x in 0..width {
2195 let ch = frame
2196 .buffer
2197 .get(x, y)
2198 .and_then(|cell| cell.content.as_char())
2199 .unwrap_or(' ');
2200 actual.push(ch);
2201 }
2202 actual
2203 }
2204
2205 #[test]
2206 fn test_new_virtualized() {
2207 let virt: Virtualized<String> = Virtualized::new(100);
2208 assert_eq!(virt.len(), 0);
2209 assert!(virt.is_empty());
2210 }
2211
2212 #[test]
2213 fn test_push_and_len() {
2214 let mut virt: Virtualized<i32> = Virtualized::new(100);
2215 virt.push(1);
2216 virt.push(2);
2217 virt.push(3);
2218 assert_eq!(virt.len(), 3);
2219 assert!(!virt.is_empty());
2220 }
2221
2222 #[test]
2223 fn test_visible_range_fixed_height() {
2224 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
2225 for i in 0..20 {
2226 virt.push(i);
2227 }
2228 let range = virt.visible_range(20);
2230 assert_eq!(range, 0..10);
2231 }
2232
2233 #[test]
2234 fn test_visible_range_variable_height_clamps() {
2235 let mut cache = HeightCache::new(1, 16);
2236 cache.set(0, 3);
2237 cache.set(1, 3);
2238 cache.set(2, 3);
2239 let mut virt: Virtualized<i32> =
2240 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2241 for i in 0..3 {
2242 virt.push(i);
2243 }
2244 let range = virt.visible_range(5);
2245 assert_eq!(range, 0..2);
2247 }
2248
2249 #[test]
2250 fn test_visible_range_variable_height_exact_fit() {
2251 let mut cache = HeightCache::new(1, 16);
2252 cache.set(0, 2);
2253 cache.set(1, 3);
2254 let mut virt: Virtualized<i32> =
2255 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2256 for i in 0..2 {
2257 virt.push(i);
2258 }
2259 let range = virt.visible_range(5);
2260 assert_eq!(range, 0..2);
2261 }
2262
2263 #[test]
2264 fn test_visible_range_with_scroll() {
2265 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
2266 for i in 0..50 {
2267 virt.push(i);
2268 }
2269 virt.scroll(10);
2270 let range = virt.visible_range(10);
2271 assert_eq!(range, 10..20);
2272 }
2273
2274 #[test]
2275 fn test_visible_range_variable_height_excludes_partial() {
2276 let mut cache = HeightCache::new(1, 16);
2277 cache.set(0, 6);
2278 cache.set(1, 6);
2279 let mut virt: Virtualized<i32> =
2280 Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2281 virt.push(1);
2282 virt.push(2);
2283 virt.push(3);
2284
2285 let range = virt.visible_range(10);
2286 assert_eq!(range, 0..2);
2288 }
2289
2290 #[test]
2291 fn test_visible_range_variable_height_exact_fit_larger() {
2292 let mut cache = HeightCache::new(1, 16);
2293 cache.set(0, 4);
2294 cache.set(1, 6);
2295 let mut virt: Virtualized<i32> =
2296 Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2297 virt.push(1);
2298 virt.push(2);
2299 virt.push(3);
2300
2301 let range = virt.visible_range(10);
2302 assert_eq!(range, 0..2);
2303 }
2304
2305 #[test]
2306 fn test_visible_range_variable_height_default_for_unmeasured() {
2307 let cache = HeightCache::new(2, 16);
2308 let mut virt: Virtualized<i32> =
2309 Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2310 for i in 0..3 {
2311 virt.push(i);
2312 }
2313
2314 let range = virt.visible_range(5);
2316 assert_eq!(range, 0..3);
2318 }
2319
2320 #[test]
2321 fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
2322 let mut virt: Virtualized<i32> =
2323 Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2324 for i in 0..20 {
2325 virt.push(i);
2326 }
2327 virt.scroll_to_bottom();
2330 assert_eq!(virt.visible_range(10), 15..20);
2331 }
2332
2333 #[test]
2334 fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
2335 let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
2336 for i in 0..20 {
2337 virt.push(i);
2338 }
2339 virt.scroll_to_bottom();
2342 assert_eq!(virt.visible_range(10), 15..20);
2343 }
2344
2345 #[test]
2346 fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
2347 let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
2350 let mut virt: Virtualized<i32> =
2351 Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
2352 for i in 0..5 {
2353 virt.push(i);
2354 }
2355 virt.scroll_to_bottom();
2356 assert_eq!(virt.visible_range(5), 3..5);
2357 virt.scroll_to_bottom();
2358 assert_eq!(virt.visible_range(6), 2..5);
2359 }
2360
2361 #[test]
2362 fn test_visible_range_variable_near_end_clamps_like_fixed() {
2363 let mut virt: Virtualized<i32> =
2366 Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2367 for i in 0..20 {
2368 virt.push(i);
2369 }
2370 virt.scroll_to(18);
2371 assert_eq!(virt.visible_range(10), 15..20);
2372 }
2373
2374 #[test]
2375 fn test_render_range_with_overscan() {
2376 let mut virt: Virtualized<i32> =
2377 Virtualized::new(100).with_fixed_height(1).with_overscan(2);
2378 for i in 0..50 {
2379 virt.push(i);
2380 }
2381 virt.scroll(10);
2382 let range = virt.render_range(10);
2383 assert_eq!(range, 8..22);
2386 }
2387
2388 #[test]
2389 fn test_scroll_bounds() {
2390 let mut virt: Virtualized<i32> = Virtualized::new(100);
2391 for i in 0..10 {
2392 virt.push(i);
2393 }
2394
2395 virt.scroll(-100);
2397 assert_eq!(virt.scroll_offset(), 0);
2398
2399 virt.scroll(100);
2401 assert_eq!(virt.scroll_offset(), 9);
2402 }
2403
2404 #[test]
2405 fn test_scroll_to() {
2406 let mut virt: Virtualized<i32> = Virtualized::new(100);
2407 for i in 0..20 {
2408 virt.push(i);
2409 }
2410
2411 virt.scroll_to(15);
2412 assert_eq!(virt.scroll_offset(), 15);
2413
2414 virt.scroll_to(100);
2416 assert_eq!(virt.scroll_offset(), 19);
2417 }
2418
2419 #[test]
2420 fn test_follow_mode() {
2421 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
2422 virt.set_visible_count(5);
2423
2424 for i in 0..10 {
2425 virt.push(i);
2426 }
2427
2428 assert!(virt.is_at_bottom());
2430
2431 virt.scroll(-5);
2433 assert!(!virt.follow_mode());
2434 }
2435
2436 #[test]
2437 fn test_scroll_to_start_and_end() {
2438 let mut virt: Virtualized<i32> = Virtualized::new(100);
2439 virt.set_visible_count(5);
2440 for i in 0..20 {
2441 virt.push(i);
2442 }
2443
2444 virt.scroll_to(10);
2446 virt.set_follow(true);
2447 virt.scroll_to_start();
2448 assert_eq!(virt.scroll_offset(), 0);
2449 assert!(!virt.follow_mode());
2450
2451 virt.scroll_to_end();
2453 assert!(virt.is_at_bottom());
2454 assert!(virt.follow_mode());
2455 }
2456
2457 #[test]
2458 fn test_virtualized_page_navigation() {
2459 let mut virt: Virtualized<i32> = Virtualized::new(100);
2460 virt.set_visible_count(5);
2461 for i in 0..30 {
2462 virt.push(i);
2463 }
2464
2465 virt.scroll_to(15);
2466 virt.page_up();
2467 assert_eq!(virt.scroll_offset(), 11);
2469
2470 virt.page_down();
2471 assert_eq!(virt.scroll_offset(), 15);
2472
2473 virt.scroll_to(2);
2475 virt.page_up();
2476 assert_eq!(virt.scroll_offset(), 0);
2477 }
2478
2479 #[test]
2480 fn test_height_cache() {
2481 let mut cache = HeightCache::new(1, 100);
2482
2483 assert_eq!(cache.get(0), 1);
2485 assert_eq!(cache.get(50), 1);
2486
2487 cache.set(5, 3);
2489 assert_eq!(cache.get(5), 3);
2490
2491 assert_eq!(cache.get(4), 1);
2493 assert_eq!(cache.get(6), 1);
2494 }
2495
2496 #[test]
2497 fn test_height_cache_large_index_window() {
2498 let mut cache = HeightCache::new(1, 8);
2499 cache.set(10_000, 4);
2500 assert_eq!(cache.get(10_000), 4);
2501 assert_eq!(cache.get(0), 1);
2502 assert!(cache.cache.len() <= cache.capacity);
2503 }
2504
2505 #[test]
2506 fn test_clear() {
2507 let mut virt: Virtualized<i32> = Virtualized::new(100);
2508 for i in 0..10 {
2509 virt.push(i);
2510 }
2511 virt.scroll(5);
2512
2513 virt.clear();
2514 assert_eq!(virt.len(), 0);
2515 assert_eq!(virt.scroll_offset(), 0);
2516 }
2517
2518 #[test]
2519 fn test_get_item() {
2520 let mut virt: Virtualized<String> = Virtualized::new(100);
2521 virt.push("hello".to_string());
2522 virt.push("world".to_string());
2523
2524 assert_eq!(virt.get(0), Some(&"hello".to_string()));
2525 assert_eq!(virt.get(1), Some(&"world".to_string()));
2526 assert_eq!(virt.get(2), None);
2527 }
2528
2529 #[test]
2530 fn test_external_storage_len() {
2531 let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
2532 assert_eq!(virt.len(), 1000);
2533
2534 virt.set_external_len(2000);
2535 assert_eq!(virt.len(), 2000);
2536 }
2537
2538 #[test]
2539 fn test_momentum_scrolling() {
2540 let mut virt: Virtualized<i32> = Virtualized::new(100);
2541 for i in 0..50 {
2542 virt.push(i);
2543 }
2544
2545 virt.fling(10.0);
2546
2547 virt.tick(Duration::from_millis(100));
2549
2550 assert!(virt.scroll_offset() > 0);
2552 }
2553
2554 #[test]
2559 fn test_virtualized_list_state_new() {
2560 let state = VirtualizedListState::new();
2561 assert_eq!(state.selected, None);
2562 assert_eq!(state.scroll_offset(), 0);
2563 assert_eq!(state.visible_count(), 0);
2564 }
2565
2566 #[test]
2567 fn test_virtualized_list_state_select_next() {
2568 let mut state = VirtualizedListState::new();
2569
2570 state.select_next(10);
2571 assert_eq!(state.selected, Some(0));
2572
2573 state.select_next(10);
2574 assert_eq!(state.selected, Some(1));
2575
2576 state.selected = Some(9);
2578 state.select_next(10);
2579 assert_eq!(state.selected, Some(9));
2580 }
2581
2582 #[test]
2583 fn test_virtualized_list_state_select_previous() {
2584 let mut state = VirtualizedListState::new();
2585 state.selected = Some(5);
2586
2587 state.select_previous(10);
2588 assert_eq!(state.selected, Some(4));
2589
2590 state.selected = Some(0);
2591 state.select_previous(10);
2592 assert_eq!(state.selected, Some(0));
2593 }
2594
2595 #[test]
2596 fn test_virtualized_list_state_scroll() {
2597 let mut state = VirtualizedListState::new();
2598
2599 state.scroll(5, 20);
2600 assert_eq!(state.scroll_offset(), 5);
2601
2602 state.scroll(-3, 20);
2603 assert_eq!(state.scroll_offset(), 2);
2604
2605 state.scroll(-100, 20);
2607 assert_eq!(state.scroll_offset(), 0);
2608
2609 state.scroll(100, 20);
2611 assert_eq!(state.scroll_offset(), 19);
2612 }
2613
2614 #[test]
2615 fn test_virtualized_list_state_follow_mode() {
2616 let mut state = VirtualizedListState::new().with_follow(true);
2617 assert!(state.follow_mode());
2618
2619 state.scroll(5, 20);
2621 assert!(!state.follow_mode());
2622 }
2623
2624 #[test]
2625 fn test_render_item_string() {
2626 let s = String::from("hello");
2628 assert_eq!(s.height(), 1);
2629 }
2630
2631 #[test]
2632 fn test_page_up_down() {
2633 let mut virt: Virtualized<i32> = Virtualized::new(100);
2634 for i in 0..50 {
2635 virt.push(i);
2636 }
2637 virt.set_visible_count(10);
2638
2639 assert_eq!(virt.scroll_offset(), 0);
2641
2642 virt.page_down();
2644 assert_eq!(virt.scroll_offset(), 9);
2645
2646 virt.page_down();
2648 assert_eq!(virt.scroll_offset(), 18);
2649
2650 virt.page_up();
2652 assert_eq!(virt.scroll_offset(), 9);
2653
2654 virt.page_up();
2656 assert_eq!(virt.scroll_offset(), 0);
2657
2658 virt.page_up();
2660 assert_eq!(virt.scroll_offset(), 0);
2661 }
2662
2663 #[test]
2668 fn test_render_scales_with_visible_not_total() {
2669 use ftui_render::grapheme_pool::GraphemePool;
2670 use std::time::Instant;
2671
2672 let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
2674 let small_list = VirtualizedList::new(&small_items);
2675 let mut small_state = VirtualizedListState::new();
2676
2677 let area = Rect::new(0, 0, 80, 24);
2678 let mut pool = GraphemePool::new();
2679 let mut frame = Frame::new(80, 24, &mut pool);
2680
2681 small_list.render(area, &mut frame, &mut small_state);
2683
2684 let start = Instant::now();
2685 for _ in 0..100 {
2686 frame.buffer.clear();
2687 small_list.render(area, &mut frame, &mut small_state);
2688 }
2689 let small_time = start.elapsed();
2690
2691 let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
2693 let large_list = VirtualizedList::new(&large_items);
2694 let mut large_state = VirtualizedListState::new();
2695
2696 large_list.render(area, &mut frame, &mut large_state);
2698
2699 let start = Instant::now();
2700 for _ in 0..100 {
2701 frame.buffer.clear();
2702 large_list.render(area, &mut frame, &mut large_state);
2703 }
2704 let large_time = start.elapsed();
2705
2706 assert!(
2708 large_time < small_time * 3,
2709 "Render does not scale O(visible): 1K={:?}, 100K={:?}",
2710 small_time,
2711 large_time
2712 );
2713 }
2714
2715 #[test]
2716 fn test_scroll_is_constant_time() {
2717 use std::time::Instant;
2718
2719 let mut small: Virtualized<i32> = Virtualized::new(1_000);
2720 for i in 0..1_000 {
2721 small.push(i);
2722 }
2723 small.set_visible_count(24);
2724
2725 let mut large: Virtualized<i32> = Virtualized::new(100_000);
2726 for i in 0..100_000 {
2727 large.push(i);
2728 }
2729 large.set_visible_count(24);
2730
2731 let iterations = 10_000;
2732
2733 for _ in 0..iterations {
2736 small.scroll(1);
2737 small.scroll(-1);
2738 large.scroll(1);
2739 large.scroll(-1);
2740 }
2741
2742 let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
2747 let runs = 5;
2748 let mut best = std::time::Duration::MAX;
2749 for _ in 0..runs {
2750 let start = Instant::now();
2751 for _ in 0..iterations {
2752 v.scroll(1);
2753 v.scroll(-1);
2754 }
2755 best = best.min(start.elapsed());
2756 }
2757 best
2758 };
2759
2760 let small_time = measure(&mut small);
2761 let large_time = measure(&mut large);
2762
2763 let ceiling = small_time
2769 .checked_mul(10)
2770 .unwrap_or(std::time::Duration::MAX);
2771 assert!(
2772 large_time < ceiling,
2773 "Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
2774 small_time,
2775 large_time
2776 );
2777 }
2778
2779 #[test]
2780 fn render_partially_offscreen_top_skips_item() {
2781 use ftui_render::grapheme_pool::GraphemePool;
2782
2783 struct IndexedItem(usize);
2785 impl RenderItem for IndexedItem {
2786 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2787 let ch = char::from_digit(self.0 as u32, 10).unwrap();
2788 for y in area.y..area.bottom() {
2789 frame.buffer.set(area.x, y, Cell::from_char(ch));
2790 }
2791 }
2792 fn height(&self) -> u16 {
2793 2
2794 }
2795 }
2796
2797 let items = vec![
2800 IndexedItem(0),
2801 IndexedItem(1),
2802 IndexedItem(2),
2803 IndexedItem(3),
2804 ];
2805 let list = VirtualizedList::new(&items).fixed_height(2);
2806
2807 let mut state = VirtualizedListState::new().with_overscan(1);
2809 state.scroll_offset = 1; let mut pool = GraphemePool::new();
2812 let mut frame = Frame::new(10, 5, &mut pool);
2813
2814 list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
2816
2817 let cell = frame.buffer.get(0, 0).unwrap();
2825 assert_eq!(cell.content.as_char(), Some('1'));
2826 }
2827
2828 #[test]
2829 fn render_bottom_boundary_clips_partial_item() {
2830 use ftui_render::grapheme_pool::GraphemePool;
2831
2832 struct IndexedItem(u16);
2833 impl RenderItem for IndexedItem {
2834 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2835 let ch = char::from_digit(self.0 as u32, 10).unwrap();
2836 for y in area.y..area.bottom() {
2837 frame.buffer.set(area.x, y, Cell::from_char(ch));
2838 }
2839 }
2840 fn height(&self) -> u16 {
2841 2
2842 }
2843 }
2844
2845 let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
2846 let list = VirtualizedList::new(&items)
2847 .fixed_height(2)
2848 .show_scrollbar(false);
2849 let mut state = VirtualizedListState::new();
2850
2851 let mut pool = GraphemePool::new();
2852 let mut frame = Frame::new(4, 4, &mut pool);
2853
2854 list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
2856
2857 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2858 assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
2859 assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
2860 assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
2862 }
2863
2864 #[test]
2865 fn render_after_fling_advances_visible_rows() {
2866 use ftui_render::grapheme_pool::GraphemePool;
2867
2868 struct IndexedItem(u16);
2869 impl RenderItem for IndexedItem {
2870 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2871 let ch = char::from_digit(self.0 as u32, 10).unwrap();
2872 for y in area.y..area.bottom() {
2873 frame.buffer.set(area.x, y, Cell::from_char(ch));
2874 }
2875 }
2876 }
2877
2878 let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
2879 let list = VirtualizedList::new(&items)
2880 .fixed_height(1)
2881 .show_scrollbar(false);
2882 let mut state = VirtualizedListState::new();
2883
2884 let mut pool = GraphemePool::new();
2885 let mut frame = Frame::new(4, 3, &mut pool);
2886 let area = Rect::new(0, 0, 4, 3);
2887
2888 list.render(area, &mut frame, &mut state);
2890 assert_eq!(state.scroll_offset(), 0);
2891 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2892
2893 state.fling(40.0);
2895 state.tick(Duration::from_millis(100), items.len());
2896 assert_eq!(state.scroll_offset(), 4);
2897
2898 frame.buffer.clear();
2899 list.render(area, &mut frame, &mut state);
2900 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
2901 }
2902
2903 #[test]
2904 fn render_empty_virtualized_list_clears_stale_viewport() {
2905 use ftui_render::grapheme_pool::GraphemePool;
2906
2907 let items: Vec<String> = Vec::new();
2908 let list = VirtualizedList::new(&items).show_scrollbar(false);
2909 let mut state = VirtualizedListState::new();
2910 let mut pool = GraphemePool::new();
2911 let mut frame = Frame::new(6, 3, &mut pool);
2912 let area = Rect::new(0, 0, 6, 3);
2913 frame.buffer.fill(area, Cell::from_char('X'));
2914
2915 list.render(area, &mut frame, &mut state);
2916
2917 assert_eq!(raw_row_text(&frame, 0), " ");
2918 assert_eq!(raw_row_text(&frame, 1), " ");
2919 assert_eq!(raw_row_text(&frame, 2), " ");
2920 }
2921
2922 #[test]
2923 fn render_shorter_virtualized_row_clears_stale_suffix() {
2924 use ftui_render::grapheme_pool::GraphemePool;
2925
2926 let long_items = vec!["Hello".to_string()];
2927 let short_items = vec!["Hi".to_string()];
2928 let area = Rect::new(0, 0, 6, 1);
2929 let mut state = VirtualizedListState::new();
2930 let mut pool = GraphemePool::new();
2931 let mut frame = Frame::new(6, 1, &mut pool);
2932
2933 VirtualizedList::new(&long_items)
2934 .show_scrollbar(false)
2935 .render(area, &mut frame, &mut state);
2936 VirtualizedList::new(&short_items)
2937 .show_scrollbar(false)
2938 .render(area, &mut frame, &mut state);
2939
2940 assert_eq!(raw_row_text(&frame, 0), "Hi ");
2941 }
2942
2943 #[test]
2944 fn test_memory_bounded_by_ring_capacity() {
2945 use crate::log_ring::LogRing;
2946
2947 let mut ring: LogRing<String> = LogRing::new(1_000);
2948
2949 for i in 0..100_000 {
2951 ring.push(format!("Line {}", i));
2952 }
2953
2954 assert_eq!(ring.len(), 1_000);
2956 assert_eq!(ring.total_count(), 100_000);
2957 assert_eq!(ring.first_index(), 99_000);
2958
2959 assert!(ring.get(99_999).is_some());
2961 assert!(ring.get(99_000).is_some());
2962 assert!(ring.get(0).is_none());
2964 assert!(ring.get(98_999).is_none());
2965 }
2966
2967 #[test]
2968 fn test_visible_range_constant_regardless_of_total() {
2969 let mut small: Virtualized<i32> = Virtualized::new(100);
2970 for i in 0..100 {
2971 small.push(i);
2972 }
2973 let small_range = small.visible_range(24);
2974
2975 let mut large: Virtualized<i32> = Virtualized::new(100_000);
2976 for i in 0..100_000 {
2977 large.push(i);
2978 }
2979 let large_range = large.visible_range(24);
2980
2981 assert_eq!(small_range.end - small_range.start, 24);
2983 assert_eq!(large_range.end - large_range.start, 24);
2984 }
2985
2986 #[test]
2987 fn test_virtualized_list_state_page_up_down() {
2988 let mut state = VirtualizedListState::new();
2989 state.visible_count = 10;
2990
2991 state.page_down(50);
2993 assert_eq!(state.scroll_offset(), 9);
2994
2995 state.page_down(50);
2997 assert_eq!(state.scroll_offset(), 18);
2998
2999 state.page_up(50);
3001 assert_eq!(state.scroll_offset(), 9);
3002
3003 state.page_up(50);
3005 assert_eq!(state.scroll_offset(), 0);
3006 }
3007
3008 #[test]
3013 fn test_variable_heights_fenwick_new() {
3014 let tracker = VariableHeightsFenwick::new(2, 10);
3015 assert_eq!(tracker.len(), 10);
3016 assert!(!tracker.is_empty());
3017 assert_eq!(tracker.default_height(), 2);
3018 }
3019
3020 #[test]
3021 fn test_variable_heights_fenwick_empty() {
3022 let tracker = VariableHeightsFenwick::new(1, 0);
3023 assert!(tracker.is_empty());
3024 assert_eq!(tracker.total_height(), 0);
3025 }
3026
3027 #[test]
3028 fn test_variable_heights_fenwick_from_heights() {
3029 let heights = vec![3, 2, 5, 1, 4];
3030 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3031
3032 assert_eq!(tracker.len(), 5);
3033 assert_eq!(tracker.get(0), 3);
3034 assert_eq!(tracker.get(1), 2);
3035 assert_eq!(tracker.get(2), 5);
3036 assert_eq!(tracker.get(3), 1);
3037 assert_eq!(tracker.get(4), 4);
3038 assert_eq!(tracker.total_height(), 15);
3039 }
3040
3041 #[test]
3042 fn test_variable_heights_fenwick_offset_of_item() {
3043 let heights = vec![3, 2, 5, 1, 4];
3045 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3046
3047 assert_eq!(tracker.offset_of_item(0), 0);
3048 assert_eq!(tracker.offset_of_item(1), 3);
3049 assert_eq!(tracker.offset_of_item(2), 5);
3050 assert_eq!(tracker.offset_of_item(3), 10);
3051 assert_eq!(tracker.offset_of_item(4), 11);
3052 assert_eq!(tracker.offset_of_item(5), 15); }
3054
3055 #[test]
3056 fn test_variable_heights_fenwick_find_item_at_offset() {
3057 let heights = vec![3, 2, 5, 1, 4];
3059 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3060
3061 assert_eq!(tracker.find_item_at_offset(0), 0);
3063 assert_eq!(tracker.find_item_at_offset(1), 0);
3065 assert_eq!(tracker.find_item_at_offset(3), 1);
3067 assert_eq!(tracker.find_item_at_offset(5), 2);
3069 assert_eq!(tracker.find_item_at_offset(10), 3);
3071 assert_eq!(tracker.find_item_at_offset(11), 4);
3073 assert_eq!(tracker.find_item_at_offset(15), 5);
3075 }
3076
3077 #[test]
3078 fn fenwick_large_height_totals_do_not_wrap() {
3079 let heights = vec![u16::MAX; 131_072];
3080 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3081 let offset = 4_294_836_224_u32;
3082 assert_eq!(
3083 tracker.find_item_at_offset(offset),
3084 (u64::from(offset) / u64::from(u16::MAX)) as usize,
3085 "a wrapped root aggregate must not skip the entire list"
3086 );
3087 assert_eq!(tracker.total_height(), u32::MAX);
3088 assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
3089 }
3090
3091 #[test]
3092 #[should_panic(expected = "height index exceeds usize")]
3093 fn fenwick_rejects_unrepresentable_index() {
3094 VariableHeightsFenwick::default().set(usize::MAX, 1);
3095 }
3096
3097 #[test]
3098 fn fenwick_large_updates_and_resize_match_u64_oracle() {
3099 fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
3100 let mut prefixes = Vec::with_capacity(heights.len() + 1);
3101 prefixes.push(0u64);
3102 for &height in heights {
3103 prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
3104 }
3105 let total = prefixes.last().copied().unwrap();
3106 assert_eq!(tracker.len(), heights.len());
3107 assert_eq!(tracker.total_height_exact(), total);
3108 assert_eq!(
3109 tracker.total_height(),
3110 total.min(u64::from(u32::MAX)) as u32
3111 );
3112 let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
3113 for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
3114 assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
3115 assert_eq!(
3116 tracker.offset_of_item(idx),
3117 prefixes[idx].min(u64::from(u32::MAX)) as u32
3118 );
3119 queries.extend([
3120 prefixes[idx].saturating_sub(1),
3121 prefixes[idx],
3122 prefixes[idx] + 1,
3123 ]);
3124 }
3125 for offset in queries {
3126 let expected = if offset == 0 {
3127 0
3128 } else {
3129 prefixes[1..].partition_point(|&prefix| prefix <= offset)
3130 };
3131 assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
3132 if let Ok(offset) = u32::try_from(offset) {
3133 assert_eq!(tracker.find_item_at_offset(offset), expected);
3134 }
3135 }
3136 }
3137
3138 for len in [65_536, 65_537, 65_538, 131_072] {
3141 let mut heights = vec![u16::MAX; len];
3142 let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
3143 check(&tracker, &heights);
3144 for idx in [0, 1, 32_768, 65_535, len - 1] {
3145 tracker.set(idx, 0);
3146 heights[idx] = 0;
3147 assert_eq!(tracker.get(idx), 0);
3148 }
3149 check(&tracker, &heights);
3150 tracker.set(0, u16::MAX);
3151 heights[0] = u16::MAX;
3152 tracker.resize(65_536);
3153 heights.truncate(65_536);
3154 check(&tracker, &heights);
3155 tracker.resize(65_540);
3156 heights.resize(65_540, u16::MAX);
3157 check(&tracker, &heights);
3158 }
3159
3160 let mut seed = 0xa076_1d64_78bd_642fu64;
3163 let mut heights: Vec<u16> = (0..131_072)
3164 .map(|_| {
3165 seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
3166 32_768 + ((seed >> 48) as u16 / 2)
3167 })
3168 .collect();
3169 let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3170 for idx in (0..heights.len()).step_by(997) {
3171 heights[idx] = (idx % 65_536) as u16;
3172 tracker.set(idx, heights[idx]);
3173 assert_eq!(tracker.get(idx), heights[idx]);
3174 }
3175 check(&tracker, &heights);
3176 tracker.drop_front(3);
3177 check(&tracker, &heights[3..]);
3178 heights.fill(u16::MAX);
3179 tracker.rebuild(&heights);
3180 check(&tracker, &heights);
3181 tracker.clear();
3182 check(&tracker, &[]);
3183 tracker.resize(4);
3184 check(&tracker, &[1; 4]);
3185 }
3186
3187 #[test]
3188 fn fenwick_large_visible_range_keeps_tail_reachable() {
3189 let len = 65_548;
3190 let mut virt: Virtualized<()> =
3191 Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
3192 for idx in 65_538..len {
3193 virt.observe_height(idx, 1);
3194 }
3195 virt.scroll_to_bottom();
3196 assert_eq!(virt.visible_range(5), len - 5..len);
3197 virt.scroll_to(len - 8);
3198 assert_eq!(virt.visible_range(5), len - 8..len - 3);
3199 }
3200
3201 #[test]
3202 fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
3203 fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
3204 let scrollbar =
3205 Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
3206 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
3207 let mut frame = Frame::new(1, 21, &mut pool);
3208 scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
3209 (0..21)
3210 .filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
3211 .collect()
3212 }
3213
3214 let capacity = u32::MAX as usize;
3217 let total = 131_072 * u64::from(u16::MAX);
3218 let viewport = 20;
3219 let max_position = total - u64::from(viewport);
3220 for (position, expected_row) in [
3221 (0, 0),
3222 (max_position / 4, 5),
3223 (max_position / 2, 10),
3224 (max_position / 4 * 3, 15),
3225 (max_position, 20),
3226 (total, 20),
3227 ] {
3228 let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3229 assert_eq!(scaled.content_length, capacity);
3230 assert!(scaled.viewport_length > 0);
3231 assert_eq!(thumb_rows(scaled), vec![expected_row]);
3232 }
3233
3234 let position = u64::from(u32::MAX) + u64::from(u16::MAX);
3235 let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3236 assert_eq!(thumb_rows(scaled), vec![10]);
3237 let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
3239 assert_eq!(thumb_rows(saturated), vec![20]);
3240
3241 for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
3242 let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
3243 assert_eq!(exact.content_length, total as usize);
3244 assert_eq!(exact.position, position as usize);
3245 assert_eq!(exact.viewport_length, usize::from(viewport));
3246 }
3247 if usize::BITS > 32 {
3248 let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
3249 assert_eq!(exact.content_length as u64, total);
3250 assert_eq!(exact.position as u64, position);
3251 assert_eq!(exact.viewport_length, usize::from(viewport));
3252 }
3253 }
3254
3255 #[test]
3256 fn test_variable_heights_fenwick_visible_count() {
3257 let heights = vec![3, 2, 5, 1, 4];
3259 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3260
3261 assert_eq!(tracker.visible_count(0, 5), 2);
3263
3264 assert_eq!(tracker.visible_count(0, 4), 2);
3266
3267 assert_eq!(tracker.visible_count(0, 10), 3);
3269
3270 assert_eq!(tracker.visible_count(2, 6), 2);
3272 }
3273
3274 #[test]
3275 fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
3276 let heights = vec![1, 1, 1];
3277 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3278
3279 assert_eq!(tracker.visible_count(0, 10), 3);
3281 assert_eq!(tracker.visible_count(1, 10), 2);
3282 assert_eq!(tracker.visible_count(2, 10), 1);
3283 }
3284
3285 #[test]
3286 fn test_variable_heights_fenwick_set() {
3287 let mut tracker = VariableHeightsFenwick::new(1, 5);
3288
3289 assert_eq!(tracker.get(0), 1);
3291 assert_eq!(tracker.total_height(), 5);
3292
3293 tracker.set(2, 10);
3295 assert_eq!(tracker.get(2), 10);
3296 assert_eq!(tracker.total_height(), 14); }
3298
3299 #[test]
3300 fn test_variable_heights_fenwick_resize() {
3301 let mut tracker = VariableHeightsFenwick::new(2, 3);
3302 assert_eq!(tracker.len(), 3);
3303 assert_eq!(tracker.total_height(), 6);
3304
3305 tracker.resize(5);
3307 assert_eq!(tracker.len(), 5);
3308 assert_eq!(tracker.total_height(), 10);
3309 assert_eq!(tracker.get(4), 2);
3310
3311 tracker.resize(2);
3313 assert_eq!(tracker.len(), 2);
3314 assert_eq!(tracker.total_height(), 4);
3315 }
3316
3317 #[test]
3318 fn test_variable_heights_fenwick_point_update_and_range_query() {
3319 fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
3320 tracker
3321 .offset_of_item(right.saturating_add(1))
3322 .saturating_sub(tracker.offset_of_item(left))
3323 }
3324
3325 let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
3326 let mut naive = [2_u32, 4, 1, 3, 5, 2];
3327
3328 tracker.set(2, 7);
3329 naive[2] = 7;
3330 tracker.set(5, 1);
3331 naive[5] = 1;
3332 tracker.set(0, 6);
3333 naive[0] = 6;
3334
3335 let mut running = 0u32;
3336 for (i, value) in naive.iter().enumerate() {
3337 running = running.saturating_add(*value);
3338 assert_eq!(tracker.offset_of_item(i + 1), running);
3339 }
3340
3341 let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
3342 assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
3343 assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
3344 assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
3345 }
3346
3347 proptest! {
3348 #![proptest_config(ProptestConfig::with_cases(96))]
3349
3350 #[test]
3351 fn property_measured_heights_survive_mutations(
3352 operations in proptest::collection::vec((0u8..3, 0usize..150, 1u16..32), 1..80)
3353 ) {
3354 let mut tracker = VariableHeightsFenwick::new(2, 0);
3355 let mut expected: Vec<Option<u16>> = Vec::new();
3356 for (operation, index, height) in operations {
3357 match operation {
3358 0 => {
3359 if index >= expected.len() {
3360 expected.resize(index + 1, None);
3361 }
3362 expected[index] = Some(height);
3363 tracker.set(index, height);
3364 }
3365 1 => {
3366 expected.resize(index, None);
3367 tracker.resize(index);
3368 }
3369 _ => {
3370 expected.drain(..index.min(expected.len()));
3371 tracker.drop_front(index);
3372 }
3373 }
3374 prop_assert_eq!(tracker.len(), expected.len());
3375 prop_assert_eq!(
3376 tracker.unmeasured_count(),
3377 expected.iter().filter(|height| height.is_none()).count()
3378 );
3379 let mut prefix = 0;
3380 for (index, height) in expected.iter().enumerate() {
3381 prop_assert_eq!(tracker.offset_of_item(index), prefix);
3382 prop_assert_eq!(tracker.is_measured(index), height.is_some());
3383 prop_assert_eq!(tracker.get(index), height.unwrap_or(2));
3384 prefix += u32::from(height.unwrap_or(2));
3385 }
3386 prop_assert_eq!(tracker.total_height(), prefix);
3387 }
3388 }
3389
3390 #[test]
3391 fn property_variable_heights_fenwick_prefix_sums_match_naive(
3392 heights in proptest::collection::vec(1u16..=32u16, 1..160)
3393 ) {
3394 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3395
3396 let mut naive_prefix = 0u32;
3397 prop_assert_eq!(tracker.offset_of_item(0), 0);
3398 for (i, height) in heights.iter().enumerate() {
3399 naive_prefix = naive_prefix.saturating_add(u32::from(*height));
3400 prop_assert_eq!(
3401 tracker.offset_of_item(i + 1),
3402 naive_prefix,
3403 "prefix mismatch at index {} for heights {:?}",
3404 i,
3405 heights
3406 );
3407 }
3408 }
3409
3410 #[test]
3411 fn property_variable_heights_fenwick_visible_count_matches_naive(
3412 heights in proptest::collection::vec(1u16..=24u16, 1..128),
3413 start_idx in 0usize..192usize,
3414 viewport_height in 1u16..=120u16
3415 ) {
3416 fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
3417 if heights.is_empty() || viewport_height == 0 {
3418 return 0;
3419 }
3420 let start = start_idx.min(heights.len());
3421 if start >= heights.len() {
3422 return 0;
3423 }
3424
3425 let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
3426 let end_offset = start_offset.saturating_add(u32::from(viewport_height));
3427 let mut count = 0usize;
3428 let mut cursor = start_offset;
3429 for &height in &heights[start..] {
3430 if cursor >= end_offset {
3431 break;
3432 }
3433 count = count.saturating_add(1);
3434 cursor = cursor.saturating_add(u32::from(height));
3435 }
3436
3437 if count == 0 { 1 } else { count }
3438 }
3439
3440 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3441 let expected = naive_visible_count(&heights, start_idx, viewport_height);
3442 let actual = tracker.visible_count(start_idx, viewport_height);
3443 prop_assert_eq!(
3444 actual,
3445 expected,
3446 "visible_count mismatch for start={} viewport={} heights={:?}",
3447 start_idx,
3448 viewport_height,
3449 heights
3450 );
3451 }
3452 }
3453
3454 #[test]
3458 fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
3459 let config = PredictorConfig {
3460 default_height: 1,
3461 prior_mean: 1.0,
3462 prior_strength: 2.0,
3463 ..PredictorConfig::default()
3464 };
3465 let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
3466 assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
3467 assert_eq!(tracker.unmeasured_count(), 10);
3468 assert_eq!(tracker.total_height(), 10);
3469
3470 for idx in 0..3 {
3472 tracker.set(idx, 3);
3473 }
3474 assert_eq!(tracker.predicted_height(), 2);
3475 assert_eq!(tracker.unmeasured_count(), 7);
3476 assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
3477 assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
3478 assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
3479 assert_eq!(tracker.offset_of_item(4), 9 + 2);
3480
3481 for idx in 3..6 {
3483 tracker.set(idx, 3);
3484 }
3485 assert_eq!(tracker.predicted_height(), 3);
3486 assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
3487 assert!(tracker.is_measured(5) && !tracker.is_measured(6));
3488 assert_eq!(
3489 tracker.predictor().map(HeightPredictor::total_measurements),
3490 Some(6)
3491 );
3492
3493 tracker.resize(12);
3495 assert_eq!(tracker.get(11), 3);
3496 assert_eq!(tracker.unmeasured_count(), 6);
3497 assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
3498
3499 tracker.resize(4);
3501 assert_eq!(tracker.unmeasured_count(), 0);
3502 tracker.resize(6);
3503 assert_eq!(tracker.unmeasured_count(), 2);
3504 assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
3505
3506 tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
3508 assert_eq!(tracker.unmeasured_count(), 0);
3509 assert_eq!(tracker.total_height(), 40);
3510 assert!(
3511 tracker.predicted_height() >= 4,
3512 "posterior pulled toward the taller rows"
3513 );
3514
3515 let mut plain = VariableHeightsFenwick::new(2, 4);
3517 plain.set(0, 9);
3518 assert_eq!(plain.predicted_height(), 2);
3519 assert_eq!(plain.get(3), 2);
3520 assert_eq!(plain.unmeasured_count(), 3);
3521 assert!(plain.predictor().is_none());
3522 }
3523
3524 #[test]
3527 fn virtualized_height_prediction_observe_height_trains_the_model() {
3528 let mut virt: Virtualized<i32> = Virtualized::new(100)
3529 .with_fixed_height(1)
3530 .with_height_prediction(PredictorConfig::default());
3531 assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
3532 assert_eq!(virt.unmeasured_item_height(), 1);
3533
3534 for idx in 0..4 {
3536 virt.observe_height(idx, 4);
3537 }
3538 assert_eq!(virt.unmeasured_item_height(), 3);
3539 let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
3540 panic!("expected the Fenwick tracker");
3541 };
3542 assert_eq!(tracker.get(0), 4);
3543 assert_eq!(tracker.len(), 4);
3544 assert_eq!(
3545 tracker.get(40),
3546 3,
3547 "beyond the tracked length: the prediction"
3548 );
3549
3550 let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
3551 fixed.observe_height(0, 9);
3552 assert_eq!(
3553 fixed.unmeasured_item_height(),
3554 2,
3555 "fixed heights ignore observations"
3556 );
3557
3558 let mut linear: Virtualized<i32> =
3559 Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
3560 linear.observe_height(1, 5);
3561 assert_eq!(linear.unmeasured_item_height(), 2);
3562 let ItemHeight::Variable(cache) = linear.item_height() else {
3563 panic!("expected the linear cache");
3564 };
3565 assert_eq!(cache.get(1), 5);
3566 }
3567
3568 #[test]
3569 fn test_virtualized_with_variable_heights_fenwick() {
3570 let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
3571
3572 for i in 0..10 {
3573 virt.push(i);
3574 }
3575
3576 let range = virt.visible_range(6);
3578 assert_eq!(range.end - range.start, 3);
3579 }
3580
3581 proptest! {
3582 #[test]
3588 fn variable_height_implementations_agree(
3589 heights in proptest::collection::vec(1u16..=5, 1..40),
3590 viewport in 1u16..=20,
3591 default_height in 1u16..=4,
3592 offset_seed in 0usize..64,
3593 ) {
3594 let len = heights.len();
3595 let mut cache: Virtualized<usize> = Virtualized::new(len)
3600 .with_item_height(ItemHeight::Variable(HeightCache::new(default_height, len)));
3601 let mut fenwick: Virtualized<usize> =
3602 Virtualized::new(len).with_variable_heights_fenwick(default_height, len);
3603 for i in 0..len {
3604 cache.push(i);
3605 fenwick.push(i);
3606 }
3607 for (idx, height) in heights.iter().enumerate() {
3608 cache.observe_height(idx, *height);
3609 fenwick.observe_height(idx, *height);
3610 }
3611
3612 let offset = offset_seed % len;
3613 cache.scroll_to(offset);
3614 fenwick.scroll_to(offset);
3615 prop_assert_eq!(
3616 cache.visible_range(viewport),
3617 fenwick.visible_range(viewport),
3618 "implementations disagree at len={} viewport={} offset={}",
3619 len,
3620 viewport,
3621 offset
3622 );
3623
3624 cache.scroll_to_bottom();
3626 fenwick.scroll_to_bottom();
3627 let bottom_cache = cache.visible_range(viewport);
3628 let bottom_fenwick = fenwick.visible_range(viewport);
3629 prop_assert_eq!(&bottom_cache, &bottom_fenwick, "bottom anchoring disagrees");
3630 prop_assert!(
3631 bottom_cache.contains(&(len - 1)),
3632 "last item unreachable: range {:?} of {} items",
3633 bottom_cache,
3634 len
3635 );
3636
3637 let keep = 1 + offset_seed % len;
3641 if keep < len {
3642 prop_assert_eq!(cache.trim_front(keep), fenwick.trim_front(keep));
3643 let len = cache.len();
3644 cache.scroll_to_bottom();
3645 fenwick.scroll_to_bottom();
3646 let trimmed_cache = cache.visible_range(viewport);
3647 let trimmed_fenwick = fenwick.visible_range(viewport);
3648 prop_assert_eq!(
3649 &trimmed_cache,
3650 &trimmed_fenwick,
3651 "implementations disagree after trimming to {} items",
3652 keep
3653 );
3654 prop_assert!(
3655 trimmed_cache.contains(&(len - 1)),
3656 "last item unreachable after a trim: range {:?} of {} items",
3657 trimmed_cache,
3658 len
3659 );
3660 }
3661 }
3662 }
3663
3664 #[test]
3665 fn test_variable_heights_fenwick_performance() {
3666 use std::time::Instant;
3667
3668 let n = 100_000;
3670 let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
3671 let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3672
3673 let _ = tracker.find_item_at_offset(500_000);
3675 let _ = tracker.offset_of_item(50_000);
3676
3677 let start = Instant::now();
3679 let mut _sink = 0usize;
3680 for i in 0..10_000 {
3681 _sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
3682 }
3683 let find_time = start.elapsed();
3684
3685 let start = Instant::now();
3687 let mut _sink2 = 0u32;
3688 for i in 0..10_000 {
3689 _sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
3690 }
3691 let offset_time = start.elapsed();
3692
3693 eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
3694 eprintln!("10k find_item_at_offset: {:?}", find_time);
3695 eprintln!("10k offset_of_item: {:?}", offset_time);
3696
3697 assert!(
3699 find_time < std::time::Duration::from_millis(50),
3700 "find_item_at_offset too slow: {:?}",
3701 find_time
3702 );
3703 assert!(
3704 offset_time < std::time::Duration::from_millis(50),
3705 "offset_of_item too slow: {:?}",
3706 offset_time
3707 );
3708 }
3709
3710 #[test]
3711 fn test_variable_heights_fenwick_scales_logarithmically() {
3712 use std::time::Instant;
3713
3714 let small_n = 1_000;
3716 let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
3717 let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
3718
3719 let large_n = 100_000;
3721 let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
3722 let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
3723
3724 let iterations = 5_000;
3725
3726 let start = Instant::now();
3728 for i in 0..iterations {
3729 let _ = small_tracker.find_item_at_offset((i * 2) as u32);
3730 }
3731 let small_time = start.elapsed();
3732
3733 let start = Instant::now();
3735 for i in 0..iterations {
3736 let _ = large_tracker.find_item_at_offset((i * 200) as u32);
3737 }
3738 let large_time = start.elapsed();
3739
3740 assert!(
3743 large_time < small_time * 10,
3744 "Not O(log n): small={:?}, large={:?}",
3745 small_time,
3746 large_time
3747 );
3748 }
3749
3750 #[test]
3757 fn new_zero_capacity() {
3758 let virt: Virtualized<i32> = Virtualized::new(0);
3759 assert_eq!(virt.len(), 0);
3760 assert!(virt.is_empty());
3761 assert_eq!(virt.scroll_offset(), 0);
3762 assert_eq!(virt.visible_count(), 0);
3763 assert!(!virt.follow_mode());
3764 }
3765
3766 #[test]
3767 fn external_zero_len_zero_cache() {
3768 let virt: Virtualized<i32> = Virtualized::external(0, 0);
3769 assert_eq!(virt.len(), 0);
3770 assert!(virt.is_empty());
3771 }
3772
3773 #[test]
3774 fn external_storage_returns_none_for_get() {
3775 let virt: Virtualized<i32> = Virtualized::external(100, 10);
3776 assert_eq!(virt.get(0), None);
3777 assert_eq!(virt.get(50), None);
3778 }
3779
3780 #[test]
3781 fn external_storage_returns_none_for_get_mut() {
3782 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3783 assert!(virt.get_mut(0).is_none());
3784 }
3785
3786 #[test]
3787 fn push_on_external_is_noop() {
3788 let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
3789 virt.push(42);
3790 assert_eq!(virt.len(), 5);
3792 }
3793
3794 #[test]
3795 fn iter_on_external_is_empty() {
3796 let virt: Virtualized<i32> = Virtualized::external(100, 10);
3797 assert_eq!(virt.iter().count(), 0);
3798 }
3799
3800 #[test]
3801 fn set_external_len_on_owned_is_noop() {
3802 let mut virt: Virtualized<i32> = Virtualized::new(100);
3803 virt.push(1);
3804 virt.set_external_len(999);
3805 assert_eq!(virt.len(), 1); }
3807
3808 #[test]
3811 fn visible_range_zero_viewport() {
3812 let mut virt: Virtualized<i32> = Virtualized::new(100);
3813 virt.push(1);
3814 let range = virt.visible_range(0);
3815 assert_eq!(range, 0..0);
3816 assert_eq!(virt.visible_count(), 0);
3817 }
3818
3819 #[test]
3820 fn visible_range_empty_container() {
3821 let virt: Virtualized<i32> = Virtualized::new(100);
3822 let range = virt.visible_range(24);
3823 assert_eq!(range, 0..0);
3824 }
3825
3826 #[test]
3827 fn visible_range_fixed_height_zero() {
3828 let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
3830 for i in 0..10 {
3831 virt.push(i);
3832 }
3833 let range = virt.visible_range(5);
3834 assert_eq!(range, 0..5);
3836 }
3837
3838 #[test]
3839 fn visible_range_fewer_items_than_viewport() {
3840 let mut virt: Virtualized<i32> = Virtualized::new(100);
3841 for i in 0..3 {
3842 virt.push(i);
3843 }
3844 let range = virt.visible_range(24);
3845 assert_eq!(range, 0..3);
3847 }
3848
3849 #[test]
3850 fn visible_range_single_item() {
3851 let mut virt: Virtualized<i32> = Virtualized::new(100);
3852 virt.push(42);
3853 let range = virt.visible_range(1);
3854 assert_eq!(range, 0..1);
3855 }
3856
3857 #[test]
3860 fn render_range_at_start_clamps_overscan() {
3861 let mut virt: Virtualized<i32> =
3862 Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3863 for i in 0..20 {
3864 virt.push(i);
3865 }
3866 let range = virt.render_range(10);
3868 assert_eq!(range.start, 0);
3869 }
3870
3871 #[test]
3872 fn render_range_at_end_clamps_overscan() {
3873 let mut virt: Virtualized<i32> =
3874 Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3875 for i in 0..20 {
3876 virt.push(i);
3877 }
3878 virt.set_visible_count(10);
3879 virt.scroll_to(10); let range = virt.render_range(10);
3881 assert_eq!(range.end, 20);
3883 }
3884
3885 #[test]
3886 fn render_range_zero_overscan() {
3887 let mut virt: Virtualized<i32> =
3888 Virtualized::new(100).with_fixed_height(1).with_overscan(0);
3889 for i in 0..20 {
3890 virt.push(i);
3891 }
3892 virt.set_visible_count(10);
3893 virt.scroll_to(5);
3894 let range = virt.render_range(10);
3895 let visible = virt.visible_range(10);
3897 assert_eq!(range, visible);
3898 }
3899
3900 #[test]
3903 fn scroll_on_empty_is_noop() {
3904 let mut virt: Virtualized<i32> = Virtualized::new(100);
3905 virt.scroll(10);
3906 assert_eq!(virt.scroll_offset(), 0);
3907 }
3908
3909 #[test]
3910 fn scroll_delta_zero_does_not_disable_follow() {
3911 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3912 virt.push(1);
3913 virt.scroll(0);
3914 assert!(virt.follow_mode());
3916 }
3917
3918 #[test]
3919 fn scroll_negative_beyond_start() {
3920 let mut virt: Virtualized<i32> = Virtualized::new(100);
3921 for i in 0..10 {
3922 virt.push(i);
3923 }
3924 virt.scroll(-1);
3925 assert_eq!(virt.scroll_offset(), 0);
3926 }
3927
3928 #[test]
3929 fn scroll_to_on_empty() {
3930 let mut virt: Virtualized<i32> = Virtualized::new(100);
3931 virt.scroll_to(100);
3933 assert_eq!(virt.scroll_offset(), 0);
3934 }
3935
3936 #[test]
3937 fn scroll_to_top_already_at_top() {
3938 let mut virt: Virtualized<i32> = Virtualized::new(100);
3939 virt.push(1);
3940 virt.scroll_to_top();
3941 assert_eq!(virt.scroll_offset(), 0);
3942 }
3943
3944 #[test]
3945 fn scroll_to_bottom_fewer_items_than_visible() {
3946 let mut virt: Virtualized<i32> = Virtualized::new(100);
3947 virt.set_visible_count(10);
3948 for i in 0..3 {
3949 virt.push(i);
3950 }
3951 virt.scroll_to_bottom();
3952 assert_eq!(virt.scroll_offset(), 0);
3954 }
3955
3956 #[test]
3957 fn scroll_to_bottom_visible_count_zero() {
3958 let mut virt: Virtualized<i32> = Virtualized::new(100);
3959 for i in 0..20 {
3960 virt.push(i);
3961 }
3962 virt.scroll_to_bottom();
3964 assert_eq!(virt.scroll_offset, usize::MAX);
3966 assert_eq!(virt.scroll_offset(), 19);
3968 }
3969
3970 #[test]
3973 fn page_up_visible_count_zero_is_noop() {
3974 let mut virt: Virtualized<i32> = Virtualized::new(100);
3975 for i in 0..20 {
3976 virt.push(i);
3977 }
3978 virt.scroll_to(10);
3979 virt.page_up();
3981 assert_eq!(virt.scroll_offset(), 10);
3982 }
3983
3984 #[test]
3985 fn page_down_visible_count_zero_is_noop() {
3986 let mut virt: Virtualized<i32> = Virtualized::new(100);
3987 for i in 0..20 {
3988 virt.push(i);
3989 }
3990 virt.page_down();
3992 assert_eq!(virt.scroll_offset(), 0);
3993 }
3994
3995 #[test]
3998 fn is_at_bottom_fewer_items_than_visible() {
3999 let mut virt: Virtualized<i32> = Virtualized::new(100);
4000 virt.set_visible_count(10);
4001 for i in 0..3 {
4002 virt.push(i);
4003 }
4004 assert!(virt.is_at_bottom());
4005 }
4006
4007 #[test]
4008 fn is_at_bottom_empty() {
4009 let virt: Virtualized<i32> = Virtualized::new(100);
4010 assert!(virt.is_at_bottom());
4012 }
4013
4014 #[test]
4017 fn trim_front_under_max_returns_zero() {
4018 let mut virt: Virtualized<i32> = Virtualized::new(100);
4019 for i in 0..5 {
4020 virt.push(i);
4021 }
4022 let removed = virt.trim_front(10);
4023 assert_eq!(removed, 0);
4024 assert_eq!(virt.len(), 5);
4025 }
4026
4027 #[test]
4028 fn trim_front_adjusts_scroll_offset() {
4029 let mut virt: Virtualized<i32> = Virtualized::new(100);
4030 for i in 0..20 {
4031 virt.push(i);
4032 }
4033 virt.scroll_to(10);
4034 let removed = virt.trim_front(15);
4035 assert_eq!(removed, 5);
4036 assert_eq!(virt.len(), 15);
4037 assert_eq!(virt.scroll_offset(), 5);
4039 }
4040
4041 #[test]
4042 fn trim_front_scroll_offset_saturates_to_zero() {
4043 let mut virt: Virtualized<i32> = Virtualized::new(100);
4044 for i in 0..20 {
4045 virt.push(i);
4046 }
4047 virt.scroll_to(2);
4048 let removed = virt.trim_front(10);
4049 assert_eq!(removed, 10);
4050 assert_eq!(virt.scroll_offset(), 0);
4052 }
4053
4054 #[test]
4055 fn trim_front_on_external_returns_zero() {
4056 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4057 let removed = virt.trim_front(5);
4058 assert_eq!(removed, 0);
4059 }
4060
4061 #[test]
4062 fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
4063 let mut virt: Virtualized<i32> = Virtualized::new(100);
4064 for i in 0..20 {
4065 virt.push(i);
4066 }
4067
4068 virt.scroll_to_bottom();
4071 assert_eq!(virt.scroll_offset, usize::MAX);
4072
4073 let range = virt.visible_range(10);
4076 assert_eq!(range, 10..20);
4077 assert_eq!(virt.visible_count(), 10);
4078 }
4079
4080 #[test]
4083 fn clear_on_external_resets_scroll() {
4084 let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4085 virt.scroll_to(50);
4086 virt.clear();
4087 assert_eq!(virt.scroll_offset(), 0);
4088 assert_eq!(virt.len(), 100);
4090 }
4091
4092 #[test]
4095 fn tick_zero_velocity_is_noop() {
4096 let mut virt: Virtualized<i32> = Virtualized::new(100);
4097 for i in 0..20 {
4098 virt.push(i);
4099 }
4100 virt.tick(Duration::from_millis(100));
4101 assert_eq!(virt.scroll_offset(), 0);
4102 }
4103
4104 #[test]
4105 fn tick_below_threshold_stops_momentum() {
4106 let mut virt: Virtualized<i32> = Virtualized::new(100);
4107 for i in 0..20 {
4108 virt.push(i);
4109 }
4110 virt.fling(0.05); virt.tick(Duration::from_millis(100));
4112 assert_eq!(virt.scroll_offset(), 0);
4114 }
4115
4116 #[test]
4117 fn tick_zero_duration_no_scroll() {
4118 let mut virt: Virtualized<i32> = Virtualized::new(100);
4119 for i in 0..50 {
4120 virt.push(i);
4121 }
4122 virt.fling(100.0);
4123 virt.tick(Duration::ZERO);
4124 assert_eq!(virt.scroll_offset(), 0);
4126 }
4127
4128 #[test]
4129 fn fling_negative_scrolls_up() {
4130 let mut virt: Virtualized<i32> = Virtualized::new(100);
4131 for i in 0..50 {
4132 virt.push(i);
4133 }
4134 virt.scroll(20);
4135 let before = virt.scroll_offset();
4136 virt.fling(-50.0);
4137 virt.tick(Duration::from_millis(100));
4138 assert!(virt.scroll_offset() < before);
4139 }
4140
4141 #[test]
4144 fn follow_mode_auto_scrolls_on_push() {
4145 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4146 virt.set_visible_count(5);
4147 for i in 0..20 {
4148 virt.push(i);
4149 }
4150 assert!(virt.is_at_bottom());
4152 assert_eq!(virt.scroll_offset(), 15); }
4154
4155 #[test]
4156 fn set_follow_false_does_not_scroll() {
4157 let mut virt: Virtualized<i32> = Virtualized::new(100);
4158 virt.set_visible_count(5);
4159 for i in 0..20 {
4160 virt.push(i);
4161 }
4162 virt.scroll_to(5);
4163 virt.set_follow(false);
4164 assert_eq!(virt.scroll_offset(), 5); }
4166
4167 #[test]
4168 fn scroll_to_start_disables_follow() {
4169 let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4170 virt.set_visible_count(5);
4171 for i in 0..20 {
4172 virt.push(i);
4173 }
4174 virt.scroll_to_start();
4175 assert!(!virt.follow_mode());
4176 assert_eq!(virt.scroll_offset(), 0);
4177 }
4178
4179 #[test]
4180 fn scroll_to_end_enables_follow() {
4181 let mut virt: Virtualized<i32> = Virtualized::new(100);
4182 virt.set_visible_count(5);
4183 for i in 0..20 {
4184 virt.push(i);
4185 }
4186 assert!(!virt.follow_mode());
4187 virt.scroll_to_end();
4188 assert!(virt.follow_mode());
4189 assert!(virt.is_at_bottom());
4190 }
4191
4192 #[test]
4193 fn external_follow_mode_scrolls_on_set_external_len() {
4194 let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
4195 virt.set_visible_count(5);
4196 virt.set_external_len(20);
4197 assert_eq!(virt.len(), 20);
4198 assert!(virt.is_at_bottom());
4199 }
4200
4201 #[test]
4204 fn builder_chain_all_options() {
4205 let virt: Virtualized<i32> = Virtualized::new(100)
4206 .with_fixed_height(3)
4207 .with_overscan(5)
4208 .with_follow(true);
4209 assert!(virt.follow_mode());
4210 let range = virt.visible_range(9);
4213 assert_eq!(range, 0..0);
4214 }
4215
4216 #[test]
4219 fn height_cache_default() {
4220 let cache = HeightCache::default();
4221 assert_eq!(cache.get(0), 1); assert_eq!(cache.capacity, 1000);
4223 }
4224
4225 #[test]
4226 fn height_cache_get_before_base_offset() {
4227 let mut cache = HeightCache::new(5, 100);
4228 cache.set(200, 10); assert_eq!(cache.get(0), 5);
4232 }
4233
4234 #[test]
4235 fn height_cache_set_before_base_offset_ignored() {
4236 let mut cache = HeightCache::new(5, 100);
4237 cache.set(200, 10);
4238 let base = cache.base_offset;
4239 cache.set(0, 99); assert_eq!(cache.get(0), 5); assert_eq!(cache.base_offset, base); }
4243
4244 #[test]
4245 fn height_cache_capacity_zero_ignores_all_sets() {
4246 let mut cache = HeightCache::new(3, 0);
4247 cache.set(0, 10);
4248 cache.set(5, 20);
4249 assert_eq!(cache.get(0), 3);
4251 assert_eq!(cache.get(5), 3);
4252 }
4253
4254 #[test]
4255 fn height_cache_clear_resets_base() {
4256 let mut cache = HeightCache::new(1, 100);
4257 cache.set(50, 10);
4258 cache.clear();
4259 assert_eq!(cache.base_offset, 0);
4260 assert_eq!(cache.get(50), 1); }
4262
4263 #[test]
4264 fn height_cache_eviction_trims_oldest() {
4265 let mut cache = HeightCache::new(1, 4);
4266 for i in 0..6 {
4268 cache.set(i, (i + 10) as u16);
4269 }
4270 assert!(cache.cache.len() <= cache.capacity);
4272 assert_eq!(cache.get(5), 15);
4274 assert_eq!(cache.get(4), 14);
4275 assert_eq!(cache.get(3), 13);
4276 assert_eq!(cache.get(2), 12);
4277 assert_eq!(cache.get(1), 1);
4279 assert_eq!(cache.get(0), 1);
4280 }
4281
4282 #[test]
4285 fn fenwick_default_is_empty() {
4286 let tracker = VariableHeightsFenwick::default();
4287 assert!(tracker.is_empty());
4288 assert_eq!(tracker.len(), 0);
4289 assert_eq!(tracker.total_height(), 0);
4290 assert_eq!(tracker.default_height(), 1);
4291 }
4292
4293 #[test]
4294 fn fenwick_get_beyond_len_returns_default() {
4295 let tracker = VariableHeightsFenwick::new(3, 5);
4296 assert_eq!(tracker.get(5), 3); assert_eq!(tracker.get(100), 3);
4298 }
4299
4300 #[test]
4301 fn fenwick_set_beyond_len_resizes() {
4302 let mut tracker = VariableHeightsFenwick::new(2, 3);
4303 assert_eq!(tracker.len(), 3);
4304 tracker.set(10, 7);
4305 assert!(tracker.len() > 10);
4306 assert_eq!(tracker.get(10), 7);
4307 }
4308
4309 #[test]
4310 fn fenwick_offset_of_item_zero_always_zero() {
4311 let tracker = VariableHeightsFenwick::new(5, 10);
4312 assert_eq!(tracker.offset_of_item(0), 0);
4313
4314 let empty = VariableHeightsFenwick::new(5, 0);
4315 assert_eq!(empty.offset_of_item(0), 0);
4316 }
4317
4318 #[test]
4319 fn fenwick_find_item_at_offset_empty() {
4320 let tracker = VariableHeightsFenwick::new(1, 0);
4321 assert_eq!(tracker.find_item_at_offset(0), 0);
4322 assert_eq!(tracker.find_item_at_offset(100), 0);
4323 }
4324
4325 #[test]
4326 fn fenwick_visible_count_zero_viewport() {
4327 let tracker = VariableHeightsFenwick::new(2, 10);
4328 assert_eq!(tracker.visible_count(0, 0), 0);
4329 }
4330
4331 #[test]
4332 fn fenwick_visible_count_start_beyond_len() {
4333 let tracker = VariableHeightsFenwick::new(2, 5);
4334 let count = tracker.visible_count(100, 10);
4336 assert_eq!(count, 0);
4338 }
4339
4340 #[test]
4341 fn fenwick_clear_then_operations() {
4342 let mut tracker = VariableHeightsFenwick::new(3, 5);
4343 assert_eq!(tracker.total_height(), 15);
4344 tracker.clear();
4345 assert_eq!(tracker.len(), 0);
4346 assert_eq!(tracker.total_height(), 0);
4347 assert_eq!(tracker.find_item_at_offset(0), 0);
4348 }
4349
4350 #[test]
4351 fn fenwick_rebuild_replaces_data() {
4352 let mut tracker = VariableHeightsFenwick::new(1, 10);
4353 assert_eq!(tracker.total_height(), 10);
4354 tracker.rebuild(&[5, 3, 2]);
4355 assert_eq!(tracker.len(), 3);
4356 assert_eq!(tracker.total_height(), 10);
4357 assert_eq!(tracker.get(0), 5);
4358 assert_eq!(tracker.get(1), 3);
4359 assert_eq!(tracker.get(2), 2);
4360 }
4361
4362 #[test]
4363 fn fenwick_resize_same_size_is_noop() {
4364 let mut tracker = VariableHeightsFenwick::new(2, 5);
4365 tracker.set(2, 10);
4366 tracker.resize(5);
4367 assert_eq!(tracker.get(2), 10);
4369 assert_eq!(tracker.len(), 5);
4370 }
4371
4372 #[test]
4375 fn list_state_default_matches_new() {
4376 let d = VirtualizedListState::default();
4377 let n = VirtualizedListState::new();
4378 assert_eq!(d.selected, n.selected);
4379 assert_eq!(d.scroll_offset(), n.scroll_offset());
4380 assert_eq!(d.visible_count(), n.visible_count());
4381 assert_eq!(d.follow_mode(), n.follow_mode());
4382 }
4383
4384 #[test]
4385 fn list_state_select_next_on_empty() {
4386 let mut state = VirtualizedListState::new();
4387 state.select_next(0);
4388 assert_eq!(state.selected, None);
4389 }
4390
4391 #[test]
4392 fn list_state_select_previous_on_empty() {
4393 let mut state = VirtualizedListState::new();
4394 state.select_previous(0);
4395 assert_eq!(state.selected, None);
4396 }
4397
4398 #[test]
4399 fn list_state_select_previous_from_none() {
4400 let mut state = VirtualizedListState::new();
4401 state.select_previous(10);
4402 assert_eq!(state.selected, Some(0));
4403 }
4404
4405 #[test]
4406 fn list_state_select_next_from_none() {
4407 let mut state = VirtualizedListState::new();
4408 state.select_next(10);
4409 assert_eq!(state.selected, Some(0));
4410 }
4411
4412 #[test]
4413 fn list_state_scroll_zero_items() {
4414 let mut state = VirtualizedListState::new();
4415 state.scroll(10, 0);
4416 assert_eq!(state.scroll_offset(), 0);
4417 }
4418
4419 #[test]
4420 fn list_state_scroll_to_clamps() {
4421 let mut state = VirtualizedListState::new();
4422 state.scroll_to(100, 10);
4423 assert_eq!(state.scroll_offset(), 9);
4424 }
4425
4426 #[test]
4427 fn list_state_scroll_to_bottom_zero_items() {
4428 let mut state = VirtualizedListState::new();
4429 state.scroll_to_bottom(0);
4430 assert_eq!(state.scroll_offset(), 0);
4431 }
4432
4433 #[test]
4434 fn list_state_is_at_bottom_zero_items() {
4435 let state = VirtualizedListState::new();
4436 assert!(state.is_at_bottom(0));
4437 }
4438
4439 #[test]
4440 fn list_state_page_up_visible_count_zero() {
4441 let mut state = VirtualizedListState::new();
4442 state.scroll_offset = 5;
4443 state.page_up(20);
4444 assert_eq!(state.scroll_offset(), 5);
4446 }
4447
4448 #[test]
4449 fn list_state_page_down_visible_count_zero() {
4450 let mut state = VirtualizedListState::new();
4451 state.page_down(20);
4452 assert_eq!(state.scroll_offset(), 0);
4454 }
4455
4456 #[test]
4457 fn list_state_set_follow_false_no_scroll() {
4458 let mut state = VirtualizedListState::new();
4459 state.scroll_offset = 5;
4460 state.set_follow(false, 20);
4461 assert_eq!(state.scroll_offset(), 5); assert!(!state.follow_mode());
4463 }
4464
4465 #[test]
4466 fn list_state_persistence_id() {
4467 let state = VirtualizedListState::new().with_persistence_id("my-list");
4468 assert_eq!(state.persistence_id(), Some("my-list"));
4469 }
4470
4471 #[test]
4472 fn list_state_persistence_id_none() {
4473 let state = VirtualizedListState::new();
4474 assert_eq!(state.persistence_id(), None);
4475 }
4476
4477 #[test]
4478 fn list_state_momentum_tick_zero_items() {
4479 let mut state = VirtualizedListState::new();
4480 state.fling(50.0);
4481 state.tick(Duration::from_millis(100), 0);
4482 assert_eq!(state.scroll_offset(), 0);
4484 }
4485
4486 #[test]
4489 fn persist_state_default() {
4490 let ps = VirtualizedListPersistState::default();
4491 assert_eq!(ps.selected, None);
4492 assert_eq!(ps.scroll_offset, 0);
4493 assert!(!ps.follow_mode);
4494 }
4495
4496 #[test]
4497 fn persist_state_eq() {
4498 let a = VirtualizedListPersistState {
4499 selected: Some(5),
4500 scroll_offset: 10,
4501 follow_mode: true,
4502 };
4503 let b = a.clone();
4504 assert_eq!(a, b);
4505 }
4506
4507 #[test]
4510 fn stateful_state_key_with_persistence_id() {
4511 use crate::stateful::Stateful;
4512 let state = VirtualizedListState::new().with_persistence_id("logs");
4513 let key = state.state_key().expect("named list has a key");
4514 assert_eq!(key.widget_type, "VirtualizedList");
4515 assert_eq!(key.instance_id, "logs");
4516 }
4517
4518 #[test]
4519 fn stateful_state_without_id_is_not_persisted() {
4520 use crate::stateful::Stateful;
4521 assert!(VirtualizedListState::new().state_key().is_none());
4522 }
4523
4524 #[test]
4525 fn stateful_save_restore_roundtrip() {
4526 use crate::stateful::Stateful;
4527 let mut state = VirtualizedListState::new();
4528 state.selected = Some(7);
4529 state.scroll_offset = 15;
4530 state.follow_mode = true;
4531 state.scroll_velocity = 42.0; let saved = state.save_state();
4534 assert_eq!(saved.selected, Some(7));
4535 assert_eq!(saved.scroll_offset, 15);
4536 assert!(saved.follow_mode);
4537
4538 let mut restored = VirtualizedListState::new();
4539 restored.scroll_velocity = 99.0;
4540 restored.restore_state(saved);
4541 assert_eq!(restored.selected, Some(7));
4542 assert_eq!(restored.scroll_offset, 15);
4543 assert!(restored.follow_mode);
4544 assert_eq!(restored.scroll_velocity, 0.0);
4546 }
4547
4548 #[test]
4551 fn virtualized_list_builder() {
4552 let items: Vec<String> = vec!["a".into()];
4553 let list = VirtualizedList::new(&items)
4554 .style(Style::default())
4555 .highlight_style(Style::default())
4556 .show_scrollbar(false)
4557 .fixed_height(3);
4558 assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
4559 assert!(!list.show_scrollbar);
4560 assert_eq!(
4561 VirtualizedList::new(&items)
4562 .variable_heights()
4563 .height_mode(),
4564 ListHeightMode::Variable
4565 );
4566 }
4567
4568 #[test]
4573 fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
4574 let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
4575 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4576 panic!("expected the Fenwick tracker, got {:?}", v.item_height());
4577 };
4578 assert_eq!(tracker.len(), 10_000);
4579 assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
4580 for k in 0..100u32 {
4581 let offset = k * 297;
4582 let idx = tracker.find_item_at_offset(offset);
4583 let start = tracker.offset_of_item(idx);
4584 assert!(
4585 start <= offset && offset < start + u32::from(tracker.get(idx)),
4586 "offset {offset} must land inside item {idx} [{start}, +{})",
4587 tracker.get(idx)
4588 );
4589 }
4590
4591 v.scroll_to(9_999);
4592 let range = v.visible_range(24);
4593 assert_eq!(range.end, 10_000);
4594 assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
4595
4596 v.observe_height(5, 7);
4597 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4598 unreachable!()
4599 };
4600 assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
4601 assert!(tracker.is_measured(5));
4602 assert_eq!(v.unmeasured_item_height(), 3);
4603 }
4604
4605 #[test]
4608 fn variable_height_tracker_follows_owned_storage() {
4609 let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
4610 for i in 0..5 {
4611 v.push(format!("row {i}"));
4612 }
4613 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4614 unreachable!()
4615 };
4616 assert_eq!(tracker.len(), 5);
4617 assert_eq!(tracker.total_height(), 10);
4618
4619 v.observe_height(0, 5);
4620 v.observe_height(3, 4);
4621 assert_eq!(v.trim_front(3), 2);
4622 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4623 unreachable!()
4624 };
4625 assert_eq!(tracker.len(), 3);
4626 assert!(!tracker.is_measured(0));
4628 assert!(tracker.is_measured(1));
4629 assert_eq!(tracker.get(1), 4);
4630 assert_eq!(tracker.total_height(), 2 + 4 + 2);
4631
4632 v.clear();
4633 let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4634 unreachable!()
4635 };
4636 assert_eq!(tracker.len(), 0);
4637 assert_eq!(tracker.total_height(), 0);
4638 }
4639
4640 #[test]
4644 fn legacy_height_cache_follows_owned_storage() {
4645 let mut v: Virtualized<String> =
4646 Virtualized::new(8).with_item_height(ItemHeight::Variable(HeightCache::new(1, 64)));
4647 for i in 0..6 {
4648 v.push(format!("row {i}"));
4649 }
4650 v.observe_height(0, 9);
4651 v.observe_height(4, 4);
4652 assert_eq!(v.trim_front(3), 3);
4653
4654 let ItemHeight::Variable(cache) = v.item_height() else {
4655 unreachable!()
4656 };
4657 assert_eq!(cache.get(0), 1);
4659 assert_eq!(cache.get(1), 4);
4660 assert_eq!(v.visible_range(4), 0..2);
4662
4663 v.clear();
4664 for i in 0..3 {
4665 v.push(format!("fresh {i}"));
4666 }
4667 let ItemHeight::Variable(cache) = v.item_height() else {
4668 unreachable!()
4669 };
4670 assert_eq!(cache.get(0), 1);
4671 assert_eq!(cache.get(1), 1);
4672 assert_eq!(v.visible_range(4), 0..3);
4673 }
4674
4675 #[test]
4678 fn height_cache_drop_front_shifts_a_window_past_the_prefix() {
4679 let mut cache = HeightCache::new(1, 4);
4680 for idx in 10..14 {
4681 cache.set(idx, idx as u16);
4682 }
4683 cache.drop_front(10);
4684 for idx in 0..4 {
4685 assert_eq!(cache.get(idx), 10 + idx as u16);
4686 }
4687
4688 cache.drop_front(2);
4690 assert_eq!(cache.get(0), 12);
4691 assert_eq!(cache.get(1), 13);
4692 assert_eq!(cache.get(2), 1);
4693
4694 cache.drop_front(9);
4696 assert_eq!(cache.get(0), 1);
4697 }
4698
4699 #[test]
4700 fn measure_updates_fenwick_and_predictor() {
4701 let mut list: Virtualized<String> = Virtualized::external(10, 0)
4702 .with_variable_heights(3)
4703 .with_height_prediction(PredictorConfig {
4704 default_height: 3,
4705 prior_mean: 3.0,
4706 prior_strength: 100.0,
4707 ..PredictorConfig::default()
4708 });
4709 let ItemHeight::VariableFenwick(before) = list.item_height() else {
4710 panic!("expected Fenwick heights");
4711 };
4712 let offset = before.offset_of_item(6);
4713 list.measure(5, 7);
4714 let ItemHeight::VariableFenwick(after) = list.item_height() else {
4715 panic!("expected Fenwick heights");
4716 };
4717 assert_eq!(after.offset_of_item(6), offset + 4);
4718 assert_eq!(list.predictor_stats().unwrap().measurements, 1);
4719 assert_eq!(list.predicted_height(0), 3);
4720 }
4721
4722 #[test]
4723 fn unmeasured_rows_use_predicted_mean() {
4724 let mut list: Virtualized<String> = Virtualized::external(100, 0)
4725 .with_variable_heights(1)
4726 .with_height_prediction(PredictorConfig::default());
4727 for idx in 0..20 {
4728 list.measure(idx, 4);
4729 }
4730 assert_eq!(list.predicted_height(0), 4);
4731 assert_eq!(list.predictor_stats().unwrap().measurements, 20);
4732 let ItemHeight::VariableFenwick(heights) = list.item_height() else {
4733 panic!("expected Fenwick heights");
4734 };
4735 assert!(!heights.is_measured(99));
4736 assert_eq!(heights.get(99), 4);
4737 assert_eq!(heights.total_height(), 400);
4738 assert_eq!(String::from("uncategorized").category(), 0);
4739 }
4740
4741 #[test]
4742 fn measured_bitset_tracks_word_boundaries_resize_and_rebuild() {
4743 let mut heights = VariableHeightsFenwick::new(2, 130);
4744 for idx in [0, 63, 64, 65, 127, 128, 129] {
4745 heights.set(idx, 3);
4746 }
4747 assert_eq!(heights.unmeasured_count(), 123);
4748 assert_eq!(heights.measured.len(), 3);
4749 heights.resize(65);
4750 assert_eq!(heights.unmeasured_count(), 62);
4751 heights.resize(130);
4752 for idx in 65..130 {
4753 assert!(!heights.is_measured(idx), "stale bit at {idx}");
4754 assert_eq!(heights.get(idx), 2);
4755 }
4756 heights.rebuild(&[4; 65]);
4757 assert_eq!(heights.unmeasured_count(), 0);
4758 assert!(heights.is_measured(64));
4759 assert!(!heights.is_measured(65));
4760 heights.resize(66);
4761 assert!(!heights.is_measured(65));
4762 heights.drop_front(64);
4763 assert!(heights.is_measured(0));
4764 assert!(!heights.is_measured(1));
4765 assert_eq!(heights.get(0), 4);
4766 assert_eq!(heights.get(1), 2);
4767 heights.clear();
4768 assert!(!heights.is_measured(0));
4769 assert_eq!(heights.unmeasured_count(), 0);
4770 assert!(heights.measured.is_empty());
4771 }
4772
4773 #[test]
4774 fn trimming_measured_rows_does_not_retrain_predictor() {
4775 let mut heights =
4776 VariableHeightsFenwick::new(1, 80).with_predictor(PredictorConfig::default());
4777 for idx in 0..70 {
4778 heights.set_in_category(idx, 5, 1);
4779 }
4780 let before = heights.predictor().unwrap().stats();
4781 heights.drop_front(65);
4782 assert_eq!(heights.predictor().unwrap().stats(), before);
4783 assert_eq!(heights.unmeasured_count(), 10);
4784 for idx in 0..5 {
4785 assert!(heights.is_measured(idx));
4786 assert_eq!(heights.get(idx), 5);
4787 }
4788 }
4789
4790 #[test]
4791 fn variable_list_trains_categories_once_per_measurement() {
4792 struct Row {
4793 height: u16,
4794 category: usize,
4795 }
4796 impl RenderItem for Row {
4797 fn render(&self, area: Rect, frame: &mut Frame, _: bool, _: u16) {
4798 for y in area.y..area.bottom() {
4799 frame.buffer.set(area.x, y, Cell::from_char('x'));
4800 }
4801 }
4802
4803 fn height(&self) -> u16 {
4804 self.height
4805 }
4806
4807 fn category(&self) -> usize {
4808 self.category
4809 }
4810 }
4811 let mut items = [
4812 Row {
4813 height: 3,
4814 category: 1,
4815 },
4816 Row {
4817 height: 1,
4818 category: 0,
4819 },
4820 ];
4821 let mut state =
4822 VirtualizedListState::variable(2).with_predictor(PredictorConfig::default());
4823 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4824 let mut frame = Frame::new(10, 5, &mut pool);
4825 let area = Rect::new(0, 0, 10, 5);
4826 VirtualizedList::new(&items)
4827 .variable_heights()
4828 .render(area, &mut frame, &mut state);
4829 assert_eq!(state.predictor_stats().unwrap().measurements, 2);
4830 assert_eq!(state.predictor_stats().unwrap().categories, 2);
4831 let predictor = state.heights().unwrap().predictor().unwrap();
4832 assert_eq!(predictor.category_observations(1), 1);
4833 assert_eq!(predictor.category_observations(0), 1);
4834 assert_eq!(state.heights().unwrap().offset_of_item(1), 3);
4835 assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), Some('x'));
4836 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some(' '));
4837 VirtualizedList::new(&items)
4838 .variable_heights()
4839 .render(area, &mut frame, &mut state);
4840 assert_eq!(state.predictor_stats().unwrap().measurements, 2);
4841 items[0].height = 4;
4842 VirtualizedList::new(&items)
4843 .variable_heights()
4844 .render(area, &mut frame, &mut state);
4845 assert_eq!(state.predictor_stats().unwrap().measurements, 3);
4846 assert_eq!(
4847 state
4848 .heights()
4849 .unwrap()
4850 .predictor()
4851 .unwrap()
4852 .category_observations(1),
4853 2
4854 );
4855
4856 VirtualizedList::new(&items[..0])
4857 .variable_heights()
4858 .render(area, &mut frame, &mut state);
4859 assert_eq!(state.visible_count(), 0);
4860 assert_eq!(state.scroll_offset(), 0);
4861 assert!(state.heights().unwrap().is_empty());
4862 assert_eq!(state.predictor_stats().unwrap().measurements, 3);
4863 VirtualizedList::new(&items)
4864 .variable_heights()
4865 .render(area, &mut frame, &mut state);
4866 assert_eq!(state.predictor_stats().unwrap().measurements, 5);
4867
4868 let mut owned = Virtualized::new(2)
4869 .with_variable_heights(2)
4870 .with_height_prediction(PredictorConfig::default());
4871 owned.push(Row {
4872 height: 4,
4873 category: 1,
4874 });
4875 owned.measure(0, 4);
4876 assert_eq!(owned.predictor_stats().unwrap().categories, 2);
4877 assert_eq!(owned.predictor_stats().unwrap().measurements, 1);
4878 assert!(owned.predicted_height(1) > owned.predicted_height(0));
4879 }
4880
4881 #[test]
4885 fn virtualized_list_variable_heights_renders_by_item_height() {
4886 struct Tall(u16);
4887 impl RenderItem for Tall {
4888 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4889 let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
4890 for row in 0..area.height {
4891 frame
4892 .buffer
4893 .set(area.x, area.y + row, Cell::from_char(glyph));
4894 }
4895 }
4896 fn height(&self) -> u16 {
4897 self.0
4898 }
4899 }
4900 let column = |frame: &Frame| -> String {
4901 (0..frame.buffer.height())
4902 .map(|y| {
4903 frame
4904 .buffer
4905 .get(0, y)
4906 .and_then(|cell| cell.content.as_char())
4907 .unwrap_or(' ')
4908 })
4909 .collect()
4910 };
4911
4912 let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
4913 let list = VirtualizedList::new(&items)
4914 .variable_heights()
4915 .show_scrollbar(false);
4916 let mut state = VirtualizedListState::new();
4917 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4918
4919 let mut frame = Frame::new(4, 5, &mut pool);
4920 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4921 assert_eq!(column(&frame), "12233");
4923 assert_eq!(state.visible_count(), 3);
4924 let heights = state.heights().expect("tracker created by render");
4925 assert_eq!(heights.get(1), 2);
4926 assert!(heights.is_measured(2));
4927 assert!(heights.is_measured(4) && heights.is_measured(3));
4929 drop(frame);
4930
4931 state.select(Some(4));
4934 let mut frame = Frame::new(4, 5, &mut pool);
4935 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4936 assert_eq!(state.scroll_offset(), 3);
4937 assert_eq!(column(&frame), "122 ");
4938 assert_eq!(state.visible_count(), 2);
4939 let heights = state.heights().expect("tracker");
4940 assert_eq!(heights.total_height(), 9);
4941 assert_eq!(heights.offset_of_item(4), 7);
4942 drop(frame);
4943
4944 state.measure(0, 3);
4946 assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
4947
4948 let list = VirtualizedList::new(&items).variable_heights();
4950 let mut state = VirtualizedListState::new();
4951 let mut frame = Frame::new(4, 5, &mut pool);
4952 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4953 assert!(
4954 frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
4955 "the last column belongs to the scrollbar"
4956 );
4957 assert_eq!(column(&frame), "12233");
4958 }
4959
4960 #[test]
4961 fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
4962 #[derive(Clone, Copy)]
4963 struct Row(u16, char);
4964 impl RenderItem for Row {
4965 fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4966 for y in area.y..area.bottom() {
4967 frame.buffer.set(area.x, y, Cell::from_char(self.1));
4968 }
4969 }
4970
4971 fn height(&self) -> u16 {
4972 self.0
4973 }
4974 }
4975
4976 let mut items = vec![Row(u16::MAX, 'X'); 65_538];
4977 items.extend([Row(1, '.'); 9]);
4978 items.push(Row(1, 'Z'));
4979 let list = VirtualizedList::new(&items).variable_heights();
4980 let mut state = VirtualizedListState::new();
4981 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4982 {
4983 let mut frame = Frame::new(4, 5, &mut pool);
4984 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4985 assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
4986 }
4987 for (idx, row) in items.iter().enumerate() {
4989 state.measure(idx, row.height());
4990 }
4991 assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
4992 state.select(Some(items.len() - 1));
4993 {
4994 let mut frame = Frame::new(4, 5, &mut pool);
4995 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4996 assert_eq!(state.scroll_offset(), items.len() - 5);
4997 assert_eq!(state.visible_count(), 5);
4998 let column: String = (0..5)
4999 .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
5000 .collect();
5001 assert_eq!(column, "....Z");
5002 assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
5003 }
5004 state.select(None);
5005 state.scroll_to_top();
5006 {
5007 let mut frame = Frame::new(4, 5, &mut pool);
5008 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5009 assert_eq!(state.scroll_offset(), 0);
5010 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
5011 }
5012 state.scroll_to_bottom(items.len());
5013 let mut frame = Frame::new(4, 5, &mut pool);
5014 StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5015 assert_eq!(state.scroll_offset(), items.len() - 5);
5016 assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
5017 }
5018
5019 #[test]
5022 fn virtualized_storage_debug() {
5023 let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
5024 let dbg = format!("{:?}", storage);
5025 assert!(dbg.contains("Owned"));
5026
5027 let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
5028 len: 100,
5029 cache_capacity: 10,
5030 };
5031 let dbg = format!("{:?}", ext);
5032 assert!(dbg.contains("External"));
5033 }
5034
5035 #[test]
5036 fn test_virtualized_list_handle_mouse_drag_smooth() {
5037 use crate::scrollbar::SCROLLBAR_PART_THUMB;
5038 use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5039 use ftui_render::frame::{HitId, HitRegion};
5040
5041 let mut state = VirtualizedListState::new();
5042 let scrollbar_hit_id = HitId::new(1);
5043 let total_items = 100;
5044 let viewport_height = 10;
5045 let fixed_height = 1;
5046
5047 let track_len = 10u64;
5053 let track_pos = 0u64;
5054 let hit_data = (SCROLLBAR_PART_THUMB << 56)
5055 | ((track_len & 0x0FFF_FFFF) << 28)
5056 | (track_pos & 0x0FFF_FFFF);
5057
5058 let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
5059 let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
5060
5061 state.handle_mouse(
5062 &down_event,
5063 hit,
5064 scrollbar_hit_id,
5065 total_items,
5066 viewport_height,
5067 fixed_height,
5068 );
5069
5070 assert!(
5071 state.scrollbar_drag_anchor.is_some(),
5072 "Drag anchor should be set on down"
5073 );
5074 assert_eq!(
5075 state.scrollbar_drag_anchor.unwrap(),
5076 0,
5077 "Anchor should be 0 (clicked top of thumb)"
5078 );
5079
5080 let drag_pos = 1u64;
5085 let drag_data = (SCROLLBAR_PART_THUMB << 56)
5086 | ((track_len & 0x0FFF_FFFF) << 28)
5087 | (drag_pos & 0x0FFF_FFFF);
5088 let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
5089 let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
5090
5091 state.handle_mouse(
5092 &drag_event,
5093 drag_hit,
5094 scrollbar_hit_id,
5095 total_items,
5096 viewport_height,
5097 fixed_height,
5098 );
5099
5100 assert_eq!(
5101 state.scroll_offset, 10,
5102 "Scroll offset should update smoothly"
5103 );
5104 }
5105
5106 #[test]
5110 fn variable_height_mouse_scrolls_in_rows() {
5111 use crate::scrollbar::SCROLLBAR_PART_TRACK;
5112 use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5113 use ftui_render::frame::{HitId, HitRegion};
5114
5115 struct Tall;
5116 impl RenderItem for Tall {
5117 fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip: u16) {}
5118 fn height(&self) -> u16 {
5119 6
5120 }
5121 }
5122 let items = [Tall, Tall, Tall, Tall, Tall];
5123 let list = VirtualizedList::new(&items).variable_heights();
5124 let mut state = VirtualizedListState::new();
5125 let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5126 let area = Rect::new(0, 0, 4, 5);
5127 let mut frame = Frame::new(4, 5, &mut pool);
5128 StatefulWidget::render(&list, area, &mut frame, &mut state);
5129
5130 let id = HitId::new(1);
5131 let mouse = |state: &mut VirtualizedListState, kind, hit| {
5132 state.handle_mouse(&MouseEvent::new(kind, 3, 4), hit, id, items.len(), 5, 1);
5133 };
5134
5135 mouse(&mut state, MouseEventKind::ScrollDown, None);
5137 assert_eq!(state.scroll_offset(), 1);
5138 mouse(&mut state, MouseEventKind::ScrollUp, None);
5139 assert_eq!(state.scroll_offset(), 0);
5140
5141 let track = (SCROLLBAR_PART_TRACK << 56) | (5 << 28) | 4;
5143 mouse(
5144 &mut state,
5145 MouseEventKind::Down(MouseButton::Left),
5146 Some((id, HitRegion::Scrollbar, track)),
5147 );
5148 assert_eq!(state.scroll_offset(), 4);
5149 StatefulWidget::render(&list, area, &mut frame, &mut state);
5150 assert_eq!(state.scroll_offset(), 4, "render keeps the offset");
5151 }
5152}