stacktools/
lib.rs

1use std::cmp::Ord;
2use std::collections::{BinaryHeap, VecDeque};
3use std::collections::binary_heap;
4use std::collections::vec_deque;
5
6pub struct Queue<T> {
7    inner: VecDeque<T>,
8}
9
10pub struct Stack<T> {
11    inner: VecDeque<T>,
12}
13
14pub struct PriorityQueue<T: Ord> {
15    inner: BinaryHeap<T>,
16}
17
18impl<T> Queue<T> {
19    pub fn new() -> Self {
20        Self {
21            inner: VecDeque::new(),
22        }
23    }
24
25    fn len(&self) -> usize {
26        self.inner.len()
27    }
28
29    fn push(&mut self, v: T) {
30        self.inner.push_back(v);
31    }
32
33    fn iter(&self) -> vec_deque::Iter<T> {
34        self.inner.iter()
35    }
36}
37
38impl<T> Stack<T> {
39    pub fn new() -> Self {
40        Self {
41            inner: VecDeque::new(),
42        }
43    }
44
45    fn len(&self) -> usize {
46        self.inner.len()
47    }
48
49    fn push(&mut self, v: T) {
50        self.inner.push_front(v);
51    }
52
53    fn iter(&self) -> vec_deque::Iter<T> {
54        self.inner.iter()
55    }
56}
57
58impl<T> Iterator for Queue<T> {
59    type Item = T;
60    fn next(&mut self) -> Option<Self::Item> {
61        self.inner.pop_front()
62    }
63}
64impl<T> Iterator for Stack<T> {
65    type Item = T;
66    fn next(&mut self) -> Option<Self::Item> {
67        self.inner.pop_front()
68    }
69}
70impl<T: Ord> Iterator for PriorityQueue<T> {
71    type Item = T;
72    fn next(&mut self) -> Option<Self::Item> {
73        self.inner.pop()
74    }
75}
76impl<T> PriorityQueue<T>
77where
78    T: Ord,
79{
80    pub fn new() -> Self {
81        Self {
82            inner: BinaryHeap::new(),
83        }
84    }
85
86    fn len(&self) -> usize {
87        self.inner.len()
88    }
89
90    fn push(&mut self, v: T) {
91        self.inner.push(v);
92    }
93
94    fn iter(&self) -> binary_heap::Iter<T> {
95        self.inner.iter()
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102    use std::cmp::Ord;
103    use std::cmp::Ordering;
104
105    #[test]
106    fn fifo_instantiate() {
107        let mut fifo: Queue<i32> = Queue::new();
108
109        assert!(fifo.len() == 0);
110        fifo.push(1);
111        fifo.push(2);
112        fifo.push(3);
113        assert!(fifo.len() == 3);
114
115        {
116            let mut iter = fifo.iter();
117
118            assert_eq!(Some(&1), iter.next());
119            assert_eq!(Some(&2), iter.next());
120            assert_eq!(Some(&3), iter.next());
121        }
122
123        assert_eq!(Some(1), fifo.next());
124        assert!(fifo.len() == 2);
125
126        assert_eq!(Some(2), fifo.next());
127        assert!(fifo.len() == 1);
128
129        assert_eq!(Some(3), fifo.next());
130        assert!(fifo.len() == 0);
131
132        assert_eq!(None, fifo.next());
133    }
134
135    #[test]
136    fn lifo_instantiate() {
137        let mut lifo: Stack<i32> = Stack::new();
138
139        assert!(lifo.len() == 0);
140        lifo.push(1);
141        lifo.push(2);
142        lifo.push(3);
143        assert!(lifo.len() == 3);
144
145        {
146            let mut iter = lifo.iter();
147
148            assert_eq!(Some(&3), iter.next());
149            assert_eq!(Some(&2), iter.next());
150            assert_eq!(Some(&1), iter.next());
151        }
152
153        assert_eq!(Some(3), lifo.next());
154        assert!(lifo.len() == 2);
155
156        assert_eq!(Some(2), lifo.next());
157        assert!(lifo.len() == 1);
158
159        assert_eq!(Some(1), lifo.next());
160        assert!(lifo.len() == 0);
161
162        assert_eq!(None, lifo.next());
163    }
164
165    #[derive(Copy, Eq, Debug, PartialOrd, PartialEq)]
166    enum Priority {
167        Trivial = 1,
168        Normal,
169        Critical,
170    }
171
172    impl Clone for Priority {
173        #[inline]
174        fn clone(&self) -> Priority {
175            *self
176        }
177    }
178
179    impl Ord for Priority {
180        #[inline]
181        fn cmp(&self, other: &Priority) -> Ordering {
182            (*self as usize).cmp(&(*other as usize))
183        }
184    }
185
186    #[derive(Eq, PartialEq, Debug)]
187    struct PriorityMessage {
188        priority: Priority,
189        value: i32,
190    }
191
192    impl Ord for PriorityMessage {
193        fn cmp(&self, other: &PriorityMessage) -> Ordering {
194            self.priority.cmp(&other.priority)
195        }
196    }
197
198    impl PartialOrd for PriorityMessage {
199        fn partial_cmp(&self, other: &PriorityMessage) -> Option<Ordering> {
200            Some(self.cmp(other))
201        }
202    }
203
204    #[test]
205    fn priority_instantiate() {
206        let mut prio: PriorityQueue<PriorityMessage> = PriorityQueue::new();
207
208        assert!(prio.len() == 0);
209        prio.push(PriorityMessage {
210            priority: Priority::Trivial,
211            value: 1,
212        });
213        prio.push(PriorityMessage {
214            priority: Priority::Normal,
215            value: 2,
216        });
217        prio.push(PriorityMessage {
218            priority: Priority::Critical,
219            value: 3,
220        });
221        prio.push(PriorityMessage {
222            priority: Priority::Critical,
223            value: 4,
224        });
225
226        assert!(prio.len() == 4);
227
228        {
229            let mut iter = prio.iter();
230
231            assert_eq!(
232                Some(&PriorityMessage {
233                    priority: Priority::Critical,
234                    value: 3,
235                }),
236                iter.next()
237            );
238            assert_eq!(
239                Some(&PriorityMessage {
240                    priority: Priority::Critical,
241                    value: 4,
242                }),
243                iter.next()
244            );
245            assert_eq!(
246                Some(&PriorityMessage {
247                    priority: Priority::Normal,
248                    value: 2,
249                }),
250                iter.next()
251            );
252            assert_eq!(
253                Some(&PriorityMessage {
254                    priority: Priority::Trivial,
255                    value: 1,
256                }),
257                iter.next()
258            );
259        }
260
261        assert_eq!(
262            Some(PriorityMessage {
263                priority: Priority::Critical,
264                value: 3,
265            }),
266            prio.next()
267        );
268        assert!(prio.len() == 3);
269
270        assert_eq!(
271            Some(PriorityMessage {
272                priority: Priority::Critical,
273                value: 4,
274            }),
275            prio.next()
276        );
277        assert!(prio.len() == 2);
278
279        assert_eq!(
280            Some(PriorityMessage {
281                priority: Priority::Normal,
282                value: 2,
283            }),
284            prio.next()
285        );
286        assert!(prio.len() == 1);
287
288        assert_eq!(
289            Some(PriorityMessage {
290                priority: Priority::Trivial,
291                value: 1,
292            }),
293            prio.next()
294        );
295        assert!(prio.len() == 0);
296
297        assert_eq!(None, prio.next());
298    }
299}