Java.util.Queue, which provides equal elements no more than once

Question

I am looking for an implementation of java.util.Queue that puts equal elements no more than once.

For example, such a specialQueue should behave like this:

 E e1; E e2; E e3; //... assertThat( e1, is(e2) ); assertThat( e1, is(not(e3)) ); Queue<E> specialQueue; //... specialQueue.offer(e1); specialQueue.offer(e2); specialQueue.offer(e3); assertThat( specialQueue.poll(), is(e1) ); assertThat( specialQueue.poll(), is(e3) ); assertThat( specialQueue.poll(), is(null) ); // FIFO semantics are not relevant to the question specialQueue.offer(e3) assertThat( specialQueue.poll(), is(null) ); 

I came up with an implementation that manages the internal Set<E> alreadySeenElements , and protects against adding items to the delegate queue by checking this set. I was wondering if there is already a "time-tested" implementation.

Answer 1

Like commentators, you are more describing a particular type of Set than Queue . As far as I understand, your requirements are:

• Iteration of insertion order
• Each item in the collection is unique (not equal)
• Previously seen items can never be added again.

The first two requirements are well served by LinkedHashSet , for example this question . The latter requirement is much stranger and requires some internal storage of previously seen values. Sort of:

 public class SeenOnceLinkedHashSet<E> implements Set<E> { private LinkedHashSet<E> data; private HashSet<E> seen; public boolean add(E e) { boolean newValue = seen.add(e); if (newValue) { return data.add(e); } // and so on in other methods } 

Note that this class has unlimited internal memory. You could easily cause a memory shortage problem using this class, as it would handle another Set without any problems. If you need the concept of "ever added," this is inevitable. You could use something more elegant like BloomFilter , but that would create false positives.

Personally, I am reviewing your requirements. Any data structure of unlimited space is almost certainly a code smell. Can you, for example, use a wrapper class that provides a more useful definition of .equals() ? Or add additional security checks when building an object, so bad objects are not built in the first place?