competitive/data_structure/
sliding_winsow_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,
27    M::T: Debug,
28{
29    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
30        f.debug_struct("QueueAggregation")
31            .field("front_stack", &self.front_stack)
32            .field("back_stack", &self.back_stack)
33            .finish()
34    }
35}
36
37impl<M> Default for QueueAggregation<M>
38where
39    M: Monoid,
40{
41    fn default() -> Self {
42        Self {
43            front_stack: Vec::new(),
44            back_stack: Vec::new(),
45        }
46    }
47}
48
49impl<M> QueueAggregation<M>
50where
51    M: Monoid,
52{
53    pub fn new() -> Self {
54        Self::default()
55    }
56    pub fn len(&self) -> usize {
57        self.front_stack.len() + self.back_stack.len()
58    }
59    pub fn is_empty(&self) -> bool {
60        self.front_stack.is_empty() && self.back_stack.is_empty()
61    }
62    pub fn fold_all(&self) -> M::T {
63        M::operate(
64            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
65            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
66        )
67    }
68    pub fn last(&self) -> Option<&M::T> {
69        self.back_stack
70            .last()
71            .or_else(|| self.front_stack.first())
72            .map(|t| &t.1)
73    }
74    pub fn push(&mut self, value: M::T) {
75        let x = M::operate(
76            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
77            &value,
78        );
79        self.back_stack.push((x, value));
80    }
81    fn push_front(&mut self, value: M::T) {
82        let x = M::operate(
83            &value,
84            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
85        );
86        self.front_stack.push((x, value));
87    }
88    pub fn pop(&mut self) -> Option<M::T> {
89        if self.front_stack.is_empty() {
90            let mut back_stack = std::mem::take(&mut self.back_stack);
91            for x in back_stack.drain(..).map(|t| t.1).rev() {
92                self.push_front(x);
93            }
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,
122    M::T: Debug,
123{
124    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
125        f.debug_struct("DequeAggregation")
126            .field("front_stack", &self.front_stack)
127            .field("back_stack", &self.back_stack)
128            .finish()
129    }
130}
131
132impl<M> Default for DequeAggregation<M>
133where
134    M: Monoid,
135{
136    fn default() -> Self {
137        Self {
138            front_stack: Vec::new(),
139            back_stack: Vec::new(),
140        }
141    }
142}
143
144impl<M> DequeAggregation<M>
145where
146    M: Monoid,
147{
148    pub fn new() -> Self {
149        Self::default()
150    }
151    pub fn len(&self) -> usize {
152        self.front_stack.len() + self.back_stack.len()
153    }
154    pub fn is_empty(&self) -> bool {
155        self.front_stack.is_empty() && self.back_stack.is_empty()
156    }
157    pub fn fold_all(&self) -> M::T {
158        M::operate(
159            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
160            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
161        )
162    }
163    pub fn front(&self) -> Option<&M::T> {
164        self.front_stack
165            .last()
166            .or_else(|| self.back_stack.first())
167            .map(|t| &t.1)
168    }
169    pub fn back(&self) -> Option<&M::T> {
170        self.back_stack
171            .last()
172            .or_else(|| self.front_stack.first())
173            .map(|t| &t.1)
174    }
175    pub fn push_front(&mut self, value: M::T) {
176        let x = M::operate(
177            &value,
178            self.front_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
179        );
180        self.front_stack.push((x, value));
181    }
182    pub fn push_back(&mut self, value: M::T) {
183        let x = M::operate(
184            self.back_stack.last().map(|t| &t.0).unwrap_or(&M::unit()),
185            &value,
186        );
187        self.back_stack.push((x, value));
188    }
189    pub fn pop_front(&mut self) -> Option<M::T> {
190        if self.front_stack.is_empty() {
191            let n = self.back_stack.len();
192            let mut back_stack = std::mem::take(&mut self.back_stack);
193            for x in back_stack.drain(..(n + 1) / 2).map(|t| t.1).rev() {
194                self.push_front(x);
195            }
196            for x in back_stack.drain(..).map(|t| t.1) {
197                self.push_back(x);
198            }
199        }
200        self.front_stack.pop().map(|t| t.1)
201    }
202    pub fn pop_back(&mut self) -> Option<M::T> {
203        if self.back_stack.is_empty() {
204            let n = self.front_stack.len();
205            let mut front_stack = std::mem::take(&mut self.front_stack);
206            for x in front_stack.drain(..(n + 1) / 2).map(|t| t.1).rev() {
207                self.push_back(x);
208            }
209            for x in front_stack.drain(..).map(|t| t.1) {
210                self.push_front(x);
211            }
212        }
213        self.back_stack.pop().map(|t| t.1)
214    }
215}
competitive/data_structure/sliding_winsow_aggregation.rs

competitive/data_structure/
sliding_winsow_aggregation.rs
