Size-limited queue that holds last N elements in Java

Question

A very simple & quick question on Java libraries: is there a ready-made class that implements a Queue with a fixed maximum size - i.e. it always allows addition of elements, but it will silently remove head elements to accomodate space for newly added elements.

Of course, it's trivial to implement it manually:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

As far as I see, there's no standard implementation in Java stdlibs, but may be there's one in Apache Commons or something like that?

Solution 1

Apache commons collections 4 has a CircularFifoQueue<> which is what you are looking for. Quoting the javadoc:

CircularFifoQueue is a first-in first-out queue with a fixed size that replaces its oldest element if full.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

If you are using an older version of the Apache commons collections (3.x), you can use the CircularFifoBuffer which is basically the same thing without generics.

Update: updated answer following release of commons collections version 4 that supports generics.

Solution 2

Guava now has an 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.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]

Solution 3

I like @FractalizeR solution. But I would in addition keep and return the value from super.add(o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

Solution 4

Use composition not extends (yes I mean extends, as in a reference to the extends keyword in java and yes this is inheritance). Composition is superier because it completely shields your implementation, allowing you to change the implementation without impacting the users of your class.

I recommend trying something like this (I'm typing directly into this window, so buyer beware of syntax errors):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

A better option (based on the answer by Asaf) might be to wrap the Apache Collections CircularFifoBuffer with a generic class. For example:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

Solution 5

The only thing I know that has limited space is the BlockingQueue interface (which is e.g. implemented by the ArrayBlockingQueue class) - but they do not remove the first element if filled, but instead block the put operation until space is free (removed by other thread).

To my knowledge your trivial implementation is the easiest way to get such an behaviour.

View more solutions

Comments

[andersoj]

Related stackoverflow.com/questions/590069/…

[Nicolas Bousquet]

Personnaly I would not introduce another library if this would the only use of this library...

[Renaud]

@Override public boolean add(PropagationTask t) { boolean added = super.add(t); while (added && size() > limit) { super.remove(); } return added; }

[Aliaksandr Arashkevich]

Be careful using the above code! We are getting java.util.NoSuchElementException when using this in multiple threads!

[Diego]

Warning: the code in question, although it apparently works, it could backfire. There are additional methods that can add more elements to the queue (such as addAll()) that ignore this size check. For more details see Effective Java 2nd Edition - Item 16: Favor composition over inheritance

[toongeorges]

you could also take a look at docs.oracle.com/en/java/javase/11/docs/api/java.base/java/ut‌​il/…

[GreyCat]

I've already browsed through Java stdlib classes, and, sadly, BlockingQueue is not an answer. I've thought of other common libraries, such as Apache Commons, Eclipse's libraries, Spring's, Google's additions, etc?

[kdgregory]

Do you understand what a priority queue is, and how it differs from the OP's example?

[moritz]

Sure, i just say u can use the MinMaxPriorityQueue, u must not care about the Priority part since there is no MinMaxQueue in the guava libs.

[Mark Peters]

@kdgregory: It can be used with some extra work. Just keep an long cursor = Long.MAX_VALUE, use it as the priority value and decrement it each time you add to the queue. In practice that will almost certainly be sufficient.

[kdgregory]

@Mark Peters - I just don't know what to say. Sure, you can make a priority queue behave like a fifo queue. You could also make a Map behave like a List. But both ideas show a complete incomprehension of algorithms and software design.

[Mark Peters]

@kdgregory: The question wasn't about a good way to implement a circular buffer, the question was about how close the common Java collections libraries could get to providing a circular buffer. This gets pretty close. I agree that it isn't a nice solution.

[jtahlborn]

@Mark Peters - isn't every question on SO about a good way to do something?

[Mark Peters]

@jtahlborn: Clearly not (code golf), but even if they were, good is not a black and white criterion. For a certain project, good might mean "most efficient", for another it might mean "easiest to maintain" and for yet another, it might mean "least amount of code with existing libraries". All that is irrelevant since I never said this was a good answer. I just said it can be a solution without too much effort. Turning a MinMaxPriorityQueue into what the OP wants is more trivial than modifying a LinkedList (the OP's code doesn't even come close).

[kdgregory]

@Mark - how does the OP's code not even come close? And I'll ask you the same question that I asked this poster: do you understand how a priority queue differs from a fifo queue? Or to be more blunt: do you understand that modifying a priority queue gives you O(logN) performance versus O(1)?

[kdgregory]

+1 if you explain why composition is a better choice (other than "prefer composition over inheritance) ... and there is a very good reason

[Mark Peters]

@kdgregory: I understand perfectly well, thank you. And as I've said multiple times, I don't think this is a good solution, just that it has the potential to be a solution. The OP's code doesn't come close because there are still about a dozen ways to circumvent the maximum size invariant. Anyway wasn't trying to kick off a huge debate here or to argue that it's a good answer, just that there is a way to turn this data type into a fifo queue.

[Mark Peters]

Maybe you guys are examining my choice of words "in practice that will almost certainly be sufficient". I didn't mean that this solution would almost certainly be sufficient for the OP's problem or in general. I was referring to the choice of a descending long as a cursor type within my own suggestion, saying that it would be sufficiently wide in practice even though theoretically you could add more than 2^64 objects to this queue at which point the solution would break down.

[GreyCat]

Composition is a poor choice for my task here: it means at least twice the number of objects => at least twice more often garbage collection. I use large quantities (tens of millions) of these limited-size queues, like that: Map<Long, LimitedSizeQueue<String>>.

[kdgregory]

@GreyCat - I take it you haven't looked at how LinkedList is implemented, then. The extra object created as a wrapper around the list will be pretty minor, even with "tens of millions" of instances.

[kdgregory]

I was going for "reduces the size of the interface," but "shields the implementation" is pretty much the same thing. Either answers Mark Peter's complaints about the OP's approach.

[GreyCat]

I don't really understand how to adapt LRUMap to act as a queue and I guess it would be rather hard to use even if it's possible.

[GreyCat]

As far as I can see, FractalizeR hasn't provided any solution, only edited the question. "Solution" within the question is not a solution, because the question was about using some class in standard or semi-standard library, not rolling your own.

[Tom Carchrae]

Here is the source: code.google.com/p/guava-libraries/source/browse/guava/src/co‌​m/… - it looks like it would be easy to copy and compile with current releases of Guava

[GreyCat]

The question was about classes in popular collection class libraries, not rolling one's own - minimalistic homebrew "solution" was already provided in question.

[user590444]

that does not matter google find this page also on another queries =)

[Basil Bourque]

See this other answer for link to EvictingQueue added to Google Guava version 15 around 2013-10.

[Basil Bourque]

Update: This class was officially released with Google Guava in version 15, around 2013-10.

[kostmo]

@MaciejMiklas The question asks for a FIFO, EvictingQueue is a FIFO. In case there is any doubt, try this program: Queue<Integer> fifo = EvictingQueue.create(2); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println(fifo); Observe the result: [2, 3]

[Konrad Morawski]

It should be pointed out that this solution is not thread-safe

[Renaud]

@KonradMorawski the whole LinkedList class is not thread-safe anyway, so your comment is pointless in this context!

[Konrad Morawski]

@RenaudBlue thread safety is a valid concern (if often overlooked), so I don't think the comment is pointless. and reminding that LinkedList isn't thread safe wouldn't be pointless either. in the context of this question, OP's specific requirement makes it particularly important that adding an item is performed as an atomic operation. in other words, the risk of not ensuring atomicity would be greater than in case of a regular LinkedList.

[Michael Böckling]

This is now the correct answer. Its a bit unclear from the documentation, but EvictingQueue is a FIFO.

[ed22]

Is there any callback called when element is evicted from the queue?

[ed22]

Is there any callback called when element is evicted from the queue due to addition to full queue?

[lmo]

This answer turned up in the low quality review queue, presumably because you don't provide any explanation of the code. If this code answers the question, consider adding adding some text explaining the code in your answer. This way, you are far more likely to get more upvotes — and help the questioner learn something new.

[simpleuser]

a "Circular Queue" is merely one implementation which satisfies the question. But the question does not directly benefit from a circular queue's main differences, i.e. not having to free/reallocate each bucket at each addition/deletion.

[Holger]

Breaks as soon as someone calls add(int,E) instead. And whether addAll works as intended, depends on unspecified implementation details. That’s why you should prefer delegation over inheritance…

[Swapnil]

@Asaf Is there any similar in STL or Booost?

[Asaf]

@Swapnil take a look here: boost.org/doc/libs/1_67_0/doc/html/circular_buffer.html

[Vsevolod Golovanov]

It's also still officially marked as @Beta, as is Guava's tradition.

[kai]

here's the maven dependency: mvnrepository.com/artifact/org.apache.commons/…