“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;
}

Answer 1

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));
    }
  }
}

Answer 2

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)

Answer 3

In simple terms, for instance if compareParents(s1, s2) == -1 than compareParents(s2, s1) == 1 is expected. With your code it's not always true.

Specifically if s1.getParent() == s2 && s2.getParent() == s1. It's just one of the possible problems.

Answer 4

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 > s1 
    return 1;
s1 < s2 
    return -1;

Answer 5

Just because this is what I got when I Googled this error, my problem was that I had

if (value < other.value)
  return -1;
else if (value >= other.value)
  return 1;
else
  return 0;

the value >= other.value should (obviously) actually be value > other.value so that you can actually return 0 with equal objects.

Answer 6

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 > compareTfidf.tfidf)
        return -1;
    else if (this.tfidf < 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) < .000000001)
        return 0;
    if (this.tfidf > compareTfidf.tfidf)
        return -1;
    else if (this.tfidf < compareTfidf.tfidf)
        return 1;
    return 0;
}