why does my compare method throw exception -- Comparison method violates its general contract!

Question

Why does this code

public class SponsoredComparator implements Comparator<SRE> {

    public boolean equals(SRE arg0, SRE arg1){
        return arg0.getSponsored()==arg1.getSponsored();
    }

    public int compare(SRE object1, SRE object2) {
        Log.d("SponsoredComparator","object1.getName() == "+ object1.getName());
        Log.d("SponsoredComparator","object1.getSponsored() == "+ object1.getSponsored());
        Log.d("SponsoredComparator","object2.getName() == "+ object2.getName());
        Log.d("SponsoredComparator","object2.getSponsored() == "+ object2.getSponsored());
        Log.d("SponsoredComparator","compare return == "+ (object1.getSponsored() && object2.getSponsored() ? 0 : object1.getSponsored() ? -1 : 1));
        return object1.getSponsored() && object2.getSponsored() ? 0 : object1.getSponsored() ? -1 : 1;
    }
}

throw this exception: ERROR/AndroidRuntime(244): java.lang.IllegalArgumentException: Comparison method violates its general contract!
ERROR/AndroidRuntime(4446): at java.util.TimSort.mergeLo(TimSort.java:743)

The method sre.getSponsored() returns a boolean.

Thanks.

Solution 1

I suspect the problem occurs when neither value is sponsored. That will return 1 whichever way you call it, i.e.

x1.compare(x2) == 1

x2.compare(x1) == 1

That's invalid.

I suggest you change this:

object1.getSponsored() && object2.getSponsored()

to

object1.getSponsored() == object2.getSponsored()

in both places. I would probably actually extract this out a method with this signature somewhere:

public static int compare(boolean x, boolean y)

and then call it like this:

public int compare(SRE object1, SRE object2) {
    return BooleanHelper.compare(object1.getSponsored(), object2.getSponsored());
}

That will make the code clearer, IMO.

Solution 2

I assume that you are using JDK 7. Check the following URL:

From http://www.oracle.com/technetwork/java/javase/compatibility-417013.html#source

Area: API: Utilities

Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException

Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.

Nature of Incompatibility: behavioral

RFE: 6804124

For more detailed info, see the bug database reference here.

Solution 3

The contract between equals() and compareTo() is that when equals() returns true, compareTo() should return 0 and when equals() is false compareTo should return -1 or +1.

BTW: I assume your compare() method is not called very often as the debug messages will use up a signficiant amount of CPU and memory.

Solution 4

I agreed with all answer specially with jon, but one addinal things I want to tell that we should always check for null safety in compare method so that our method never be break and it's good habit in programming for always null checking. For more info look here

View more solutions

Comments

[lost baby]

those debug messages are just there to help fix this bug.

[Clockwork-Muse]

And this isn't related directly to the issue you're experiencing, but do you have to worry about nulls?

[Idolon]

You're almost right. OP uses Android (and not JDK 7), but your reference is still correct since both JDK 7 and Android uses TimSort algorithm which throws IllegalArgumentException if used with Comparable that violates the Comparable contract.

[Artur Skrzydło]

as documentation says "It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y))". And this exception from question is not derived from breaking contract with equals method. I write this comment on this old answer because it leads me to wrong conclusions that breaking contract in this exception can be connected with equals method

[zreptil]

@Peter Lawrey This is the first information i found where someone made clear, what the contract really is. Thank you for this But given that equals has to give back a value that corresponds to compareTo, i think the best solution for all the users implementing compareTo could be to override also equals and simply calling compareTo within this method, returning true, if the result is 0 and false if it is not 0. The only thing that should be looked at is, that within compareTo there must not be a call to equals.

[Vishy]

@zreptil Using compareTo has some problems; a) sometimes two values can be equals but compareTo is not 0 e.g. -0.0 and 0.0 and BigDecimal values. The other problem is that two values might not have any reasonable concept of higher or lower, not you can check for equality.

[zreptil]

@Peter Lawrey i think compareTo can be used without any problem. It worked for me for years until the java-Team decided that a violation of the contract between compareTo and equals has to throw an exception, that doesn't really clarify what is going wrong. I use compareTo rarely, but it is a handy method to compare two instances of a class to decide which one has to be sorted before the other one. After knowing the details of the contract the bugfix for that exception was really easy and works like a charme.