paradigms/java/queue/ArrayQueueADT.java

package queue;

import java.util.function.Predicate;

/**
 * @author Doschennikov Nikita (me@fymio.us)
 */
public class ArrayQueueADT {
    private Object[] queue;
    private int head;
    private int size;

    public ArrayQueueADT() {
        queue = new Object[4];
        head = 0;
        size = 0;
    }

    public static ArrayQueueADT create() {
        return new ArrayQueueADT();
    }

    public static void enqueue(ArrayQueueADT q, Object element) {
        assert q != null && element != null : "Queue and element must not be null";
        ensureCapacity(q);
        q.queue[(q.head + q.size) % q.queue.length] = element;
        q.size++;
    }

    public static void push(ArrayQueueADT q, Object element) {
        assert q != null && element != null : "Queue and element must not be null";
        ensureCapacity(q);
        q.head = (q.head - 1 + q.queue.length) % q.queue.length;
        q.queue[q.head] = element;
        q.size++;
    }

    public static Object element(ArrayQueueADT q) {
        assert q != null && q.size > 0 : "Queue must not be null and not be empty";
        return q.queue[q.head];
    }

    public static Object peek(ArrayQueueADT q) {
        assert q != null && q.size > 0 : "Queue must not be null and not be empty";
        return q.queue[(q.head + q.size - 1) % q.queue.length];
    }

    public static Object dequeue(ArrayQueueADT q) {
        assert q != null && q.size > 0 : "Queue must not be null and not be empty";
        Object result = q.queue[q.head];
        q.queue[q.head] = null;
        q.head = (q.head + 1) % q.queue.length;
        q.size--;
        return result;
    }

    public static Object remove(ArrayQueueADT q) {
        assert q != null && q.size > 0 : "Queue must not be null and not be empty";
        int tail = (q.head + q.size - 1) % q.queue.length;
        Object result = q.queue[tail];
        q.queue[tail] = null;
        q.size--;
        return result;
    }

    public static int size(ArrayQueueADT q) {
        assert q != null : "Queue must not be null";
        return q.size;
    }

    public static boolean isEmpty(ArrayQueueADT q) {
        assert q != null : "Queue must not be null";
        return q.size == 0;
    }

    public static void clear(ArrayQueueADT q) {
        assert q != null : "Queue must not be null";
        q.queue = new Object[4];
        q.head = 0;
        q.size = 0;
    }

    public static int count(ArrayQueueADT q, Object element) {
        assert q != null && element != null : "Queue and element must not be null";
        int cnt = 0;
        for (int i = 0; i < q.size; i++) {
            if (element.equals(q.queue[(q.head + i) % q.queue.length])) {
                cnt++;
            }
        }
        return cnt;
    }

    public static int countIf(ArrayQueueADT q, Predicate<Object> predicate) {
        assert q != null && predicate != null : "Queue and predicate must not be null";
        int cnt = 0;
        for (int i = 0; i < q.size; i++) {
            if (predicate.test(q.queue[(q.head + i) % q.queue.length])) {
                cnt++;
            }
        }
        return cnt;
    }

    public static int indexIf(ArrayQueueADT q, Predicate<Object> predicate) {
        assert q != null && predicate != null : "Queue and predicate must not be null";
        for (int i = 0; i < q.size; i++) {
            if (predicate.test(q.queue[(q.head + i) % q.queue.length])) {
                return i;
            }
        }
        return -1;
    }

    public static int lastIndexIf(ArrayQueueADT q, Predicate<Object> predicate) {
        assert q != null && predicate != null : "Queue and predicate must not be null";
        for (int i = q.size - 1; i >= 0; i--) {
            if (predicate.test(q.queue[(q.head + i) % q.queue.length])) {
                return i;
            }
        }
        return -1;
    }

    public static int indexOf(ArrayQueueADT q, Object element) {
        assert element != null : "Predicate must not be null";
        for (int i = 0; i < q.size; i++) {
            if (q.queue[(q.head + i) % q.queue.length].equals(element)) return i;
        }
        return -1;
    }

    public static int lastIndexOf(ArrayQueueADT q, Object element) {
        assert element != null : "Predicate must not be null";
        for (int i = q.size - 1; i >= 0; i--) {
            if (q.queue[(q.head + i) % q.queue.length].equals(element)) return i;
        }
        return -1;
    }

    private static void ensureCapacity(ArrayQueueADT q) {
        if (q.size < q.queue.length) return;
        Object[] newQueue = new Object[q.queue.length * 2];
        for (int i = 0; i < q.size; i++) {
            newQueue[i] = q.queue[(q.head + i) % q.queue.length];
        }
        q.queue = newQueue;
        q.head = 0;
    }
}