java.lang.IllegalArgumentException: Comparison method violates its general contract [duplicate]

Question

Hi below is my compare method of my comparator. I am not sure what is wrong. I looked up other similar titled questions and answers on stack overflow but not sure what is wrong with my method but I keep getting java.lang.IllegalArgumentException: Comparison method violates its general contract!

Any help will be greatly appreciated

public int compare(Node o1, Node o2) {     HashMap<Integer,Integer> childMap = orderMap.get(parentID);     if(childMap != null && childMap.containsKey(o1.getID()) &&                             childMap.containsKey(o2.getID()))     {         int order1 = childMap.get(o1.getID());         int order2 = childMap.get(o2.getID());          if(order1<order2)              return -1;         else if(order1>order2)              return 1;         else              return 0;     }     else         return 0; } 

Adding the exception I am getting

java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeLo(TimSort.java:747) at java.util.TimSort.mergeAt(TimSort.java:483) at java.util.TimSort.mergeCollapse(TimSort.java:410) at java.util.TimSort.sort(TimSort.java:214) at java.util.TimSort.sort(TimSort.java:173) at java.util.Arrays.sort(Arrays.java:659) at java.util.Collections.sort(Collections.java:217) 

Answer 1

Your compare() method is not transitive. If A == B and B == C, then A must be equal to C.

Now consider this case:

For A, B, and C, suppose the containsKey() method return these results:

• childMap.containsKey(A.getID()) returns true
• childMap.containsKey(B.getID()) returns false
• childMap.containsKey(C.getID()) returns true

Also, consider orders for A.getId() != B.getId().

So,

1. A and B would return 0, as outer if condition will be false => A == B
2. B and C would return 0, as outer if condition will be false => B == C

But, A and C, could return -1, or 1, based on your test inside the if block. So, A != C. This violates the transitivity principle.

I think, you should add some condition inside your else block, that performs check similar to how you do in if block.

Answer 2

I think the problem is in your default case. Consider the set of nodes A, B, and C, where the IDs are 'a', 'b', and 'c'. Consider further that your childMap, which contains the relative ordering information, has the following contents:

{ 'a' => 1, 'c' => 3 } 

Now if you run your compare method on A and B, you return 0, indicating that A and B are equivalent. Further, if you compare B and C, you still return 0. However, if you compare A and C, then you return -1, indicating that A is smaller. This violates the transitivity property of the Comparator contract:

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

You can't treat "items which don't have an order assigned" as having the value "somewhere vaguely in the middle", since sorting algorithms don't know where to put them. If you want to stay with this approach, then in the case where the value is not present in the map, you need to assign a fixed value to be the ordering number; something like either 0 or MIN_INT is a reasonable choice (but any choice needs to be documented in the Javadoc for compare!).