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}