Confusing Comparable- & Comparator-Contract

Read here more about the Confusing Comparable- & Comparator-Contract in Java today. I recently came accross the following exception, thrown by the Java Runtime Environment:

“Comparison method violates its general contract!”

The Exception occurred in a Comparable-implementation looking similar as the following code, when Collections.sort() was invoked on an ArrayList of the Foo type:

public class Foo implements Comparable<Bar> {

...

  @Override
  public int compareTo(Bar bar) {
    Date thisDate = this.getCreateDate();
    Date otherDate = bar.getCreateDate();
    if (thisDate.after(otherDate)) {
      return -1;
    }
    return 1;
  }
  ...
}

I was a bit confused, because as I knew a comparator doesn’t necessarily have to be consistent with equals (see here). The same situation we have when implementing the Comparable interface (see here).

Until Java 1.6, sort functionality was fine with equal-inconsistent Comparator- / Comparable-implementations. Even if your Comparable / Comparator implementations returned the same non-zero integer value for equal objects, Collections.sort(..) would have been working fine. Not now, after timsort – a better-performing sorting algorithm by Tim Peter in Python – was introduced by Oracle with Java 7 to be the default sorting algorithm, whose implementation obviously needs the Comparable- and Comparator-interfaces to be consistent with equals. After not being able to reproduce the Exception mentioned above for some time, I finally managed to write a sample Project, which is able to demonstrate the issue. You need three classes:

File 1: CollectionsAutomatedTest.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsAutomatedTest {

	private static final int CST_MAX_INT = 10;
	private static final int CST_MAX_SIZE = 100000;

	public static void main(String[] args) {
		System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
		List<Foo> fooList = new ArrayList<>();

		while (fooList.size() < CST_MAX_SIZE) {
			int i = (int) (Math.random() * CST_MAX_INT);
			fooList.add(new Foo(i));
		}
		System.out.println("now sorting list...");

		// a) first try sort using Comparable implementation of Foo
		try {
			Collections.sort(fooList, new FooComparator());
			System.out.println("successful sorted by Comparable<T>.");
		}
		catch (IllegalArgumentException e) {
			System.out.println("boooom! Sort by Comparable<T> fails, if not consistent with equals.");
		}

		// b) second try sorting using Comparator implementation of FooComparator
		try {
			Collections.sort(fooList, new FooComparator());
			System.out.println("successful sorted by Comparator<T>.");
		}
		catch (IllegalArgumentException e) {
			System.out.println("boooom! Sort by Comparator<T> fails, if not consistent with equals.");
		}
	}
}

File 2: Foo.java

public class Foo implements Comparable<Foo> {

	private int orderId = 0;

	public Foo(int orderId) {
		this.orderId = orderId;
	}

	public int getOrderId() {
		return orderId;
	}

	@Override
	public int compareTo(Foo o) {
		if (this.orderId < o.getOrderId()) {
			return -1;
		}
		return 1;
	}

}

File 2: FooComparator.java

import java.util.Comparator;

public class FooComparator implements Comparator<Foo> {

	@Override
	public int compare(Foo o1, Foo o2) {
		if (o1.getOrderId() < o2.getOrderId()) {
			return -1;
		}
		return 1;
	}

}

Findings

When running the main() under a Java 7 based runtime environment – I tested it with JDK 1.7.0_21 – you’ll get the following output:

now sorting list...
boooom! Sort by Comparable<T> fails, if not consistent with equals.
boooom! Sort by Comparator<T> fails, if not consistent with equals.

 

When running the main() under a Java 1.6 based runtime environment – I tested it with JDK 1.6.0_37 – you’ll get the following output:

now sorting list...
successful sorted by Comparable<T>.
successful sorted by Comparator<T>.

This only proves empirically, that the Sort-Functionality requires the Comparator- and Comparable-interfaces to be consistent with equals to work as expected under JDK 1.7.0_21, but not under JDK 1.6.0_37. To demonstrate, that this issue is related to timsort, let us run the application under JDK 1.7.0_21 and disable timsort using the useLegacyMergeSort-system property. Just add the following line to be the first line within the main-method:

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

and run the application again. This would produce the following output even under JDK 1.7.0_21:

now sorting list...
successful sorted by Comparable<T>.
successful sorted by Comparator<T>.

Consequences

In words: The introduction of timsort changed the behaviour of Collections.sort() / Arrays.sort(). Starting from Java 7 you have the following options:

  • either make sure, your Comparator- / Comparable-interfaces are consistent with equals (see example beneath) or
  • use the ‘-Djava.util.Arrays.useLegacyMergeSort=true’ switch to disable timsort

To make the compareTo()-implementation consistent with equals, just make sure, that the method not only provides negative / positive integers for smaller / bigger object but also returns 0 for objects where a.equals(b) or b.equals(a) would return true. To continue with the example from the beginning (where no date may ever be equal to null), this would turn out to be:

public class Foo implements Comparable<Bar> {

...

  @Override
  public int compareTo(Bar bar) {
    Date thisDate = this.getCreateDate();
    Date otherDate = bar.getCreateDate();
    if (thisDate.after(otherDate)) {
      return -1;
    } else if (thisDate.before(otherDate)) {
      return 1;
    }
    return 0;
  }
  ...
}
Share on FacebookShare on LinkedInShare on Google+Tweet about this on TwitterEmail this to someone
PDF herunterladen
Posted in Software, Software Architecture, Uncategorized