#[derive(Clone, Default)]
pub struct Cactus<T> {
    node: Option<Rc<RefCell<Node<T>>>>
}

#[derive(Clone)]
pub struct Node<T> {
    val: Rc<RefCell<T>>,
    parent: Option<Rc<RefCell<Node<T>>>>,
    len: usize
}

impl<T> Cactus<T> {
    pub fn new() -> Cactus<T> {
        Cactus { node: None }
    }

    pub fn is_empty(&self) -> bool {
        self.node.is_none()
    }

    pub fn len(&self) -> usize {
        self.node.as_ref().map_or(0, |x| x.borrow().len)
    }

    pub fn child(&self, val: T) -> Cactus<T> {

        Cactus {
            node: Some(Rc::new(RefCell::new(Node {
                val: Rc::new(RefCell::new(val)),
                parent: self.node.clone(),
                len: self.node.as_ref().map_or(1, |x| x.borrow().len + 1)
            })))
        }
    }

    pub fn parent(&self) -> Option<Cactus<T>> {
        self.node.as_ref()
            .map(|n| Cactus { node: n.borrow().parent.clone() })
    }

    pub fn val(&mut self) -> Option<Rc<RefCell<T>>> {
        self.node.map(|n| n.borrow_mut().val.clone())
    }
}