imagecli/
stack.rs

1/// A stack supporting basic manipulations required for
2/// stack-based programming.
3pub struct Stack<T> {
4    // The top of the stack is the last element in the vector.
5    contents: Vec<T>,
6}
7
8impl<T: Clone> Stack<T> {
9    /// Creates a stack with the given initial elements.
10    /// The top of the stack is the first element of the input.
11    pub fn new(contents: Vec<T>) -> Self {
12        let contents = contents.into_iter().rev().collect();
13        Stack { contents }
14    }
15
16    /// Consumes the stack and return its elements.
17    /// The top of the stack is the first element of the output.
18    pub fn contents(self) -> Vec<T> {
19        self.contents.into_iter().rev().collect()
20    }
21
22    /// Duplicates the top element of the stack n times.
23    ///
24    /// dup 1 (a -- a a)
25    /// dup 2 (a -- a a a)
26    pub fn dup(&mut self, n: usize) {
27        self.assert_stack_size("dup", 1);
28        let a = self.contents.pop().unwrap();
29        for _ in 0..n {
30            self.contents.push(a.clone());
31        }
32        self.contents.push(a);
33    }
34
35    /// Rotates the top n elements of the stack.
36    /// rot(1) is a no-op, rot(2) swaps the top two elements.
37    pub fn rot(&mut self, n: usize) {
38        if n < 2 {
39            return;
40        }
41        self.assert_stack_size("rot", n);
42        let a = self.contents.remove(self.contents.len() - 1);
43        self.contents.insert(self.len() - (n - 1), a);
44    }
45
46    /// Pops the top of the stack.
47    pub fn pop(&mut self) -> T {
48        self.assert_stack_size("pop", 1);
49        self.contents.pop().unwrap()
50    }
51
52    /// Pops the to n elements of the stack.
53    pub fn pop_n(&mut self, n: usize) -> Vec<T> {
54        self.assert_stack_size("pop_n", n);
55        // TODO: remove unnecessary work
56        let mut popped = self.contents.split_off(self.len() - n);
57        popped.reverse();
58        popped
59    }
60
61    /// Pushes onto the top of the stack.
62    pub fn push(&mut self, x: T) {
63        self.contents.push(x);
64    }
65
66    /// The number of items in the stack.
67    pub fn len(&self) -> usize {
68        self.contents.len()
69    }
70
71    fn assert_stack_size(&self, op: &str, required: usize) {
72        assert!(
73            self.len() >= required,
74            "operation {} requires {} elements, but the stack only contains {}",
75            op,
76            required,
77            self.len()
78        );
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_new_contents() {
88        let stack = Stack::new(vec![1, 2, 3]);
89        let contents = stack.contents();
90        assert_eq!(contents, vec![1, 2, 3]);
91    }
92
93    #[test]
94    fn test_pop() {
95        let mut stack = Stack::new(vec![1, 2]);
96        assert_eq!(stack.len(), 2);
97        assert_eq!(stack.pop(), 1);
98        assert_eq!(stack.len(), 1);
99        assert_eq!(stack.pop(), 2);
100    }
101
102    #[test]
103    #[should_panic]
104    fn test_pop_empty() {
105        let mut stack = Stack::new(vec![1]);
106        assert_eq!(stack.len(), 1);
107        assert_eq!(stack.pop(), 1);
108        let _ = stack.pop();
109    }
110
111    #[test]
112    fn test_dup() {
113        let mut stack = Stack::new(vec![10, 11]);
114        stack.dup(1);
115        assert_eq!(stack.pop(), 10);
116        assert_eq!(stack.pop(), 10);
117        assert_eq!(stack.pop(), 11);
118        stack.push(12);
119        stack.dup(2);
120        assert_eq!(stack.pop(), 12);
121        assert_eq!(stack.pop(), 12);
122        assert_eq!(stack.pop(), 12);
123        assert_eq!(stack.len(), 0);
124    }
125
126    #[test]
127    fn test_rot() {
128        let mut stack = Stack::new(vec![1, 2, 3]);
129        stack.rot(0);
130        assert_eq!(stack.contents(), vec![1, 2, 3]);
131
132        let mut stack = Stack::new(vec![1, 2, 3]);
133        stack.rot(1);
134        assert_eq!(stack.contents(), vec![1, 2, 3]);
135
136        let mut stack = Stack::new(vec![1, 2, 3]);
137        stack.rot(2);
138        assert_eq!(stack.contents(), vec![2, 1, 3]);
139
140        let mut stack = Stack::new(vec![1, 2, 3]);
141        stack.rot(3);
142        assert_eq!(stack.contents(), vec![2, 3, 1]);
143    }
144
145    #[test]
146    #[should_panic]
147    fn test_rot_exceeding_len() {
148        let mut stack = Stack::new(vec![1, 2, 3]);
149        stack.rot(4);
150    }
151
152    #[test]
153    fn test_pop_n() {
154        let mut stack = Stack::new(vec![1, 2, 3]);
155        let top = stack.pop_n(2);
156        assert_eq!(top, vec![1, 2]);
157        assert_eq!(stack.contents(), vec![3]);
158    }
159}
imagecli/stack.rs

imagecli/
stack.rs
