cranpose_foundation/lazy/
nearest_range.rs

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

cranpose_foundation/lazy/
nearest_range.rs
