What could possibly be wrong with this Comparator?

Question

I'm getting

"Exception in thread "AWT-EventQueue-0"
java.lang.IllegalArgumentException: Comparison method violates its general contract!"

errors with this comparator. It is used in a PriorityQueue.

public class NodeFPQComp implements Comparator<Node> {

    @Override
    public int compare(Node arg0, Node arg1) {
        int result=0;

        if (arg0.getF() - arg1.getF() > 0) result = 1;
        if (arg0.getF() - arg1.getF() < 0) result = -1;

        return result;  
    }

}

getF() is a float value that never gets close to the limits so no overflow issues here.
It simply returns the sum of two other floats:

public float getG() {
        return this.G;
    }

    public float getH() {
        return this.H;
    }

    public float getF() {
        return getG() + getH();
    }

Here's the queue that uses it:

openList = new PriorityQueue<Node>((int) gridSizeX()*gridSizeY()/10, new NodeFPQComp());

What I want is to have the queue (A-Star path finding) accept multiple objects of the same value (same f-value), but different identity (the different nodes/squares on the map).

The weird thing is that the path finding still works, but why am I getting the exception? How could that comparator not be working? What am I missing? Could it be that changing the values that getF() relies on after the object has been added to the queue (this happens a lot in a-star) mess it up somehow?

And here's the full stacktrace:

