competitive/data_structure/
sliding_window_aggregation.rs

1use super::Monoid;
2use std::fmt::{self, Debug, Formatter};
3
4pub struct QueueAggregation<M>
5where
6    M: Monoid,
7{
8    front_stack: Vec<(M::T, M::T)>,
9    back_stack: Vec<(M::T, M::T)>,
10}
11
12impl<M> Clone for QueueAggregation<M>
13where
14    M: Monoid,
15{
16    fn clone(&self) -> Self {
17        Self {
18            front_stack: self.front_stack.clone(),
19            back_stack: self.back_stack.clone(),
20        }
21    }
22}
23
24impl<M> Debug for QueueAggregation<M>
25where
26    M: Monoid<T: Debug>,
27{
28    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
29        f.debug_struct("QueueAggregation")
30            .field("front_stack", &self.front_stack)
31            .field("back_stack", &self.back_stack)
32            .finish()
33    }
34}
35
36impl<M> Default for QueueAggregation<M>
37where
38    M: Monoid,
39{
40    fn default() -> Self {
41        Self {
42            front_stack: Vec::new(),
43            back_stack: Vec::new(),
44        }
45    }
46}
47
48impl<M> QueueAggregation<M>
49where
50    M: Monoid,
51{
52    pub fn new() -> Self {
53        Self::default()
54    }
55    pub fn len(&self) -> usize {
56        self.front_stack.len() + self.back_stack.len()
57    }
58    pub fn is_empty(&self) -> bool {
59        self.front_stack.is_empty() && self.back_stack.is_empty()
60    }
61    pub fn fold_all(&self) -> M::T {
62        M::operate(
63            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
64            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
65        )
66    }
67    pub fn last(&self) -> Option<&M::T> {
68        self.back_stack
69            .last()
70            .or_else(|| self.front_stack.first())
71            .map(|t| &t.1)
72    }
73    pub fn push(&mut self, value: M::T) {
74        let x = M::operate(
75            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
76            &value,
77        );
78        self.back_stack.push((x, value));
79    }
80    fn push_front(&mut self, value: M::T) {
81        let x = M::operate(
82            &value,
83            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
84        );
85        self.front_stack.push((x, value));
86    }
87    pub fn pop(&mut self) -> Option<M::T> {
88        if self.front_stack.is_empty() {
89            let mut back_stack = std::mem::take(&mut self.back_stack);
90            for x in back_stack.drain(..).map(|t| t.1).rev() {
91                self.push_front(x);
92            }
93        }
94        self.front_stack.pop().map(|t| t.1)
95    }
96}
97
98pub struct DequeAggregation<M>
99where
100    M: Monoid,
101{
102    front_stack: Vec<(M::T, M::T)>,
103    back_stack: Vec<(M::T, M::T)>,
104}
105
106impl<M> Clone for DequeAggregation<M>
107where
108    M: Monoid,
109{
110    fn clone(&self) -> Self {
111        Self {
112            front_stack: self.front_stack.clone(),
113            back_stack: self.back_stack.clone(),
114        }
115    }
116}
117
118impl<M> Debug for DequeAggregation<M>
119where
120    M: Monoid<T: Debug>,
121{
122    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
123        f.debug_struct("DequeAggregation")
124            .field("front_stack", &self.front_stack)
125            .field("back_stack", &self.back_stack)
126            .finish()
127    }
128}
129
130impl<M> Default for DequeAggregation<M>
131where
132    M: Monoid,
133{
134    fn default() -> Self {
135        Self {
136            front_stack: Vec::new(),
137            back_stack: Vec::new(),
138        }
139    }
140}
141
142impl<M> DequeAggregation<M>
143where
144    M: Monoid,
145{
146    pub fn new() -> Self {
147        Self::default()
148    }
149    pub fn len(&self) -> usize {
150        self.front_stack.len() + self.back_stack.len()
151    }
152    pub fn is_empty(&self) -> bool {
153        self.front_stack.is_empty() && self.back_stack.is_empty()
154    }
155    pub fn fold_all(&self) -> M::T {
156        M::operate(
157            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
158            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
159        )
160    }
161    pub fn front(&self) -> Option<&M::T> {
162        self.front_stack
163            .last()
164            .or_else(|| self.back_stack.first())
165            .map(|t| &t.1)
166    }
167    pub fn back(&self) -> Option<&M::T> {
168        self.back_stack
169            .last()
170            .or_else(|| self.front_stack.first())
171            .map(|t| &t.1)
172    }
173    pub fn push_front(&mut self, value: M::T) {
174        let x = M::operate(
175            &value,
176            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
177        );
178        self.front_stack.push((x, value));
179    }
180    pub fn push_back(&mut self, value: M::T) {
181        let x = M::operate(
182            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
183            &value,
184        );
185        self.back_stack.push((x, value));
186    }
187    pub fn pop_front(&mut self) -> Option<M::T> {
188        if self.front_stack.is_empty() {
189            let n = self.back_stack.len();
190            let mut back_stack = std::mem::take(&mut self.back_stack);
191            for x in back_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
192                self.push_front(x);
193            }
194            for x in back_stack.drain(..).map(|t| t.1) {
195                self.push_back(x);
196            }
197        }
198        self.front_stack.pop().map(|t| t.1)
199    }
200    pub fn pop_back(&mut self) -> Option<M::T> {
201        if self.back_stack.is_empty() {
202            let n = self.front_stack.len();
203            let mut front_stack = std::mem::take(&mut self.front_stack);
204            for x in front_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
205                self.push_back(x);
206            }
207            for x in front_stack.drain(..).map(|t| t.1) {
208                self.push_front(x);
209            }
210        }
211        self.back_stack.pop().map(|t| t.1)
212    }
213}
competitive/data_structure/sliding_window_aggregation.rs

competitive/data_structure/
sliding_window_aggregation.rs
