First of all I know that this issue was described in many other threads. However I was not able to find and answer to the question, why this error is not always thrown?
Let me describe what I mean. I have written some sample code to illustrate this :
public class Mushroom {
public int size;
public Mushroom(int size) {
this.size = size;
}
@Override
public boolean equals(Object obj) {
//this is intentionally false - read in description
return false;
}
}
dsa
public class MushroomComparator implements Comparator<Mushroom> {
@Override
public int compare(Mushroom o1, Mushroom o2) {
// here is the code which breaks the contract
if (o1.size < o2.size){
return 1;
}else if(o1.size >o2.size){
return -1;
}
return 1;
}
}
and finally test for comparison:
public class ComparisonTest {
public static void main(String[] args) {
// System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
List<Mushroom> forest = new ArrayList<>();
for(int i =0; i<18; i++){
Mushroom mushroom1 = new Mushroom(1);
Mushroom mushroom2 = new Mushroom(3);
Mushroom mushroom3 = new Mushroom(2);
forest.add(mushroom1);
forest.add(mushroom2);
forest.add(mushroom3);
}
Collections.sort(forest, new MushroomComparator());
}
}
During runtime we will receive this described issue
java.lang.IllegalArgumentException: Comparison method violates its general contract!
According to documentation of Collections.sort method :
(optional) if the implementation detects that the natural ordering of the list elements is found to violate the Comparable contract
So let's answer the question what is this contract in documentation of Comparable (in my example I use Comparator, but from the documentation it should fulfill the same requirements)
The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y
This rule I intentionally break to get error about which I'm writing about. This is one of the rule which implementation of compareTo method should follow. The rest of them are described in documentation, but generally speaking as I understand well documentation equivalence relation should be fulfilled
It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, and that the natural ordering is a total order on C
What is now what really bothers me is a result of change to iterations number in my test method. If you change number from 18 to 22 then ... exception will not be thrown. This exception is described as Optional so it does mean that sometimes this exception will be thrown, and sometimes no. I was not diving deeply into new implementation of sorting algorithm (TimSort) (change of sort agorithm since Java 7). I understand that it could be mabye some CPU consuming to check every set of data for breaking comparator contract, but what is an intetion to sometimes shows that and sometimes no. It could be really missleading.
Morover I can change the implementation of compare method to simply .. return 1. According to the documentation it should break the contract. But it isn't. In documentation stays also something about the contract with equals method but it not really needed
It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y))
And to check it in my example I've implemented equals method to return always false. With this I was sure that equals method doesn't impose on breaking comparator contract.
Now my question is : What is really contract of comparator (in context of breaking it) ? Why for some set of data this exception is thrown and for other not ? Maybe I'm missing something ? And last but not least - which rules exatcly need to be broken to throw this exception ?
Just to note, solution for this, could be turning off this new implementation of sort algorithm what is described here and commented in my sample code.
