CODEWITHSUNDEEP
javacollectionsqueueguavaunique-constraint
Antoine Claval
Antoine Claval

Reputation: 4944

A Queue that ensure uniqueness of the elements?

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?

Upvotes: 80

Views: 65215

Answers (10)

Abd Qadr
Abd Qadr

Reputation: 63

You can override the add method when initializing your queue variable.

Queue<T> queue = new PriorityQueue<>() {
  @Override
  public boolean add(T t) {
    return !this.contains(t) && super.add(t);
  }
};

... or you can implement the Queue interface.

Upvotes: 1

Homayoon Ahmadi
Homayoon Ahmadi

Reputation: 2833

I used LinkedHashSet for that:

public class UniqueQueue<T> {

    private final LinkedHashSet<T> queue;

    public UniqueQueue() {
        queue = new LinkedHashSet<>();
    }

    public void enqueue(T item) {
        synchronized (UniqueQueue.class) {
            queue.add(item);
        }
    }

    public T dequeue() {
        synchronized (UniqueQueue.class) {
            Iterator<T> i = queue.iterator();

            T next = i.next();
            i.remove();

            return next;
        }
    }
}

Upvotes: 1

Tom
Tom

Reputation: 322

I am a bit late to answer but I ended up solving a similar problem using an ArrayDeque and overriding the add method that I needed.

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

Upvotes: 3

Benoit Vanalderweireldt
Benoit Vanalderweireldt

Reputation: 2989

Unfortunately it doesn't exist. Since I needed such a Queue I have developed a Blocking Queue backed by a set, inspired by 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>

Upvotes: 3

Erel Segal-Halevi
Erel Segal-Halevi

Reputation: 36715

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

Upvotes: 5

Kevin Bourrillion
Kevin Bourrillion

Reputation: 40851

This is a very good question. There is no existing straightforward solution. I'll dig up some code I wrote a while back that attempted to do this, and come back and edit this answer.

EDIT: I'm back. Truly, if you don't need concurrency, you are better off maintaining a Queue and Set separately. For what I was doing, concurrency was a goal, but the best solution I could come up with given that constraint was problematic; basically, since it used a ConcurrentHashMap, the more you were removing the "head" element from the queue (a basic thing to do with a queue), the more unbalanced the hash table would become over time. I can still share this code with you, but I doubt you really want it.

EDIT: For the case where concurrency is required I gave this answer: Concurrent Set Queue

Upvotes: 1

erickson
erickson

Reputation: 269627

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();

Upvotes: 65

Alex Miller
Alex Miller

Reputation: 70201

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.

Upvotes: 4

Adamski
Adamski

Reputation: 54697

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.
}

Upvotes: 26

tvanfosson
tvanfosson

Reputation: 532445

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.

Upvotes: 6

Related Questions