Android - Comparison method violates its general contract

Question

I've seen other questions about this exception but my compare method is so simple that I'm unable to figure out what's wrong with it and I can't reproduce it with any of the Android devices that I own.

I'm getting this exception from some users of my Android app, most of which seem to be on very new devices like GS3 or GS4, which I'm guessing run the Java 7 variant of merge sort.

Here's my compare method:

            Collections.sort(collectionOfThings, new Comparator<Thing>()
            {
                public int compare(Thing lhs, Thing rhs) 
                {
                    //getDist() returns a Double with a capital D...perhaps that has something to do with it?
                    if(lhs.getDist() < rhs.getDist())
                    {
                        return -1;
                    }
                    if(lhs.getDist() == rhs.getDist())
                    {
                        return 0;
                    }

                    return 1;
                };
            });

Here's the exception:

Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:743)
    at java.util.TimSort.mergeAt(TimSort.java:479)
    at java.util.TimSort.mergeCollapse(TimSort.java:404)
    at java.util.TimSort.sort(TimSort.java:210)
    at java.util.TimSort.sort(TimSort.java:169)
    at java.util.Arrays.sort(Arrays.java:2038)
    at java.util.Collections.sort(Collections.java:1891)

Seems to be limited to Android 4.0+. Any help is greatly appreciated.

I am not certain this would fix it but I would just do `return lhs.getDist().compareTo(rhs.getDist());` http://docs.oracle.com/javase/6/docs/api/java/lang/Double.html#compareTo(java.lang.Double) — Ken Wolf, Jul 15 '13 at 16:36
http://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract — Dave Newton, Jul 15 '13 at 16:38
Is there a possibility that `Thing.getDist()` modifies the `Thing`? — Ted Hopp, Jul 15 '13 at 16:38

AllTooSir · Accepted Answer · 2013-07-16T04:22:17.520

No use in re inventing the wheel. I believe you should just return lhs.getDist().compareTo(rhs.getDist()); and let the provided implementation compareTo do the job .

Compares two Double objects numerically.

There are two ways in which comparisons performed by this method differ from those performed by the Java language numerical comparison operators (<, <=, ==, >=, >) when applied to primitive double values:

Double.NaN is considered by this method to be equal to itself and greater than all other double values (including Double.POSITIVE_INFINITY).

0.0d is considered by this method to be greater than -0.0d.

This ensures that the natural ordering of Double objects imposed by this method is consistent with equals.

I believe you get this Exception because your present implementation may not be apt to deal with Double.NaN and positive/negative zero values , and yet honor the general contract. Look at the OpenJDK Double#compare(double,double) source code :

public static int More ...compare(double d1, double d2) {
   if (d1 < d2)
        return -1;           // Neither val is NaN, thisVal is smaller
    if (d1 > d2)
        return 1;            // Neither val is NaN, thisVal is larger

    long thisBits = Double.doubleToLongBits(d1);
    long anotherBits = Double.doubleToLongBits(d2);

    return (thisBits == anotherBits ?  0 : // Values are equal
            (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
             1));                          // (0.0, -0.0) or (NaN, !NaN)
}

Also go through the documentation of Double#equals()

Note that in most cases, for two instances of class Double, d1 and d2, the value of d1.equals(d2) is true if and only if d1.doubleValue() == d2.doubleValue()

also has the value true. However, there are two exceptions:

If d1 and d2 both represent Double.NaN, then the equals method returns true, even though Double.NaN==Double.NaN has the value false. If d1 represents +0.0 while d2 represents -0.0, or vice versa, the equal test has the value false, even though +0.0==-0.0 has the value true.

Hey there - thanks for the answer. I have a feeling that you are right, but there's really no reason why getDist() should ever be NAN or infinity. The value of getDist is set for every item in the collection just before the sort call. I'm going to try changing my compare method as you suggested but unfortunately since I can't reproduce this error locally, I'll have to release it to the Play Store and see if the error reports cease. I'll accept this answer once I know if it worked. Thanks! — DiscDev, Jul 15 '13 at 16:46
Also, I totally agree - no use reinventing the wheel - I guess I am just so used to having to write my own comparators for custom Objects that I forget there already exist comparators for the built-in Object library. Sometimes I get way too deep in my own code to remember things like that :) — DiscDev, Jul 15 '13 at 16:51
Note that `POSITIVE_INFINITY` and `NEGATIVE_INFINITY` should not be problems when using the numerical comparison operators. It's just `NaN` and the positive/negative zero cases that would be problematic. — Ted Hopp, Jul 15 '13 at 17:09

score 2 · Answer 2 · answered Jul 15 '13 at 16:39

2

Instead of comparing two Double objects, you should really be comparing their values (getDoubleValue()). Comparing two objects will not necessarily mean their values are equal.

answered Jul 15 '13 at 16:39

Alex Fu

5,509
3
31
40

Alex - I thought that java would be smart enough to compare the double values...this compare method works fine on older Android devices so there's no possibility that it's comparing object references otherwise the results I get back from the compare would be erratic. I think that Ken Wolf and The New Idiot are on to something... – DiscDev Jul 15 '13 at 16:42
@spotdog13 The < operator will unbox the Double objects for comparison, but the == operator will compare the object references. Objects should always be compared with .equals(). – Michael Krussel Jul 15 '13 at 16:52
Ah yes Michael you are correct. I knew the < would unbox them...it's actually very unlikely that getDist() will ever be the same for 2 objects due to the precision involved in the value...that would probably explain why this sorts things correctly and I missed my typo :). I actually didn't realize getDist() was a Double (thought it was a double but it's a value pulled from the DB which I believe required me to choose Double at the time I created the table) until I asked this question. – DiscDev Jul 15 '13 at 17:08
Using `==` is probably the root of the problem. It's possible that Android 4.0+ changed strategies for how frequently requested `Double` values are cached (and hence considered `==`), which would explain the change in behavior of your code. – Ted Hopp Jul 15 '13 at 17:15

Android - Comparison method violates its general contract

2 Answers2