PriorityQueue ordering issue

Question

I have a PriorityQueue of Vehicles that has one item that is not ordering correctly. I assume there is something in my compareTo that is wonky, but I haven't been able to find it.

public class Vehicle implements Comparable<Vehicle> {

private int id;
private Calendar queueTime;
private int type;
private int size;
 }

@Override
public int compareTo(Vehicle vehicle) {
    if (this.getType() == vehicle.getType()) {
        if (this.getSize() == vehice.getSize()) {
            return (this.queueTime.compareTo(vehicle.queueTime));
        } else if (this.getSize().compareTo(vehicle.getSize()) > 0) {
            return -1;
        } else {
            return 1;
        }
    } else if (this.getType().compareTo(vehicle.getType()) > 0) {
        return -1;
    } else {
        return 1;
    }
}

I have a main class which creates the PriorityQueue, creates a bunch of Vehicle objects and then adds them to the queue.

Queue<Vehicle> currentQueue = new PriorityQueue<Vehicle>();
Vehicle smallPass1 = new Vehicle(1, Calendar.getInstance(), 1, 0);
Vehicle smallCargo1 = new Vehicle(2, Calendar.getInstance(), 0, 0);
Vehicle largePass1 = new Vehicle(3, Calendar.getInstance(), 1, 1);
Vehicle largeCargo1 = new Vehicle(4, Calendar.getInstance(), 0, 1);
Vehicle smallPass2 = new Vehicle(5, Calendar.getInstance(), 1, 0);
Vehicle smallCargo2 = new Vehicle(6, Calendar.getInstance(), 0, 0);
Vehicle largePass2 = new Vehicle(7, Calendar.getInstance(), 1, 1);
Vehicle largeCargo2 = new Vehicle(8, Calendar.getInstance(), 0, 1);

I am expecting this output:

Queue is: [
Vehicle [id=3, queueTime=1396824774459], 
Vehicle [id=7, queueTime=1396824774459],  
Vehicle [id=5, queueTime=1396824774459], 
Vehicle [id=1, queueTime=1396824774458], 
Vehicle [id=8, queueTime=1396824774459], 
Vehicle [id=4, queueTime=1396824774459], 
Vehicle [id=2, queueTime=1396824774459], 
Vehicle [id=6, queueTime=1396824774459]]

But I get this instead:

Queue is: [
Vehicle [id=3, queueTime=1396824774459], 
Vehicle [id=7, queueTime=1396824774459], 
Vehicle [id=8, queueTime=1396824774459], 
Vehicle [id=5, queueTime=1396824774459], 
Vehicle [id=1, queueTime=1396824774458], 
Vehicle [id=2, queueTime=1396824774459], 
Vehicle [id=4, queueTime=1396824774459], 
Vehicle [id=6, queueTime=1396824774459]]

How are the priorities being set? The queue has its own priorities, separate from what the `compareTo` induces. — Dawood ibn Kareem, Apr 06 '14 at 23:34
@DavidWallace: I disagree. If no Comparator is used, then the natural ordering ***is*** in fact used to determine priorities or order. — Hovercraft Full Of Eels, Apr 06 '14 at 23:36
You get this output how? If you're not removing items from the PQ you won't get its order. See the Javadoc. — user207421, Apr 06 '14 at 23:39
@DavidWallace No it doesn't. PriorityQueue doesn't 'have its own priorities'. It has what the Comparator or Comparable delivers, period. — user207421, Apr 06 '14 at 23:42
True, but OP hasn't shown us how the queue is being created. Presumably though, they are not providing a `Comparator` - otherwise they would have shown it here. So I take back my remarks. This `compareTo` is what matters. — Dawood ibn Kareem, Apr 07 '14 at 00:37
I presume the third constructor argument is the type and the fourth is the size? — Dawood ibn Kareem, Apr 07 '14 at 00:38
The variable `aircraft` in the first `else-if` clause should definitely be `vehicle` - is this just a copy/paste error? Because it could actually cause the problem that you're seeing. — Dawood ibn Kareem, Apr 07 '14 at 00:41
Yes, that is just a copy/paste error. I am not using an iterator to get the results...I realize iterator does not produce sorted results. I am simply printing the entire queue contents. — cicit, Apr 07 '14 at 03:25

Hovercraft Full Of Eels · Accepted Answer · 2014-04-06T23:40:48.410

7

Your queue and the compareTo method are likely working correctly. Note what the API says about it:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

The order is apparent when you retrieve items from the queue via the operations poll, remove, peek, and element.

edited Apr 06 '14 at 23:40

answered Apr 06 '14 at 23:33

Hovercraft Full Of Eels

283,665
25
256
373

2

That's a good point. If this thing is implemented as a heap, for example, under the hood, then yeah you're likely to see some really funny things when you serialize it. (in fact maintaining a full sort on the priority queue is often very inefficient for the task) – DrLivingston Apr 06 '14 at 23:36
1

@DrLivingston It is implemented as a heap: see the Javadoc. – user207421 Apr 06 '14 at 23:40
I am not using an iterator to get the results...I realize iterator does not produce sorted results. I am simply printing the entire queue contents....System.out.println(currentQueue). – cicit Apr 07 '14 at 03:28
@Ci-CiMillsThomson: yes of course you are using an iterator. The `toString()` method used by your collection to print out its results uses an iterator behind the scenes. One more reason you should never rely on the results of `toString()` for production code. – Hovercraft Full Of Eels Apr 07 '14 at 10:47

PriorityQueue ordering issue

1 Answers1

Linked

Related