Last active
September 21, 2019 23:13
-
-
Save shathor/44de9daa5807aa05dfc1 to your computer and use it in GitHub Desktop.
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).
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.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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment