haar_lib/ds/
rollbackable_vector.rs

1//! ロールバック可能Vec
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc165/tasks/abc165_f>
5
6use std::{
7    fmt,
8    fmt::{Debug, Formatter},
9    ops::Index,
10};
11
12#[derive(Clone)]
13enum History<T> {
14    Update(T, usize),
15    Push,
16    Pop(T),
17}
18
19/// ロールバック可能Vec
20#[derive(Clone, Default)]
21pub struct RollbackableVec<T> {
22    data: Vec<T>,
23    history: Vec<History<T>>,
24}
25
26impl<T> RollbackableVec<T>
27where
28    T: Clone,
29{
30    /// `RollbackableVec`を生成
31    pub fn new() -> Self {
32        Self {
33            data: vec![],
34            history: vec![],
35        }
36    }
37
38    /// 末尾に`value`を追加
39    pub fn push(&mut self, value: T) {
40        self.history.push(History::Push);
41        self.data.push(value);
42    }
43
44    /// 末尾の要素を削除して返す
45    pub fn pop(&mut self) -> Option<T> {
46        let x = self.data.pop()?;
47        self.history.push(History::Pop(x.clone()));
48        Some(x)
49    }
50
51    /// `index`番目の要素を`value`に変更する
52    pub fn assign(&mut self, index: usize, value: T) {
53        self.history
54            .push(History::Update(self.data[index].clone(), index));
55        self.data[index] = value;
56    }
57
58    /// 直前の`push` / `pop` / `assign`操作を取り消す
59    pub fn rollback(&mut self) -> bool {
60        match self.history.pop() {
61            None => false,
62            Some(x) => {
63                match x {
64                    History::Update(value, index) => {
65                        self.data[index] = value;
66                    }
67                    History::Push => {
68                        self.data.pop();
69                    }
70                    History::Pop(value) => {
71                        self.data.push(value);
72                    }
73                }
74                true
75            }
76        }
77    }
78
79    /// 現在の要素数を返す
80    pub fn len(&self) -> usize {
81        self.data.len()
82    }
83
84    /// 要素が存在しないかを判定する
85    pub fn is_empty(&self) -> bool {
86        self.data.is_empty()
87    }
88
89    /// スライスを返す
90    pub fn as_slice(&self) -> &[T] {
91        &self.data
92    }
93
94    /// 先頭の要素を返す
95    pub fn first(&self) -> Option<&T> {
96        self.data.first()
97    }
98
99    /// 末尾の要素を返す
100    pub fn last(&self) -> Option<&T> {
101        self.data.last()
102    }
103}
104
105impl<T> Index<usize> for RollbackableVec<T> {
106    type Output = T;
107
108    fn index(&self, i: usize) -> &Self::Output {
109        &self.data[i]
110    }
111}
112
113impl<T: Debug> Debug for RollbackableVec<T> {
114    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
115        write!(f, "{:?}", self.data)
116    }
117}
118
119impl<T: Clone> From<&RollbackableVec<T>> for Vec<T> {
120    fn from(from: &RollbackableVec<T>) -> Self {
121        from.data.clone()
122    }
123}
124
125impl<T> From<Vec<T>> for RollbackableVec<T> {
126    fn from(from: Vec<T>) -> Self {
127        Self {
128            data: from,
129            history: vec![],
130        }
131    }
132}
133
134#[cfg(test)]
135mod test {
136    use super::*;
137
138    #[test]
139    fn test() {
140        let mut a = RollbackableVec::from(vec![1, 2, 3, 4]);
141
142        assert_eq!(a.as_slice(), &[1, 2, 3, 4]);
143
144        a.push(5);
145        assert_eq!(a.as_slice(), &[1, 2, 3, 4, 5]);
146
147        a.rollback();
148        assert_eq!(a.as_slice(), &[1, 2, 3, 4]);
149
150        a.pop();
151        assert_eq!(a.as_slice(), &[1, 2, 3]);
152
153        a.rollback();
154        assert_eq!(a.as_slice(), &[1, 2, 3, 4]);
155
156        a.assign(2, 9);
157        assert_eq!(a.as_slice(), &[1, 2, 9, 4]);
158
159        a.rollback();
160        assert_eq!(a.as_slice(), &[1, 2, 3, 4]);
161    }
162}
haar_lib/ds/rollbackable_vector.rs

haar_lib/ds/
rollbackable_vector.rs
