Comparison method violates its general contract

Question

Can someone explain me in simple terms  why does this code throw an exception   Comparison method violates its general contract    and how do I fix it   private int compareParents Foo s1  Foo s2        if  s1 getParent      s2  return -1      if  s2 getParent      s1  return 1      return 0

User · Answer

You can t compare object data like this s1 getParent      s2 - this will compare the object references  You should override equals function for Foo class and then compare them like this s1 getParent   equals s2

User · Answer

Editing VM Configuration worked for me   -Djava util Arrays useLegacyMergeSort true

User · Answer

Your comparator is not transitive   Let A be the parent of B  and B be the parent of C  Since A  gt  B and B  gt  C  then it must be the case that A  gt  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

User · Answer

I ve seen this happen in a piece of code where the often recurring check for null values was performed   if   A  null    amp  amp    B  null     return  1   WRONG  two null values should return 0

User · Answer

In my case I was doing something like the following   if  a someField    null        return 1     if  b someField    null        return -1     if  a someField equals b someField         return a someOtherField compareTo b someOtherField      return a someField compareTo b someField     What I forgot to check was when both a someField and b someField are null

User · Answer

Even if your compareTo is holds transitivity in theory  sometimes subtle bugs mess things up    such as floating point arithmetic error  It happened to me  this was my code   public int compareTo tfidfContainer compareTfidf          descending order     if  this tfidf  gt  compareTfidf tfidf          return -1      else if  this tfidf  lt  compareTfidf tfidf          return 1      else         return 0          The transitive property clearly holds  but for some reason I was getting the IllegalArgumentException  And it turns out that due to tiny errors in floating point arithmetic  the round-off errors where causing the transitive property to break where they shouldn t  So I rewrote the code to consider really tiny differences 0  and it worked   public int compareTo tfidfContainer compareTfidf          descending order     if   this tfidf - compareTfidf tfidf   lt   000000001          return 0      if  this tfidf  gt  compareTfidf tfidf          return -1      else if  this tfidf  lt  compareTfidf tfidf          return 1      return 0

User · Answer

Java does not check consistency in a strict sense  only notifies you if it runs into serious trouble  Also it does not give you much information from the error   I was puzzled with what s happening in my sorter and made a strict consistencyChecker  maybe this will help you           param dailyReports     param comparator     public static  lt T gt  void checkConsitency final List lt T gt  dailyReports  final Comparator lt T gt  comparator      final Map lt T  List lt T gt  gt  objectMapSmallerOnes   new HashMap lt T  List lt T gt  gt        iterateDistinctPairs dailyReports iterator    new IPairIteratorCallback lt T gt                      param o1         param o2              Override     public void pair T o1  T o2          final int diff   comparator compare o1  o2         if  diff  lt  Compare EQUAL            checkConsistency objectMapSmallerOnes  o1  o2           getListSafely objectMapSmallerOnes  o2  add o1           else if  Compare EQUAL  lt  diff            checkConsistency objectMapSmallerOnes  o2  o1           getListSafely objectMapSmallerOnes  o1  add o2           else           throw new IllegalStateException  Equals not expected                                    param objectMapSmallerOnes     param o1     param o2     static  lt T gt  void checkConsistency final Map lt T  List lt T gt  gt  objectMapSmallerOnes  T o1  T o2      final List lt T gt  smallerThan   objectMapSmallerOnes get o1      if  smallerThan    null        for  final T o   smallerThan          if  o    o2            throw new IllegalStateException o2      cannot be smaller than     o1     if it s supposed to be vice versa                   checkConsistency objectMapSmallerOnes  o  o2                        param keyMapValues      param key      param  lt Key gt       param  lt Value gt       return List lt Value gt       public static  lt Key  Value gt  List lt Value gt  getListSafely Map lt Key  List lt Value gt  gt  keyMapValues  Key key      List lt Value gt  values   keyMapValues get key      if  values    null        keyMapValues put key  values   new LinkedList lt Value gt             return values             author Oku        param  lt T gt      public interface IPairIteratorCallback lt T gt                param o1       param o2         void pair T o1  T o2                 Iterates through each distinct unordered pair formed by the elements of a given iterator        param it     param callback     public static  lt T gt  void iterateDistinctPairs final Iterator lt T gt  it  IPairIteratorCallback lt T gt  callback      List lt T gt  list   Convert toMinimumArrayList new Iterable lt T gt            Override     public Iterator lt T gt  iterator           return it                  for  int outerIndex   0  outerIndex  lt  list size   - 1  outerIndex          for  int innerIndex   outerIndex   1  innerIndex  lt  list size    innerIndex            callback pair list get outerIndex   list get innerIndex

User · Answer

If compareParents s1  s2     -1 then compareParents s2  s1     1 is expected  With your code it s not always true    Specifically if s1 getParent      s2  amp  amp  s2 getParent      s1   It s just one of the possible problems

User · Answer

Just because this is what I got when I Googled this error  my problem was that I had   if  value  lt  other value    return -1  else if  value  gt   other value    return 1  else   return 0    the value  gt   other value should  obviously  actually be value  gt  other value so that you can actually return 0 with equal objects

User · Answer

In our case were were getting this error because we had accidentally flipped the order of comparison of s1 and s2   So watch out for that   It was obviously way more complicated than the following but this is an illustration   s1    s2        return 0  s2  gt  s1      return 1  s1  lt  s2      return -1

User · Answer

In my case  it was an infinite sort  That is  at first the line moved up according to the condition  and then the same line moved down to the same place  I added one more condition at the end that unambiguously established the order of the lines

User · Answer

The violation of the contract often means that the comparator is not providing the correct or consistent value when comparing objects  For example  you might want to perform a string compare and force empty strings to sort to the end with   if   one length      0         return 1                       empty string sorts last   if   two length      0         return -1                      empty string sorts last                     return one compareToIgnoreCase  two      But this overlooks the case where BOTH one and two are empty - and in that case  the wrong value is returned  1 instead of 0 to show a match   and the comparator reports that as a violation  It should have been written as   if   one length      0         if   two length      0             return 0                   BOth empty - so indicate           return 1                       empty string sorts last   if   two length      0         return -1                      empty string sorts last                     return one compareToIgnoreCase  two

[java] "Comparison method violates its general contract!"

Examples related to java

Examples related to comparator