package second_term.third_week;

import second_term.first_week.EmptyCollectionException;

public class deque<T> implements DequeADT<T> {

    private Node first;//最左边的头节点
    private Node last;//最右边的节点
    private  int N;//记录链表中的总结点数

    private class Node{
        private Node previous;//向前的指针
        private Node next;//向后的指针
        private T element;
    }

    @Override
    public void enqueueLeft(T element) {
        if (isEmpty()){
            first = new Node();
            first.element =element;
            last = first ;
        }
        else{
            Node temp = first;;
            first = new Node();
            first.element = element;//个人觉得是temp.element = element
            first.next = temp;
            temp.previous = first;
        }
        N++;
    }

    @Override
    public void enqueueRight(T element) {
        if (isEmpty()){
            last = new Node();
            last.element=element;
            first = last;
        }
        else{
            Node temp = last;
            last = new Node();
            last.element = element;
            last.previous = temp;
            temp.next = last;
        }
        N++;
    }

    @Override
    public T dequeueLeft() throws EmptyCollectionException {
        if (isEmpty())
            throw new EmptyCollectionException("deque");
        else{
            T element = first.element;
            first = first.next;
            if (N == 1){
                first = last = null;
            }
            else{
                first.previous = null;
            }
            N--;

            return element;
        }
    }

    @Override
    public T dequeueRight() {
        if (isEmpty())
            throw new EmptyCollectionException("deque");
        else{
            T element = last.element;
            last = last.previous;
            if (N == 1){
                first = last = null;
            }
            else{
                last.next = null;
            }
            N--;
            return element;
        }
    }

    @Override
    public T first() throws EmptyCollectionException{
        if (first.element == null)
            throw new EmptyCollectionException("dequeue");
        else
             return first.element;
    }

    @Override
    public boolean isEmpty() {
        return N==0;
    }

    @Override
    public int size() {
        return N;
    }

    public String toString(){
        String result = "";
        Node current = first;
        while(current!=null){
            result += current.element.toString()+" ";
            current= current.next;
        }
        return result;
    }
    public  static void main(String []args){
        deque queue = new deque();
        System.out.println(queue.isEmpty());

        queue.enqueueLeft(3);
        queue.enqueueLeft(2);
        queue.enqueueLeft(1);
        queue.enqueueRight(4);
        queue.enqueueRight(5);
        queue.dequeueLeft();
        queue.dequeueLeft();
        queue.dequeueRight();

        System.out.println(queue.toString());
    }
}