sliding_windows/
sliding_windows.rs

1use std::cell::{Cell, UnsafeCell};
2use std::fmt;
3use std::marker::PhantomData;
4#[cfg(nightly)]
5use std::iterator::FusedIterator;
6
7/// This holds the backing allocation for the `Window` of an `Adaptor`.
8///
9/// See [sliding_windows](index.html) for more information.
10pub struct Storage<T> {
11    window_size: usize,
12    // this is the offset of the first element
13    window_offset: Cell<usize>,
14    /// acts as a refcount
15    uniquely_owned: Cell<bool>,
16    data: UnsafeCell<Vec<T>>,
17}
18
19impl<T> Storage<T> {
20    /// Create a new `Storage` with a given window size.
21    /// This will allocate `window_size * sizeof::<T>` bytes on the heap.
22    ///
23    /// See [sliding_windows](index.html) for more information.
24    pub fn new(window_size: usize) -> Storage<T> {
25        Storage::from_vec(Vec::with_capacity(window_size), window_size)
26    }
27
28    /// Create a new `Storage` with a given window size from a given type implementing `Into<Vec>`.
29    /// The contents of the Vec will be removed.
30    /// This will reuse the allocation of the Vec instead of allocating new memory.
31    ///
32    /// See [sliding_windows](index.html) for more information.
33    pub fn from_vec<S: Into<Vec<T>>>(vec: S, window_size: usize) -> Storage<T> {
34        Storage {
35            window_size: window_size,
36            window_offset: Cell::new(0),
37            uniquely_owned: Cell::new(true),
38            data: UnsafeCell::new(vec.into())
39        }
40    }
41
42    fn new_window<'a>(&'a self) -> Window<'a, T> {
43        // assert that the last window went out of scope
44        assert!(self.uniquely_owned.get(), "next() called before previous Window went out of scope");
45        let data = unsafe { &mut *self.data.get() };
46        let window_offset = self.window_offset.get();
47
48        self.uniquely_owned.set(false);
49
50        Window { drop_flag: &self.uniquely_owned, data: &mut data[..], window_offset: window_offset }
51    }
52
53    // push value onto self, return true if window is full (for initialization)
54    // this assumes that data.capacity >= self.window_size
55    fn push(&self, elt: T) -> bool {
56        assert!(self.uniquely_owned.get(), "next() called before previous Window went out of scope");
57        let data = unsafe { &mut *self.data.get() };
58        let window_offset = self.window_offset.get();
59
60        // if storage is not full simply push the element
61        // this is only the case when filling storage initially
62        if data.len() < self.window_size
63        {
64            data.push(elt);
65            return data.len() == self.window_size;
66        }
67
68        debug_assert!(data.len() == self.window_size);
69
70        // the storage is full, overwrite the last element
71        let new_offset;
72        if window_offset >= (self.window_size - 1) {
73            new_offset = 0;
74        } else {
75            new_offset = window_offset + 1;
76        }
77
78        data[window_offset] = elt;
79        self.window_offset.set(new_offset);
80        true
81    }
82
83    // clear backing storage
84    fn clear(&self) {
85        assert!(self.uniquely_owned.get(), "next() called before previous Window went out of scope");
86        let data = unsafe { &mut *self.data.get() };
87        data.clear();
88    }
89}
90
91impl<T> Into<Vec<T>> for Storage<T> {
92    fn into(self) -> Vec<T> {
93        assert!(self.uniquely_owned.get(), "Storage dereferenced before previous Window went out of scope");
94        unsafe {
95            self.data.into_inner()
96        }
97    }
98}
99
100/// This is the `Item` type of the `Adaptor` iterator.
101///
102/// # Usage:
103///
104/// Use [WindowIter](struct.WindowIter.html) or [WindowIterMut](struct.WindowIterMut.html) to access the elements of the Window.
105///
106/// ```
107/// use sliding_windows::IterExt;
108/// use sliding_windows::Storage;
109///
110/// let mut storage: Storage<u32> = Storage::new(3);
111/// let mut windowed_iter = (0..5).sliding_windows(&mut storage);
112///
113/// for mut window in windowed_iter {
114///     // extra scope, so that later mutable borrow is possible
115///     {
116///         for x in &window {
117///             // work with data immutably
118///         }
119///     }
120///
121///     // mutable
122///     let mut iter_mut = window.iter_mut();
123///     for x in iter_mut {
124///         // work with data mutably (affecting the next windows of course)
125///     }
126/// }
127/// ```
128///
129/// See [sliding_windows](index.html) for more information.
130pub struct Window<'a, T: 'a> {
131    drop_flag: &'a Cell<bool>,
132    // index of first element
133    window_offset: usize,
134    data: &'a mut [T],
135}
136
137impl<'a, T> Window<'a, T>
138{
139    pub fn iter(&self) -> WindowIter<T> {
140        WindowIter {
141            data: self.data,
142            current_index: self.window_offset,
143            iteration_num: 0
144        }
145    }
146
147    pub fn iter_mut(&mut self) -> WindowIterMut<T> {
148        WindowIterMut {
149            data: self.data.as_mut_ptr(),
150            data_len: self.data.len(),
151            current_index: self.window_offset,
152            iteration_num: 0,
153            _p: PhantomData
154        }
155    }
156}
157
158impl<'a, T> fmt::Debug for Window<'a, T> where T: fmt::Debug
159{
160    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
161        f.write_str("Window")?;
162        return f.debug_list().entries(self.into_iter()).finish();
163    }
164}
165
166impl<'a, T> Drop for Window<'a, T> {
167    fn drop(&mut self) {
168        // set flag to indicate this window was dropped
169        self.drop_flag.set(true);
170    }
171}
172
173impl<'a, 'b, T> PartialEq<&'b [T]> for Window<'a, T> where T: PartialEq
174{
175    fn eq(&self, other: &&'b [T]) -> bool {
176        if self.data.len() != other.len() { return false }
177        for (i, x) in self.into_iter().enumerate() {
178            if *x != other[i] { return false }
179        }
180        true
181    }
182}
183
184impl<'a, T> IntoIterator for &'a Window<'a, T>
185{
186    type Item = &'a T;
187    type IntoIter = WindowIter<'a, T>;
188    fn into_iter(self) -> Self::IntoIter {
189        self.iter()
190    }
191}
192
193pub struct WindowIter<'a, T: 'a>
194{
195    data: &'a [T],
196    current_index: usize,
197    // number of next() calls made which returned Some(_)
198    iteration_num: usize,
199}
200
201impl<'a, T> Iterator for WindowIter<'a, T>
202{
203    type Item = &'a T;
204
205    fn next(&mut self) -> Option<Self::Item> {
206        let current_element = &self.data[self.current_index];
207
208        if self.iteration_num >= self.data.len() {
209            // the end was reached
210            return None;
211        } else if self.current_index >= (self.data.len() - 1) {
212            // wrap around if the increment would create an invalid index
213            self.current_index = 0;
214        } else {
215            self.current_index += 1;
216        }
217
218        self.iteration_num += 1;
219        Some(current_element)
220    }
221
222    fn size_hint(&self) -> (usize, Option<usize>) {
223        (self.data.len(), Some(self.data.len()))
224    }
225}
226
227impl<'a, T> ExactSizeIterator for WindowIter<'a, T> {}
228#[cfg(nightly)]
229impl<'a, T> FusedIterator for WindowIter<'a, T> {}
230
231pub struct WindowIterMut<'a, T: 'a>
232{
233    data: *mut T,
234    data_len: usize,
235    current_index: usize,
236    // number of next() calls made which returned Some(_)
237    iteration_num: usize,
238    _p: PhantomData<&'a T>,
239}
240
241impl<'a, T> Iterator for WindowIterMut<'a, T>
242{
243    type Item = &'a mut T;
244
245    fn next(&mut self) -> Option<Self::Item> {
246        let current_element = unsafe { self.data.offset(self.current_index as isize).as_mut().unwrap() };
247
248        if self.iteration_num >= self.data_len {
249            // the end was reached
250            return None;
251        } else if self.current_index >= (self.data_len - 1) {
252            // wrap around if the increment would create an invalid index
253            self.current_index = 0;
254        } else {
255            self.current_index += 1;
256        }
257
258        self.iteration_num += 1;
259        Some(current_element)
260    }
261
262    fn size_hint(&self) -> (usize, Option<usize>) {
263        (self.data_len, Some(self.data_len))
264    }
265}
266
267impl<'a, T> ExactSizeIterator for WindowIterMut<'a, T> {}
268#[cfg(nightly)]
269impl<'a, T> FusedIterator for WindowIterMut<'a, T> {}
270
271// TODO add other stuff like DoubleEndedIterator etc.
272
273/// See [sliding_windows](index.html) for more information.
274pub struct Adaptor<'a, I: Iterator> where <I as Iterator>::Item: 'a {
275    iter: I,
276    done: bool,
277    storage: &'a Storage<I::Item>,
278}
279
280impl<'a, I: Iterator> Adaptor<'a, I> {
281    /// This creates a new Adaptor. Usually you should be using
282    ///
283    /// See [sliding_windows](index.html) for more information.
284    pub fn new(iter: I, storage: &'a Storage<I::Item>) -> Adaptor<'a, I> {
285        // in case the storage was reused
286        storage.clear();
287
288        Adaptor {
289            iter: iter,
290            done: false,
291            storage: storage,
292        }
293    }
294}
295
296impl<'a, I: Iterator> Iterator for Adaptor<'a, I> {
297    type Item = Window<'a, I::Item>;
298
299    fn next(&mut self) -> Option<Self::Item> {
300        if self.done || self.storage.window_size == 0 {
301            return None;
302        }
303        self.done = true;
304
305        for elt in &mut self.iter {
306            self.done = false;
307            if self.storage.push(elt) {
308                break;
309            }
310        }
311
312        if !self.done {
313            // return new window
314            Some(self.storage.new_window())
315        } else {
316            None
317        }
318    }
319
320    fn size_hint(&self) -> (usize, Option<usize>) {
321        let size = self.storage.window_size;
322        let (mut lower, mut upper): (usize, Option<usize>) = self.iter.size_hint();
323
324        if size == 0 {
325            return (0, None);
326        }
327
328        lower = match lower {
329            0 => 0,
330            x if x >= size => x - size + 1,
331            _ => 1
332        };
333
334        upper = upper.map(|upper|
335            match upper {
336                0 => 0,
337                x if x >= size => x - size + 1,
338                _ => 1
339            }
340        );
341
342        (lower, upper)
343    }
344}
sliding_windows/sliding_windows.rs

sliding_windows/
sliding_windows.rs
