sliding_window_aggregation/
lib.rs

1/// F must give a semigroup: it is required that F satisfies associativity.
2/// Commutativity and existence of the identity are not required.
3/// Reference: https://scrapbox.io/data-structures/Sliding_Window_Aggregation
4pub struct SWAg<T, F> {
5    back: Vec<T>,
6    back_agg: Vec<T>,
7    front: Vec<T>,
8    front_agg: Vec<T>,
9    f: F,
10}
11
12impl<T: Copy, F: Fn(T, T) -> T> SWAg<T, F> {
13    pub fn new(f: F) -> Self {
14        SWAg {
15            back: Vec::new(),
16            back_agg: Vec::new(),
17            front: Vec::new(),
18            front_agg: Vec::new(),
19            f: f,
20        }
21    }
22    pub fn fold_all(&self) -> Option<T> {
23        match (self.back_agg.last(), self.front_agg.last()) {
24            (None, None) => None,
25            (None, x) => x.cloned(),
26            (x, None) => x.cloned(),
27            (Some(&x), Some(&y)) => Some((self.f)(x, y)),
28        }
29    }
30    pub fn push_back(&mut self, x: T) {
31        let last = self.front_agg.last().cloned();
32        self.front.push(x);
33        self.front_agg.push(match last {
34            None => x,
35            Some(y) => (self.f)(y, x),
36        });
37    }
38    pub fn pop_front(&mut self) -> Option<T> {
39        match self.back.pop() {
40            Some(x) => return Some(x),
41            None => (),
42        };
43        std::mem::swap(&mut self.front, &mut self.back);
44        self.back.reverse();
45        let returned = self.back.pop();
46        let len = self.back.len();
47        self.back_agg = Vec::with_capacity(self.back.len());
48        if len > 0 {
49            self.back_agg.push(self.back[0]);
50            let mut cur = self.back[0];
51            for i in 1..len {
52                cur = (self.f)(self.back[i], cur);
53                self.back_agg.push(cur);
54            }
55        }
56        self.front = Vec::new();
57        self.front_agg = Vec::new();
58        returned
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65    #[test]
66    fn fold_all_works() {
67        let mut swag = SWAg::<i32, _>::new(|x, y| x + y);
68        swag.push_back(3);
69        swag.push_back(4);
70        swag.push_back(1);
71        assert_eq!(swag.fold_all(), Some(8));
72    }
73    #[test]
74    fn fold_all_not_commutative_works() {
75        let mut swag = SWAg::<(i32, i32), _>::new(|(x, b), (y, c)| (c * x + y, b * c));
76        swag.push_back((3, 10));
77        swag.push_back((4, 10));
78        swag.push_back((1, 10));
79        assert_eq!(swag.fold_all(), Some((341, 1000)));
80    }
81    #[test]
82    fn fold_all_with_pop_front_works() {
83        let mut swag = SWAg::<(i32, i32), _>::new(|(x, b), (y, c)| (c * x + y, b * c));
84        swag.push_back((3, 10));
85        swag.push_back((4, 10));
86        swag.push_back((5, 10));
87        swag.push_back((6, 10));
88        assert_eq!(swag.pop_front(), Some((3, 10))); // 4 5 6 |
89        swag.push_back((1, 10)); // 4 5 6 | 1
90        assert_eq!(swag.fold_all(), Some((4561, 10000)));
91    }
92}
sliding_window_aggregation/lib.rs

sliding_window_aggregation/
lib.rs
