// Week 8 – Double-ended queue (deque) with a circular array
// Run: java CircularDeque.java
public class CircularDeque {
    private final int[] data;
    private int front = 0, count = 0;

    CircularDeque(int capacity) { data = new int[capacity]; }

    boolean isEmpty() { return count == 0; }
    boolean isFull() { return count == data.length; }

    private int index(int i) { return (front + i) % data.length; } // position of the i-th element

    // Insertion at the front: front steps back by one (wrapping around) – O(1)
    void addFirst(int x) {
        if (isFull()) throw new IllegalStateException("full");
        front = (front - 1 + data.length) % data.length; // so that -1 mod n is correctly n-1
        data[front] = x;
        count++;
    }

    void addLast(int x) {
        if (isFull()) throw new IllegalStateException("full");
        data[index(count)] = x;
        count++;
    }

    int removeFirst() {
        if (isEmpty()) throw new IllegalStateException("empty");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    int removeLast() {
        if (isEmpty()) throw new IllegalStateException("empty");
        int x = data[index(count - 1)];
        count--;
        return x;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < count; i++) sb.append(i > 0 ? " " : "").append(data[index(i)]);
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        CircularDeque d = new CircularDeque(6);
        d.addLast(3);
        d.addLast(4);
        d.addFirst(2);
        d.addFirst(1);
        d.addLast(5);
        System.out.println("deque: " + d);
        System.out.println("removeFirst = " + d.removeFirst() + ", removeLast = " + d.removeLast() + " -> " + d);

        // Stack and queue in one: using one end it is a stack, using both ends a queue
        java.util.ArrayDeque<Character> dq = new java.util.ArrayDeque<>();
        for (char c : "racecar".toCharArray()) dq.addLast(c);
        boolean pal = true;
        while (dq.size() > 1) if (dq.pollFirst() != dq.pollLast()) pal = false;
        System.out.println("\"racecar\" is a palindrome (with a deque)? " + pal);
    }
}