Is There a Fixed Sized Queue Which Removes Excessive Elements

Is there a fixed sized queue which removes excessive elements?

There is no existing implementation in the Java Language and Runtime. All Queues extend AbstractQueue, and its doc clearly states that adding an element to a full queue always ends with an exception. It would be best ( and quite simple ) to wrap a Queue into a class of your own for having the functionality you need.

Once again, because all queues are children of AbstractQueue, simply use that as your internal data type and you should have a flexible implementation running in virtually no time :-)

UPDATE:

As outlined below, there are two open implementations available (this answer is quite old, folks!), see this answer for details.

Is there a fixed size Deque which removes old elements in Java?

I can use something like this (need also rewrite other insert methods like push, pushLast...) but would like to hear other available solutions (if they exist).

public class ConcurrentFixedSizeLinkedDeque<T> extends ConcurrentLinkedDeque<T> {

    private int sizeLimit = Integer.MAX_VALUE;

    public ConcurrentFixedSizeLinkedDeque() {
    }

    public ConcurrentFixedSizeLinkedDeque(Collection<? extends T> c) {
        super(c);
    }

    public ConcurrentFixedSizeLinkedDeque(int sizeLimit) {
        if(sizeLimit<0) sizeLimit=0;
        this.sizeLimit = sizeLimit;
    }

    public ConcurrentFixedSizeLinkedDeque(Collection<? extends T> c, int sizeLimit) {
        super(c);
        if(sizeLimit<0) sizeLimit=0;
        this.sizeLimit = sizeLimit;
    }

    public int getSizeLimit() {
        return sizeLimit;
    }

    public void setSizeLimit(int sizeLimit) {
        this.sizeLimit = sizeLimit;
    }

    @Override
    public void addFirst(T e){
        while(size()>=this.sizeLimit){
            pollLast();
        }
        super.addFirst(e);
    }

    @Override
    public void addLast(T e){
        while(size()>=this.sizeLimit){
            pollFirst();
        }
        super.addLast(e);
    }
}

Fixed-length Queue which removes first element when an element is appended at end (FIFO)

Answering my own question:

I have tried using collections.deque() and queue.Queue(), and deque is such an implementation

d = deque(maxlen=5)
d.extend([1,2,3,4,5])
print(d)
# deque([1, 2, 3, 4, 5], maxlen=5)
d.append(10)
print(d)
# deque([2, 3, 4, 5, 10], maxlen=5)

Size-limited queue that holds last N elements in Java

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.

Fixed size queue which automatically dequeues old values upon new enques

I would write a wrapper class that on Enqueue would check the Count and then Dequeue when the count exceeds the limit.

 public class FixedSizedQueue<T>
 {
     ConcurrentQueue<T> q = new ConcurrentQueue<T>();
     private object lockObject = new object();

     public int Limit { get; set; }
     public void Enqueue(T obj)
     {
        q.Enqueue(obj);
        lock (lockObject)
        {
           T overflow;
           while (q.Count > Limit && q.TryDequeue(out overflow)) ;
        }
     }
 }

Is there a Java collection which removes items as more items are added? (a simple cache)

Apache Commons – CircularFifoQueue

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

I guess this is the behavior what you are looking for. Its from the Apache commons collections (link)

Fixed Size Persisted to Disk Queue using queuelib

So after looking through the source code of queuelib it appears that what queuelib actually does when you add and remove records from the persistent disk storage, what it is actually doing is keeping track of an internal offset and adding or subtracting from it while the Queue remains open.

This means that every record that you add to the queue is written to the file and remains written to the file until the queue is closed at which point it discards any data that you previously popped from the data structure.

So one possible solution would be to close and then reopen the queue once in a while.

For example,

from queuelib import FifoDiskQueue
import numpy as np

path = "C:\\temp"
data = FifoDiskQueue(path)

counter = 0
while True:
    frame = np.random.rand(2,3).tobytes()
    data.push(frame)
    if len(data) >= 10:
        data.pop()
    counter += 1
    if counter % 1000 == 0:
        data.close()
        data = FifoDiskQueue(path)

---

Update

There is also the chunksize argument that could be lowered which essentially would do the same thing as the previous solution when set to a low number. The default is 100,000. Setting this to a lower value is the better solution. The chunksize is a reference to the number of records kept in the storage before it closes the file internally, so a lower number limits the maximum size a file can get before it is closed and popped data is discarded.

For example:

from queuelib import FifoDiskQueue
import numpy as np

path = "C:\\temp"
data = FifoDiskQueue(path, chunksize=1000)
while True:
    frame = np.random.rand(2,3).tobytes()
    data.push(frame)
    if len(data) >= 10:
        data.pop()

FIFO queue in JDK

If you see the ArrayBlockingQueue's offer implementation, it has a line, so value 3 is not even appended to the items array.

if (count == items.length)
  return false;

So you can do this:

static void append(Queue<Integer> fifo, int i) {
  if (!fifo.offer(i)) {
      fifo.poll();
      fifo.offer(i);
  }
}

// in main:
Queue<Integer> fifo3 = new ArrayBlockingQueue<>(2);
append(fifo3, 1);
append(fifo3, 2);
append(fifo3, 3);
System.out.println(fifo3); // prints [2, 3]

---

Related Topics