Exception in thread "AWT-EventQueue-0" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(Unknown Source)
    at java.util.TimSort.mergeAt(Unknown Source)
    at java.util.TimSort.mergeCollapse(Unknown Source)
    at java.util.TimSort.sort(Unknown Source)
    at java.util.TimSort.sort(Unknown Source)
    at java.util.Arrays.sort(Unknown Source)
    at java.util.Collections.sort(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.enumerateAndSortCycle(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.getFocusTraversalCycle(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.getFirstComponent(Unknown Source)
    at javax.swing.LayoutFocusTraversalPolicy.getFirstComponent(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.getDefaultComponent(Unknown Source)
    at java.awt.FocusTraversalPolicy.getInitialComponent(Unknown Source)
    at java.awt.DefaultKeyboardFocusManager.dispatchEvent(Unknown Source)
    at java.awt.Component.dispatchEventImpl(Unknown Source)
    at java.awt.Container.dispatchEventImpl(Unknown Source)
    at java.awt.Window.dispatchEventImpl(Unknown Source)
    at java.awt.Component.dispatchEvent(Unknown Source)
    at java.awt.EventQueue.dispatchEventImpl(Unknown Source)
    at java.awt.EventQueue.access$200(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue.dispatchEvent(Unknown Source)
    at java.awt.SequencedEvent.dispatch(Unknown Source)
    at java.awt.EventQueue.dispatchEventImpl(Unknown Source)
    at java.awt.EventQueue.access$200(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue.dispatchEvent(Unknown Source)
    at java.awt.EventDispatchThread.pumpOneEventForFilters(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForFilter(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.run(Unknown Source)

could it be non-transitive like the following answer? Of course, it will depend on getF's return type and how it behaves under subtraction. http://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract — Graham Griffiths, Mar 10 '14 at 16:59
ah, you might be having troubles caused by NaNs ? obligatory Jon Skeet reference : http://stackoverflow.com/questions/9469308/java-error-comparison-method-violates-its-general-contract — Graham Griffiths, Mar 10 '14 at 17:07
*Could it be that changing the values that getF() relies on after the object has been added to the queue (this happens a lot in a-star) mess it up somehow?* - **YES**, this could definitely be a problem. The simplest ("clean") solution is to remove and re-insert the element. It has a slight performance penalty, but the alternative would be to implement an own PriorityQueue or another data structure, e.g. a heap that can quickly re-establish the heap property after values have changed. — Marco13, Mar 10 '14 at 17:29
An aside: You could just write `return Float.compare(arg0.getF(), arg1.getF());`. But I guess the actual problem is the values that are changing after the node was inserted into the queue. — Marco13, Mar 10 '14 at 17:37
Have you tried changing the second `if` to an `else if`? Your compiler may not be able to tell that the clauses are mutually exclusive. — MrLore, Mar 10 '14 at 17:37
@MrLore... the compiler is not the problem here. All compiles well, it is a runtime exception. And the result is initialized to 0 anyway. — jackthehipster, Mar 10 '14 at 18:42
@Marco13: I thought so, too, but according to other posts on SO, the PQ will only insert the element at the right point, but not update itself if a value changes. That means that my A-Star might take longer to find a path, but would still find it. There should be no other issue with changing values after adding an element. But I'll try your suggestion to remove/add instead of updating an element. — jackthehipster, Mar 10 '14 at 18:46
Can you post the full stack trace of the exception? (I know this message only from "manual" sorts with `Collections.sort`, so I'm wondering where it actually comes from — Marco13, Mar 10 '14 at 18:52
@Marco: posted the stack trace. Funny thing about it is, it never mentions anything from my code. And come to think of it, my comparator is only called later after I click a button. The exception occurs immediately after the gui is displayed... but I have no other comparators anywhere?! — jackthehipster, Mar 10 '14 at 20:31
OK, this should be *entirely* unrelated to your priority queue. I'd guess you are modifying the GUI from the wrong thread. Do you have any other threads in your program that you construct explicitly (with `new Thread(...)`? If not: Are you sure that your GUI is created on the Event Dispatch Thread? — Marco13, Mar 10 '14 at 21:13

webuster · Answer 1 · 2014-03-10T19:28:46.793

2

The "contract" means the compare method should be a total ordering. (Edit) This should also be consistent with the equals(Object obj) method (even though it may not be strictly imposed) to make sure data structures (such as TreeSet, TreeMap) behave the way you expect, as they may be based on both conparison and the equals method.

Make sure you have those in check.

Total ordering means

a.compareTo(a) >= 0, for every a
a.compareTo(b) >= 0 and b.compareTo(a) >= 0 implies that a is "equal" to b, for every a,b; that means if a.compareTo(b) == 0, then also b.compareTo(a) == 0
a.compareTo(b) >= 0 and b.compareTo(c) >= 0 implies a.compareTo(c) >= 0, for every a,b,c

It's easy to give counterexamples where the compare method returns {0,1,-1} and not be consistent with total ordering, so check that in particular.

edited Mar 10 '14 at 19:28

answered Mar 10 '14 at 17:03

webuster

2,490
18
27

Ok, I thought it might be related to equals, but how do I accomplish what I need, it seems very simple to me but doing it not so. How can I have a sorted list where different objects with the same sorting-values are kept in a sorted order (so no ArrayList that needs to be sorted after every change)? – jackthehipster Mar 10 '14 at 17:05
You can override `equals` to return whether a `Comparator` of yours returns 0 at comparison (first thing that comes to mind). – webuster Mar 10 '14 at 17:09
that is clear, only it would cause other headaches, because semantically, two nodes can and will have same f-values, but will be different nodes?! isn't that what comparators are for, to have comparisons other than the "natural ordering"? – jackthehipster Mar 10 '14 at 17:34
Natural order and total ordering are different concepts. Also, the `==` operator tests if nodes are *exactly* the same (they refer to the exact same object), whereas the `equals` method tests whether objects are conceptually "equal" or equivalent in your custom sense. – webuster Mar 10 '14 at 17:39
1

Comparators do not have to be consistent with equals. See the JavaDocs for [Comparator](http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html) – Daniel Mar 10 '14 at 17:44
Thanks @Daniel, that's what I thought. If they had to be consistent, there would be little point in having multiple comparators but only one equals()... – jackthehipster Mar 10 '14 at 18:40
Consistency with equals does not mean you're stuck with just one comparison method, there are tons of Comparators consistent with equals that do crazy stuff. It *should* be consistent with equals even though you're not constrainted to that, edited my answer. – webuster Mar 10 '14 at 19:24
@webuster: what I mean is, it is simply impossible to have several comparators that, for example, compare different properties of the objects, to all be consistent with one single equals method... and since having multiple comparators is a feature by design, it would be illogical (to my understanding) to go for any consistency here with one equals() method. – jackthehipster Mar 10 '14 at 20:25
Why is that? You can have Comparators for Numbers that for example, return the difference of their values, or minus their difference, or 1 - `e` raised to their difference (why you would do that, up to you); all of those are consistent with equals, but they do wildly different things. – webuster Mar 10 '14 at 20:46

score 0 · Answer 2 · answered Mar 10 '14 at 17:42

There are two possible failures here, both of which might be ignorable.

The first possible failure is that either arg0 or arg1 may be null, in which case you'll end up with an NullPointerException being thrown. This may be acceptible since many times you wouldn't allow nulls in collections anyway.

The other possible failures are for getF() returning certain integer types (int, byte, long) can occur if the return values the two getF() calls have a large enough difference that they overflow.

The maximum valid difference for this kind of comparison would depend on the type, and would be either Integer.MAX_VALUE for byte and int, or Long.MAX_VALUE for longs.

Since you're already comparing the result of the subtraction, why not just compare the two values directly?

int result = 0;

if (arg0 != arg1) {
   if (arg0 == null) { 
      result = -1;
   } else if (arg1 == null) {
      result = 1;
   }
   if (arg0.getF() < arg1.getF()) {
      result = -1;
   }
   if (arg0.getF() > arg1.getF()) {
      result = 1;
   }
}

return result;

if you prefer concise code:

return arg0 != null && arg1 != null ? 
    Integer.compare(arg0.getF(), arg1.getF()) : // Neither are null, compare vlues
      arg0 == arg1 ? 
         0 : // both are null, return 0
         arg0 == null ? -1 : 1;  // arg0 != arg1, so one of them must be null.

both are no issues in my case. The f-vals are pretty small (<1000000), and there is never a null value. And even if there was, I would get a null-value exception and not that contract violation. — jackthehipster, Mar 10 '14 at 18:49

What could possibly be wrong with this Comparator?

2 Answers2