nekolib/ds/
foldable_queue.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::{Pop, PopFront, Push, PushBack};
12
13/// fold 可能キュー。
14///
15/// いわゆる SWAG (*S*liding *W*indow *Ag*gregation)。
16/// モノイドを要素とするキューであって、全体のモノイド積を計算できる。
17/// 逆元がある演算であれば、単に要素を一つ持って計算すればよい。
18///
19/// # Idea
20/// スタックを二つ使ってキューを実現できることを応用する。
21/// モノイド積を管理するスタックも二つ用意する。
22/// 後者のスタックそれぞれの top が、対応する前者のスタック中の要素の総積となるように管理する。
23/// これにより、キュー全体としての積は、二つの要素の積として計算できる。
24///
25/// # Implementation notes
26/// `fold()` だけを考えると front stack には元の値を入れる必要はないが、
27/// `pop()` の際の挙動を標準の [`VecDeque`] などと合わせたかったので、含めることにした。
28/// fold した値を返すということにすれば含めなくて済むが、あまりそうしたくなかったので。
29///
30/// [`VecDeque`]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html#method.pop_front
31///
32/// # Complexity
33/// |演算|時間計算量|
34/// |---|---|
35/// |`new`|$\\Theta(1)$|
36/// |`push` (`push_back`)|$\\Theta(1)$|
37/// |`pop` (`pop_front`)|amortized $\\Theta(1)$|
38/// |`fold`|$\\Theta(1)$|
39///
40/// `pop` の計算量は、two-stack queue のならし解析から従う。
41/// わかりやすい資料として
42/// [CS166](http://web.stanford.edu/class/archive/cs/cs166/cs166.1206/lectures/07/Small07.pdf)
43/// を挙げておく。
44///
45/// # Examples
46/// ```
47/// use nekolib::ds::FoldableQueue;
48/// use nekolib::traits::{Fold, Pop, Push};
49/// use nekolib::utils::OpMin;
50///
51/// let mut fq = FoldableQueue::<OpMin<i32>>::new();
52/// assert_eq!(fq.fold(..), std::i32::MAX);
53/// fq.push(6);
54/// assert_eq!(fq.fold(..), 6);
55/// fq.push(3);
56/// assert_eq!(fq.fold(..), 3);
57/// fq.push(4);
58/// assert_eq!(fq.fold(..), 3);
59/// fq.pop();
60/// assert_eq!(fq.fold(..), 3);
61/// fq.pop();
62/// assert_eq!(fq.fold(..), 4);
63/// ```
64#[derive(Clone, Debug)]
65pub struct FoldableQueue<M: Monoid> {
66    buf_front: Vec<M::Set>,
67    buf_folded_front: Vec<M::Set>,
68    buf_back: Vec<M::Set>,
69    folded_back: M::Set,
70    monoid: M,
71}
72
73impl<M: Monoid> FoldableQueue<M>
74where
75    M::Set: Clone,
76{
77    #[must_use]
78    pub fn new() -> Self
79    where
80        M: Default,
81    {
82        Self::with(M::default())
83    }
84    #[must_use]
85    pub fn with(monoid: M) -> Self {
86        Self {
87            buf_front: vec![],
88            buf_folded_front: vec![monoid.id()],
89            buf_back: vec![],
90            folded_back: monoid.id(),
91            monoid,
92        }
93    }
94    fn rotate(&mut self) {
95        if self.buf_front.is_empty() {
96            std::mem::swap(&mut self.buf_back, &mut self.buf_front);
97            self.buf_front.reverse();
98            self.build_folded();
99        }
100    }
101    fn build_folded(&mut self) {
102        self.folded_back = (self.buf_back.iter())
103            .fold(self.monoid.id(), |acc, x| self.monoid.op(acc, x.clone()));
104        let n = self.buf_front.len();
105        self.buf_folded_front = vec![self.monoid.id(); n + 1];
106        for i in 0..n {
107            self.buf_folded_front[i + 1] = self.monoid.op(
108                self.buf_folded_front[i].clone(),
109                self.buf_front[i].clone(),
110            );
111        }
112    }
113}
114
115impl<M: Monoid> PushBack for FoldableQueue<M>
116where
117    M::Set: Clone,
118{
119    type Input = M::Set;
120    fn push_back(&mut self, x: Self::Input) {
121        self.folded_back = self.monoid.op(
122            std::mem::replace(&mut self.folded_back, self.monoid.id()),
123            x.clone(),
124        );
125        self.buf_back.push(x);
126    }
127}
128
129impl<M: Monoid> Push for FoldableQueue<M>
130where
131    M::Set: Clone,
132{
133    type Input = M::Set;
134    fn push(&mut self, x: Self::Input) { self.push_back(x); }
135}
136
137impl<M: Monoid> PopFront for FoldableQueue<M>
138where
139    M::Set: Clone,
140{
141    type Output = M::Set;
142    fn pop_front(&mut self) -> Option<Self::Output> {
143        self.rotate();
144        if self.buf_folded_front.len() > 1 {
145            self.buf_folded_front.pop();
146        }
147        self.buf_front.pop()
148    }
149}
150
151impl<M: Monoid> Pop for FoldableQueue<M>
152where
153    M::Set: Clone,
154{
155    type Output = M::Set;
156    fn pop(&mut self) -> Option<Self::Output> { self.pop_front() }
157}
158
159impl<M: Monoid> Fold<RangeFull> for FoldableQueue<M>
160where
161    M::Set: Clone,
162{
163    type Output = M;
164    fn fold(&self, _: RangeFull) -> M::Set {
165        let front = self.buf_folded_front.last().unwrap().clone();
166        self.monoid.op(front, self.folded_back.clone())
167    }
168}
169
170impl<M: Monoid> Default for FoldableQueue<M>
171where
172    M: Default,
173    M::Set: Clone,
174{
175    fn default() -> Self { Self::new() }
176}
nekolib/ds/foldable_queue.rs

nekolib/ds/
foldable_queue.rs
