Skip to content

Instantly share code, notes, and snippets.

@shathor
Last active October 14, 2021 19:26
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shathor/007a66c731592012bd9a to your computer and use it in GitHub Desktop.
Save shathor/007a66c731592012bd9a to your computer and use it in GitHub Desktop.
Sliding window view on a stream / sequence of 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).
package ch.sgwerder.gist;
import java.lang.reflect.Array;
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 EjectingQueue<String> eq = new EjectingQueue<>(String[].class, 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 EjectingQueue<E> implements Collection<E>, Iterable<E>, RandomAccess {
private final static int DEFAULT_CAPACITY = 16;
private int head, tail, count;
private E[] queue;
private Class<E[]> type;
public Class<E[]> getType() {
return type;
}
public EjectingQueue(Class<E[]> type) {
this(type, DEFAULT_CAPACITY);
}
public EjectingQueue(Class<E[]> type, int capacity) {
this.head = this.tail = this.count = 0;
this.type = type;
this.queue = newArray(type, capacity);
}
private static <E> E[] newArray(Class<E[]> type) {
return newArray(type, DEFAULT_CAPACITY);
}
private static <E> E[] newArray(Class<E[]> type, int capacity) {
return type.cast(Array.newInstance(type.getComponentType(), 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 E get(int i) {
rangeCheck(i);
return queue[wrapIndex(head + i)];
}
public void enqueue(E element) {
if (element == null) {
throw new IllegalArgumentException();
}
if (count == queue.length) {
// queue[head] = null;
head = wrapIndex(head + 1); // Ejecting head element here
}
else {
count++;
}
queue[tail] = element;
tail = wrapIndex(tail + 1);
}
public E dequeue() {
if (isEmpty()) {
return null;
}
E result = queue[head];
queue[head] = null;
head = wrapIndex(head + 1);
count--;
return result;
}
public boolean dequeue(E element) {
if (element == null) {
throw new IllegalArgumentException();
}
if (isEmpty()) {
return false;
}
if (getFirst() != null && getFirst().equals(element)) {
dequeueFirst();
return true;
}
if (getLast() != null && getLast().equals(element)) {
dequeueLast();
}
for (int i = 1; i < count - 1; i++) {
if (element.equals(get(i))) {
for (int x = i + 1; x < count; x++) {
E e = get(x);
if (e != null) {
queue[wrapIndex(head + x - 1)] = e;
}
}
queue[wrapIndex(tail - 1)] = null;
tail = wrapIndex(tail - 1);
count--;
return true;
}
}
return false;
}
public E getFirst() {
if (isEmpty()) {
return null;
}
return queue[head];
}
public E getLast() {
if (isEmpty()) {
return null;
}
return queue[wrapIndex(tail - 1)];
}
public E dequeueFirst() {
return dequeue();
}
public E dequeueLast() {
if (isEmpty()) {
return null;
}
E result = queue[wrapIndex(tail - 1)];
tail = wrapIndex(tail - 1);
queue[tail] = null;
count--;
return result;
}
public void expandCapacity() {
expandCapacity(2);
}
public void expandCapacity(int factor) {
E[] larger = newArray(type, 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(E element) {
if (element == null) {
throw new IllegalArgumentException();
}
if (count >= queue.length) {
return false;
}
enqueue(element);
return true;
}
public int indexOf(E element) {
if (element == null) {
throw new IllegalArgumentException();
}
for (int i = 0; i < count; i++) {
int index = wrapIndex(head + i);
if (element.equals(queue[index])) {
return i;
}
}
return -1;
}
public int lastIndexOf(E element) {
if (element == null) {
throw new IllegalArgumentException();
}
for (int i = count - 1; i >= 0; i--) {
int index = wrapIndex(head + i);
if (element.equals(queue[index])) {
return i;
}
}
return -1;
}
public EjectingQueue<E> subQueueCopy(int fromIndex, int toIndex, int newCapacity) {
rangeCheck(fromIndex);
rangeCheck(toIndex - 1);
int newCount = toIndex - fromIndex;
if (newCount < 0 || newCapacity < newCount) {
throw new IllegalArgumentException();
}
EjectingQueue<E> newQueue = new EjectingQueue<>(type, 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 EjectingQueue<E> subQueueCopy(int fromIndex, int toIndex) {
return subQueueCopy(fromIndex, toIndex, queue.length);
}
public E[] subArrayCopy(int fromIndex, int toIndex, int newCapacity) {
return subQueueCopy(fromIndex, toIndex, newCapacity).queue;
}
public E[] subArrayCopy(int fromIndex, int toIndex) {
return subArrayCopy(fromIndex, toIndex, queue.length);
}
public E[] snapShot() {
E[] snapshot = newArray(type, 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 (E e : this) {
result.append(e.toString() + separator);
}
int lastIndex = result.lastIndexOf(separator);
if (lastIndex >= 0) {
result.delete(lastIndex, result.length());
}
result.append("]");
return result.toString();
}
@Override
public Iterator<E> iterator() {
Iterator<E> it = new Iterator<E>() {
private int currentIndex = 0;
@Override
public boolean hasNext() {
return currentIndex < count;
}
@Override
public E next() {
return get(currentIndex++);
}
@Override
public void remove() {
dequeue(getLast());
}
};
return it;
}
@Override
public int size() {
return count;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public boolean contains(Object o) {
try {
return indexOf((E) o) != -1;
}
catch (ClassCastException cce) {
return false;
}
}
@Override
public void clear() {
this.head = this.tail = this.count = 0;
this.queue = newArray(type, queue.length);
}
@Override
public Object[] toArray() {
Object[] o = new Object[queue.length];
System.arraycopy(subArrayCopy(0, count), 0, o, 0, queue.length);
return o;
}
@Override
public <T> T[] toArray(T[] a) {
if (a.length < queue.length) {
a = newArray((Class<T[]>) a.getClass(), queue.length);
}
else {
Arrays.fill(a, null);
}
System.arraycopy(subArrayCopy(0, count), 0, a, 0, queue.length);
return a;
}
@Override
public boolean add(E e) {
if (e == null) {
return false;
}
enqueue(e);
return true;
}
@Override
public boolean remove(Object o) {
try {
return dequeue((E) 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 E> c) {
if (c.isEmpty()) {
return false;
}
for (E e : c) {
add(e);
}
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment