use std::cell::RefCell;
use std::rc::Rc;
use std::fmt;

type NodePtr<T> = Rc<RefCell<Node<T>>>;

#[derive(Clone)]
enum Zipper<T> {
    Clean,
    Dirty(NodePtr<T>, Option<NodePtr<T>>),
}

struct Node<T> {
    value: T,
    next: Option<NodePtr<T>>,
    zipper: Zipper<T>,
}

impl<T: Clone> Node<T> {
    fn alloc(node: Node<T>) -> NodePtr<T> {
        Rc::from(RefCell::from(node))
    }

    fn create_lazy(x: &Option<NodePtr<T>>, y: Option<NodePtr<T>>) -> Option<NodePtr<T>> {
        if let Some(x) = x {
            let xb = x.borrow();
            let y = y.expect("create_lazy: imbalance");

            Some(Node::alloc(Node {
                value: xb.value.clone(),
                next: xb.next.clone(),
                zipper: Zipper::Dirty(y, None),
            }))
        } else {
            y
        }
    }

    fn rotate_zipper(x: &NodePtr<T>) {
        let xb = x.borrow();
        if let Zipper::Dirty(c, d) = xb.zipper.clone() {
            let cb = c.borrow();

            let node_1 = Node {
                value: cb.value.clone(),
                next: d,
                zipper: Zipper::Clean,
            };

            let node_1_ptr = Node::alloc(node_1);

            let new_next;

            let cb_next = cb.next.clone()
                .expect("rotate_zipper: imbalance");

            if let Some(next) = xb.next.clone() {
                let nextb = next.borrow();
                new_next = Node {
                    value: nextb.value.clone(),
                    next: nextb.next.clone(),
                    zipper: Zipper::Dirty(cb_next, Some(node_1_ptr)),
                };
            } else {
                new_next = Node {
                    value: cb_next.borrow().value.clone(),
                    next: Some(node_1_ptr),
                    zipper: Zipper::Clean
                };
            }

            let new_node = Node {
                value: xb.value.clone(),
                next: Some(Node::alloc(new_next)),
                zipper: Zipper::Clean,
            };

            drop(xb);

            x.replace(new_node);
        }
    }
}

#[derive(Clone)]
struct Queue<T> {
    front: Option<NodePtr<T>>,
    back: Option<NodePtr<T>>,
    jump: Option<NodePtr<T>>,
}

impl<T: Clone> Queue<T> {
    fn new() -> Queue<T> {
        Queue {
            front: None,
            back: None,
            jump: None,
        }
    }

    fn pop_front(self) -> Option<(Queue<T>, T)> {
        let front = self.front?;
        let res = front.borrow().value.clone();

        let res_queue;

        if let Some(jump) = self.jump {
            Node::rotate_zipper(&jump);

            let jumpb = jump.borrow();

            let frontb = front.borrow();
            res_queue = Queue {
                front: frontb.next.clone(),
                back: self.back,
                jump: jumpb.next.clone(),
            }
        } else {
            let frontb = front.borrow();
            let zipper = Node::create_lazy(&frontb.next, self.back);
            res_queue = Queue {
                front: zipper.clone(),
                back: None,
                jump: zipper,
            }
        }

        Some((res_queue, res))
    }

    fn push_back(self, v: T) -> Queue<T> {
        let new_node = Node::alloc(Node {
            value: v,
            next: self.back.clone(),
            zipper: Zipper::Clean,
        });

        if let Some(jump) = self.jump {
            Node::rotate_zipper(&jump);

            let jumpb = jump.borrow();

            Queue {
                front: self.front.clone(),
                back: Some(new_node),
                jump: jumpb.next.clone(),
            }
        } else {
            let zipper = Node::create_lazy(&self.front, Some(new_node));

            Queue {
                front: zipper.clone(),
                back: None,
                jump: zipper,
            }
        }
    }
}

struct QueueIter<T> {
    dat: Queue<T>
}

impl<T: Clone> Iterator for QueueIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        let (next, res) = self.dat.clone().pop_front()?;
        self.dat = next;
        Some(res)
    }
}

impl<T: Clone> IntoIterator for Queue<T> {
    type Item = T;
    type IntoIter = QueueIter<T>;

    fn into_iter(self) -> QueueIter<T> {
        QueueIter { dat: self }
    }
}

impl<T: fmt::Debug + Clone> fmt::Debug for Queue<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let vec: Vec<T> = self.clone().into_iter().collect();
        write!(f, "Queue{:?}", vec)
    }
}

fn main() {
    let a: Queue<u32> = Queue::new()
        .push_back(3)
        .push_back(4)
        .push_back(5);

    println!("a = {:?}", a);

    println!("-----");

    // Cloning is fast -- only a few pointers copied
    let (b, x) = a.clone()
        .pop_front().unwrap();


    println!("a = {:?} (unchanged)", a);
    println!();
    println!("b = {:?}", b);
    println!("x = {:?}", x);

    println!("-----");

    let c = b.clone().push_back(7);
    let d = b.clone().push_back(8);
    let e = a.clone().push_back(9);

    println!("a = {:?} (unchanged)", a);
    println!("b = {:?} (unchanged)", b);
    println!();
    println!("c = {:?}", c);
    println!("d = {:?}", d);
    println!("e = {:?}", e);
}