//循环双端队列：Circle Double Ended Queue
//本质是对动态数组的优化
//队头队尾都可以添加或删除元素
//相比于普通循环队列需要注意的点是在队头插入元素时的对front前移的处理

public class CircleDequeZH<E> {
    private int size;
    private int front;
    private  E elements[];
    private static final int DEFAULT_CAPACITY = 10;

    public CircleDequeZH() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    private int getMo(int a, int b){
        return a > b ? (a-b) : a;
        //%运算效率太低，当a<2b时可以用这个表达式替代取模，而循环队列front+index最大等于2*length-1，恰好符合要求
    }

    //计算队头队尾元素下标可以写一个函数，用来映射循环队列中的真实索引
    public int realIndexCaculate(int index){
        if (index<0){
            return getMo((index + front + elements.length), elements.length);
            //当front=0时，我们在队头插入元素，front要前移，也就是到整个数组的末尾，所以单独写一个if应对这种情况
            //这时候front的新位置为（front-1+length）%length
        }
        return getMo((index+front),elements.length);//!!!
        //就是要找队列中的下标为index的（第index+1个）元素，返回它在我们数组里的真实下标
        //我觉得影响以后的可读性就没用
    }


    private void ifNeedEnLarge(int needCapacity){
        int oldcapacity = elements.length;
        if (needCapacity<=oldcapacity){
            return;
        }else{
            int newcapacity = oldcapacity + (oldcapacity>>1);
            E[] newElements = (E[]) new Object[newcapacity];
            for (int i=0;i<size;i++){
                //循环队列获取第i个元素的下标的方式：
                newElements[i]=elements[(i+front)%elements.length];
                //这个扩容的方式就是把队列里的元素依次出队到另一个队列里，同时重置队头的位置
            }
            front = 0;
            elements = newElements;
            System.out.println("enLarge Success"+"  newCapacity = "+newcapacity);
        }
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    //清空循环队列，涉及到元素的真实下标计算，同扩容那里
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[(i+front)%elements.length]=null;
        }
        size = 0;
        front = 0;
    }

    //出队，主要注意对front的处理
    public E deQueueFront(){
        E element = elements[front];
        elements[front] = null;
        front = (front+1)%elements.length;
        size--;
        return element;
    }

    //从队尾出队
    public E deQueueNear(){
        E element = elements[realIndexCaculate(size-1)];
        elements[realIndexCaculate(size-1)] = null;
        size--;
        return element;
    }

    //从队头入队
    public void enQueueFront(E element){
        ifNeedEnLarge(size+1);
        elements[realIndexCaculate(-1)] = element;
        front = realIndexCaculate(-1);
        size++;
    }

    //入队，主要注意对入队位置的计算
    public void enQueueNear(E element){
        ifNeedEnLarge(size+1);
        elements[(front+size)% elements.length] = element;
        size++;
    }

    public String arrayPrint(){
        StringBuilder string = new StringBuilder();
        string.append("size = ").append(size).append(" ").append("front= ").append(elements[front]).append(" [");
        for (int i = 0; i< elements.length; i++ ){
            if (elements[i]==null){
                string.append("null,");
            }else {
                string.append(elements[i]).append(",");
            }
        }
        string.append("]");
        return string.toString();
    }
}