use std::alloc::Allocator;

#[derive(Clone)]
enum List<T, A: Allocator> {
    Nil,
    Cons(T, Box<List<T, A>, A>),
}

/*
-- Written in a real programming /language/
reverse a = reverseOnto [] a where
    reverseOnto rs [] = rs
    reverseOnto rs (x:xs) = reverseOnto (x:rs) xs
*/
fn reverse<T, A: Allocator + Copy>(mut list: List<T, A>, alloc: A) -> List<T, A> {
    let mut r = List::Nil;
    loop {
        match list {
            List::Nil => break r,
            List::Cons(x, xs) => {
                r = List::Cons(x, Box::new_in(r, alloc));
                list = *xs;
            }
        }
    }
}

impl<T, A: Allocator> List<T, A> {
    fn point_in(x: T, alloc: A) -> Self {
        List::Cons(x, List::nil_in(alloc))
    }
    fn nil_in(alloc: A) -> Box<Self, A> {
        Box::new_in(List::Nil, alloc)
    }
}

impl<T, A: Allocator + Copy> List<T, A> {
    fn snoc(self, x: T, alloc: A) -> Self {
        match self {
            List::Nil => List::Cons(x, Self::nil_in(alloc)),
            List::Cons(head, tail) => List::Cons(
                head,
                Box::new_in(tail.snoc(x, alloc), alloc),
            )
        }
    }
}

impl<T: Clone, A: Allocator + Copy> List<T, A> {
    fn copy_from_slice(xs: &[T], a: A) -> Self {
        let mut r = List::Nil;
        for x in xs.iter().rev() {
            let tail = Box::new_in(r, a);
            r = List::Cons(x.clone(), tail);
        }
        r
    }
}

// Have to implement all this shit by hand because of rust's broken bounds

impl<T: std::fmt::Debug, A: Allocator> std::fmt::Debug for List<T, A> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            List::Nil => write!(f, "Nil"),
            List::Cons(x, xs) => write!(f, "Cons({:?}, {:?})", x, *xs),
        }
    }
}
impl<T: PartialEq, A: Allocator> PartialEq for List<T, A> {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (List::Nil, List::Nil) => true,
            (List::Cons(a, s1), List::Cons(b, o1)) if a == b => *s1 == *o1,
            _ => false,
        }
    }
}
impl<T: Eq, A: Allocator> Eq for List<T, A> {}

// Shit implementation end

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn construct_list() {
        let xs = super::List::copy_from_slice(&[1, 2, 3], std::alloc::Global);
        let ideal = List::Cons(
            1,
            Box::new(List::Cons(
                2,
                Box::new(List::Cons(
                    3,
                    Box::new(List::Nil),
                )),
            )),
        );
        assert_eq!(xs, ideal);
    }

    #[test]
    fn snoc() {
        let a = std::alloc::Global;
        let x = List::copy_from_slice(&[1, 2, 3], a);
        let y = List::point_in(1, a).snoc(2, a).snoc(3, a);
        assert_eq!(x, y);
    }

    #[test]
    fn reverses() {
        let a = std::alloc::Global;
        assert_eq!(
            List::copy_from_slice(&[1, 2, 3], a),
            reverse(List::copy_from_slice(&[3, 2, 1], a), a)
        )
    }

    #[test]
    fn reverses_in() {
        let a = crate::Arena::new(1024);
        fn inner(list: List<i64, &crate::Arena>, a: &crate::Arena) {
            let lhs = List::copy_from_slice(&[1, 2, 3], a);
            let rhs = reverse(list, a);
            assert_eq!(lhs, rhs);
        }
        inner(List::copy_from_slice(&[3, 2, 1], &a), &a);
    }
}