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

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 <T> void checkConsitency(final List<T> dailyReports, final Comparator<T> comparator) {
  final Map<T, List<T>> objectMapSmallerOnes = new HashMap<T, List<T>>();

  iterateDistinctPairs(dailyReports.iterator(), new IPairIteratorCallback<T>() {
    /**
     * @param o1
     * @param o2
     */
    @Override
    public void pair(T o1, T o2) {
      final int diff = comparator.compare(o1, o2);
      if (diff < Compare.EQUAL) {
        checkConsistency(objectMapSmallerOnes, o1, o2);
        getListSafely(objectMapSmallerOnes, o2).add(o1);
      } else if (Compare.EQUAL < diff) {
        checkConsistency(objectMapSmallerOnes, o2, o1);
        getListSafely(objectMapSmallerOnes, o1).add(o2);
      } else {
        throw new IllegalStateException("Equals not expected?");
      }
    }
  });
}

/**
 * @param objectMapSmallerOnes
 * @param o1
 * @param o2
 */
static <T> void checkConsistency(final Map<T, List<T>> objectMapSmallerOnes, T o1, T o2) {
  final List<T> 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 <Key> 
 * @param <Value> 
 * @return List<Value>
 */ 
public static <Key, Value> List<Value> getListSafely(Map<Key, List<Value>> keyMapValues, Key key) {
  List<Value> values = keyMapValues.get(key);

  if (values == null) {
    keyMapValues.put(key, values = new LinkedList<Value>());
  }

  return values;
}

/**
 * @author Oku
 *
 * @param <T>
 */
public interface IPairIteratorCallback<T> {
  /**
   * @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 <T> void iterateDistinctPairs(final Iterator<T> it, IPairIteratorCallback<T> callback) {
  List<T> list = Convert.toMinimumArrayList(new Iterable<T>() {

    @Override
    public Iterator<T> iterator() {
      return it;
    }

  });

  for (int outerIndex = 0; outerIndex < list.size() - 1; outerIndex++) {
    for (int innerIndex = outerIndex + 1; innerIndex < list.size(); innerIndex++) {
      callback.pair(list.get(outerIndex), list.get(innerIndex));
    }
  }
}

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

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

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

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

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

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

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

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

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

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

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

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

Examples related to java

Examples related to comparator