simrs/
queue.rs

1use std::collections::{BinaryHeap, VecDeque};
2
3/// Error return when an attempt to push an element to a queue fails due to the queue having
4/// reached its capacity.
5#[derive(Debug, PartialEq, Eq, Clone, Copy)]
6pub struct PushError;
7
8impl std::fmt::Display for PushError {
9    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
10        write!(f, "queue reached its capacity")
11    }
12}
13
14impl std::error::Error for PushError {}
15
16/// Trait implemented by the queues used in the simulation.
17pub trait Queue {
18    /// Type of elements held by the queue.
19    type Item;
20
21    /// Add an element to the queue.
22    ///
23    /// # Errors
24    ///
25    /// Returns an error if the queue is bounded in size and full.
26    fn push(&mut self, value: Self::Item) -> Result<(), PushError>;
27
28    /// Removes the next element and returns it, or `None` if the `Queue` is empty.
29    fn pop(&mut self) -> Option<Self::Item>;
30
31    /// Returns the number of elements in the queue.
32    fn len(&self) -> usize;
33
34    /// Returns `true` if there are no elements in the queue.
35    fn is_empty(&self) -> bool {
36        self.len() == 0
37    }
38}
39
40/// Abstraction over [`VecDeque`] that allows to limit the capacity of the queue.
41/// This means that push operations can fail.
42/// By default, the capacity is equal to [`usize::MAX`], which makes unlimited in practice.
43///
44/// [`VecDeque`]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
45/// [`usize::MAX`]: https://doc.rust-lang.org/std/primitive.usize.html#associatedconstant.MAX
46pub struct Fifo<T> {
47    inner: VecDeque<T>,
48    capacity: usize,
49}
50
51impl<T> Default for Fifo<T> {
52    fn default() -> Self {
53        Self {
54            inner: VecDeque::default(),
55            capacity: usize::MAX,
56        }
57    }
58}
59
60impl<T> Fifo<T> {
61    /// Creates a new queue with limited capacity.
62    #[must_use]
63    pub fn bounded(capacity: usize) -> Self {
64        Self {
65            inner: VecDeque::with_capacity(capacity),
66            capacity,
67        }
68    }
69}
70
71impl<T> Queue for Fifo<T> {
72    type Item = T;
73
74    fn push(&mut self, value: T) -> Result<(), PushError> {
75        if self.inner.len() < self.capacity {
76            self.inner.push_back(value);
77            Ok(())
78        } else {
79            Err(PushError)
80        }
81    }
82
83    fn pop(&mut self) -> Option<T> {
84        self.inner.pop_front()
85    }
86
87    fn len(&self) -> usize {
88        self.inner.len()
89    }
90}
91
92/// Binary heap implementation of [`Queue`].
93pub struct PriorityQueue<T> {
94    inner: BinaryHeap<T>,
95    capacity: usize,
96}
97
98impl<T: Ord> Default for PriorityQueue<T> {
99    fn default() -> Self {
100        Self {
101            inner: BinaryHeap::default(),
102            capacity: usize::MAX,
103        }
104    }
105}
106
107impl<T: Ord> PriorityQueue<T> {
108    /// Creates a new queue with limited capacity.
109    #[must_use]
110    pub fn bounded(capacity: usize) -> Self {
111        Self {
112            inner: BinaryHeap::with_capacity(capacity),
113            capacity,
114        }
115    }
116}
117
118impl<T: Ord> Queue for PriorityQueue<T> {
119    type Item = T;
120
121    fn push(&mut self, value: T) -> Result<(), PushError> {
122        if self.inner.len() < self.capacity {
123            self.inner.push(value);
124            Ok(())
125        } else {
126            Err(PushError)
127        }
128    }
129
130    fn pop(&mut self) -> Option<T> {
131        self.inner.pop()
132    }
133
134    fn len(&self) -> usize {
135        self.inner.len()
136    }
137}
138
139#[cfg(test)]
140mod test {
141    use super::*;
142
143    #[test]
144    fn test_unbounded_queue() {
145        let mut queue = Fifo::<i32>::default();
146        assert_eq!(queue.len(), 0);
147        assert!(queue.is_empty());
148        assert!(queue.push(0).is_ok());
149        assert_eq!(queue.len(), 1);
150        assert!(!queue.is_empty());
151        assert!(queue.push(1).is_ok());
152        assert_eq!(queue.len(), 2);
153        assert_eq!(queue.pop(), Some(0));
154        assert_eq!(queue.len(), 1);
155        assert_eq!(queue.pop(), Some(1));
156        assert_eq!(queue.len(), 0);
157        assert_eq!(queue.pop(), None);
158    }
159
160    #[test]
161    fn test_bounded_queue() {
162        let mut queue = Fifo::<i32>::bounded(2);
163        assert_eq!(queue.len(), 0);
164        assert!(queue.is_empty());
165        assert!(queue.push(0).is_ok());
166        assert_eq!(queue.len(), 1);
167        assert!(!queue.is_empty());
168        assert!(queue.push(1).is_ok());
169        assert_eq!(queue.len(), 2);
170        let err = queue.push(2).err();
171        assert!(err.is_some());
172        let err = err.unwrap();
173        assert_eq!(&format!("{}", err), "queue reached its capacity");
174        assert_eq!(queue.pop(), Some(0));
175        assert_eq!(queue.len(), 1);
176        assert!(queue.push(2).is_ok());
177        assert_eq!(queue.len(), 2);
178        assert_eq!(queue.pop(), Some(1));
179        assert_eq!(queue.len(), 1);
180        assert_eq!(queue.pop(), Some(2));
181        assert_eq!(queue.len(), 0);
182        assert_eq!(queue.pop(), None);
183    }
184
185    #[test]
186    fn test_priority_queue() -> Result<(), PushError> {
187        let queue = PriorityQueue::<i32>::default();
188        assert_eq!(queue.capacity, usize::MAX);
189        let mut queue = PriorityQueue::<i32>::bounded(2);
190        assert_eq!(queue.capacity, 2);
191
192        assert_eq!(queue.len(), 0);
193        queue.push(1)?;
194        assert_eq!(queue.len(), 1);
195        queue.push(2)?;
196        assert_eq!(queue.len(), 2);
197
198        assert_eq!(queue.push(2).err(), Some(PushError));
199
200        assert_eq!(queue.len(), 2);
201        assert_eq!(queue.pop(), Some(2));
202        assert_eq!(queue.len(), 1);
203        assert_eq!(queue.pop(), Some(1));
204        assert_eq!(queue.len(), 0);
205
206        Ok(())
207    }
208}
simrs/queue.rs

simrs/
queue.rs
