miniextendr_api/altrep_data/iter/
windowed.rs

1//! Windowed iterator-backed ALTREP infrastructure.
2//!
3//! Provides `WindowedIterState<I, T>` which keeps a sliding window of elements
4//! in memory, and wrapper types for each ALTREP family.
5
6use std::cell::RefCell;
7use std::sync::OnceLock;
8
9use crate::altrep_data::{AltIntegerData, AltRealData, AltrepLen, InferBase, fill_region};
10
11/// Core state for windowed iterator-backed ALTREP vectors.
12///
13/// Like [`super::IterState`], but only keeps a sliding window of elements in memory.
14/// Sequential access within the window is O(1). Access outside the window
15/// materializes the entire vector (falling back to full caching).
16///
17/// This is useful for large iterators where only a small region is accessed
18/// at a time (e.g., streaming data processed in order).
19///
20/// # Type Parameters
21///
22/// - `I`: The iterator type
23/// - `T`: The element type produced by the iterator
24pub struct WindowedIterState<I, T> {
25    len: usize,
26    iter: RefCell<Option<I>>,
27    consumed: RefCell<usize>,
28    window: RefCell<Vec<T>>,
29    window_start: RefCell<usize>,
30    window_size: usize,
31    materialized: OnceLock<Vec<T>>,
32}
33
34impl<I, T> WindowedIterState<I, T>
35where
36    I: Iterator<Item = T>,
37    T: Copy,
38{
39    /// Create a new windowed iterator state.
40    pub fn new(iter: I, len: usize, window_size: usize) -> Self {
41        let window_size = window_size.max(1);
42        Self {
43            len,
44            iter: RefCell::new(Some(iter)),
45            consumed: RefCell::new(0),
46            window: RefCell::new(Vec::with_capacity(window_size)),
47            window_start: RefCell::new(0),
48            window_size,
49            materialized: OnceLock::new(),
50        }
51    }
52
53    /// Get element at index `i`.
54    pub fn get_element(&self, i: usize) -> Option<T> {
55        if i >= self.len {
56            return None;
57        }
58
59        // Check materialized first
60        if let Some(vec) = self.materialized.get() {
61            return vec.get(i).copied();
62        }
63
64        let window_start = *self.window_start.borrow();
65        let window = self.window.borrow();
66
67        // Check if in current window
68        if i >= window_start && i < window_start + window.len() {
69            return Some(window[i - window_start]);
70        }
71        drop(window);
72
73        // Check if we can advance to reach this index
74        let consumed = *self.consumed.borrow();
75        if i >= consumed {
76            // Forward access — advance iterator to fill window containing i
77            self.advance_to(i);
78            let window = self.window.borrow();
79            let window_start = *self.window_start.borrow();
80            if i >= window_start && i < window_start + window.len() {
81                return Some(window[i - window_start]);
82            }
83            return None; // iterator exhausted
84        }
85
86        // Backward access — must materialize
87        self.materialize_all();
88        self.materialized.get().and_then(|v| v.get(i).copied())
89    }
90
91    /// Advance the iterator to fill a window containing index `i`.
92    fn advance_to(&self, i: usize) {
93        let mut iter_opt = self.iter.borrow_mut();
94        let iter = match iter_opt.as_mut() {
95            Some(it) => it,
96            None => return,
97        };
98
99        let mut consumed = self.consumed.borrow_mut();
100        let mut window = self.window.borrow_mut();
101        let mut window_start = self.window_start.borrow_mut();
102
103        // Skip elements before the target window
104        let target_window_start = if i >= self.window_size {
105            i - self.window_size + 1
106        } else {
107            0
108        };
109
110        // Skip elements we need to discard
111        while *consumed < target_window_start {
112            if iter.next().is_some() {
113                *consumed += 1;
114            } else {
115                return;
116            }
117        }
118
119        // Fill the window
120        window.clear();
121        *window_start = *consumed;
122
123        while window.len() < self.window_size && *consumed < self.len {
124            if let Some(elem) = iter.next() {
125                window.push(elem);
126                *consumed += 1;
127            } else {
128                break;
129            }
130            // Stop once we've passed index i
131            if *consumed > i + 1 && window.len() >= self.window_size {
132                break;
133            }
134        }
135    }
136
137    /// Materialize all elements.
138    pub fn materialize_all(&self) -> &[T] {
139        if let Some(vec) = self.materialized.get() {
140            return vec;
141        }
142
143        // We can only materialize elements from consumed onward
144        // For backward access, we'd need to restart the iterator
145        // Since iterators are consumed, materialize what we can
146        let mut iter_opt = self.iter.borrow_mut();
147        let window = self.window.borrow();
148        let window_start = *self.window_start.borrow();
149
150        let mut result = Vec::with_capacity(self.len);
151
152        // Copy window elements at their correct positions
153        // Start fresh approach: collect remaining from iterator
154        if let Some(iter) = iter_opt.take() {
155            // We have: window contents at window_start..window_start+window.len()
156            // And: unconsumed elements from consumed onward
157            // Elements before window_start are lost (consumed and discarded)
158
159            // Fill lost positions with default
160            for _ in 0..window_start {
161                // These elements were consumed — can't recover
162                result.push(window.first().copied().unwrap_or_else(|| {
163                    // This shouldn't happen with valid usage
164                    unsafe { std::mem::zeroed() }
165                }));
166            }
167
168            // Copy window
169            result.extend_from_slice(&window);
170
171            // Consume rest
172            for elem in iter {
173                if result.len() >= self.len {
174                    break;
175                }
176                result.push(elem);
177            }
178        }
179
180        drop(window);
181        drop(iter_opt);
182
183        if result.len() < self.len {
184            eprintln!(
185                "[miniextendr warning] windowed iterator ALTREP: could only recover {}/{} elements on materialization",
186                result.len(),
187                self.len
188            );
189        }
190
191        self.materialized.get_or_init(|| result)
192    }
193
194    /// Get materialized slice if available.
195    pub fn as_materialized(&self) -> Option<&[T]> {
196        self.materialized.get().map(|v| v.as_slice())
197    }
198
199    /// Get the length.
200    pub fn len(&self) -> usize {
201        self.len
202    }
203
204    /// Check if empty.
205    pub fn is_empty(&self) -> bool {
206        self.len == 0
207    }
208}
209
210impl<I, T> WindowedIterState<I, T>
211where
212    I: ExactSizeIterator<Item = T>,
213    T: Copy,
214{
215    /// Create from an ExactSizeIterator.
216    pub fn from_exact_size(iter: I, window_size: usize) -> Self {
217        let len = iter.len();
218        Self::new(iter, len, window_size)
219    }
220}
221// endregion
222
223// region: Windowed Iterator wrapper types
224
225/// Windowed iterator-backed integer vector data.
226///
227/// Like [`super::IterIntData`], but only keeps a sliding window of elements in memory.
228/// Sequential forward access within the window is O(1). Access outside the
229/// window triggers full materialization.
230pub struct WindowedIterIntData<I: Iterator<Item = i32>> {
231    state: WindowedIterState<I, i32>,
232}
233
234impl<I: Iterator<Item = i32>> WindowedIterIntData<I> {
235    /// Create from an iterator with explicit length and window size.
236    pub fn from_iter(iter: I, len: usize, window_size: usize) -> Self {
237        Self {
238            state: WindowedIterState::new(iter, len, window_size),
239        }
240    }
241}
242
243impl<I: ExactSizeIterator<Item = i32>> WindowedIterIntData<I> {
244    /// Create from an ExactSizeIterator with window size (length auto-detected).
245    pub fn from_exact_iter(iter: I, window_size: usize) -> Self {
246        Self {
247            state: WindowedIterState::from_exact_size(iter, window_size),
248        }
249    }
250}
251
252impl<I: Iterator<Item = i32>> AltrepLen for WindowedIterIntData<I> {
253    fn len(&self) -> usize {
254        self.state.len()
255    }
256}
257
258impl<I: Iterator<Item = i32>> AltIntegerData for WindowedIterIntData<I> {
259    fn elt(&self, i: usize) -> i32 {
260        self.state
261            .get_element(i)
262            .unwrap_or(crate::altrep_traits::NA_INTEGER)
263    }
264
265    fn as_slice(&self) -> Option<&[i32]> {
266        self.state.as_materialized()
267    }
268
269    fn get_region(&self, start: usize, len: usize, buf: &mut [i32]) -> usize {
270        fill_region(start, len, self.len(), buf, |idx| self.elt(idx))
271    }
272}
273
274impl<I: Iterator<Item = i32> + 'static> crate::externalptr::TypedExternal
275    for WindowedIterIntData<I>
276{
277    const TYPE_NAME: &'static str = "WindowedIterIntData";
278    const TYPE_NAME_CSTR: &'static [u8] = b"WindowedIterIntData\0";
279    const TYPE_ID_CSTR: &'static [u8] = b"miniextendr_api::altrep::WindowedIterIntData\0";
280}
281
282impl<I: Iterator<Item = i32> + 'static> InferBase for WindowedIterIntData<I> {
283    const BASE: crate::altrep::RBase = crate::altrep::RBase::Int;
284
285    unsafe fn make_class(
286        class_name: *const i8,
287        pkg_name: *const i8,
288    ) -> crate::ffi::altrep::R_altrep_class_t {
289        unsafe {
290            crate::ffi::altrep::R_make_altinteger_class(class_name, pkg_name, core::ptr::null_mut())
291        }
292    }
293
294    unsafe fn install_methods(cls: crate::ffi::altrep::R_altrep_class_t) {
295        unsafe { crate::altrep_bridge::install_base::<Self>(cls) };
296        unsafe { crate::altrep_bridge::install_vec::<Self>(cls) };
297        unsafe { crate::altrep_bridge::install_int::<Self>(cls) };
298    }
299}
300
301impl<I: Iterator<Item = i32> + 'static> crate::altrep_traits::Altrep for WindowedIterIntData<I> {
302    fn length(x: crate::ffi::SEXP) -> crate::ffi::R_xlen_t {
303        let data = unsafe { <Self as crate::altrep_data::AltrepExtract>::altrep_extract_ref(x) };
304        data.len() as crate::ffi::R_xlen_t
305    }
306}
307
308impl<I: Iterator<Item = i32> + 'static> crate::altrep_traits::AltVec for WindowedIterIntData<I> {}
309
310impl<I: Iterator<Item = i32> + 'static> crate::altrep_traits::AltInteger
311    for WindowedIterIntData<I>
312{
313    const HAS_ELT: bool = true;
314
315    fn elt(x: crate::ffi::SEXP, i: crate::ffi::R_xlen_t) -> i32 {
316        let data = unsafe { <Self as crate::altrep_data::AltrepExtract>::altrep_extract_ref(x) };
317        AltIntegerData::elt(data, i as usize)
318    }
319
320    const HAS_GET_REGION: bool = true;
321
322    fn get_region(
323        x: crate::ffi::SEXP,
324        start: crate::ffi::R_xlen_t,
325        len: crate::ffi::R_xlen_t,
326        buf: &mut [i32],
327    ) -> crate::ffi::R_xlen_t {
328        let data = unsafe { <Self as crate::altrep_data::AltrepExtract>::altrep_extract_ref(x) };
329        AltIntegerData::get_region(data, start as usize, len as usize, buf) as crate::ffi::R_xlen_t
330    }
331}
332
333/// Windowed iterator-backed real (f64) vector data.
334///
335/// Like [`super::IterRealData`], but only keeps a sliding window of elements in memory.
336/// Sequential forward access within the window is O(1). Access outside the
337/// window triggers full materialization.
338pub struct WindowedIterRealData<I: Iterator<Item = f64>> {
339    state: WindowedIterState<I, f64>,
340}
341
342impl<I: Iterator<Item = f64>> WindowedIterRealData<I> {
343    /// Create from an iterator with explicit length and window size.
344    pub fn from_iter(iter: I, len: usize, window_size: usize) -> Self {
345        Self {
346            state: WindowedIterState::new(iter, len, window_size),
347        }
348    }
349}
350
351impl<I: ExactSizeIterator<Item = f64>> WindowedIterRealData<I> {
352    /// Create from an ExactSizeIterator with window size (length auto-detected).
353    pub fn from_exact_iter(iter: I, window_size: usize) -> Self {
354        Self {
355            state: WindowedIterState::from_exact_size(iter, window_size),
356        }
357    }
358}
359
360impl<I: Iterator<Item = f64>> AltrepLen for WindowedIterRealData<I> {
361    fn len(&self) -> usize {
362        self.state.len()
363    }
364}
365
366impl<I: Iterator<Item = f64>> AltRealData for WindowedIterRealData<I> {
367    fn elt(&self, i: usize) -> f64 {
368        self.state.get_element(i).unwrap_or(f64::NAN)
369    }
370
371    fn as_slice(&self) -> Option<&[f64]> {
372        self.state.as_materialized()
373    }
374
375    fn get_region(&self, start: usize, len: usize, buf: &mut [f64]) -> usize {
376        fill_region(start, len, self.len(), buf, |idx| self.elt(idx))
377    }
378}
379
380impl<I: Iterator<Item = f64> + 'static> crate::externalptr::TypedExternal
381    for WindowedIterRealData<I>
382{
383    const TYPE_NAME: &'static str = "WindowedIterRealData";
384    const TYPE_NAME_CSTR: &'static [u8] = b"WindowedIterRealData\0";
385    const TYPE_ID_CSTR: &'static [u8] = b"miniextendr_api::altrep::WindowedIterRealData\0";
386}
387
388impl<I: Iterator<Item = f64> + 'static> InferBase for WindowedIterRealData<I> {
389    const BASE: crate::altrep::RBase = crate::altrep::RBase::Real;
390
391    unsafe fn make_class(
392        class_name: *const i8,
393        pkg_name: *const i8,
394    ) -> crate::ffi::altrep::R_altrep_class_t {
395        unsafe {
396            crate::ffi::altrep::R_make_altreal_class(class_name, pkg_name, core::ptr::null_mut())
397        }
398    }
399
400    unsafe fn install_methods(cls: crate::ffi::altrep::R_altrep_class_t) {
401        unsafe { crate::altrep_bridge::install_base::<Self>(cls) };
402        unsafe { crate::altrep_bridge::install_vec::<Self>(cls) };
403        unsafe { crate::altrep_bridge::install_real::<Self>(cls) };
404    }
405}
406
407impl<I: Iterator<Item = f64> + 'static> crate::altrep_traits::Altrep for WindowedIterRealData<I> {
408    fn length(x: crate::ffi::SEXP) -> crate::ffi::R_xlen_t {
409        let data = unsafe { <Self as crate::altrep_data::AltrepExtract>::altrep_extract_ref(x) };
410        data.len() as crate::ffi::R_xlen_t
411    }
412}
413
414impl<I: Iterator<Item = f64> + 'static> crate::altrep_traits::AltVec for WindowedIterRealData<I> {}
415
416impl<I: Iterator<Item = f64> + 'static> crate::altrep_traits::AltReal for WindowedIterRealData<I> {
417    const HAS_ELT: bool = true;
418
419    fn elt(x: crate::ffi::SEXP, i: crate::ffi::R_xlen_t) -> f64 {
420        let data = unsafe { <Self as crate::altrep_data::AltrepExtract>::altrep_extract_ref(x) };
421        AltRealData::elt(data, i as usize)
422    }
423
424    const HAS_GET_REGION: bool = true;
425
426    fn get_region(
427        x: crate::ffi::SEXP,
428        start: crate::ffi::R_xlen_t,
429        len: crate::ffi::R_xlen_t,
430        buf: &mut [f64],
431    ) -> crate::ffi::R_xlen_t {
432        let data = unsafe { <Self as crate::altrep_data::AltrepExtract>::altrep_extract_ref(x) };
433        AltRealData::get_region(data, start as usize, len as usize, buf) as crate::ffi::R_xlen_t
434    }
435}
436// endregion
miniextendr_api/altrep_data/iter/windowed.rs

miniextendr_api/altrep_data/iter/
windowed.rs
