use std::cell::RefCell;
use std::iter::FromIterator;
use std::rc::Rc;

pub struct List<T> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
}

struct Node<T> {
    element: T,
    next: Option<Rc<RefCell<Node<T>>>>,
}

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

    pub fn push_front(&mut self, element: T) {
        let mut new_head = Node { element: element, next: None };
        if let Some(old_head) = self.head.take() {
            new_head.next = Some(old_head);
        }
        self.head = Some(Rc::new(RefCell::new(new_head)));
        if self.tail.is_none() {
            self.tail = Some(self.head.as_ref().unwrap().clone());
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        if let Some(old_head) = self.head.take() {
            let mut old_head = Rc::try_unwrap(old_head)
                .map_err(|_| ()).unwrap()
                .into_inner();
            self.head = old_head.next.take();
            if self.head.is_none() {
                self.tail = None;
            }
            Some(old_head.element)
        } else {
            None
        }
    }

    pub fn push_back(&mut self, element: T) {
        let new_tail = Rc::new(RefCell::new(Node { element: element, next: None }));
        if let Some(old_tail) = self.tail.take() {
            old_tail.borrow_mut().next = Some(new_tail.clone());
        }
        self.tail = Some(new_tail);
        if self.head.is_none() {
            self.head = Some(self.head.as_ref().unwrap().clone());
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        // if let Some(mut previous) = self.head.clone() {
        //     let old_tail = self.tail.take().unwrap();
        //     while let Some(node) = previous.borrow().next.as_ref() {
        //         if Rc::ptr_eq(&node, &old_tail) {
        //             self.tail = Some(node.clone());
        //             let old_tail = Rc::try_unwrap(old_tail)
        //                 .map_err(|_| ()).unwrap()
        //                 .into_inner();
        //             return Some(old_tail.element);
        //         }
        //         previous = node.clone();
        //     }
        // }
        // None
        unimplemented!()
    }
}

impl<T> FromIterator<T> for List<T> {
    fn from_iter<It: IntoIterator<Item=T>>(iter: It) -> Self {
        let mut list = List::new();
        for element in iter {
            list.push_back(element);
        }
        list
    }
}

impl<T> Extend<T> for List<T> {
    fn extend<It: IntoIterator<Item=T>>(&mut self, iter: It) {
        for element in iter {
            self.push_back(element);
        }
    }
}