Last active
October 14, 2021 19:26
-
-
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).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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