java.lang.IllegalArgumentException: Comparison method violates its general contract! How to handle possible null objects?

Question

private Comparator<Entity> spriteSorter = new Comparator<Entity>() {
    public int compare(Entity e0, Entity e1) {
        if (e0 == null || e1 == null) return -1; //was 0
        if (e1.getY() < e0.getY()) return +1;
        if (e1.getY() > e0.getY()) return -1;
        return -1; //was 0
    }
};

I have read many articles about this one, but I still don't know how to solve this little problem:

This is the core that works:

if (e1.getY() < e0.getY()) return +1;
if (e1.getY() > e0.getY()) return -1;

But sometimes (I have to deal with many houndred entities which are being added and removed from a concurrent array list very often in a second) one of the entities is null. Therefore I have to check this inside this comparator. But then I violate this general contract, once one of the two objects is null.

Any idea how I can solve this? Please help! :)

Answer 1

Your comparator, if called with c.compare(null, null), will compare null < null, even though they are equal. Further, it breaks the rule for inverses, which is that sgn(compare(a, b)) == -sgn(compare(b, a)), that is, comparing two things backwards returns the opposite of comparing them forwards. You can fix all this simply by treating null as "negative infinity," that is enforcing that null < a for all nonnull a and null == null.

public int compare(Entity l, Entity r) {
    if (Objects.equals(l, r)) return 0; // Handles normal and null equality
    else if(l == null) return -1; // Enforce null < a ∀ nonnull a
    else if(r == null) return +1; // Enforce a > null ∀ nonnull a
    else return Integer.compare(l.getY(), r.getY()); // Base comparison
}