Sliding window view on a stream / sequence of int data. A non-blocking circular queue which automatically evicts elements from the head of the queue when attempting to add new elements into the array and it is full. Provides element insertion and removal at opposite ends (like a queue) and access to random elements in the container (like an array).

EjectingIntQueue.java

package ch.sgwerder.gist;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.RandomAccess;

/**
 * Copyright (C) 2015 Simon Gwerder.
 * <p/>
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 * <p/>
 * Applications sometimes need a sliding window view on a stream / sequence of data.
 * This can be provided by a container with:
 * - fast element insertion and removal at opposite ends (like a queue)
 * - fast access to random elements in the container (like an array)
 * Unfortunately, no existing implementation in the Java Collections Framework satisfies both of these requirements.
 * This problem can be solved by using a circular array (also called a circular buffer, cyclic buffer, or ring buffer)
 * as the underlying data structure.
 * <p/>
 * A non-blocking circular queue which automatically evicts elements from the head of the queue when attempting to add
 * new elements into the array and it is full.
 * An evicting queue must be configured with a maximum size. Each time an element is added to a full queue, the queue
 * automatically removes its head element.
 * This class is not thread-safe. Does not support null elements.
 * <p/>
 * {@code EjectingIntQueue eiq = new EjectingIntQueue(25);}
 * <p/>
 * Based on:
 * http://faculty.washington.edu/moishe/javademos/ch07%20Code/jss2/CircularArrayQueue.java
 * http://www.museful.net/2012/software-development/circulararraylist-for-java
 * https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/EvictingQueue.html
 * https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/queue/CircularFifoQueue.html
 */
public class EjectingIntQueue implements Collection<Integer>, Iterable<Integer>, RandomAccess {

    private final static int DEFAULT_CAPACITY = 16;
    private int head, tail, count;
    private int[] queue;

    public EjectingIntQueue() {
        this(DEFAULT_CAPACITY);
    }

    public EjectingIntQueue(int capacity) {
        this.head = this.tail = this.count = 0;
        this.queue = new int[capacity];
    }

