#![feature(box_syntax)]

use std::rc::Rc;

#[derive(Debug)]
enum List<T: Clone> {
    Empty,
    Exist(Rc<Box<Node<T>>>),
}

#[derive(Debug)]
struct Node<T: Clone> {
    elm: T,
    next: Rc<List<T>>,
}

trait Stack_<T> {
    fn new(T, Self) -> Self;
    fn is_empty(&self) -> bool;
    fn head(&self) -> Option<T>;
    fn tail(&self) -> Option<&Self>;
    fn append(&self, Self) -> Self;
    fn update(self, u32, T) -> Self;
}

impl<T: Clone> Stack_<T> for List<T> {
    fn new(elm: T, next: Self) -> Self {
        List::Exist(Rc::new(box Node{
            elm: elm,
            next: Rc::new(next)
        }))
    }

    fn is_empty(&self) -> bool {
        match *self {
            List::Empty => true,
            List::Exist(_) => false,
        }
    }

    fn head(&self) -> Option<T> {
        match self {
            &List::Empty => None,
            &List::Exist(ref n) => Some(n.elm.clone())
        }
    }

    fn tail(&self) -> Option<&Self> {
        match self {
            &List::Empty => None,
            &List::Exist(ref n) => Some(&n.next)
        }
    }

    fn append(&self, l: Self) -> Self {
        match self {
            &List::Empty => l,
            &List::Exist(_) => {
                List::Exist(Rc::new(box Node{
                    elm: self.head().unwrap(),
                    next: Rc::new(self.tail().unwrap().append(l))
                }))
            },
        }
    }

    fn update(self, i: u32, elm: T) -> Self {
        if self.is_empty(){
            List::Empty
        } else if i == 0 {
            List::new(elm, self)
        } else {
            List::new(self.head().unwrap(), self.update(i-1, elm))
        }
    }
}

fn main() {
    let a = List::new(1, List::new(2, List::Empty));
    let b = List::new(3, List::new(4, List::Empty));
    let c = b.update(1, 3000);
    println!("{:?}", a.append(c));
}