Is there a Queue (PriorityQueue) implementation wh

Question

I'm looking for a PriorityQueue implementation which is also a Set.

The compareTo implementation if its elements must not have the requirement to be consistent with the implementation of equals.

Is there somewhere such a implementation for java?

Update: I implemented it now using a SortedSet as the internal collection. So I only had to implement the missing methods to satisfy the queue interface. I also forgot to mention that it also had to be a bounded queue, so it features a capacity and discards the last element of the set if capacity is reached.

Answer 1

Well the PriorityQueue is going to itself be dependent on the Comparitor or the natural ordering of the items for its sorting, likewise the Set would be dependent on the natural ordering or the Comparitor function so no I don't think one exists as part of the default Java install...

But you could probably create one pretty easily if speed isn't a worry by simply implementing the interfaces you want, and using their natural backings, etc... aka

MyQueueSet extends PriorityQueue implements Set {
    HashSet set;
    ...
}

Unfortunately Java's java.util.* data-set classes aren't always the easiest to extend without rewriting chunks of their code.

The PriorityQueue backing is a heap sorted list of elements, so inserting a new element and then doing a contains(e) test will an O(n) search because sorting is based on the queuing, not on the data value, if you include a HashSet to support the Set functionality though, you can improve your lookup time a lot at the expense of maintaining the dataset references twice (remember that Java is pass-by-value and all objects live on the heap). This should improve performance of a large set.

Answer 2

If it's sufficient to have a queue with a 'Set-like' behaviour, iaw you just don't want to accept duplicate entries, then I think, an easy solution could be to subclass PriorityQueue and override the add(), addAll() and offer() methods like:

@Override
public boolean offer(E e) {
  if (contains(e)) {
    return false; 
  } else {
    return super.offer(e);
  }
}

BTW - add() calls offer() internally, so maybe it's even enough to just override the offer() method and do the check there.

Answer 3

PriorityQueue is an AbstractCollection - this has an almost identical interface to a Set. I'm sure it would be easy to make a wrapper that converts a PriorityQueue to a Set. You could keep a side hash table of inserted elements to avoid duplicates, if you really need to enforce that.

I don't think PriorityQueue requires compareTo to be consistent with equals. PriorityQueue doesn't use equals at all (except for its inherited AbstractCollection operations?).

Answer 4

TreeSet is a set that provides an ordered iterator. It implements the SortedSet interface, which guarantees that the iterator returned by the iterator method will return the set's elements in ascending order as determined either by their natural ordering (through Comparable), or as determined by a comparator given to the set at its creation.