Is there a Guava equivalent to Apache Commons CircularFifoBuffer?

Question

I need a data structure that can efficiently buffer a specific number of elements, in FIFO order.

As mentioned in this question, Apache Commons has a CircularFifoBuffer, but it is sadly not generified. Some forks exist, but I'm not sure of their maintenance status.

Since Guava is the go-to library for my collection needs, I'm wondering: is there a good alternative in Guava? If not, should I implement it in my project, based on Apache Commons' CircularFifoBuffer?

What do you need from the "circular" part? An "infinite" iteration? — fge, Jan 09 '13 at 10:03
The "circular" part refers to the common implementation, which is an array with two indexes to the start and end of the buffer. When the array is full, the data structure starts writing again at the beginning of the array, overwriting the oldest elements, in a "circular" manner. The cool thing with this implementation, is that you don't need to create unnecessary entries like in a LinkedList, which reduces garbage collection. Since I don't need to remove elements in the middle of the buffer, this seems like a perfect fit. — Etienne Neveu, Jan 09 '13 at 10:06
Yeah, sorry, I only went and read the javadoc after I posted the first comment ;) Looks like Guava has no "limited size collections", so you are probably condemned to implementing this by yourself :/ — fge, Jan 09 '13 at 10:08
Is it a required feature that, when full, the oldest entry is overwritten? If so I'll remove my answer, as `ArrayBlockingQueue` will block when full. — SimonC, Jan 09 '13 at 10:35
Well, I have two use cases. 1) I want to keep around a rolling buffer of the last N events processed by our application, and log these events when an exception is thrown. Ideally, the buffer should automatically overwrite the oldest event, instead of doing it manually. 2) I have a transformation that buffers the last 10 events. When the buffer is full, I want to process the oldest event and remove it from the buffer. So the removal is manual in this case. — Etienne Neveu, Jan 09 '13 at 12:38

score 31 · Accepted Answer · edited Nov 01 '16 at 05:32

31

Starting Guava 15.0 - you can use EvictingQueue

edited Nov 01 '16 at 05:32

chad luo

109
10

answered May 06 '13 at 07:41

MosheElisha

1,930
2
22
27

score 7 · Answer 2 · edited Mar 21 '18 at 10:55

7

I don't see anything like that in Guava, but how about a ForwardingQueue built around an ArrayDeque where you check the capacity on add(), offer(), etc. and remove() old entries if it's already full?

edited Mar 21 '18 at 10:55

Iulian Popescu

2,595
4
23
31

answered Jan 09 '13 at 10:28

Frank Pavageau

11,477
1
43
53

1

I really like this solution, because the behavior of `ArrayDeque` is actually very close to that of the `CircularFifoBuffer`, once you decorate it to remove the oldest element when full. The class has no locking / synchronization, which is good, since I don't care about thread safety. The only disadvantage I can see is that the underlying array might be bigger than needed, since its size must be a power of 2. But that's premature optimization :) – Etienne Neveu Jan 09 '13 at 12:19

Grzegorz Rożniecki · Answer 3 · 2013-01-09T12:19:48.810

Commons-Collections with Generics (maven link) is the way to go if you want to use Apache Collections with generics (and it contains working CircularFifoBuffer<E> class).

On the other hand, as @FrankPavageau says, you can use your own ForwardingQueue implementatation. A naive approach (with place for further optimizations) would be something like this:

static class BoundedQueue<E> extends ForwardingQueue<E> {

  private final Queue<E> delegate;
  private final int capacity;

  public BoundedQueue(final int capacity) {
    this.delegate = 
        new ArrayDeque<E>(capacity); // specifying initial capacity is optional
    this.capacity = capacity;
  }

  @Override
  protected Queue<E> delegate() {
    return delegate;
  }

  @Override
  public boolean add(final E element) {
    if (size() >= capacity) {
      delegate.poll();
    }
    return delegate.add(element);
  }

  @Override
  public boolean addAll(final Collection<? extends E> collection) {
    return standardAddAll(collection);
  }

  @Override
  public boolean offer(final E o) {
    return standardOffer(o);
  }

}

Usage:

final BoundedQueue<Integer> boundedQueue = new BoundedQueue<Integer>(3);
boundedQueue.add(1);
System.out.println(boundedQueue); // [1]
boundedQueue.add(2);
System.out.println(boundedQueue); // [1, 2]
boundedQueue.add(3);
System.out.println(boundedQueue); // [1, 2, 3]
boundedQueue.add(4);
System.out.println(boundedQueue); // [2, 3, 4]
boundedQueue.addAll(Arrays.asList(5, 6, 7, 8));
System.out.println(boundedQueue); // [6, 7, 8]
((Queue<Integer>) boundedQueue).offer(9);
System.out.println(boundedQueue); // [7, 8, 9]

Yep. I'm going to use the `CircularFifoBuffer` to solve my current problem. I changed my dependency from `commons-collections:commons-collections:3.2` to `net.sourceforge.collections:collections-generic:4.01`, after some searching around (there is not much documentation). I hope the "official" generified version of commons-collections will be released soon, though. Barring that, it would be awesome if such a data structure could be added to Guava. — Etienne Neveu, Jan 09 '13 at 12:25
Similar feature request is submitted [as issue #336](https://code.google.com/p/guava-libraries/issues/detail?id=336). Star and/or comment to see if it's going to be implemented. — Grzegorz Rożniecki, Jan 09 '13 at 12:28
Guava just open sourced "EvictingQueue": https://code.google.com/p/guava-libraries/source/detail?r=4c376a212781ad5f8afe1e901e3668f7db50b395 Seems like what I needed :) — Etienne Neveu, Feb 12 '13 at 08:33
Nice, but won't be there until 15.0... Plus, they came up with better name than mine ;) — Grzegorz Rożniecki, Feb 12 '13 at 10:32

score -2 · Answer 4 · answered Jan 09 '13 at 10:32

-2

Java's ArrayBlockingQueue offers a fixed sized circular buffer.

answered Jan 09 '13 at 10:32

SimonC

6,590
1
23
40

enevu mentions in a comment that "when the array is full, the data structure starts writing again at the beginning of the array, overwriting the oldest elements". That's not what `ArrayBlockingQueue` does. However, it shouldn't be too hard to modify it. – Tom Anderson Jan 09 '13 at 10:46
ArrayBlockingQueue is pretty close to what I want, but I don't need the synchronization. I think I prefer ArrayDeque. But it's definitely a good choice in a concurrent environment. The fact that it blocks when full is not that problematic, since it's actually pretty easy to decorate it to remove the oldest elements when full. – Etienne Neveu Jan 09 '13 at 12:27
2

This answer is **incorrect**. When adding an item beyond the limit, `ArrayBlockingQueue` blocks (thus the name) whereas `CircularFifoQueue` drops the oldest item. To quote the [ArrayBlockingQueue doc](http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ArrayBlockingQueue.html): `Attempts to put an element into a full queue will result in the operation blocking` – Basil Bourque Feb 11 '14 at 10:01
@BasilBourque, how is this answer incorrect? The question was "is there a good alternative in Guava?", not "is there an alternative that is functionally identical in every single way". Also, the OP states directly above your comment "The fact that it blocks when full is not that problematic". Please read the other comments before posting. – SimonC Feb 11 '14 at 14:44

Is there a Guava equivalent to Apache Commons CircularFifoBuffer?

4 Answers4