logicsim/data_structures/
double_stack.rs

1use std::iter::FromIterator;
2
3/// Data structure consisting of a write stack and a read stack, write operations are performed on the write stack,
4/// read operations are performed on the read stack and calling [DoubleStack::swap] swaps them.
5///
6/// # Example
7/// ```
8/// # use logicsim::data_structures::DoubleStack;
9/// let mut stacks = DoubleStack::new();
10///
11/// stacks.push(1);
12/// stacks.push(2);
13/// stacks.push(3);
14///
15/// assert_eq!(stacks.pop(), None);
16///
17/// stacks.swap();
18///
19/// assert_eq!(stacks.pop().unwrap(), 3);
20/// assert_eq!(stacks.pop().unwrap(), 2);
21/// assert_eq!(stacks.pop().unwrap(), 1);
22///
23/// assert_eq!(stacks.pop(), None);
24/// ```
25#[derive(Debug, Clone, Eq, PartialEq, Hash)]
26pub struct DoubleStack<T> {
27    read_stack: Vec<T>,
28    write_stack: Vec<T>,
29}
30
31impl<T> DoubleStack<T> {
32    /// Returns an empty [DoubleStack].
33    pub fn new() -> Self {
34        Self {
35            read_stack: Default::default(),
36            write_stack: Default::default(),
37        }
38    }
39
40    /// Pops an item from the end of the read stack and returns it.
41    /// If the read stack is empty, returns None.
42    #[inline(always)]
43    pub fn pop(&mut self) -> Option<T> {
44        self.read_stack.pop()
45    }
46
47    /// Pushes an item to the end of the write stack.
48    #[inline(always)]
49    pub fn push(&mut self, v: T) {
50        self.write_stack.push(v);
51    }
52
53    /// Pushes all the items in the iterator to the end of the write stack.
54    #[inline(always)]
55    pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
56        self.write_stack.extend(iter)
57    }
58
59    /// Swaps the write and read stacks, after calling this method you can [pop](DoubleStack::pop)
60    /// items that you had previously [pushed](DoubleStack::push).
61    #[inline(always)]
62    pub fn swap(&mut self) {
63        debug_assert!(
64            self.read_stack.is_empty(),
65            "Tried to swap stacks while the read stack is not empty"
66        );
67        std::mem::swap(&mut self.read_stack, &mut self.write_stack);
68    }
69
70    /// Returns the sum of the items in the read and write stacks.
71    pub fn len(&self) -> usize {
72        self.read_stack.len() + self.write_stack.len()
73    }
74
75    /// Returns true if both the read and write stacks are empty.
76    pub fn is_empty(&self) -> bool {
77        self.len() == 0
78    }
79}
80
81impl<T: Clone> DoubleStack<T> {
82    #[inline(always)]
83    /// Clones all items from the slice to the end of the write stack.
84    pub fn extend_from_slice(&mut self, v: &[T]) {
85        self.write_stack.extend_from_slice(&v)
86    }
87}
88
89impl<T> Default for DoubleStack<T> {
90    fn default() -> Self {
91        Self::new()
92    }
93}
94
95impl<T> FromIterator<T> for DoubleStack<T> {
96    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
97        Self {
98            read_stack: Default::default(),
99            write_stack: iter.into_iter().collect(),
100        }
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn test_push_pop() {
110        let mut s: DoubleStack<u8> = Default::default();
111
112        assert_eq!(s.pop(), None);
113
114        for i in 0..10 {
115            s.push(i);
116            assert_eq!(s.pop(), None);
117        }
118
119        s.swap();
120
121        for i in (0..10).rev() {
122            s.push(i);
123            assert_eq!(s.pop(), Some(i));
124        }
125        assert_eq!(s.pop(), None);
126
127        s.swap();
128
129        for i in 0..10 {
130            assert_eq!(s.pop(), Some(i));
131        }
132        assert_eq!(s.pop(), None);
133    }
134
135    #[test]
136    fn test_extend() {
137        let mut s: DoubleStack<u8> = Default::default();
138
139        s.extend(0..10);
140        assert_eq!(s.pop(), None);
141
142        s.swap();
143        for i in (0..10).rev() {
144            assert_eq!(s.pop(), Some(i))
145        }
146        assert_eq!(s.pop(), None);
147    }
148
149    #[test]
150    fn test_extend_from_slice() {
151        let mut s: DoubleStack<u8> = Default::default();
152
153        s.extend(0..10);
154        assert_eq!(s.pop(), None);
155
156        s.swap();
157        for i in (0..10).rev() {
158            assert_eq!(s.pop(), Some(i))
159        }
160        assert_eq!(s.pop(), None);
161    }
162
163    #[test]
164    fn test_from_iter() {
165        let mut s: DoubleStack<u8> = (0..10).collect();
166
167        assert_eq!(s.pop(), None);
168
169        s.swap();
170        for i in (0..10).rev() {
171            assert_eq!(s.pop(), Some(i))
172        }
173        assert_eq!(s.pop(), None);
174    }
175}
logicsim/data_structures/double_stack.rs

logicsim/data_structures/
double_stack.rs
