1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
#[derive(Copy, Clone, Debug)]
pub struct ModifyRecord {
pub point: (u32, u32),
pub old_val: bool,
pub val: bool,
}
impl ModifyRecord {
pub fn new(point: (u32, u32), old_val: bool, val: bool) -> Self {
ModifyRecord {
point,
old_val,
val,
}
}
}
pub enum OpKind {
Undo,
Redo,
}
pub type Operation = Vec<ModifyRecord>;
#[derive(Debug)]
pub struct UndoStack<T> {
operations: Vec<T>,
position: Option<u32>,
}
impl<T> UndoStack<T>
where
T: Clone,
{
pub fn new() -> Self {
Self {
operations: Vec::with_capacity(64),
position: None,
}
}
pub fn push(&mut self, op: T) {
if let Some(p) = self.position {
// remove all operations past the newly pushed operation
for _ in 1 + (p as usize)..self.operations.len() {
self.operations.pop();
}
// advance position
self.position = Some(p + 1);
// add new operation
self.operations.push(op);
} else {
// empty ops list or undone till start of stack
// remove all operations past the newly pushed operation
self.operations.clear();
// advance position
self.position = Some(0);
// add new operation
self.operations.push(op);
}
}
pub fn undo(&mut self) -> Option<T> {
if let Some(p) = self.position {
self.position = p.checked_sub(1);
// we want to return a clone and not a reference because push deletes the item
return Some(self.operations[p as usize].clone());
}
return None;
}
pub fn redo(&mut self) -> Option<T> {
if let Some(p) = self.position {
if p < self.operations.len() as u32 - 1 {
self.position = Some(p + 1);
return Some(self.operations[1 + p as usize].clone());
}
} else if !self.operations.is_empty() {
self.position = Some(0);
return Some(self.operations[0].clone());
}
return None;
}
}
#[cfg(test)]
mod tests {
use super::*;
fn setup() -> UndoStack<u32> {
let mut stack = UndoStack::new();
stack.push(10);
stack.push(5);
stack.push(2);
stack
}
#[test]
fn undo_works() {
let mut stack = setup();
assert_eq!(stack.undo(), Some(2));
assert_eq!(stack.undo(), Some(5));
assert_eq!(stack.undo(), Some(10));
}
#[test]
fn redo_works() {
let mut stack = setup();
stack.undo();
stack.undo();
stack.undo();
assert_eq!(stack.redo(), Some(10));
assert_eq!(stack.redo(), Some(5));
assert_eq!(stack.redo(), Some(2));
}
#[test]
fn undo_push_redo() {
let mut stack = setup();
stack.undo();
stack.push(16);
assert_eq!(stack.redo(), None);
assert_eq!(stack.undo(), Some(16));
}
#[test]
fn stack_identity() {
let mut stack = setup();
stack.undo();
stack.redo();
stack.undo();
assert_eq!(stack.operations, setup().operations);
}
}
|
