AList
l
may be sorted as follows.If theCollections.sort(l);List
consists ofString
elements, it will be sorted into alphabetical order. If it consists ofDate
elements, it will be sorted into chronological order. How does this happen?String
andDate
both implement theComparable
interface.Comparable
implementations provide a natural ordering for a class, which allows objects of that class to be sorted automatically. The following table summarizes some of the more important Java platform classes that implementComparable
.
Classes Implementing Comparable Class Natural Ordering Byte
Signed numerical Character
Unsigned numerical Long
Signed numerical Integer
Signed numerical Short
Signed numerical Double
Signed numerical Float
Signed numerical BigInteger
Signed numerical BigDecimal
Signed numerical Boolean
Boolean.FALSE < Boolean.TRUE
File
System-dependent lexicographic on path name String
Lexicographic Date
Chronological CollationKey
Locale-specific lexicographic If you try to sort a list, the elements of which do not implement
Comparable
,Collections.sort(list)
will throw aClassCastException
. Similarly,Collections.sort(list, comparator)
will throw aClassCastException
if you try to sort a list whose elements cannot be compared to one another using thecomparator
. Elements that can be compared to one another are called mutually comparable. Although elements of different types may be mutually comparable, none of the classes listed here permit interclass comparison.This is all you really need to know about the
Comparable
interface if you just want to sort lists of comparable elements or to create sorted collections of them. The next section will be of interest to you if you want to implement your ownComparable
type.
TheComparable
interface consists of the following method.Thepublic interface Comparable<T> { public int compareTo(T o); }compareTo
method compares the receiving object with the specified object and returns a negative integer, 0, or a positive integer depending on whether the receiving object is less than, equal to, or greater than the specified object. If the specified object cannot be compared to the receiving object, the method throws aClassCastException
.The
following class representing a person's name
implementsComparable
.To keep the preceding example short, the class is somewhat limited: It doesn't support middle names, it demands both a first and a last name, and it is not internationalized in any way. Nonetheless, it illustrates the following important points:import java.util.*; public class Name implements Comparable<Name> { private final String firstName, lastName; public Name(String firstName, String lastName) { if (firstName == null || lastName == null) throw new NullPointerException(); this.firstName = firstName; this.lastName = lastName; } public String firstName() { return firstName; } public String lastName() { return lastName; } public boolean equals(Object o) { if (!(o instanceof Name)) return false; Name n = (Name)o; return n.firstName.equals(firstName) && n.lastName.equals(lastName); } public int hashCode() { return 31*firstName.hashCode() + lastName.hashCode(); } public String toString() { return firstName + " " + lastName; } public int compareTo(Name n) { int lastCmp = lastName.compareTo(n.lastName); return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName)); } }Since this section is about element ordering, let's talk a bit more about
Name
objects are immutable. All other things being equal, immutable types are the way to go, especially for objects that will be used as elements inSet
s or as keys inMap
s. These collections will break if you modify their elements or keys while they're in the collection.- The constructor checks its arguments for
null
. This ensures that allName
objects are well formed so that none of the other methods will ever throw aNullPointerException
.- The
hashCode
method is redefined. This is essential for any class that redefines theequals
method. (Equal objects must have equal hash codes.)- The
equals
method returnsfalse
if the specified object isnull
or of an inappropriate type. ThecompareTo
method throws a runtime exception under these circumstances. Both of these behaviors are required by the general contracts of the respective methods.- The
toString
method has been redefined so it prints theName
in human-readable form. This is always a good idea, especially for objects that are going to get put into collections. The various collection types'toString
methods depend on thetoString
methods of their elements, keys, and values.Name
'scompareTo
method. It implements the standard name-ordering algorithm, where last names take precedence over first names. This is exactly what you want in a natural ordering. It would be very confusing indeed if the natural ordering were unnatural!Take a look at how
compareTo
is implemented, because it's quite typical. First, you compare the most significant part of the object (in this case, the last name). Often, you can just use the natural ordering of the part's type. In this case, the part is aString
and the natural (lexicographic) ordering is exactly what's called for. If the comparison results in anything other than zero, which represents equality, you're done: You just return the result. If the most significant parts are equal, you go on to compare the next most-significant parts. In this case, there are only two parts first name and last name. If there were more parts, you'd proceed in the obvious fashion, comparing parts until you found two that weren't equal or you were comparing the least-significant parts, at which point you'd return the result of the comparison.Just to show that it all works, here's
a program that builds a list of names and sorts them
.If you run this program, here's what it prints.import java.util.*; public class NameSort { public static void main(String[] args) { Name nameArray[] = { new Name("John", "Lennon"), new Name("Karl", "Marx"), new Name("Groucho", "Marx"), new Name("Oscar", "Grouch") }; List<Name> names = Arrays.asList(nameArray); Collections.sort(names); System.out.println(names); } }There are four restrictions on the behavior of the[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]compareTo
method, which we won't go into now because they're fairly technical and boring and are better left in the API documentation. It's really important that all classes that implementComparable
obey these restrictions, so read the documentation forComparable
if you're writing a class that implements it. Attempting to sort a list of objects that violate the restrictions has undefined behavior. Technically speaking, these restrictions ensure that the natural ordering is a total order on the objects of a class that implements it; this is necessary to ensure that sorting is well defined.
What if you want to sort some objects in an order other than their natural ordering? Or what if you want to sort some objects that don't implementComparable
? To do either of these things, you'll need to provide aComparator
an object that encapsulates an ordering. Like theComparable
interface, theComparator
interface consists of a single method.Thepublic interface Comparator<T> { int compare(T o1, T o2); }compare
method compares its two arguments, returning a negative integer, 0, or a positive integer depending on whether the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for theComparator
, thecompare
method throws aClassCastException
.Much of what was said about
Comparable
applies toComparator
as well. Writing acompare
method is nearly identical to writing acompareTo
method, except that the former gets both objects passed in as arguments. Thecompare
method has to obey the same four technical restrictions asComparable
'scompareTo
method for the same reason aComparator
must induce a total order on the objects it compares.Suppose you have a class called
Employee
, as follows.Let's assume that the natural ordering ofpublic class Employee implements Comparable<Employee> { public Name name() { ... } public int number() { ... } public Date hireDate() { ... } ... }Employee
instances isName
ordering (as defined in the previous example) on employee name. Unfortunately, the boss has asked for a list of employees in order of seniority. This means we have to do some work, but not much. The following program will produce the required list.Theimport java.util.*; public class EmpSort { static final Comparator<Employee> SENIORITY_ORDER = new Comparator<Employee>() { public int compare(Employee e1, Employee e2) { return e2.hireDate().compareTo(e1.hireDate()); } }; // Employee database static final Collection<Employee> employees = ... ; public static void main(String[] args) { List<Employee>e = new ArrayList<Employee>(employees); Collections.sort(e, SENIORITY_ORDER); System.out.println(e); } }Comparator
in the program is reasonably straightforward. It relies on the natural ordering ofDate
applied to the values returned by thehireDate
accessor method. Note that theComparator
passes the hire date of its second argument to its first rather than vice versa. The reason is that the employee who was hired most recently is the least senior; sorting in the order of hire date would put the list in reverse seniority order. Another technique people sometimes use to achieve this effect is to maintain the argument order but to negate the result of the comparison.You should always use the former technique in favor of the latter because the latter is not guaranteed to work. The reason for this is that the// Don't do this!! return -r1.hireDate().compareTo(r2.hireDate());compareTo
method can return any negativeint
if its argument is less than the object on which it is invoked. There is one negativeint
that remains negative when negated, strange as it may seem.The-Integer.MIN_VALUE == Integer.MIN_VALUEComparator
in the preceding program works fine for sorting aList
, but it does have one deficiency: It cannot be used to order a sorted collection, such asTreeSet
, because it generates an ordering that is not compatible with equals. This means that thisComparator
equates objects that theequals
method does not. In particular, any two employees who were hired on the same date will compare as equal. When you're sorting aList
, this doesn't matter; but when you're using theComparator
to order a sorted collection, it's fatal. If you use thisComparator
to insert multiple employees hired on the same date into aTreeSet
, only the first one will be added to the set; the second will be seen as a duplicate element and will be ignored.To fix this problem, simply tweak the
Comparator
so that it produces an ordering that is compatible withequals
. In other words, tweak it so that the only elements seen as equal when usingcompare
are those that are also seen as equal when compared usingequals
. The way to do this is to perform a two-part comparison (as forName
), where the first part is the one we're interested in in this case, the hire date and the second part is an attribute that uniquely identifies the object. Here the employee number is the obvious attribute. This is theComparator
that results.One last note: You might be tempted to replace the finalstatic final Comparator<Employee> SENIORITY_ORDER = new Comparator<Employee>() { public int compare(Employee e1, Employee e2) { int dateCmp = e2.hireDate().compareTo(e1.hireDate()); if (dateCmp != 0) return dateCmp; return (e1.number() < e2.number() ? -1 : (e1.number() == e2.number() ? 0 : 1)); } };return
statement in theComparator
with the simpler:Don't do it unless you're absolutely sure no one will ever have a negative employee number! This trick does not work in general because the signed integer type is not big enough to represent the difference of two arbitrary signed integers. Ifreturn e1.number() - e2.number();i
is a large positive integer andj
is a large negative integer,i - j
will overflow and will return a negative integer. The resultingcomparator
violates one of the four technical restrictions we keep talking about (transitivity) and produces horrible, subtle bugs. This is not a purely theoretical concern; people get burned by it.