Bounded, auto-discarding, non-blocking, concurrent collection

Question

I'm looking for a collection that:

• is a Deque/List - i.e. supports inserting elements at "the top" (newest items go to the top) - deque.addFirst(..) / list.add(0, ..). It could be a Queue, but the iteration order should be reverse - i.e. the most recently added items should come first.
• is bounded - i.e. has a limit of 20 items
• auto-discards the oldest items (those "at the bottom", added first) when the capacity is reached
• non-blocking - if the deque is empty, retrievals should not block. It should also not block / return false / null / throw exception is the deque is full.
• concurrent - multiple threads should be able to operate on it

I can take LinkedBlockingDeque and wrap it into my custom collection that, on add operations checks the size and discards the last item(s). Is there a better option?

Answer 1

I believe what you're looking for is a bounded stack. There isn't a core library class that does this, so I think the best way of doing this is to take a non-synchronized stack (LinkedList) and wrap it in a synchronized collection that does the auto-discard and returning null on empty pop. Something like this:

import java.util.Iterator;
import java.util.LinkedList;

public class BoundedStack<T> implements Iterable<T> {
    private final LinkedList<T> ll = new LinkedList<T>();
    private final int bound;

    public BoundedStack(int bound) {
        this.bound = bound;
    }

    public synchronized void push(T item) {
        ll.push(item);
        if (ll.size() > bound) {
            ll.remove(ll.size() - 1);
        }
    }

    public synchronized T pop() {
        return ll.isEmpty() ? null : ll.pop();
    }

    public synchronized Iterator<T> iterator() {
        return ll.iterator();
    }
}

...adding methods like isEmpty as required, if you want it to implement eg List.

Answer 2

I made this simple imeplementation:

public class AutoDiscardingDeque<E> extends LinkedBlockingDeque<E> {

    public AutoDiscardingDeque() {
        super();
    }

    public AutoDiscardingDeque(int capacity) {
        super(capacity);
    }

    @Override
    public synchronized boolean offerFirst(E e) {
        if (remainingCapacity() == 0) {
            removeLast();
        }
        super.offerFirst(e);
        return true;
    }
}

For my needs this suffices, but it should be well-documented methods different than addFirst / offerFirst are still following the semantics of a blocking deque.