"Comparison Method Violates Its General Contract!"

Java error: Comparison method violates its general contract

The exception message is actually pretty descriptive. The contract it mentions is transitivity: if A > B and B > C then for any A, B and C: A > C. I checked it with paper and pencil and your code seems to have few holes:

if (card1.getRarity() < card2.getRarity()) {
  return 1;

you do not return -1 if card1.getRarity() > card2.getRarity().

if (card1.getId() == card2.getId()) {
  //...
}
return -1;

You return -1 if ids aren't equal. You should return -1 or 1 depending on which id was bigger.

Take a look at this. Apart from being much more readable, I think it should actually work:

if (card1.getSet() > card2.getSet()) {
    return 1;
}
if (card1.getSet() < card2.getSet()) {
    return -1;
};
if (card1.getRarity() < card2.getRarity()) {
    return 1;
}
if (card1.getRarity() > card2.getRarity()) {
    return -1;
}
if (card1.getId() > card2.getId()) {
    return 1;
}
if (card1.getId() < card2.getId()) {
    return -1;
}
return cardType - item.getCardType();  //watch out for overflow!

Comparison method violates its general contract!

Your comparator is not transitive.

Let A be the parent of B, and B be the parent of C. Since A > B and B > C, then it must be the case that A > C. However, if your comparator is invoked on A and C, it would return zero, meaning A == C. This violates the contract and hence throws the exception.

It's rather nice of the library to detect this and let you know, rather than behave erratically.

One way to satisfy the transitivity requirement in compareParents() is to traverse the getParent() chain instead of only looking at the immediate ancestor.

Comparison method violates its general contract - how to avoid it

Your comparator doesn't deal with nulls and unparseable dates correctly. Consider the following case:

Suppose you have two non null dates d1 and d2 and a null d3.
Suppose d1 > d2.

You thus have

d1 > d2
d1 == d3
d2 == d3

So, if d1 and d2 are both equal to d3, they should also be equal to each other, but they're not.

Start by transforming all your strings to dates or null.

Then use a comparator which considers all null values as bigger (or lower) than all non null values. Comparator has utility methods to transform a comparator of non-null objects into a comparator which deals with nulls by putting them all first or last.

Comparison method violates its general contract while comparing java.util.Date

The "contract" for comparison is that the comparison function has to define a total order. One of the requirements of a total order is "asymmetry", which basically means that if a < b, then b > a. In Java terms, this means that if compare(a,b) (or a.compareTo(b)) returns a result < 0, then compare(b,a) (or b.compareTo(a)) must return a result > 0. Your comparison function doesn't obey this rule; if x.getAttribute() is non-null and y.getAttribute() is null, then compare(x,y) returns -1 and compare(y,x) also returns -1.
TimSort sometimes notices this and throws an exception when it spots a comparison that doesn't return what it expects.

Another way to look at it: you have to decide beforehand what order you want things to be in if there are "special" values in the input (except that if you want objects to be compare as "equal", the order doesn't matter). Suppose your input contains objects whose getAttribute() is null, and objects whose getAttribute() is non-null. Where do you want the ones with the null attribute to appear in the output? How do you want them to be ordered? "I don't care" is not an option. Let's say you want all the null-attribute ones to come last, but you don't care about how the null-attribute objects are ordered. Then you need to write your comparison function so that

an object with a non-null attribute < an object with a null attribute;
an object with a null attribute > an object with a non-null attribute;
two object with null attributes are treated as equal (comparison function returns 0).

If you want the null ones to appear first in the array, then the < and > in the first two points would be reversed. If you want two objects with null attributes to be ordered based on some other attribute, then write your comparison function so that it does that, but you'll still need to decide where the ones with the null attribute appear relative to the ones with the non-null attribute. Maybe it doesn't matter which one you choose. But you have to choose something, and you have to write your comparison function to return the result based on what you've chosen.

P.S.: There's no particular reason why your second code snippet with Employee works and the first one doesn't. Your comparator in the second case is just as wrong as in the first one. However, TimSort doesn't look at every pair of elements to make sure the comparison meets the contract (that would make it an O(n²) algorithm). I'm not familiar with the details of TimSort, but I suspect that it only makes this check when it has a reason to compare two elements to see if the comparison is (perhaps) <0 or =0, and it "knows" that >0 should not be possible if the comparison function meets the contract. It's pretty cheap to check the result for >0 if it already has to make the comparison, but I doubt that TimSort calls comparators when it doesn't have to, since the execution time of a comparator is beyond its control. So the basic reason your second example works is "you got lucky".

“Comparison method violates its general contract!”

Both these cases are problematic.

if (lhs == null || rhs == null) return 0;

If you have [123, null, 234], then you compare 123 as equal to null, null as equal to 234, and by transitivity you should get 123 equals 234. But that is not what your comparator returns.

The solution here would be to either disallow null or sort all nulls to the bottom (or top), i.e. only return 0 is both are null, otherwise return 1 or -1 (depending on the null being left or right).

return (int) (lhs.mTaskInfo.time - rhs.mTaskInfo.time);

Consider comparing Integer.MAX_VALUE + 1 to 0. The difference between the two is Integer.MAX_VALUE + 1. Casting this to int wraps to Integer.MIN_VALUE. The opposite comparison should then give you - Integer.MIN_VALUE, but that is Integer.MIN_VALUE again due to overflow.

The solution here is to use Long.compare(a,b).

Collections.sort() Comparison method violates its general contract in Java

You should start by reading the JavaDoc of Comparator.compare() to understand what that "contract" is:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y,
x)) for all x and y.

