sliding_window/
lib.rs

1//! This crate provides a heapless, fixed size sliding window.
2//!
3//! Sliding windows are used to hold the N most recent samples of a data stream.
4//!
5//! # Example
6//!
7//! ```rust
8//! use sliding_window::*;
9//! use sliding_window::typenum::consts::*;
10//!
11//! // Create a SlidingWindow with a window size of 4 elements
12//! let mut sw: SlidingWindow<_, U4> = SlidingWindow::new();
13//!
14//! // Insert some data
15//! sw.insert(1);
16//! sw.insert(2);
17//! sw.insert(3);
18//! sw.insert(4);
19//!
20//! // The 0 index always returns the oldest element in the window
21//! assert_eq!(1, sw[0]);
22//!
23//! // When full, inserting a new element removes and returns the oldest
24//! assert_eq!(Some(1), sw.insert(5));
25//! ```
26#![cfg_attr(not(test), no_std)]
27
28pub use generic_array::typenum;
29
30mod wrapping {
31    pub trait WrappingExt {
32        type Rhs;
33        type Output;
34        fn wrapping_add_limited(self, r: Self::Rhs, max: Self::Rhs) -> Self::Output;
35        fn wrapping_add1_limited(self, max: Self::Rhs) -> Self::Output;
36    }
37
38    impl WrappingExt for usize {
39        type Rhs = Self;
40        type Output = Self;
41        fn wrapping_add_limited(self, r: Self::Rhs, max: Self::Rhs) -> Self::Output {
42            match self.checked_add(r) {
43                Some(v) => v % max,
44                None => (r - (usize::MAX - self)) % max
45            }
46        }
47
48        fn wrapping_add1_limited(self, max: Self::Rhs) -> Self::Output {
49            if self == max - 1 { 0 } else { self + 1 }
50        }
51    }
52
53    #[cfg(test)]
54    mod test {
55        use super::WrappingExt;
56
57        #[test]
58        pub fn sanity_check() {
59            let vector: &[(usize, usize, usize, usize)] = &[
60                (5, 1, 10, 6),
61                (5, 5, 10, 0),
62                (5, 6, 10, 1),
63                (5, 16, 10, 1),
64                (usize::MAX, usize::MAX, usize::MAX, 0),
65                (usize::MAX, 1, usize::MAX, 1),
66                (usize::MAX - 1, 2, usize::MAX, 1)
67            ];
68
69            for &(lhs, rhs, limit, expectation) in vector.iter() {
70                assert_eq!(expectation, lhs.wrapping_add_limited(rhs, limit), "({} + {}) mod {} == {}", lhs, rhs, limit, expectation);
71            }
72        }
73
74        #[test]
75        pub fn sanity_check_increment() {
76            let vector: &[(usize, usize, usize)] = &[
77                (5, 10, 6),
78                (9, 10, 0)
79            ];
80
81            for &(lhs, limit, expectation) in vector.iter() {
82                assert_eq!(lhs.wrapping_add_limited(1, limit), lhs.wrapping_add1_limited(limit), "({} + 1) mod {} == {}", lhs, limit, expectation);
83            }
84        }
85    }
86}
87
88use generic_array::{GenericArray, ArrayLength, sequence::GenericSequence};
89use wrapping::WrappingExt as _;
90use core::mem::MaybeUninit;
91
92pub trait Size<I>: ArrayLength<MaybeUninit<I>> {}
93impl<T, I> Size<I> for T where T: ArrayLength<MaybeUninit<I>> {}
94
95/// A sliding window.
96///
97/// Sliding windows are queues that overwrite their oldest data when full.
98pub struct SlidingWindow<IT, N>
99    where
100        N: Size<IT> {
101    items: GenericArray<MaybeUninit<IT>, N>,
102    write_idx: usize,
103    is_full: bool
104}
105
106impl<IT, N> Default for SlidingWindow<IT, N>
107    where
108        N: Size<IT> {
109
110    fn default() -> Self {
111        Self {
112            items: GenericArray::generate(|_| MaybeUninit::uninit()),
113            write_idx: 0,
114            is_full: false
115        }
116    }
117}
118
119impl<IT, N> core::ops::Index<usize> for SlidingWindow<IT, N>
120    where
121        N: Size<IT> {
122    type Output = IT;
123    fn index(&self, idx: usize) -> &Self::Output {
124        let read_from = if self.is_full {
125            self.write_idx.wrapping_add_limited(idx, N::USIZE)
126        } else {
127            assert!(idx < self.write_idx, "Trying to access uninitialized memory");
128            idx
129        };
130
131        unsafe { &*self.items[read_from].as_ptr() }
132    }
133}
134
135/// Read-only iterator that returns elements in the order of insertion.
136pub struct Iter<'a, IT, N>
137    where
138        N: Size<IT> {
139    window: &'a SlidingWindow<IT, N>,
140    start: usize,
141    offset: usize,
142    count: usize
143}
144
145impl<'a, IT, N> Iterator for Iter<'a, IT, N>
146    where N:
147        Size<IT> {
148    type Item = &'a IT;
149
150    fn next(&mut self) -> Option<Self::Item> {
151        if self.offset < self.count {
152            let read_from = self.start.wrapping_add_limited(self.offset, N::USIZE);
153            self.offset += 1;
154
155            Some(unsafe { &*self.window.items[read_from].as_ptr() })
156        } else {
157            None
158        }
159    }
160
161    fn size_hint(&self) -> (usize, Option<usize>) {
162        let remaining = self.count - self.offset;
163        (remaining, Some(remaining))
164    }
165}
166
167impl<'a, IT, N> ExactSizeIterator for Iter<'a, IT, N>
168    where N:
169        Size<IT> {
170    fn len(&self) -> usize {
171        let (lower, upper) = self.size_hint();
172        debug_assert_eq!(upper, Some(lower));
173        lower
174    }
175}
176
177/// Read-only iterator that does not respect the order of insertion.
178pub struct UnorderedIter<'a, IT, N>
179    where
180        N: Size<IT> {
181    window: &'a SlidingWindow<IT, N>,
182    offset: usize
183}
184
185impl<'a, IT, N> Iterator for UnorderedIter<'a, IT, N>
186    where
187        N: Size<IT> {
188    type Item = &'a IT;
189
190    fn next(&mut self) -> Option<Self::Item> {
191        if self.offset > 0 {
192            self.offset -= 1;
193
194            Some(unsafe { &*self.window.items[self.offset].as_ptr() })
195        } else {
196            None
197        }
198    }
199
200    fn size_hint(&self) -> (usize, Option<usize>) {
201        let remaining = self.offset;
202        (remaining, Some(remaining))
203    }
204}
205
206impl<'a, IT, N> ExactSizeIterator for UnorderedIter<'a, IT, N>
207    where N:
208        Size<IT> {
209    fn len(&self) -> usize {
210        let (lower, upper) = self.size_hint();
211        debug_assert_eq!(upper, Some(lower));
212        lower
213    }
214}
215
216impl<IT, N> SlidingWindow<IT, N>
217    where
218        N: Size<IT> {
219
220    /// Returns an empty sliding window object.
221    pub fn new() -> Self {
222        Self::default()
223    }
224
225    /// Insert an element into the window.
226    ///
227    /// If the window is full, this method will remove and return the oldest element.
228    pub fn insert(&mut self, t: IT) -> Option<IT> {
229        let new: MaybeUninit<IT> = MaybeUninit::new(t);
230
231        if !self.is_full {
232            self.items[self.write_idx] = new;
233            if self.write_idx == N::USIZE - 1 {
234                self.write_idx = 0;
235                self.is_full = true;
236            } else {
237                self.write_idx += 1;
238            }
239            None
240        } else {
241            let old = core::mem::replace(&mut self.items[self.write_idx], new);
242            self.write_idx = self.write_idx.wrapping_add1_limited(N::USIZE);
243
244            Some(unsafe { old.assume_init() })
245        }
246    }
247
248    /// Removes all elements from the window.
249    pub fn clear(&mut self) {
250        let count = self.count();
251        for elem in &mut self.items[0..count] {
252            unsafe { core::ptr::drop_in_place(elem.as_mut_ptr()); }
253        }
254
255        *self = Self::new();
256    }
257
258    /// Returns `true` if the window is full.
259    pub fn is_full(&self) -> bool {
260        self.is_full
261    }
262
263    /// Returns the number of elements stored in the window.
264    pub fn count(&self) -> usize {
265        if self.is_full {
266            N::USIZE
267        } else {
268            self.write_idx
269        }
270    }
271
272    /// Returns an iterator to read from the window.
273    ///
274    /// The iterator starts at the oldest element and ends with the newest.
275    pub fn iter(&self) -> Iter<IT, N> {
276        Iter {
277            window: self,
278            start: if self.is_full() { self.write_idx } else { 0 },
279            offset: 0,
280            count: self.count()
281        }
282    }
283
284    /// Returns an iterator to read from the window.
285    ///
286    /// This iterator starts at the beginning of the internal array instead of the oldest element
287    /// so it does not return the elements in the order of insertion.
288    pub fn iter_unordered(&self) -> UnorderedIter<IT, N> {
289        UnorderedIter {
290            window: self,
291            offset: self.count()
292        }
293    }
294}
295
296#[cfg(test)]
297mod test {
298    use super::*;
299    use super::typenum::consts::*;
300
301    #[test]
302    fn basics() {
303        let mut sw: SlidingWindow<_, U4> = SlidingWindow::new();
304
305        sw.insert(1);
306        sw.insert(2);
307        sw.insert(3);
308
309        assert_eq!(1, sw[0]);
310
311        assert_eq!(3, sw.count());
312        assert_eq!(false, sw.is_full());
313
314        assert_eq!(None, sw.insert(4));
315
316        assert_eq!(1, sw[0]);
317        assert_eq!(4, sw.count());
318        assert_eq!(true, sw.is_full());
319
320        assert_eq!(Some(1), sw.insert(5));
321
322        assert_eq!(2, sw[0]);
323        assert_eq!(4, sw.count());
324        assert_eq!(true, sw.is_full());
325
326        sw.clear();
327
328        assert_eq!(0, sw.count());
329        assert_eq!(false, sw.is_full());
330    }
331
332    #[test]
333    fn iter() {
334        let mut sw: SlidingWindow<_, U4> = SlidingWindow::new();
335
336        sw.insert(1);
337        sw.insert(2);
338        sw.insert(3);
339        sw.insert(4);
340        sw.insert(5);
341        sw.insert(6);
342
343        assert_eq!(&3, sw.iter().next().unwrap()); // first element is the oldest
344        assert_eq!(18, sw.iter().sum());
345
346        let mut ordered = sw.iter();
347        let mut unordered = sw.iter_unordered();
348
349        assert_eq!(4, ordered.len());
350        assert_eq!(4, unordered.len());
351
352        ordered.next();
353        ordered.next();
354
355        unordered.next();
356        unordered.next();
357
358        assert_eq!(2, ordered.len());
359        assert_eq!(2, unordered.len());
360    }
361
362    #[test]
363    fn unordered_iter() {
364        let mut sw: SlidingWindow<_, U4> = SlidingWindow::new();
365
366        sw.insert(1);
367        sw.insert(2);
368        sw.insert(3);
369        sw.insert(4);
370        sw.insert(5);
371        sw.insert(6);
372
373        assert_eq!(18, sw.iter_unordered().sum());
374    }
375
376    #[test]
377    #[should_panic(expected = "Trying to access uninitialized memory")]
378    fn index_to_uninited() {
379        let mut sw: SlidingWindow<_, U4> = SlidingWindow::new();
380
381        sw.insert(1);
382        sw.insert(2);
383        sw.insert(3);
384
385        sw[3];
386    }
387}
sliding_window/lib.rs

sliding_window/
lib.rs
