foldable_queue/
lib.rs

1use std::ops::RangeFull;
2
3use monoid::Monoid;
4
5#[derive(Clone, PartialEq, Eq)]
6pub struct FoldableQueue<M: Monoid> {
7    front: Vec<M::Set>,
8    front_folded: Vec<M::Set>,
9    back: Vec<M::Set>,
10    back_folded: Vec<M::Set>,
11    monoid: M,
12}
13
14impl<M: Monoid> FoldableQueue<M> {
15    pub fn new() -> Self
16    where
17        M: Default,
18    {
19        let monoid = M::default();
20        Self {
21            front: vec![],
22            front_folded: vec![monoid.id()],
23            back: vec![],
24            back_folded: vec![monoid.id()],
25            monoid,
26        }
27    }
28    pub fn push(&mut self, elt: M::Set) {
29        let tmp = self.monoid.op(self.back_folded.last().unwrap(), &elt);
30        self.back_folded.push(tmp);
31        self.back.push(elt);
32    }
33    pub fn pop(&mut self) -> Option<M::Set> {
34        self.rotate();
35        let elt = self.front.pop()?;
36        self.front_folded.pop().unwrap();
37        Some(elt)
38    }
39    pub fn fold(&self, _: RangeFull) -> M::Set {
40        self.monoid.op(
41            self.front_folded.last().unwrap(),
42            self.back_folded.last().unwrap(),
43        )
44    }
45
46    fn rotate(&mut self) {
47        if !self.front.is_empty() {
48            return;
49        }
50        while let Some(elt) = self.back.pop() {
51            self.back_folded.pop();
52            self.front_folded
53                .push(self.monoid.op(&elt, self.front_folded.last().unwrap()));
54            self.front.push(elt);
55        }
56    }
57}
58
59impl<M: Monoid> std::fmt::Debug for FoldableQueue<M>
60where
61    M::Set: std::fmt::Debug,
62{
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        f.debug_list()
65            .entries(self.front.iter().rev().chain(self.back.iter()))
66            .finish()
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use concat_monoid::OpConcat;
73
74    use crate::*;
75
76    #[test]
77    fn sanity_check() {
78        let mut queue = FoldableQueue::<OpConcat<i32, Vec<_>>>::new();
79        queue.push(vec![1]);
80        assert_eq!(queue.fold(..), vec![1]);
81        assert_eq!(queue.pop(), Some(vec![1]));
82
83        queue.push(vec![1]);
84        assert_eq!(queue.fold(..), vec![1]);
85        queue.push(vec![2]);
86        assert_eq!(queue.fold(..), vec![1, 2]);
87        queue.push(vec![3]);
88        assert_eq!(queue.fold(..), vec![1, 2, 3]);
89
90        assert_eq!(queue.pop(), Some(vec![1]));
91        assert_eq!(queue.fold(..), vec![2, 3]);
92
93        queue.push(vec![4]);
94        assert_eq!(queue.fold(..), vec![2, 3, 4]);
95        assert_eq!(queue.pop(), Some(vec![2]));
96        assert_eq!(queue.fold(..), vec![3, 4]);
97        assert_eq!(queue.pop(), Some(vec![3]));
98        assert_eq!(queue.fold(..), vec![4]);
99        assert_eq!(queue.pop(), Some(vec![4]));
100        assert_eq!(queue.fold(..), vec![]);
101        assert_eq!(queue.pop(), None);
102        assert_eq!(queue.fold(..), vec![]);
103    }
104
105    #[test]
106    fn test_fmt() {
107        let mut queue = FoldableQueue::<OpConcat<_, Vec<_>>>::new();
108        assert_eq!(format!("{queue:?}"), "[]");
109        queue.push(vec![1]);
110        queue.push(vec![2]);
111        queue.push(vec![3]);
112        queue.push(vec![4]);
113        assert_eq!(format!("{queue:?}"), "[[1], [2], [3], [4]]");
114    }
115}
foldable_queue/lib.rs

foldable_queue/
lib.rs
