Java Collections sort: Comparison method violates its general contract

Question

I know it has been asked and answered millions of times but still I am unable to figure out why I am receiving with the violation during sort. Here is my code:

Collections.sort(sorted, new Comparator<MyObject>() {
    @Override
    public int compare(MyObject m1, MyObject m2) {
        // Actual energy comparison :-
        // THE higher the energy, the earlier in the list
        float delta = m1.getTotalEnergy() - m2.getTotalEnergy();

        if (delta > 0) {
            return 1;
        } else if (delta < 0) {
            return -1;
        } else {
            return 0;
        }
    }
});

and I receive this error

java.lang.IllegalArgumentException: Comparison method violates its general contract!  
        at java.util.TimSort.mergeHi(TimSort.java:895)  
        at java.util.TimSort.mergeAt(TimSort.java:512)  
        at java.util.TimSort.mergeForceCollapse(TimSort.java:453)  
        at java.util.TimSort.sort(TimSort.java:250)  
        at java.util.Arrays.sort(Arrays.java:1512)  
        at java.util.ArrayList.sort(ArrayList.java:1454)  
        at java.util.Collections.sort(Collections.java:175)

Any ideas ?

Answer 1

There was some discussion of NaN values in the comments. This is important, because NaN violates our typical expectations of comparisons of floating point numbers. For example, Double.NaN > 0.0 and Double.NaN < 1.0 are both false!

This may cause the sort to throw the exception as you encountered. Even if the exception isn't thrown, it may cause the list to end up sorted in the wrong order. Therefore, your sort comparator must deal with NaN values. Fortunately, the library's built-in comparisons such as Double.compare() do this for you. This has the same semantics as Double.compareTo(), except that boxed Double values aren't necessary. See the documentation for details. Briefly, NaN values are considered greater than all other values (including +Inf), and negative zero is less than positive zero.

To use Double.compare() in a Comparator for sort, do this:

Collections.sort(data, new Comparator<MyObject>() {
    public int compare(MyObject m1, MyObject m2) {
        return Double.compare(m1.getTotalEnergy(), m2.getTotalEnergy());
    }
});

If you're using Java 8, you could do this:

data.sort(Comparator.comparing(MyObject::getTotalEnergy));

To handle nulls, wrap the comparator with nullsFirst or nullsLast:

data.sort(Comparator.nullsFirst(Comparator.comparing(MyObject::getTotalEnergy)));

Answer 2

The following code has been tested with float, NaN, and null values. All cases are handled correctly. I created a hashCode() and equals() method to the MyObject class.

Result: [null, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, NaN]

SortObjectFloatProperty

package q28004269;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortObjectFloatProperty {
    public static void main(String[] args) {
        List<MyObject> sorted;

        sorted = create(1f, 4f, 6f, null, 8f, 5f, Float.NaN, 3f, 2f, 7f, 0f, 9f);

        Collections.sort(sorted, new Comparator<MyObject>() {
            @Override
            public int compare(MyObject m1, MyObject m2) {
                if (m1 == m2) return 0;
                if (m1 == null) return -1;
                if (m2 == null) return 1;
                if (m1.equals(m2)) return 0;
                int value = Float.compare(m1.getTotalEnergy(), m2.getTotalEnergy());
                if (value != 0) return value;
                return m1.hashCode() - m2.hashCode();
            }
        });

        System.out.println(sorted);
    }

    public static MyObject create(float totalEnergy) {
        return new MyObject(totalEnergy);
    }

    public static List<MyObject> create(Object ...values) {
        List<MyObject> objs = new ArrayList<SortObjectFloatProperty.MyObject>();
        for (int i = 0; i < values.length; i++) {
            if (values[i] instanceof Float) {
                objs.add(create((float) values[i]));
            } else {
                objs.add(null);
            }
        }
        return objs;
    }
}

MyObject

package q28004269;

public static class MyObject {
    private float totalEnergy;

    public float getTotalEnergy() {
        return totalEnergy;
    }

    public void setTotalEnergy(float totalEnergy) {
        this.totalEnergy = totalEnergy;
    }

    public MyObject() {
        this(0.0f);
    }

    public MyObject(float totalEnergy) {
        this.totalEnergy = totalEnergy;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Float.floatToIntBits(totalEnergy);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        MyObject other = (MyObject) obj;
        return !(Float.floatToIntBits(totalEnergy) != Float.floatToIntBits(other.totalEnergy));
    }

    @Override
    public String toString() {
        return Float.toString(totalEnergy);
    }
}

Answer 3

Assuming getTotalEnergy() return(s) float, you could use

return new Float(m1.getTotalEnergy()).compareTo(m2.getTotalEnergy());

Using Float.valueOf(float) is probably slightly more efficient, and hopefully this is easier to read.

Float f1 = Float.valueOf(m1.getTotalEnergy());
Float f2 = Float.valueOf(m2.getTotalEnergy());
return f1.compareTo(f2);

Answer 4

Without reference to MyObject. My guess is that the comparator is inconsistent with MyObject.equal.

That is, the contract you are violating is:

(comparator.compare(mo1, mo2) == 0) == mo1.equals(mo2)

Your comparator will compare objects with the same float value as being equal, where a more complex comparator would give an ordering, whilst the equals method would say the objects were not equal. Or you could have the reverse problem -- the equals method says the objects are equal and the compare method says they are different.

The following should work.

public int compare(MyObject m1, MyObject m2) {
    if (m1 == m2) return 0;
    if (m1 == null) return -1;
    if (m2 == null) return 1;
    if (m1.equals(m2)) return 0;

    int value = Float.compare(m1.getTotalEnergy(), m2.getTotalEnergy());
    if (value != 0) return value;

    // Warning, this line is not fool proof as unequal objects can have identical hash 
    // codes.
    return m1.hashCode() - m2.hashCode();
}

Answer 5

Maybe this will make the change:

public int compare(Object m1, Object m2) {
    // Actual energy comparison :-
    // THE higher the energy, the earlier in the list
    float delta = ((MyObject)m1).getTotalEnergy() - ((MyObject)m2).getTotalEnergy();
....
}