when will priority queue call compareTo of the elements?

Question

I am writing a ai of dots and boxes. I am using the priority queue to contain my edges of boxes. And I make a move by the priority of a box. After a move, I have to update the priority and pool() the head of queue.

Here is some code:

   public int compareTo(MyPosition o) {
        if (new Integer(o.getPriority())> new Integer(getPriority())) {
            return 1;
        }else if(new Integer(o.getPriority())== new Integer(getPriority())){
            return 0;
        }else {
            return -1;
        }
        
    }

But what the order of my move is not correspond to the priority of queue. Here is picture (the last number is the priority of edge):

So could anyone explain why and how to improve it. (I guess the priority queue don't compare the priority after updates.)

Thanks a lot.

Answer 1

In Java PriorityQueues are implemented as heaps. So the compareTo() is evaluated at insertion time.

One of The problems you might be facing is that you may not be overriding the correct method (as others have pointed out). Add an @Override annotation to your compareTo() method and the compiler will tell you if you're not doing what you think you're doing (if you're using Java 1.5 or newer).

Here is code:

public class MyPosition implements Comparable<MyPosition>{
    private Integer priority;

    @Override
    public int compareTo(MyPosition that) {
        return this.priority.compareTo(that.priority);
    }
}

Answer 2

Try implementing your compareTo by utilizing the compareTo method of an Integer class:

public int compareTo(MyPosition o) {
    return Integer.valueOf(getPriority()).compareTo(Integer.valueOf(o.getPriority()));
}

One of the errors I see here is that you compare objects with == sign. While it works for primitive types (e.g. int) and in some cases for Integer it gives wrong results for larger numbers. It does not seem that this is a problem in your example but I just wanted to point this out. Objects should be compared for equality with equals() method.

Another problem might be that you did not implement the Comparable interface in your MyPosition class.