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.

Answer 1

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:

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

2. 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.

Answer 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.