nekolib/ds/
foldable_deque.rs

1//! fold 可能両端キュー。
2
3use super::super::traits::binop;
4use super::super::traits::fold;
5use super::super::traits::push_pop;
6
7use std::ops::RangeFull;
8
9use binop::Monoid;
10use fold::Fold;
11use push_pop::{PopBack, PopFront, PushBack, PushFront};
12
13/// fold 可能両端キュー。
14///
15/// モノイドを要素とする両端キューであって、全体のモノイド積を計算できる。
16/// 逆元がある演算であれば、単に要素を一つ持って計算すればよい。
17///
18/// # Idea
19/// スタックを二つ使って両端キューを実現できることを応用する[^1]。
20/// モノイド積に関する方針は [`FoldableQueue`] と同じ。
21///
22/// [^1]: 内部的には `std::VecDeque` を使ってスタックを実現しているため、
23/// 両端キュー二つで両端キューを実現していることになっている。ギャグ？
24///
25/// [`FoldableQueue`]: struct.FoldableQueue.html
26///
27/// # Complexity
28/// |演算|時間計算量|
29/// |---|---|
30/// |`new`|$\\Theta(1)$|
31/// |`push_back`, `push_front`|$\\Theta(1)$|
32/// |`pop_back`, `pop_front`|amortized $\\Theta(1)$|
33/// |`fold`|$\\Theta(1)$|
34///
35/// キューを実現する場合と異なり、pop したい側の stack が空の際は、
36/// 他方の stack から半分（奇数なら切り上げ）だけ要素をもらってくるようにする。
37/// 各スタックの要素数の差の絶対値をポテンシャルとすることで、ならし定数時間が示せる。
38///
39/// # Examples
40/// ```
41/// use nekolib::ds::FoldableDeque;
42/// use nekolib::traits::{Fold, PopBack, PopFront, PushBack, PushFront};
43/// use nekolib::utils::OpMin;
44///
45/// let mut fq = FoldableDeque::<OpMin<i32>>::new();
46/// assert_eq!(fq.fold(..), std::i32::MAX);
47/// fq.push_back(6);
48/// assert_eq!(fq.fold(..), 6);
49/// fq.push_back(3);
50/// assert_eq!(fq.fold(..), 3);
51/// fq.push_front(4);
52/// assert_eq!(fq.fold(..), 3);
53/// fq.pop_back();
54/// assert_eq!(fq.fold(..), 4);
55/// fq.pop_front();
56/// assert_eq!(fq.fold(..), 6);
57/// fq.pop_back();
58/// assert_eq!(fq.fold(..), std::i32::MAX);
59/// ```
60#[derive(Clone, Debug)]
61pub struct FoldableDeque<M: Monoid> {
62    buf_front: Vec<M::Set>,
63    buf_folded_front: Vec<M::Set>,
64    buf_back: Vec<M::Set>,
65    buf_folded_back: Vec<M::Set>,
66    monoid: M,
67}
68
69impl<M: Monoid> FoldableDeque<M>
70where
71    M::Set: Clone,
72{
73    #[must_use]
74    pub fn new() -> Self
75    where
76        M: Default,
77    {
78        Self::with(M::default())
79    }
80    #[must_use]
81    pub fn with(monoid: M) -> Self {
82        Self {
83            buf_front: vec![],
84            buf_folded_front: vec![monoid.id()],
85            buf_back: vec![],
86            buf_folded_back: vec![monoid.id()],
87            monoid,
88        }
89    }
90    fn rotate_to_front(&mut self) {
91        if !self.buf_front.is_empty() {
92            return;
93        }
94        let n = (self.buf_back.len() + 1) / 2;
95        let tmp_back = self.buf_back.split_off(n);
96        self.buf_front = self.buf_back.split_off(0);
97        self.buf_front.reverse();
98        self.buf_back = tmp_back;
99        self.build_folded();
100    }
101    fn rotate_to_back(&mut self) {
102        if !self.buf_back.is_empty() {
103            return;
104        }
105        let n = (self.buf_front.len() + 1) / 2;
106        let tmp_front = self.buf_front.split_off(n);
107        self.buf_back = self.buf_front.split_off(0);
108        self.buf_back.reverse();
109        self.buf_front = tmp_front;
110        self.build_folded();
111    }
112    fn build_folded(&mut self) {
113        {
114            // front
115            let n = self.buf_front.len();
116            self.buf_folded_front = vec![self.monoid.id(); n + 1];
117            for i in 0..n {
118                self.buf_folded_front[i + 1] = self.monoid.op(
119                    self.buf_front[i].clone(),
120                    self.buf_folded_front[i].clone(),
121                );
122            }
123        }
124        {
125            // back
126            let n = self.buf_back.len();
127            self.buf_folded_back = vec![self.monoid.id(); n + 1];
128            for i in 0..n {
129                self.buf_folded_back[i + 1] = self.monoid.op(
130                    self.buf_folded_back[i].clone(),
131                    self.buf_back[i].clone(),
132                );
133            }
134        }
135    }
136}
137
138impl<M: Monoid> PushBack for FoldableDeque<M>
139where
140    M::Set: Clone,
141{
142    type Input = M::Set;
143    fn push_back(&mut self, x: Self::Input) {
144        self.buf_back.push(x.clone());
145        self.buf_folded_back.push(
146            self.monoid.op(self.buf_folded_back.last().unwrap().clone(), x),
147        );
148    }
149}
150
151impl<M: Monoid> PushFront for FoldableDeque<M>
152where
153    M::Set: Clone,
154{
155    type Input = M::Set;
156    fn push_front(&mut self, x: Self::Input) {
157        self.buf_front.push(x.clone());
158        self.buf_folded_front.push(
159            self.monoid.op(x, self.buf_folded_front.last().unwrap().clone()),
160        );
161    }
162}
163
164impl<M: Monoid> PopBack for FoldableDeque<M>
165where
166    M::Set: Clone,
167{
168    type Output = M::Set;
169    fn pop_back(&mut self) -> Option<Self::Output> {
170        self.rotate_to_back();
171        if self.buf_folded_back.len() > 1 {
172            self.buf_folded_back.pop();
173        }
174        self.buf_back.pop()
175    }
176}
177
178impl<M: Monoid> PopFront for FoldableDeque<M>
179where
180    M::Set: Clone,
181{
182    type Output = M::Set;
183    fn pop_front(&mut self) -> Option<Self::Output> {
184        self.rotate_to_front();
185        if self.buf_folded_front.len() > 1 {
186            self.buf_folded_front.pop();
187        }
188        self.buf_front.pop()
189    }
190}
191
192impl<M: Monoid> Fold<RangeFull> for FoldableDeque<M>
193where
194    M::Set: Clone,
195{
196    type Output = M;
197    fn fold(&self, _: RangeFull) -> M::Set {
198        let front = self.buf_folded_front.last().unwrap().clone();
199        let back = self.buf_folded_back.last().unwrap().clone();
200        self.monoid.op(front, back)
201    }
202}
203
204impl<M: Monoid> Default for FoldableDeque<M>
205where
206    M: Default,
207    M::Set: Clone,
208{
209    fn default() -> Self { Self::new() }
210}
nekolib/ds/foldable_deque.rs

nekolib/ds/
foldable_deque.rs
