use std::iter::FromIterator;

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    pub fn new(data: T, next: Option<Box<Node<T>>>) -> Self {
        Node { data, next }
    }

    pub fn len(&self) -> usize {
        1 + self.next.as_ref().map(|n| n.len()).unwrap_or(0)
    }
}

#[derive(Debug)]
pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        SimpleLinkedList { head: None }
    }

    // You may be wondering why it's necessary to have is_empty()
    // when it can easily be determined from len().
    // It's good custom to have both because len() can be expensive for some types,
    // whereas is_empty() is almost always cheap.
    // (Also ask yourself whether len() is expensive for SimpleLinkedList)
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    pub fn len(&self) -> usize {
        self.head.as_ref().map(|n| n.len()).unwrap_or(0)
    }

    pub fn push(&mut self, _element: T) {
        // let node = Box::new(Node::new(_element, self.head.take()));
        // self.head.replace(node);
        self.head = Some(Box::new(Node::new(_element, self.head.take())));
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|n| {
            // n.next.map(|n1| self.head.replace(n1));
            self.head = n.next;
            n.data
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|n| &n.data)
    }

    pub fn rev(self) -> SimpleLinkedList<T> {
        self.rev_aux(SimpleLinkedList::new())
    }

    pub fn rev_aux(mut self, mut acc: SimpleLinkedList<T>) -> SimpleLinkedList<T> {
        if let Some(e) = self.pop() {
            acc.push(e);
            self.rev_aux(acc)
        } else {
            acc
        }
    }

    fn into_aux(mut self, mut acc: Vec<T>) -> Vec<T> {
        if let Some(e) = self.pop() {
            acc.push(e);
            self.into_aux(acc)
        } else {
            acc
        }
    }
}

impl<T> FromIterator<T> for SimpleLinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(_iter: I) -> Self {
        _iter
            .into_iter()
            .fold(SimpleLinkedList::new(), |mut acc, n| {
                acc.push(n);
                acc
            })
    }
}

// In general, it would be preferable to implement IntoIterator for SimpleLinkedList<T>
// instead of implementing an explicit conversion to a vector. This is because, together,
// FromIterator and IntoIterator enable conversion between arbitrary collections.
// Given that implementation, converting to a vector is trivial:
//
// let vec: Vec<_> = simple_linked_list.into_iter().collect();
//
// The reason this exercise's API includes an explicit conversion to Vec<T> instead
// of IntoIterator is that implementing that interface is fairly complicated, and
// demands more of the student than we expect at this point in the track.

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
    fn into(self) -> Vec<T> {
        self.rev().into_aux(Vec::new())
    }
}