foldable_deque/
lib.rs

1use std::ops::RangeFull;
2
3use monoid::Monoid;
4
5#[derive(Clone, Eq, PartialEq)]
6pub struct FoldableDeque<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> FoldableDeque<M>
15where
16    M::Set: Clone,
17{
18    pub fn new() -> Self
19    where
20        M: Default,
21    {
22        let monoid = M::default();
23        Self {
24            front: vec![],
25            front_folded: vec![monoid.id()],
26            back: vec![],
27            back_folded: vec![monoid.id()],
28            monoid,
29        }
30    }
31    pub fn push_back(&mut self, elt: M::Set) {
32        let tmp = self.monoid.op(self.back_folded.last().unwrap(), &elt);
33        self.back_folded.push(tmp);
34        self.back.push(elt);
35    }
36    pub fn push_front(&mut self, elt: M::Set) {
37        let tmp = self.monoid.op(&elt, self.front_folded.last().unwrap());
38        self.front_folded.push(tmp);
39        self.front.push(elt);
40    }
41    pub fn pop_back(&mut self) -> Option<M::Set> {
42        self.rotate_back();
43        let elt = self.back.pop()?;
44        self.back_folded.pop().unwrap();
45        Some(elt)
46    }
47    pub fn pop_front(&mut self) -> Option<M::Set> {
48        self.rotate_front();
49        let elt = self.front.pop()?;
50        self.front_folded.pop().unwrap();
51        Some(elt)
52    }
53    pub fn fold(&self, _: RangeFull) -> M::Set {
54        self.monoid.op(
55            self.front_folded.last().unwrap(),
56            self.back_folded.last().unwrap(),
57        )
58    }
59
60    fn rotate_front(&mut self) {
61        if !self.front.is_empty() {
62            return;
63        }
64        let mut front = std::mem::take(&mut self.back);
65        let len = front.len();
66
67        // *][01234*; front: [], back: [0, 1, 2, 3, 4]
68        // *012][34*; front: [2, 1, 0], back: [3, 4]
69        let back = front.split_off((len + 1) / 2);
70        front.reverse();
71        self.front = front;
72        self.back = back;
73        self.fixup();
74    }
75    fn rotate_back(&mut self) {
76        if !self.back.is_empty() {
77            return;
78        }
79        let mut back = std::mem::take(&mut self.front);
80        let len = back.len();
81
82        // *01234][*; front: [4, 3, 2, 1, 0], back: []
83        // *01][234*; front: [1, 0], back: [2, 3, 4]
84        let front = back.split_off((len + 1) / 2);
85        back.reverse();
86        self.front = front;
87        self.back = back;
88        self.fixup();
89    }
90    fn fixup(&mut self) {
91        self.front_folded = vec![self.monoid.id()];
92        self.front_folded.extend(self.front.iter().scan(
93            self.monoid.id(),
94            |acc, x| {
95                *acc = self.monoid.op(x, acc);
96                Some(acc.clone())
97            },
98        ));
99
100        self.back_folded = vec![self.monoid.id()];
101        self.back_folded.extend(self.back.iter().scan(
102            self.monoid.id(),
103            |acc, x| {
104                *acc = self.monoid.op(acc, x);
105                Some(acc.clone())
106            },
107        ));
108    }
109}
110
111impl<M: Monoid> std::fmt::Debug for FoldableDeque<M>
112where
113    M::Set: std::fmt::Debug,
114{
115    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
116        f.debug_list()
117            .entries(self.front.iter().rev().chain(self.back.iter()))
118            .finish()
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use concat_monoid::OpConcat;
125
126    use crate::FoldableDeque;
127
128    #[test]
129    fn sanity_check() {
130        let mut queue = FoldableDeque::<OpConcat<_, Vec<_>>>::new();
131        queue.push_back(vec![1]);
132        assert_eq!(queue.fold(..), vec![1]);
133        assert_eq!(queue.pop_back(), Some(vec![1]));
134
135        queue.push_back(vec![1]);
136        queue.push_back(vec![2]);
137        queue.push_back(vec![3]);
138        queue.push_back(vec![4]);
139        queue.push_back(vec![5]);
140        assert_eq!(queue.fold(..), vec![1, 2, 3, 4, 5]);
141
142        assert_eq!(queue.pop_front(), Some(vec![1]));
143        assert_eq!(queue.fold(..), vec![2, 3, 4, 5]);
144        assert_eq!(queue.pop_front(), Some(vec![2]));
145        assert_eq!(queue.fold(..), vec![3, 4, 5]);
146        assert_eq!(queue.pop_front(), Some(vec![3]));
147        assert_eq!(queue.fold(..), vec![4, 5]);
148        assert_eq!(queue.pop_front(), Some(vec![4]));
149        assert_eq!(queue.fold(..), vec![5]);
150        assert_eq!(queue.pop_front(), Some(vec![5]));
151        assert_eq!(queue.fold(..), vec![]);
152        assert_eq!(queue.pop_front(), None);
153        assert_eq!(queue.fold(..), vec![]);
154
155        queue.push_front(vec![5]);
156        queue.push_front(vec![4]);
157        queue.push_front(vec![3]);
158        queue.push_front(vec![2]);
159        queue.push_front(vec![1]);
160        assert_eq!(queue.fold(..), vec![1, 2, 3, 4, 5]);
161
162        assert_eq!(queue.pop_back(), Some(vec![5]));
163        assert_eq!(queue.fold(..), vec![1, 2, 3, 4]);
164        assert_eq!(queue.pop_back(), Some(vec![4]));
165        assert_eq!(queue.fold(..), vec![1, 2, 3]);
166        assert_eq!(queue.pop_back(), Some(vec![3]));
167        assert_eq!(queue.fold(..), vec![1, 2]);
168        assert_eq!(queue.pop_back(), Some(vec![2]));
169        assert_eq!(queue.fold(..), vec![1]);
170        assert_eq!(queue.pop_back(), Some(vec![1]));
171        assert_eq!(queue.fold(..), vec![]);
172        assert_eq!(queue.pop_back(), None);
173        assert_eq!(queue.fold(..), vec![]);
174    }
175
176    #[test]
177    fn test_fmt() {
178        let mut queue = FoldableDeque::<OpConcat<_, Vec<_>>>::new();
179        assert_eq!(format!("{queue:?}"), "[]");
180        queue.push_front(vec![2]);
181        queue.push_front(vec![1]);
182        queue.push_back(vec![3]);
183        queue.push_back(vec![4]);
184        assert_eq!(format!("{queue:?}"), "[[1], [2], [3], [4]]");
185    }
186}
foldable_deque/lib.rs

foldable_deque/
lib.rs
