Java - Ring Buffer

Question

I have a streaming time series, of which I am interested in keeping the last 4 elements, which means I want to be able to pop the first, and add to the end. Which Java Collection is the best for this? Vector ?

Answer 1

Consider CircularFifoBuffer from Apache Common.Collections. Unlike Queue you don't have to maintain the limited size of underlying collection and wrap it once you hit the limit.

Buffer buf = new CircularFifoBuffer(4);
buf.add("A");
buf.add("B");
buf.add("C");
buf.add("D"); //ABCD
buf.add("E"); //BCDE

CircularFifoBuffer will do this for you because of the following properties:

• CircularFifoBuffer is a first in first out buffer with a fixed size that replaces its oldest element if full.
• The removal order of a CircularFifoBuffer is based on the insertion order; elements are removed in the same order in which they were added. The iteration order is the same as the removal order.
• The add(Object), BoundedFifoBuffer.remove() and BoundedFifoBuffer.get() operations all perform in constant time. All other operations perform in linear time or worse.

However you should consider it's limitations as well - for example, you can't add missing timeseries to this collection becaue it doens't allow nulls.

Answer 2

If you need

• O(1) insertion and removal
• O(1) indexing to interior elements
• access from a single thread only
• generic element type

then you can use this CircularArrayList for Java in this way (for example):

CircularArrayList<String> buf = new CircularArrayList<String>(4);

buf.add("A");
buf.add("B");
buf.add("C");
buf.add("D"); // ABCD

String pop = buf.remove(0); // A <- BCD
buf.add("E"); // BCDE

String interiorElement = buf.get(i);

All these methods run in O(1).

Answer 3

None of the previously given examples were meeting my needs completely, so I wrote my own queue that allows following functionality: iteration, index access, indexOf, lastIndexOf, get first, get last, offer, remaining capacity, expand capacity, dequeue last, dequeue first, enqueue / add element, dequeue / remove element, subQueueCopy, subArrayCopy, toArray, snapshot, basics like size, remove or contains.

EjectingQueue

EjectingIntQueue

Answer 4

Since Guava 15.0 (released September 2013) there's EvictingQueue:

A non-blocking queue which automatically evicts elements from the head of the queue when attempting to add new elements onto the queue 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 is different from conventional bounded queues, which either block or reject new elements when full.

This class is not thread-safe, and does not accept null elements.

Example use:

EvictingQueue<String> queue = EvictingQueue.create(2);
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.print(queue); //outputs [c, d]

Answer 5

Since Java 1.6, there is ArrayDeque, which implements Queue and seems to be faster and more memory efficient than a LinkedList and doesn't have the thread synchronization overhead of the ArrayBlockingQueue: from the API docs: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."

final Queue<Object> q = new ArrayDeque<Object>();
q.add(new Object()); //insert element
q.poll(); //remove element

Answer 6

Use a Queue

Queue<String> qe=new LinkedList<String>();

qe.add("a");
qe.add("b");
qe.add("c");
qe.add("d");

System.out.println(qe.poll()); //returns a
System.out.println(qe.poll()); //returns b
System.out.println(qe.poll()); //returns c
System.out.println(qe.poll()); //returns d

There's five simple methods of a Queue

• element() -- Retrieves, but does not remove, the head of this queue.

• offer(E o) -- Inserts the specified element into this queue, if
  possible.

• peek() -- Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.

• poll() -- Retrieves and removes the head of this queue, or null if this queue is empty.

• remove() -- Retrieves and removes the head of this queue.