PriorityQueue has objects with the same priority.

Question

I use the priority queue to sort and use a large number of user objects. Objects have a "weight", which is their natural order. However, different objects inserted in the priority queue can have the same “weight”. In such cases, I want the priority queue to order them in the same order in which they were queued.

For example, if I add all with the same “weight” to CustomObjects A, B, C, D in this order, then the priority queue should also return them in that order - even if I poll one or more objects before adding them to others.

Here is CompareTo for my custom object:

public int compareTo(CustomObject o) { int thisWeight = this.weight; int thatWeight = o.weight; if(thisWeight < thatWeight){ return -1; } else{ return 1; } } 

While I thought that this would maintain this initial order, this is not so. This happens when I enter A, B, C with a weight of 1; Poll A; and add D, E also with weight 1. Somehow, D and E are sorted after B, but before C.

I know that the Iterator for PriorityQueues does not return the correct order, therefore I am limited in my ability to look at the ordering - however, I see the order in which the elements leave the queue, and this clearly does not follow the path I want.

Suggestions?

Answer 1

If you need to order in accordance with the insertion order, you need to use an additional item to mark the time. That is, on inserts and equal weight, use timestamp to see which element was inserted first. So CustomObject should look something like this:

 class CustomObject { int weight; long timestamp; } 

And the comparison should be:

 public int compareTo (CustomObject o) { int thisWeight = this.weight; int thatWeight = o.weight; if (thisWeight != thatWeight) { return thisWeight - thatWeight; } else { return this.timestamp - o.timestamp; } } 

A timestamp means that it was inserted earlier, so you keep the insertion order.

You can also use “logical” time by maintaining a counter that you update on each add or remove .

Answer 2

You can use a sequence number with auto-increment as a secondary key and use it to break ties.

The javadoc for PriorityBlockingQueue contains an example of this technique:

Operations on this class give no guarantees regarding the ordering of elements with equal priority. If you need to enforce order, you can define custom classes or comparators that use a secondary key to break ties in primary priority values. For example, here is a class that applies the decoupling of the former in the former case to comparable elements. To use it, you must insert a new FIFOEntry(anEntry) instead of a simple recording object.

 class FIFOEntry<E extends Comparable<? super E>> implements Comparable<FIFOEntry<E>> { final static AtomicLong seq = new AtomicLong(); final long seqNum; final E entry; public FIFOEntry(E entry) { seqNum = seq.getAndIncrement(); this.entry = entry; } public E getEntry() { return entry; } public int compareTo(FIFOEntry<E> other) { int res = entry.compareTo(other.entry); if (res == 0 && other.entry != this.entry) res = (seqNum < other.seqNum ? -1 : 1); return res; } }