I'm implementing a sliding window over a stream of events, in Java.
So I want a data structure which allows me to do the following:
add to the end of the data structure when new events occur;
remove from the start of the data structure when old events are processed;
get standard random access (
get(i)) to the elements of the data structure; in general, typical List "read" operations;
is efficient for all of the above operations;
No other access is required. And no thread safety is required.
I'm currently doing this with an ArrayList, to get things up and running. But I want something more efficient; the
remove(0) method (2. above) is inefficient with an
Numbers 1. and 2. are standard Queue-style operations. However, the implementations of
Queue in the JDK (such as ArrayDeque) don't allow for
get(i) in 3.
So, I'm wondering if there are any libraries out there which have such an implementation, and are suitable for commercial use.
If not, I guess I'll resort to writing my own…
Seems like a task for a Circular Buffer - as long as it's okay if the queue has a fixed capacity. I don't know of any standard implementation though. But here is a nice recipe to roll your own.