Collections - Java: The Good Parts - page 122

Or we could take a look at the collection classes to see if there is anything there that can help
us. And, what do you know, there is. In particular, there is an interface for a SortedSet , and
a TreeSet class that implements this interface. The SortedSet will give us an Iterator that
will present the members of the set in increasing order, and the TreeSet is an implementation
of that interface that backs the set with a Tree . Even better, we can create the TreeSet spe-
cifying a Comparator object, which will determine the order of the objects in the SortedSet .
Given the kinds of comparison that statistics weenies [ 27 ] like to use, being able to specify vari-
ous orders (batters by on-base percentage and batting average minus walks) sounds like just
the ticket.
Let's start with the Comparator object. The idea of a comparator is to supply an implement-
ation of an interface that contains two methods. The first, compare() , allows any two objects
of the appropriate type to be compared; it will return a negative number if the first object is
less than the second, a positive if the first number is greater than the second, and zero if the
first has the same value as the second. The second method is equals() , which should return
true if the two objects are equal and false if they are not.
This seems pretty simple, but there are some rules that must be followed. In particular, the
usual rules of logic should apply. If object1 is less than object2 , which in turn is less than
object3 , then object1 had better be less than object3 . And if object1 is equal to object2 and
object2 is equal to object3 , then object1 had better be equal to object3 . You can write a com-
parator in which these rules are not observed, but if you do, you will almost certainly get what
you deserve. It's a really bad idea to mess with basic logic, so unless you are a trained profes-
sional logician, don't do it.
This is actually a special case of the more general problem that has been introduced in other,
less fortunate languages by allowing operator overloading. Although it seems like a good idea
to allow users to extend the notion of, say, the + operator to objects such as complex numbers
or vectors, allowing this tempts the less disciplined to overload the operators in ways that vi-
olate the logic of the operator. So when overloading + , one should ensure that the usual rules
of arithmetic apply, so that, say, a + b - b = a remains true. There are some experiment-
al languages that have introduced mechanisms that enforce such a requirement, but without
these mechanisms it is up to the programmer to ensure that the usual conventions are followed.
Java doesn't have operator overloading, but it does have a user-defined equality operator (the
equals() method), the comparator, and the hashcode() method, all of which must be imple-
mented in such a way as to retain the basic rules of those operations.
It's also best if the implementation of a comparator gives a full ordering of the objects being
compared. This means that any two objects are such that either they are equal, or one is great-