You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
116 lines
1.9 KiB
116 lines
1.9 KiB
use std::{
|
|
mem,
|
|
};
|
|
struct Cons<T>
|
|
{
|
|
item: T,
|
|
next: Option<Box<Cons<T>>>,
|
|
}
|
|
|
|
/// A safe linked list, with remove() for non-nightly build.
|
|
pub struct LinkedList<T>
|
|
{
|
|
head: Option<Cons<T>>,
|
|
sz: usize,
|
|
}
|
|
|
|
pub struct Iter<'a, T>
|
|
{
|
|
current: Option<&'a Cons<T>>,
|
|
}
|
|
|
|
pub struct IterMut<'a, T>
|
|
{
|
|
current: Option<&'a mut Cons<T>>,
|
|
}
|
|
|
|
pub struct IntoIter<T>
|
|
{
|
|
current: Option<Box<Cons<T>>>,
|
|
}
|
|
|
|
impl<T> Default for LinkedList<T>
|
|
{
|
|
#[inline]
|
|
fn default() -> Self
|
|
{
|
|
Self::new()
|
|
}
|
|
}
|
|
|
|
impl<T> LinkedList<T>
|
|
{
|
|
pub const fn new() -> Self
|
|
{
|
|
Self { head: None, sz: 0 }
|
|
}
|
|
|
|
pub fn push(&mut self, value: T)
|
|
{
|
|
if let Some(head) = &mut self.head
|
|
{
|
|
head.next = Some(Box::new(mem::replace(head, Cons{ item: value, next: None })));
|
|
self.sz+=1;
|
|
} else {
|
|
self.head = Some(Cons{item: value, next: None});
|
|
self.sz=1;
|
|
}
|
|
}
|
|
|
|
#[inline]
|
|
pub fn len(&self) -> usize
|
|
{
|
|
self.sz
|
|
}
|
|
|
|
pub fn pop(&mut self) -> Option<T>
|
|
{
|
|
if let Some(_) = self.head
|
|
{
|
|
let old = mem::replace(&mut self.head, None).unwrap();
|
|
self.head = old.next.map(|x| *x);
|
|
self.sz-=1;
|
|
Some(old.item)
|
|
} else {
|
|
None
|
|
}
|
|
}
|
|
|
|
pub fn clear(&mut self)
|
|
{
|
|
self.head = None;
|
|
self.sz=0;
|
|
}
|
|
|
|
pub fn iter<'a>(&'a self) -> Iter<'a, T>
|
|
{
|
|
Iter{ current: self.head.as_ref() }
|
|
}
|
|
|
|
pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T>
|
|
{
|
|
IterMut{ current: self.head.as_mut() }
|
|
}
|
|
|
|
pub fn remove(&mut self, at: usize) -> T
|
|
{
|
|
assert!(at < self.sz, "Cannot remove at element > than size");
|
|
|
|
todo!()
|
|
}
|
|
}
|
|
|
|
impl<'a, T> Iterator for Iter<'a, T>
|
|
{
|
|
type Item = &'a T;
|
|
fn next(&mut self) -> Option<Self::Item>
|
|
{
|
|
if self.current.is_some() {
|
|
let mut current = mem::replace(&mut self.current, None);
|
|
let mut nref = current.unwrap().next.as_ref().map(|x| x.as_ref())
|
|
} else {
|
|
None
|
|
}
|
|
}
|
|
}
|