Section 3.1. Comparable

3.1. Comparable

The interface Comparable<T> contains a single method that can be used to compare one object to another:

 interface Comparable<T> {   public int compareTo(T o); } 

The compareTo method returns a value that is negative, zero, or positive depending upon whether the argument is less than, equal to, or greater than the given object. When a class implements Comparable, the ordering specified by this interface is called the natural ordering for that class.

Typically, an object belonging to a class can only be compared with an object belonging to the same class. For instance, Integer implements Comparable<Integer>:

 Integer int0 = 0; Integer int1 = 1; assert int0.compareTo(int1) < 0; 

The comparison returns a negative number, since 0 precedes 1 under numerical ordering. Similarly, String implements Comparable<String>:

   String str0 = "zero";   String str1 = "one";   assert str0.compareTo(str1) > 0; 

This comparison returns a positive number, since "zero" follows "one" under alphabetic ordering.

The type parameter to the interface allows nonsensical comparisons to be caught at compile time:

 Integer i = 0; String s = "one"; assert i.compareTo(s) < 0;  // compile-time error 

You can compare an integer with an integer or a string with a string, but attempting to compare an integer with a string signals a compile-time error.

Comparison is not supported between arbitrary numerical types:

 Number m = new Integer(2); Number n = new Double(3.14); assert m.compareTo(n) < 0;  // compile-time error 

Here the comparison is illegal, because the Number class does not implement the Compar-able interface.

Consistent with Equals Usually, we require that two objects are equal if and only if they compare as the same:

 x.equals(y)  if and only if  x.compareTo(y) == 0 

In this case, we say that the natural ordering is consistent with equals.

It is recommended that when designing a class you choose a natural ordering that is consistent with equals. This is particularly important if you use the interfaces SortedSet or SortedMap in the Collections Framework, both of which compare items using natural ordering. If two items that compare as the same are added to a sorted set, then only one will be stored, even if the two items are not equal; the same is true for a sorted map. (You may also specify a different ordering for use with a sorted set or sorted map, using a comparator as described in Section 3.4; but in that case the specified ordering should again be consistent with equals.)

Almost every class in the Java core libraries that has a natural ordering is consistent with equals. An exception is java.math.BigDecimal, which compares as the same two decimals that have the same value but different precisions, such as 4.0 and 4.00. Section 3.3 gives another example of a class with a natural ordering that is not consistent with equals.

Comparison differs from equality in that is does not accept a null argument. If x is not null, x.equals(null) must return false, while x.compareTo(null) must throw a NullPointerException.

We use standard idioms for comparison, writing x.compareTo(y) < 0 instead of x < y, and writing x.compareTo(y) <= 0 instead of x <= y. It is perfectly sensible to use the last of these even on types such as java.math.BigDecimal, where the natural ordering is not consistent with equals.

Contract for Comparable The contract for the Comparable<T> interface specifies three properties. The properties are defined using the sign function, which is defined such that sgn(x) returns -1, 0, or 1, depending on whether x is negative, zero, or positive.

First, comparison is anti-symmetric. Reversing the order of arguments reverses the result:

 sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) 

This generalizes the property for numbers: x < y if and only if y < x. It is also required that x.compareTo(y) raises an exception if and only if y.compareTo(x) raises an exception.

Second, comparison is transitive. If one value is smaller than a second, and the second is smaller than a third, then the first is smaller than the third:

 if x.compareTo(y) < 0 and y.compareTo(z) < 0 then x.compareTo(z) < 0 

This generalizes the property for integers: if x < y and y < z then x < z.

Third, comparison is a congruence. If two values compare as the same then they compare the same way with any third value:

 if x.compareTo(y) == 0 then sgn(x.compareTo(z)) == sgn(y.compareTo(z)) 

This generalizes the property for integers: if x == y then x < z if and only if y < z. Presumably, it is also required that if x.compareTo(y) == 0 then x.compareTo(z) raises an exception if and only if y.compareTo(z) raises an exception, although this is not explicitly stated.

It is strongly recommended that comparison be compatible with equality:

 x.equals(y)  if and only if  x.compareTo(y) == 0 

As we saw earlier, a few exceptional classes, such as java.math.BigDecimal, violate this constraint.

However, it is always required that comparison be reflexive. Every value is compares as the same as itself:

 x.compareTo(x) == 0 

This follows from the first requirement, since taking x and y to be the same gives us sgn(x.compareTo(x)) == -sgn(x.compareTo(x)).

Look Out for This! It's worth pointing out a subtlety in the definition of comparison. Here is the right way to compare two integers:

 class Integer implements Comparable<Integer> {   ...   public int compareTo(Integer that) {     return this.value < that.value ? -1 :            this.value == that.value ? 0 : 1 ;   }   ... } 

The conditional expression returns -1, 0, or 1 depending on whether the receiver is less than, equal to, or greater than the argument. You might think the following code would work just as well, since the method is permitted to return any negative integer if the receiver is less than the argument:

 class Integer implements Comparable<Integer> {   ...   public int compareTo(Integer that) {     // bad implementation -- don't do it this way!     return this.value - that.value;   }   ... } 

But this code may give the wrong answer when there is overflow. For instance, when comparing a large negative value to a large positive value, the difference may be more than the largest value that can be stored in an integer, Integer.MAX_VALUE.