A Queue that ensure uniqueness of the elements?

Question

I'm looking for a implementation of java.util.Queue or something in the Google collection who behave like a Queue, but also ensure that each element of the queue is unique. (all further insertion will have no effect)

It's that possible, or will I have to do it by hand?

For now I'm using a Queue, with a LinkedList implementation, and I check the uniqueness before insertion. ( I use a side Map for doing this, add / remove element from the side map before / after the queu ). I don't like it too much.

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

Solution 1

How about a LinkedHashSet? Its iterator preserves insertion order, but because it's a Set, its elements are unique.

As its documentation says,

Note that insertion order is not affected if an element is re-inserted into the set.

In order to efficiently remove elements from the head of this "queue", go through its iterator:

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

Solution 2

This doesn't exist as far as I know but would be fairly simple to implement using a LinkedList in conjunction with a 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.
}

Solution 3

I'd be tempted to maintain a HashSet containing a key that uniquely identifies the items in the queue side-by-side with it. 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 the key from the HashSet as well.

Solution 4

Just to complete Adamski's answer:

/**
 * 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();
}
}

Solution 5

Checking uniqueness of course has a cost (either in space or time). Seems like it might be interesting to work from something like a PriorityQueue which will maintain a heap sorted by Comparator of the elements. You might be able to leverage that to more efficiently (O(log n)) check existence without maintaining a side map.

If you do want to wrap a Queue with a uniqueness checker, I would strongly recommend using the Google Collections ForwardingQueue to build such a thing.

View more solutions

Comments

[Adamski]

The problem is it doesn't implement Queue and hence there's no way to remove elements in FIFO order.

[brady]

@Adamski - removing elements in FIFO order is simple. See my update.

[Cshah]

Although this works, there is a huge performance cosr to it. I dont think you need both a set and a linkedlist

[Antoine Claval]

that's what tvanfosson is proposing as well, and very close of what i already have. I'm just curious about a more standard way.

[Brandon DuRette]

Easy enough to augment LinkedHashSet to add push and pop. Not efficient, but naive pop could be: Iterator<T> it = iterator(); T result = it.next(); it.remove(); return result;

[Adamski]

@Cshah: Why do you think there's a huge cost performance? Assuming your hash algorithm is fast and efficient, set insert and removal operations will approximate to O(1), which is much faster than scanning the LinkedList each time: O(n).

[Antoine Claval]

Nice. Sorry, i miss the LinkedHashSet while scanning the collection. What do you think of implementing java.util.Queue with a home made class, and with a backend LinkedHashSet ?

[Adamski]

... although creating an iterator for each removal operation seems pretty ugly.

[Cshah]

@adamki: The approach by tvanfosson is much cleaner. In your case, each element is added to both the queue(linked list) and the set (to ensure uniqueness). I believe that just a hashset should suffice

[brady]

It depends on how you want to use the queue. If you are going to add a bunch of objects and then remove a bunch of objects---probably within a single thread---using the Iterator is perfectly natural, and I'd probably just reference it as a Collection. If you really need a BlockingQueue to communicate between threads, this isn't the right approach.

[Adamski]

@Cshah: What are you talking about?! tvanfosson's approach is the same as mine - He just hasn't provided example code. Also, erickson's approach of using a LinkedHashSet is essentially the same, as internally LinkedHashSet contains a linked list. Using "just a hashset" will not provide queue-like behaviour.

[Dean J]

Why not just use java.util.TreeSet?

[Adamski]

A TreeSet does not support FIFO access: Elements will be inserted according to their natural ordering (or the ordering of the supplied Comparator) rather thn at the end of the "queue". Granted you could provide a Comparator to mimic FIFO-like behavior but this is an ugly hack IMHO that offers no real benefit.

[Nitsan Wakart]

If you replace the LinkedList with ArrayDeque you will get better performance (x2) for polling than the LinkedHashSet. Here's a blog post comparing the implementations: psy-lob-saw.blogspot.com/2013/03/…

[Nitsan Wakart]

If you replace the LinkedList with ArrayDeque you will get better performance (x2) for polling than the LinkedHashSet, and should beat your implementation as well. Here's a blog post comparing the implementations: psy-lob-saw.blogspot.com/2013/03/…

[Theodore Murdock]

It also depends on whether you're going to add to the end of the queue while processing an element. Adding to a Queue during processing of elements removed from that Queue is well-defined behavior, but with an Iterator, you'll get a ConcurrentModificationException because the built-in Java Collections assume it's a threading issue, not someone abusing the Collection and its Iterator as if the two combined were a Queue implementation.

[toniedzwiedz]

About the return true in add. Isn't there a conflict between the contract of Collection#add and Queue#add? This collection is supposed to guarantee the uniqueness so it should return false according to the Collection javadoc. At the same time, the Queue javadoc explicitly mentions the method as returning true or throwing an exception. docs.oracle.com/javase/7/docs/api/java/util/Queue.html#add(E‌​) docs.oracle.com/javase/7/docs/api/java/util/… Not sure which of these two contracts should be followed in this case.

[Adamski]

@toniedzwiedz: +1 That's a really good point. My first thought was that given the class implements Queue (and only uses Set internally) it should follow the Queue contract. However, the contract states that an IllegalStateException should only be thrown if the capacity is exceeded. In this case it's not even that; I'm simply ignoring the add attempt for non-unique elements. Given this, I wonder if in fact the class should implement neither Queue, nor Set.

[UninformedUser]

The queue methods are not in sync with the set methods, e.g. poll() should also remove the element from the set, otherwise it can happen that you ask !isEmpty() somewhere in the code, and then when you call poll() it results in a NPE.

[Marc]

This seems like the way to go when dealing with a scenario like this question here : stackoverflow.com/questions/4447461/…

[eric A]

The purpose being to implement a queue handling uniqueness, the queue#add should definitely return the return value of the set#add because you may want to know, when calling the method, whether the element was already in there or not. Additionnally, this class should implement the remaining Queue methods like element(), offer() poll(), peek(). Except that, this class definitely meet the needs

[Kevin K]

@TheodoreMurdock Concurrent modification issues can be worked around by only using the iterator for a single retrieval: Object next = queue.iterator.next(); queue.remove(next);. But having to create a new iterator for each retrieval might not be great for efficiency.

[Alan Evangelista]

What if thread safety was a requirement?