    private int wrapIndex(int i) {
        int m = i % queue.length;
        if (m < 0) { // Modulus can be negative
            m += queue.length;
        }
        return m;
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= count) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + count;
    }

    public int get(int i) {
        rangeCheck(i);
        return queue[wrapIndex(head + i)];
    }

    public void enqueue(int element) {
        if (count == queue.length) {
            // queue[head] = 0;
            head = wrapIndex(head + 1); // Ejecting head element here
        }
        else {
            count++;
        }
        queue[tail] = element;
        tail = wrapIndex(tail + 1);
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        int result = queue[head];
        queue[head] = 0;
        head = wrapIndex(head + 1);
        count--;
        return result;
    }

    public boolean dequeue(int element) {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        if (getFirst() == element) {
            dequeueFirst();
            return true;
        }
        if (getLast() == element) {
            dequeueLast();
        }
        for (int i = 1; i < count - 1; i++) {
            if (element == get(i)) {
                for (int x = i + 1; x < count; x++) {
                    int e = get(x);
                    queue[wrapIndex(head + x - 1)] = e;
                }
                queue[wrapIndex(tail - 1)] = 0;
                tail = wrapIndex(tail - 1);
                count--;
                return true;
            }
        }
        return false;
    }

    public int getFirst() {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        return queue[head];
    }

    public int getLast() {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        return queue[wrapIndex(tail - 1)];
    }

    public int dequeueFirst() {
        return dequeue();
    }

    public int dequeueLast() {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        int result = queue[wrapIndex(tail - 1)];
        tail = wrapIndex(tail - 1);
        queue[tail] = 0;
        count--;
        return result;
    }

    public void expandCapacity() {
        expandCapacity(2);
    }

    public void expandCapacity(int factor) {
        int[] larger = new int[queue.length * factor];

        for (int i = 0; i < count; i++) {
            larger[i] = queue[head];
            head = wrapIndex(head + 1);
        }

        head = 0;
        tail = count;
        queue = larger;
    }

    public int remainingCapacity() {
        return queue.length - count;
    }

    public boolean offer(int element) {
        if (count >= queue.length) {
            return false;
        }
        enqueue(element);
        return true;
    }

    public int indexOf(int element) {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        for (int i = 0; i < count; i++) {
            int index = wrapIndex(head + i);
            if (element == queue[index]) {
                return i;
            }
        }
        return -1;
    }

    public int lastIndexOf(int element) {
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        for (int i = count - 1; i >= 0; i--) {
            int index = wrapIndex(head + i);
            if (element == queue[index]) {
                return i;
            }
        }
        return -1;
    }

    public EjectingIntQueue subQueueCopy(int fromIndex, int toIndex, int newCapacity) {
        rangeCheck(fromIndex);
        rangeCheck(toIndex - 1);
        int newCount = toIndex - fromIndex;
        if (newCount < 0 || newCapacity < newCount) {
            throw new IllegalArgumentException();
        }
        EjectingIntQueue newQueue = new EjectingIntQueue(newCapacity);
        int pos = 0;
        for (int i = fromIndex; i < toIndex; i++) {
            newQueue.queue[pos] = queue[wrapIndex(head + i)];
            pos++;
        }
        newQueue.head = 0;
        newQueue.tail = newCount;
        newQueue.count = newCount;
        return newQueue;
    }

    public EjectingIntQueue subQueueCopy(int fromIndex, int toIndex) {
        return subQueueCopy(fromIndex, toIndex, queue.length);
    }

    public int[] subArrayCopy(int fromIndex, int toIndex, int newCapacity) {
        return subQueueCopy(fromIndex, toIndex, newCapacity).queue;
    }

    public int[] subArrayCopy(int fromIndex, int toIndex) {
        return subArrayCopy(fromIndex, toIndex, queue.length);
    }

    public int[] snapShot() {
        int[] snapshot = new int[queue.length];
        System.arraycopy(queue, 0, snapshot, 0, queue.length);
        return snapshot;
    }

    public String scan() {
        return Arrays.toString(queue);
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return Arrays.toString(queue);
        }
        StringBuilder result = new StringBuilder();
        result.append("[");
        String separator = ", ";
        for (int i = 0; i < count; i++) {
            result.append(get(i) + separator);
        }
        int lastIndex = result.lastIndexOf(separator);
        if (lastIndex >= 0) {
            result.delete(lastIndex, result.length());
        }
        result.append("]");
        return result.toString();
    }

    @Override
    public Iterator<Integer> iterator() {
        Iterator<Integer> it = new Iterator<Integer>() {

            private int currentIndex = 0;

            @Override
            public boolean hasNext() {
                return currentIndex < count;
            }

            @Override
            public Integer next() {
                return get(currentIndex++);
            }

            @Override
            public void remove() {
                dequeue(getLast());
            }

        };
        return it;
    }

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

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

    @Override
    public boolean contains(Object o) {
        if (!(o instanceof Integer)) {
            return false;
        }
        return indexOf((Integer) o) != -1;
    }

    public void clear() {
        this.head = this.tail = this.count = 0;
        this.queue = new int[queue.length];
    }

    @Override
    public Object[] toArray() {
        Integer[] a = new Integer[queue.length];
        System.arraycopy(subArrayCopy(0, count), 0, a, 0, queue.length);
        return a;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        if (a.length < queue.length) {
            a = (T[]) new Integer[queue.length];
        }
        else {
            Arrays.fill(a, null);
        }
        System.arraycopy(subArrayCopy(0, count), 0, a, 0, queue.length);
        return a;
    }

    @Override
    public boolean add(Integer integer) {
        if (integer == null) {
            return false;
        }
        enqueue(integer);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        try {
            return dequeue((Integer) o);
        }
        catch (ClassCastException cce) {
            return false;
        }
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends Integer> c) {
        if (c.isEmpty()) {
            return false;
        }
        for (Integer integer : c) {
            add(integer);
        }
        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        if (c.isEmpty()) {
            return false;
        }
        for (Object o : c) {
            remove(o);
        }
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean changed = false;
        for (Object o : c) {
            if (!contains(o)) {
                remove(o);
                changed = true;
            }
        }
        return changed;
    }

}