java.lang.IllegalArgumentException: Comparison method violates its general contract

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)

@tieTYT I think the exception is being thrown from within a collection he's passing this to as a `Comparator`. This comparator looks really unstable, as any modifications to *`orderMap[parentID]`* or the ordering specified in `childMap` will move the items around. — chrylis -cautiouslyoptimistic-, Oct 11 '13 at 18:57
What is `parentId`'s type? Are you storing a HashMap within a Map? — Kevin Bowersox, Oct 11 '13 at 18:58
Similar question is already answered...Check it here http://stackoverflow.com/questions/11441666/java-error-comparison-method-violates-its-general-contract — MAK, Oct 11 '13 at 19:05
check out the following link ... similar question has been answered already http://stackoverflow.com/questions/11441666/java-error-comparison-method-violates-its-general-contract . — MAK, Oct 11 '13 at 19:08
I have below code that also happened of this exception error: — Wing Hing Raymond Chiu, Aug 31 '16 at 09:57
@Override public int compareTo(ActivitiesCourseWebVo another){ if(this.courseInfo.getCourseEndDate().after(another.courseInfo.getCourseEndDate())) return 1; else return -1; } — Wing Hing Raymond Chiu, Aug 31 '16 at 09:57
I have solved by using compareTo as i need to take care of same condition. — Wing Hing Raymond Chiu, Sep 03 '16 at 02:44

Rohit Jain · Accepted Answer · 2013-10-11T19:17:48.927

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,

A and B would return 0, as outer if condition will be false => A == B
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.

score 7 · Answer 2 · edited Jun 20 '20 at 09:12

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!).

This answer also provides a solution, in addition to the explanation. — Manuel, Jun 04 '19 at 00:30

java.lang.IllegalArgumentException: Comparison method violates its general contract

2 Answers2

Linked

Related