cranpose_foundation/lazy/
nearest_range.rs

1//! Nearest range state for optimized key→index lookup.
2//!
3//! Based on JC's `LazyLayoutNearestRangeState`. Uses a sliding window
4//! to limit key lookup to items near the current scroll position,
5//! providing O(1) lookup instead of O(n).
6
7use std::ops::Range;
8
9/// Sliding window size for key lookup optimization.
10/// JC uses 30 for lists, 90 for grids.
11pub const NEAREST_ITEMS_SLIDING_WINDOW_SIZE: usize = 30;
12
13/// Extra items to include beyond the sliding window.
14/// JC uses 100.
15pub const NEAREST_ITEMS_EXTRA_COUNT: usize = 100;
16
17/// Tracks a range of indices near the first visible item for optimized key lookup.
18///
19/// Instead of searching all items (O(n)), we only search within this range.
20/// The range is calculated using a sliding window that only updates when
21/// the first visible item crosses a window boundary.
22///
23/// Matches JC's `LazyLayoutNearestRangeState`.
24#[derive(Debug, Clone)]
25pub struct NearestRangeState {
26    value: Range<usize>,
27    last_first_visible_item: usize,
28    sliding_window_size: usize,
29    extra_item_count: usize,
30}
31
32impl Default for NearestRangeState {
33    fn default() -> Self {
34        Self::new(0)
35    }
36}
37
38impl NearestRangeState {
39    /// Creates a new NearestRangeState with default window sizes.
40    pub fn new(first_visible_item: usize) -> Self {
41        Self::with_sizes(
42            first_visible_item,
43            NEAREST_ITEMS_SLIDING_WINDOW_SIZE,
44            NEAREST_ITEMS_EXTRA_COUNT,
45        )
46    }
47
48    /// Creates a NearestRangeState with custom window sizes.
49    pub fn with_sizes(
50        first_visible_item: usize,
51        sliding_window_size: usize,
52        extra_item_count: usize,
53    ) -> Self {
54        let value =
55            Self::calculate_range(first_visible_item, sliding_window_size, extra_item_count);
56        Self {
57            value,
58            last_first_visible_item: first_visible_item,
59            sliding_window_size,
60            extra_item_count,
61        }
62    }
63
64    /// Returns the current range of indices to search.
65    pub fn range(&self) -> Range<usize> {
66        self.value.clone()
67    }
68
69    /// Updates the range based on the new first visible item.
70    /// Only recalculates when crossing a window boundary.
71    pub fn update(&mut self, first_visible_item: usize) {
72        if first_visible_item != self.last_first_visible_item {
73            self.last_first_visible_item = first_visible_item;
74            self.value = Self::calculate_range(
75                first_visible_item,
76                self.sliding_window_size,
77                self.extra_item_count,
78            );
79        }
80    }
81
82    fn calculate_range(
83        first_visible_item: usize,
84        sliding_window_size: usize,
85        extra_item_count: usize,
86    ) -> Range<usize> {
87        let sliding_window_start =
88            sliding_window_size.saturating_mul(first_visible_item / sliding_window_size);
89        let start = sliding_window_start.saturating_sub(extra_item_count);
90        let end = sliding_window_start
91            .saturating_add(sliding_window_size)
92            .saturating_add(extra_item_count);
93        start..end
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn test_initial_range() {
103        let state = NearestRangeState::new(0);
104        assert_eq!(state.range(), 0..130);
105    }
106
107    #[test]
108    fn test_range_after_small_scroll() {
109        let mut state = NearestRangeState::new(0);
110        state.update(5);
111        assert_eq!(state.range(), 0..130);
112    }
113
114    #[test]
115    fn test_range_after_crossing_window() {
116        let mut state = NearestRangeState::new(0);
117        state.update(35);
118        assert_eq!(state.range(), 0..160);
119    }
120
121    #[test]
122    fn test_range_far_scroll() {
123        let mut state = NearestRangeState::new(0);
124        state.update(1000);
125        assert_eq!(state.range(), 890..1120);
126    }
127}
cranpose_foundation/lazy/nearest_range.rs

cranpose_foundation/lazy/
nearest_range.rs
