//! A linked list whose nodes can be stack-allocated.

use core::fmt;

/// A linked list whose nodes can be stack-allocated.
#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
pub struct StackLinkedList<'list, T>(Option<(T, &'list StackLinkedList<'list, T>)>);

impl<'list, T> StackLinkedList<'list, T> {
    /// An empty linked list.
    pub const NIL: StackLinkedList<'list, T> = StackLinkedList(None);

    /// Prepends an element to the linked list, returning the new head node.
    pub fn cons(&'list self, head: T) -> StackLinkedList<'list, T> {
        StackLinkedList(Some((head, self)))
    }

    /// Attempts to return the head and tail of the list.
    pub fn uncons(&self) -> Option<(&T, &'list StackLinkedList<'list, T>)> {
        let (hd, tl) = self.0.as_ref()?;
        Some((hd, tl))
    }

    /// Returns an iterator over the elements in the list.
    pub fn iter<'iter: 'list>(&'iter self) -> impl 'iter + Iterator<Item = &'list T> {
        struct Iter<'iter, 'list, T>(&'iter StackLinkedList<'list, T>);

        impl<'iter: 'list, 'list, T> Iterator for Iter<'iter, 'list, T> {
            type Item = &'list T;

            fn next(&mut self) -> Option<&'list T> {
                match &(self.0).0 {
                    Some((hd, tl)) => {
                        self.0 = tl;
                        Some(hd)
                    }
                    None => None,
                }
            }
        }

        Iter(self)
    }
}

impl<'list, T: fmt::Debug> fmt::Debug for StackLinkedList<'list, T> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        fmt.debug_list().entries(self.iter()).finish()
    }
}

impl<'list, T: Copy> IntoIterator for StackLinkedList<'list, T> {
    type Item = T;

    type IntoIter = OwnedIter<'list, T>;

    fn into_iter(self) -> OwnedIter<'list, T> {
        OwnedIter(self)
    }
}

/// An (owned) iterator over a `StackLinkedList`.
#[derive(Clone)]
pub struct OwnedIter<'list, T>(StackLinkedList<'list, T>);

impl<'list, T: Copy> Iterator for OwnedIter<'list, T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        match (self.0).0 {
            Some((hd, tl)) => {
                self.0 = *tl;
                Some(hd)
            }
            None => None,
        }
    }
}