A queue that ensures the uniqueness of elements?

Question

I am looking for an implementation of java.util.Queue or something in the Google collection that behaves like a queue, but also ensures that each element of the queue is unique. (all subsequent insertion will have no effect)

Is this possible, or will I have to do it manually?

Now I use the queue with the implementation of LinkedList, and I check the uniqueness before inserting. (I use the side map for this, add / remove an element from the side map before / after queu). I don’t really like it.

Any input is welcome. If it's not in the java.util package, maybe this is a bad idea?

Answer 1

How about a LinkedHashSet ? Its iterator preserves the insertion order, but since it is a Set , its elements are unique.

As the documentation says,

Note that the insertion order does not change if an item is reinserted into the set.

To effectively remove items from the header of this queue, go through its iterator:

 Iterator<?> i = queue.iterator(); ... Object next = i.next(); i.remove(); 

Answer 2

This does not exist, as far as I know, but it would be quite simple to implement using LinkedList in combination with Set :

 /** * Thread unsafe implementation of UniqueQueue. */ public class UniqueQueue<T> implements Queue<T> { private final Queue<T> queue = new LinkedList<T>(); private final Set<T> set = new HashSet<T>(); public boolean add(T t) { // Only add element to queue if the set does not contain the specified element. if (set.add(t)) { queue.add(t); } return true; // Must always return true as per API def. } public T remove() throws NoSuchElementException { T ret = queue.remove(); set.remove(ret); return ret; } // TODO: Implement other Queue methods. } 

Answer 3

I will be tempted to maintain a HashSet containing a key that uniquely identifies the items in the queue side by side with this. Then just check the HashSet to see if the item is in the queue before adding it. When you remove an item from the queue, simply remove it from the HashSet.

Answer 4

Checking the uniqueness of a course has a cost (either in space or in time). It seems like it would be interesting to work with something like PriorityQueue, which would support a bunch sorted by element comparator. You may be able to use this more effectively (O (log n)) to check for existence without saving the side map.

If you want to wrap a queue with a uniqueness check, I highly recommend using the Google ForwardingQueue collection to create such a thing.

Answer 5

Just to answer Adamsky:

 /** * A queue that keeps each element only once. * If you try to add an element that already exists - nothing will happen. * * @author Adamski http://stackoverflow.com/a/2319156/827927 * @NotThreadSafe */ public class UniqueQueue<T> implements Queue<T> { private final Queue<T> queue = new LinkedList<T>(); private final Set<T> set = new HashSet<T>(); @Override public boolean add(T t) { // Only add element to queue if the set does not contain the specified element. if (set.add(t)) queue.add(t); return true; // Must always return true as per API def. } @Override public boolean addAll(Collection<? extends T> arg0) { boolean ret = false; for (T t: arg0) if (set.add(t)) { queue.add(t); ret = true; } return ret; } @Override public T remove() throws NoSuchElementException { T ret = queue.remove(); set.remove(ret); return ret; } @Override public boolean remove(Object arg0) { boolean ret = queue.remove(arg0); set.remove(arg0); return ret; } @Override public boolean removeAll(Collection<?> arg0) { boolean ret = queue.removeAll(arg0); set.removeAll(arg0); return ret; } @Override public void clear() { set.clear(); queue.clear(); } @Override public boolean contains(Object arg0) { return set.contains(arg0); } @Override public boolean containsAll(Collection<?> arg0) { return set.containsAll(arg0); } @Override public boolean isEmpty() { return set.isEmpty(); } @Override public Iterator<T> iterator() { return queue.iterator(); } @Override public boolean retainAll(Collection<?> arg0) { throw new UnsupportedOperationException(); } @Override public int size() { return queue.size(); } @Override public Object[] toArray() { return queue.toArray(); } @Override public <T> T[] toArray(T[] arg0) { return queue.toArray(arg0); } @Override public T element() { return queue.element(); } @Override public boolean offer(T e) { return queue.offer(e); } @Override public T peek() { return queue.peek(); } @Override public T poll() { return queue.poll(); } } 

Answer 6

This is a very good question. There is no direct solution. I will dig out the code that I wrote some time ago that tried to do this, and go back and edit this answer.

EDIT: I'm back. Truly, if you do not need concurrency, you better maintain the queue and install separately. For what I was doing, concurrency was the goal, but I could come up with a better solution, given that the restriction was problematic; basically, since he used ConcurrentHashMap, the more you removed the head element from the queue (the main task associated with the queue), the more unbalanced the hash table became over time. I can still share this code with you, but I doubt that you really want it.

EDIT: For the case where concurrency is required, I gave the following answer: Concurrent queue setting

Answer 7

Unfortunately, this does not exist. Since I need such a queue, I developed a blocking queue supported by a collection created using java.util.concurrent.LinkedBlockingQueue.

You can find it here:

https://github.com/bvanalderweireldt/concurrent-unique-queue

Example:

 final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1); queue.offer(new Integer(1)); //True queue.offer(new Integer(1)); //False 

You can use it with Maven:

 <dependency> <groupId>com.hybhub</groupId> <artifactId>concurrent-util</artifactId> <version>0.1</version> </dependency> 

Answer 8

I was a bit late with the answer, but in the end I solved a similar problem with ArrayDeque and redefined the add method I needed.

  Deque<Long> myQueue = new ArrayDeque<Long>() { @Override public boolean add(Long e) { return !this.contains(e) && super.add(e);} }; 

Answer 9

Treeset This is a sorted set, and Set means "no duplicate elements."