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 Stack<T> {
head: Link<T>,
len: usize,
_data: PhantomData<T>,
}
type Link<T> = Option<NonNull<Node<T>>>;
struct Node<T> {
next: Link<T>,
elem: T,
}
impl<T> Stack<T> {
pub fn new() -> Self {
Self {
head: None,
len: 0,
_data: PhantomData,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn push(&mut self, elem: T) {
unsafe {
let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node {
next: None,
elem,
})));
if let Some(old) = self.head {
(*new.as_ptr()).next = Some(old);
}
self.head = Some(new);
self.len += 1;
}
}
pub fn pop(&mut self) -> Option<T> {
unsafe {
self.head.map(|node| {
let boxed_node = Box::from_raw(node.as_ptr());
let result = boxed_node.elem;
self.head = boxed_node.next;
self.len -= 1;
result
})
}
}
pub fn peek(&self) -> Option<&T> {
unsafe { Some(&(*self.head?.as_ptr()).elem) }
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
unsafe { Some(&mut (*self.head?.as_ptr()).elem) }
}
pub fn iter(&'_ self) -> Iter<'_, T> {
Iter {
curr: self.head,
len: self.len,
_boo: PhantomData,
}
}
pub fn iter_mut(&'_ mut self) -> IterMut<'_, T> {
IterMut {
curr: self.head,
len: self.len,
_boo: PhantomData,
}
}
}
extend_singly_linked_list!(Stack<T>; Link<T>);
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_basic() {
let mut list = Stack::new();
assert_eq!(list.len(), 0);
assert_eq!(list.pop(), None);
assert_eq!(list.len(), 0);
list.push(10);
assert_eq!(list.len(), 1);
assert_eq!(list.pop(), Some(10));
assert_eq!(list.len(), 0);
assert_eq!(list.pop(), None);
assert_eq!(list.len(), 0);
list.push(10);
assert_eq!(list.len(), 1);
list.push(20);
assert_eq!(list.len(), 2);
list.push(30);
assert_eq!(list.len(), 3);
assert_eq!(list.pop(), Some(30));
assert_eq!(list.len(), 2);
list.push(40);
assert_eq!(list.len(), 3);
assert_eq!(list.pop(), Some(40));
assert_eq!(list.len(), 2);
assert_eq!(list.pop(), Some(20));
assert_eq!(list.len(), 1);
assert_eq!(list.pop(), Some(10));
assert_eq!(list.len(), 0);
assert_eq!(list.pop(), None);
assert_eq!(list.len(), 0);
assert_eq!(list.pop(), None);
assert_eq!(list.len(), 0);
}
}