If you google the term ‘Comparison method violates its general contract’, you will find some articles on stackoverflow that sort of help. But these didn’t help me because like Forrest Gump, “I’m not a smart man but I know what love is”.

So anyways, I had a list of things and the call to Collections.sort was breaking which this error. After reading the replies on stackoverflow, I knew why it was breaking, but I still didn’t know why it was breaking for me and in my specific case. What I needed was the exact case which broke the transitivity contract. And my list had over fiddy items.

Now according to the posts on stackoverflow transitivity of a Comparator comparing 3 items is that if A > B and then B > C then it must be that A > C.
So if you get this exception it means that you are breaking the above contract.

What stackoverflow doesn’t say (but I think the javadoc does) is that this error seems to related to the initial sorting of the list. For example in my case, this caused a problem:

Collections.sort(myListOfThings, new ComparatorForMyListOfThings());

But this didn’t cause problems:

Collections.shuffle(myListOfThings);
Collections.sort(myListOfThings, new ComparatorForMyListOfThings());

So if you do get this problem, here is what you should do to start off:

  1. Recreate the problem
  2. Modify the code, so that just before the sort, you dump the whole list into a file (via serialization)
  3. Write new code to read this file, and re-create the list
  4. Run the list into a Sort to verify the problem exists
  5. Modify the comparator to statisfy the Java Gods
  6. ???
  7. Profit

Given that a comparator might be breaking the the transitivity thing, and we know what the rules of transitivity are, what I needed to know was which of the 3 items on my list were breaking the comparator and why. And so here is some code that will itterate over a list and do the following:

  1. Select (the next) 3 items from the list
  2. check the 3 items for the transitivity
  3. go to step 1

Since order matters, we have to select every 3 item combination from this list. So that is what the following bit of code does. It helps to identify the 3 items that are breaking the contact of transitivity. Then using just those 3 items, you can debug your comparator and finally modify it to appease the Java Gods. Here is the code to find those 3 items:


import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;

/**
 * See this blog entry yo!
 *
 * @author srasul
 *
 * @param 
 */
public class TestComparatorForTransitivity {
	private List listOfThings;
	private Comparator comparator;

	public TestComparatorForTransitivity(Collection thingsToSort, Comparator comparator) {
		if (thingsToSort.size() < 3) {
			throw new IllegalArgumentException("Collection 'thingsToSort' must have atleast 3 items: " +
					thingsToSort + ". It has only " + thingsToSort.size() + " iteam");
		}
		if (comparator == null) {
			throw new IllegalArgumentException("Comparator cannot be null yo!");
		}

		listOfThings = new ArrayList(thingsToSort);
		this.comparator = comparator;
	}

	public void doCheck() {
		for (int count = 0; count < listOfThings.size(); count++) {
			for (int i = 1; i < listOfThings.size(); i++) {
				for (int j = 2; j < listOfThings.size(); j++) {
					if ((count != i) && (i != j) && (count != j)) {
						checkComparator(listOfThings, comparator, i, j, count);
					}

				}
			}
		}

	}

	private void checkComparator(List listOfThings, Comparator comparator, int pointer1, int pointer2, int pointer3) {
		T oA = listOfThings.get(pointer1);
		T oB = listOfThings.get(pointer2);
		T oC = listOfThings.get(pointer3);
		int compareAwithB = comparator.compare(oA, oB);
		int compareBwithC = comparator.compare(oB, oC);
		int compareAwithC = comparator.compare(oA, oC);

		if (compareAwithB < 0) {
			if (compareBwithC < 0) {
				if (compareAwithC >= 0) {
					System.out.println("Got ya! #1");
					System.out.println("compare A < B: " + compareAwithB);
					System.out.println("compare B < C: " + compareBwithC);
					System.out.println("compare A < C: " + compareAwithC);
					System.out.println("A: " + oA);
					System.out.println("B: " + oB);
					System.out.println("C: " + oC);
					System.out.println("");
				}
			}
		}

		if (compareAwithB > 0) {
			if (compareBwithC > 0) {
				if (compareAwithC <= 0) {
					System.out.println("Got ya! #2");
					System.out.println("compare A > B: " + compareAwithB);
					System.out.println("compare B > C: " + compareBwithC);
					System.out.println("compare A > C: " + compareAwithC);
					System.out.println("A: " + oA);
					System.out.println("B: " + oB);
					System.out.println("C: " + oC);
					System.out.println("");
				}
			}
		}
	}
}