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.
asked Dec 8, 2009 at 18:46 17.1k 29 29 gold badges 89 89 silver badges 115 115 bronze badgesIf 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.
598 5 5 silver badges 14 14 bronze badges answered Dec 8, 2009 at 19:04 Andreas Dolk Andreas Dolk 114k 19 19 gold badges 182 182 silver badges 269 269 bronze badgesThats one possibility I thought of. I just thought that somebody maybe already implemented such a collection.
Commented Dec 10, 2009 at 8:31TreeSet 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.
answered Aug 8, 2011 at 3:06 14.8k 10 10 gold badges 63 63 silver badges 81 81 bronze badgesWell 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
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.