use std::{
cmp::Ordering,
fmt,
fmt::Debug,
hash::{Hash, Hasher},
marker::PhantomData,
ptr::NonNull,
};
use crate::collections::extend_singly_linked_list;
#[derive(Default)]
pub struct Queue<T> {
front: Link<T>,
back: Link<T>,
len: usize,
_data: PhantomData<T>,
}
type Link<T> = Option<NonNull<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Queue<T> {
pub fn new() -> Self {
Self {
front: None,
back: None,
len: 0,
_data: PhantomData,
}
}
pub fn is_empty(&self) -> bool {
self.front == None
}
pub fn len(&self) -> usize {
self.len
}
pub fn enqueue(&mut self, elem: T) {
unsafe {
let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { next: None, elem })));
if let Some(old) = self.back {
(*old.as_ptr()).next = Some(new);
} else {
self.front = Some(new);
}
self.back = Some(new);
self.len += 1;
}
}
pub fn push(&mut self, elem: T) {
self.enqueue(elem)
}
pub fn dequeue(&mut self) -> Option<T> {
unsafe {
self.front.map(|node| {
let boxed_node = Box::from_raw(node.as_ptr());
let elem = boxed_node.elem;
self.front = boxed_node.next;
if self.front == None {
self.back = None; }
self.len -= 1;
elem
})
}
}
pub fn pop(&mut self) -> Option<T> {
self.dequeue()
}
pub fn peek(&self) -> Option<&T> {
unsafe { Some(&(*self.front?.as_ptr()).elem) }
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
unsafe { Some(&mut (*self.front?.as_ptr()).elem) }
}
pub fn iter(&'_ self) -> Iter<'_, T> {
Iter {
curr: self.front,
len: self.len,
_boo: PhantomData,
}
}
pub fn iter_mut(&'_ mut self) -> IterMut<'_, T> {
IterMut {
curr: self.front,
len: self.len,
_boo: PhantomData,
}
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter { item: self }
}
}
extend_singly_linked_list!(Queue<T>; Link<T>);
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_queue() {
let mut queue = Queue::new();
assert_eq!(queue.len(), 0);
assert_eq!(queue.peek(), None);
assert_eq!(queue.pop(), None);
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(3);
assert_eq!(queue.len(), 4);
assert_eq!(queue.peek(), Some(&1));
assert_eq!(queue.pop(), Some(1));
assert_eq!(queue.len(), 3);
assert_eq!(queue.peek(), Some(&2));
assert_eq!(queue.pop(), Some(2));
assert_eq!(queue.len(), 2);
assert_eq!(queue.peek(), Some(&3));
assert_eq!(queue.pop(), Some(3));
assert_eq!(queue.len(), 1);
assert_eq!(queue.peek(), Some(&3));
assert_eq!(queue.pop(), Some(3));
assert_eq!(queue.len(), 0);
assert_eq!(queue.peek(), None);
assert_eq!(queue.pop(), None);
assert_eq!(queue.len(), 0);
assert_eq!(queue.peek(), None);
assert_eq!(queue.pop(), None);
assert_eq!(queue.len(), 0);
assert_eq!(queue.peek(), None);
assert_eq!(queue.pop(), None);
}
}