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            self.back_stack = back_stack;
94        }
95        self.front_stack.pop().map(|t| t.1)
96    }
97}
98
99pub struct DequeAggregation<M>
100where
101    M: Monoid,
102{
103    front_stack: Vec<(M::T, M::T)>,
104    back_stack: Vec<(M::T, M::T)>,
105}
106
107impl<M> Clone for DequeAggregation<M>
108where
109    M: Monoid,
110{
111    fn clone(&self) -> Self {
112        Self {
113            front_stack: self.front_stack.clone(),
114            back_stack: self.back_stack.clone(),
115        }
116    }
117}
118
119impl<M> Debug for DequeAggregation<M>
120where
121    M: Monoid<T: Debug>,
122{
123    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
124        f.debug_struct("DequeAggregation")
125            .field("front_stack", &self.front_stack)
126            .field("back_stack", &self.back_stack)
127            .finish()
128    }
129}
130
131impl<M> Default for DequeAggregation<M>
132where
133    M: Monoid,
134{
135    fn default() -> Self {
136        Self {
137            front_stack: Vec::new(),
138            back_stack: Vec::new(),
139        }
140    }
141}
142
143impl<M> DequeAggregation<M>
144where
145    M: Monoid,
146{
147    pub fn new() -> Self {
148        Self::default()
149    }
150    pub fn len(&self) -> usize {
151        self.front_stack.len() + self.back_stack.len()
152    }
153    pub fn is_empty(&self) -> bool {
154        self.front_stack.is_empty() && self.back_stack.is_empty()
155    }
156    pub fn fold_all(&self) -> M::T {
157        M::operate(
158            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
159            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
160        )
161    }
162    pub fn front(&self) -> Option<&M::T> {
163        self.front_stack
164            .last()
165            .or_else(|| self.back_stack.first())
166            .map(|t| &t.1)
167    }
168    pub fn back(&self) -> Option<&M::T> {
169        self.back_stack
170            .last()
171            .or_else(|| self.front_stack.first())
172            .map(|t| &t.1)
173    }
174    pub fn push_front(&mut self, value: M::T) {
175        let x = M::operate(
176            &value,
177            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
178        );
179        self.front_stack.push((x, value));
180    }
181    pub fn push_back(&mut self, value: M::T) {
182        let x = M::operate(
183            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
184            &value,
185        );
186        self.back_stack.push((x, value));
187    }
188    pub fn pop_front(&mut self) -> Option<M::T> {
189        if self.front_stack.is_empty() {
190            let n = self.back_stack.len();
191            let mut back_stack = std::mem::take(&mut self.back_stack);
192            for x in back_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
193                self.push_front(x);
194            }
195            for x in back_stack.drain(..).map(|t| t.1) {
196                self.push_back(x);
197            }
198        }
199        self.front_stack.pop().map(|t| t.1)
200    }
201    pub fn pop_back(&mut self) -> Option<M::T> {
202        if self.back_stack.is_empty() {
203            let n = self.front_stack.len();
204            let mut front_stack = std::mem::take(&mut self.front_stack);
205            for x in front_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
206                self.push_back(x);
207            }
208            for x in front_stack.drain(..).map(|t| t.1) {
209                self.push_front(x);
210            }
211        }
212        self.back_stack.pop().map(|t| t.1)
213    }
214}
competitive/data_structure/sliding_window_aggregation.rs

competitive/data_structure/
sliding_window_aggregation.rs