In normal terms it says that if "x is greater than y, y must be smaller than x". Sounds obvious, but is not the case in your comparator:

In your case you violate it when two Users have checkMatchConditions false, in which case compare(u1, u2) and compare(u2, u1) both return 1. Hence, there are cases where u1 is greater than u2, and u2 is greater than u1, which is a violation.
Similarely, if both Users have checkMatchConditions true, and their lastMatchDates are both null, they will also violate the contract.
In addition, because you manually try to compare the dates with isBefore, you also return -1 in both cases when two Users have checkMatchConditions true and their lastMatchDates are both equal.

In order to fix this, you should first add a natural language description of how you want the Users to be ordered. Then you can work out the comparator logic.

The error has nothing to do with the Boolean.valueOf() by the way.

Now that you explained how you want to order, have a look at this comparator:

public int compare(MiniUser u1, MiniUser u2)
{
    // order by match
    boolean u1Matches = checkMatchConditions(u1, user);
    boolean u2Matches = checkMatchConditions(u2, user);

    if (u1Matches != u2Matches)
    {
        // put matching ones first
        return u1Matches ? -1 : 1;
    }
    else if (u1Matches)
    {
        // order by dates
        boolean u1HasDate = u1.getLastMatchDate() != null;
        boolean u2HasDate = u2.getLastMatchDate() != null;

        if (u1HasDate != u2HasDate)
        {
            // put the ones without date first
            return u1HasDate ? 1 : -1;
        }
        else if (u1HasDate)
        {
            // order chronologically
            return u1.getLastMatchDate().compareTo(u2.getLastMatchDate());
        }
        else
        {
            // no dates, no order possible
            return 0;
        }
    }
    else
    {
        // both don't match, no order possible
        return 0;
    }
}

If I understood your requirements correctly, this should impose a consistent order to your elements. Note how I use Date's compareTo for the date ordering instead of doing it myself, and how I return 0 in case they are "equal" in regards to the order instead of "randomly" returning 1 or -1.

java.lang.IllegalArgumentException: Comparison method violates its general contract

Your compare() method is not transitive. If A == B and B == C, then A must be equal to C.

Now consider this case:

For A, B, and C, suppose the containsKey() method return these results:

childMap.containsKey(A.getID()) returns true
childMap.containsKey(B.getID()) returns false
childMap.containsKey(C.getID()) returns true

Also, consider orders for A.getId() != B.getId().

So,

A and B would return 0, as outer if condition will be false => A == B
B and C would return 0, as outer if condition will be false => B == C

But, A and C, could return -1, or 1, based on your test inside the if block. So, A != C. This violates the transitivity principle.

I think, you should add some condition inside your else block, that performs check similar to how you do in if block.