use std::{
cmp::Ordering,
fmt::{self, Debug},
hash::{Hash, Hasher},
marker::PhantomData,
ops::Index,
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> {
#[must_use]
pub fn new() -> Self {
Self {
front: None,
back: None,
len: 0,
_data: PhantomData,
}
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.front.is_none()
}
#[must_use]
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)
}
#[must_use]
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.is_none() {
self.back = None; }
self.len -= 1;
elem
})
}
}
#[must_use]
pub fn pop(&mut self) -> Option<T> {
self.dequeue()
}
#[must_use]
pub fn peek(&self) -> Option<&T> {
unsafe { Some(&(*self.front?.as_ptr()).elem) }
}
#[must_use]
pub fn peek_mut(&mut self) -> Option<&mut T> {
unsafe { Some(&mut (*self.front?.as_ptr()).elem) }
}
#[must_use]
pub fn iter(&'_ self) -> Iter<'_, T> {
Iter {
curr: self.front,
len: self.len,
_boo: PhantomData,
}
}
#[must_use]
pub fn iter_mut(&'_ mut self) -> IterMut<'_, T> {
IterMut {
curr: self.front,
len: self.len,
_boo: PhantomData,
}
}
#[must_use]
pub fn delete_inner(&mut self, elem: &T) -> bool
where
T: Eq,
{
unsafe {
if let Some(f) = self.front {
if &f.as_ref().elem == elem {
self.front = f.as_ref().next;
let _ = Box::from_raw(f.as_ptr());
self.len -= 1;
if self.front.is_none() {
self.back = None; }
return true;
}
}
let mut current = self.front;
while let Some(mut node) = current {
let node = node.as_mut();
if let Some(next) = node.next
&& &next.as_ref().elem == elem
{
let n = Box::from_raw(next.as_ptr());
node.next = n.next;
self.len -= 1;
if self.front.is_none() {
self.back = None; }
return true;
} else {
current = node.next;
}
}
false
}
}
pub fn clear(&mut self) {
while self.front.is_some() {
let _ = self.pop();
}
}
}
impl<T> Index<usize> for Queue<T> {
type Output = T;
fn index(&self, index: usize) -> &Self::Output {
let mut iter = self.iter().skip(index);
iter.next().unwrap()
}
}
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);
}
#[test]
fn test_big() {
let mut queue = Queue::new();
assert_eq!(queue.len(), 0);
assert!(queue.is_empty());
assert_eq!(queue.dequeue(), None);
for i in 0..1_000 {
queue.enqueue(i);
}
assert_eq!(queue.len(), 1_000);
assert!(!queue.is_empty());
assert_eq!(queue.peek(), Some(&0));
for i in (0..1_000).rev() {
assert!(queue.delete_inner(&i));
}
assert_eq!(queue.len(), 0);
assert!(queue.is_empty());
assert_eq!(queue.dequeue(), None);
for i in 0..1_000 {
queue.enqueue(i);
}
assert_eq!(queue.len(), 1_000);
assert!(!queue.is_empty());
assert_eq!(queue.peek(), Some(&0));
for i in 0..1_000 {
assert_eq!(queue.dequeue(), Some(i));
}
assert_eq!(queue.len(), 0);
assert!(queue.is_empty());
}
}