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
	}
    }
}