use std::collections::{BinaryHeap, VecDeque};
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub struct PushError;
impl std::fmt::Display for PushError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "queue reached its capacity")
}
}
impl std::error::Error for PushError {}
pub trait Queue {
type Item;
fn push(&mut self, value: Self::Item) -> Result<(), PushError>;
fn pop(&mut self) -> Option<Self::Item>;
fn len(&self) -> usize;
fn is_empty(&self) -> bool {
self.len() == 0
}
}
pub struct Fifo<T> {
inner: VecDeque<T>,
capacity: usize,
}
impl<T> Default for Fifo<T> {
fn default() -> Self {
Self {
inner: VecDeque::default(),
capacity: usize::MAX,
}
}
}
impl<T> Fifo<T> {
#[must_use]
pub fn bounded(capacity: usize) -> Self {
Self {
inner: VecDeque::with_capacity(capacity),
capacity,
}
}
}
impl<T> Queue for Fifo<T> {
type Item = T;
fn push(&mut self, value: T) -> Result<(), PushError> {
if self.inner.len() < self.capacity {
self.inner.push_back(value);
Ok(())
} else {
Err(PushError)
}
}
fn pop(&mut self) -> Option<T> {
self.inner.pop_front()
}
fn len(&self) -> usize {
self.inner.len()
}
}
pub struct PriorityQueue<T> {
inner: BinaryHeap<T>,
capacity: usize,
}
impl<T: Ord> Default for PriorityQueue<T> {
fn default() -> Self {
Self {
inner: BinaryHeap::default(),
capacity: usize::MAX,
}
}
}
impl<T: Ord> PriorityQueue<T> {
#[must_use]
pub fn bounded(capacity: usize) -> Self {
Self {
inner: BinaryHeap::with_capacity(capacity),
capacity,
}
}
}
impl<T: Ord> Queue for PriorityQueue<T> {
type Item = T;
fn push(&mut self, value: T) -> Result<(), PushError> {
if self.inner.len() < self.capacity {
self.inner.push(value);
Ok(())
} else {
Err(PushError)
}
}
fn pop(&mut self) -> Option<T> {
self.inner.pop()
}
fn len(&self) -> usize {
self.inner.len()
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_unbounded_queue() {
let mut queue = Fifo::<i32>::default();
assert_eq!(queue.len(), 0);
assert!(queue.is_empty());
assert!(queue.push(0).is_ok());
assert_eq!(queue.len(), 1);
assert!(!queue.is_empty());
assert!(queue.push(1).is_ok());
assert_eq!(queue.len(), 2);
assert_eq!(queue.pop(), Some(0));
assert_eq!(queue.len(), 1);
assert_eq!(queue.pop(), Some(1));
assert_eq!(queue.len(), 0);
assert_eq!(queue.pop(), None);
}
#[test]
fn test_bounded_queue() {
let mut queue = Fifo::<i32>::bounded(2);
assert_eq!(queue.len(), 0);
assert!(queue.is_empty());
assert!(queue.push(0).is_ok());
assert_eq!(queue.len(), 1);
assert!(!queue.is_empty());
assert!(queue.push(1).is_ok());
assert_eq!(queue.len(), 2);
let err = queue.push(2).err();
assert!(err.is_some());
let err = err.unwrap();
assert_eq!(&format!("{}", err), "queue reached its capacity");
assert_eq!(queue.pop(), Some(0));
assert_eq!(queue.len(), 1);
assert!(queue.push(2).is_ok());
assert_eq!(queue.len(), 2);
assert_eq!(queue.pop(), Some(1));
assert_eq!(queue.len(), 1);
assert_eq!(queue.pop(), Some(2));
assert_eq!(queue.len(), 0);
assert_eq!(queue.pop(), None);
}
#[test]
fn test_priority_queue() -> Result<(), PushError> {
let queue = PriorityQueue::<i32>::default();
assert_eq!(queue.capacity, usize::MAX);
let mut queue = PriorityQueue::<i32>::bounded(2);
assert_eq!(queue.capacity, 2);
assert_eq!(queue.len(), 0);
queue.push(1)?;
assert_eq!(queue.len(), 1);
queue.push(2)?;
assert_eq!(queue.len(), 2);
assert_eq!(queue.push(2).err(), Some(PushError));
assert_eq!(queue.len(), 2);
assert_eq!(queue.pop(), Some(2));
assert_eq!(queue.len(), 1);
assert_eq!(queue.pop(), Some(1));
assert_eq!(queue.len(), 0);
Ok(())
}
}