Comparable, Comparators, and how Java gets by without overloaded operators

In C++, you had the opportunity to overload operators for whichever types you wanted. In 214 you may have implemented a templatized binary search tree (BST) that worked with the caveat that the provided type had to have at least its 'less than' operator overloaded. This is fine and it works, but there's no elegant way for you to enforce this invariant in code--the BST would simply break if you passed in a class that didn't have its operator properly defined. Furthermore, suppose your application changes and you want to sort your data elements in a different order. With the stock C++ approach you'd need to modify the data element's less than operator to reflect the change. But what happens if your application changes again and you want to have both of the orderings (forward and reverse) available simultaneously? Have two versions of your data element, with different operators? That probably sounds like a terrible solution because it is. Overloaded operators are one feature that many programmers (even those who would call themselves OO competent) claim to miss. But overloaded operators actually cause more problems than they solve, and Java's solution is actually much more elegant and far more modular.

It is true that not all objects can be compared to one another in any meaningful way; some data is simply not sortable. Some data has many different orderings. Some data has one obvious and universally meaningful ordering. Numbers, for instance, typically have a well understood ordering. Strings, too, have an accepted lexicographical ordering that programmers have come to expect. In Java, objects that have one commonly accepted method for comparing themselves against each other are designated to implement the Comparable interface.

The Comparable interface contains one method with the following signature:

public int compareTo(Object obj);

Note the return type. The API specifies that the int value returned must obey three rules: if the parameter is less than this object, return a number strictly less than zero ($x < 0$). If the parameter is equal to this object, return exactly 0. If the parameter is greater than this object, return a number strictly greater than zero ($x > 0$). Objects that implement this interface can be compared like this:

public class Foo implements Comparable { ... }
...
Foo f1 = new Foo();
Foo f2 = new Foo();
int r = f1.compareTo(f2);
if (r < 0) System.out.println(``foo1 < foo2'');
else if (r == 0) System.out.prinltn(``foo1 == foo2'');
else System.out.println(``foo1 > foo2'');

Note that in Java, the == operator is unilaterally used for pointer comparison. The == operator will return true only if the two variables refer to exactly the same object in memory (i.e., they point to the same location). The most commonly used class that implements Comparable is String. Remember that interfaces are types. The following code segments are legal:

Comparable c = new String();
if (c instanceof Comparable) System.out.println(``tautology'');
int r = ((Comparable)c).compareTo(``hello'');

Be warned, however, that the object versions of the primitives (Integer, Float, Double, Long, Short, Byte, Boolean) do in fact implement the Comparable interface, but they are not Comparable to each other--this has to do with precision issues. You can compare a Float against a Float, but if you try to compare a Float against an Integer, a ClassCastException will be thrown.

Objects that implement the Comparable interface can be inserted into sorted data structures in the API such as TreeMap.

This is fine, but suppose you are given some class for which you lack the ability or the privileges to modify its source to make it implement the Comparable interface, or you are in the situation whereby you wish to impose an alternate ordering to preexisting objects. The Comparable interface does not solve the BST problem suggested previously--you would need to modify the body of String's compareTo() method to sort strings in reverse asciibetical order. In this case, you can't modify String or TreeMap, so how could you put Strings into a TreeMap and have them sorted in reverse order? The answer is by introducing a third party object that will do the comparison for you.

A Comparator is an independent class which contains one method which takes two parameters--these two parameters are the two objects being compared. Where the compareTo() method in Comparable always uses the invocation target as one of the two objects being compared (i.e., the object on the left of the .), a comparator takes both sides of the comparison as parameters. In Java, comparators are defined by the Comparator interface, which contains a compare method with this signature:

public int compare(Object o1, Object o2);

A typical Comparator class will look like this:

public class MyComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        // code to compare o1 against o2 goes here
    }
}

Observe that to be as generic as possible, the parameters that the compare method takes are both Objects, but typically a comparator is designated for a specific type. Usually the first thing the compare() method will do is cast the parameters into the target types. For instance, let's write a comparator for Strings that imposes reverse ordering:

public class StringReverseComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        String s1 = (String)o1;
        String s2 = (String)o2;
        int r = s1.compareTo(s2);
        if (r < 0) return Math.abs(r);
        else if (r == 0) return 0;
        else return -r;
    }
}

It's easy to see that this code can be reduced: all we're doing is swapping the sign of the result of the compareTo() method for the two Strings. A better version would be:

public class StringReverseComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        String s1 = (String)o1;
        String s2 = (String)o2;
        return -s1.compareTo(s2);
    }
}

However, to be even more generic, we can observe that this code would work for any two objects that implement Comparable. In fact, at a minimum, it would work for any two objects as long as the first parameter implements Comparable. (By work, I mean execute without throwing an exception). Granted, o1 and o2 should probably not just be Comparable but also be the same type. We can check that programmatically, but for brevity's sake let's trust the user (cardinal rule in software engineering: never trust the user). A still better version:

public class ReverseComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        return -((Comparable)o1).compareTo(o2);
    }
}

We can still make another improvement. Here, we are reversing the ordering imposed by the compareTo() method only for objects that implement Comparable. But remember the entire reason for inventing Comparators in the first place--not all objects are comparable! We might want to reverse an ordering imposed by another comparator. Thus, what we really want to do is compose our ReverseComparator out of another comparator. Consider this implementation:

public class ReverseComparator implements Comparator {
    private Comparator comp;
    public ReverseComparator() { this(null); }
    public ReverseComparator(Comparator comp) { this.comp = comp; }
    public int compare(Object o1, Object o2) {
        if (comp != null) return -comp.compare(o1,o2);
        else return -((Comparable)o1).compareTo(o2);
    }
}

Now we have a comparator that can handle both situations--if you create a ReverseComparator based on some other Comparator, the result will be the reversal of that comparator's ordering. Otherwise, if you pass in nothing (or null), it will assume that the objects you pass it implement Comparable. (If they don't, a ClassCastException will be thrown).

Now that you see how a Comparator is implemented, consider how a TreeMap could use one. Taking a look at the docs for TreeMap, you will notice that TreeMap has a constructor which takes a Comparator as a parameter. By passing in an instance of our ReverseComparator, TreeMap will use that comparator whenever it has to make a comparison between two objects. It will use this comparator to figure out where in the tree each object belongs. TreeMap will sort a given object x as first in its ordering if, for all other objects y in the map, comp.compare(x,y) < 0 where comp is the comparator passed in to the TreeMap at creation time. Likewise, when searching the TreeMap for a given object x, the TreeMap will report a successful search if it finds some other object y in the map such that comp.compare(x,y) == 0. You can make TreeMap (or any other sorted structure available in Java) do amazing and varied things by altering the comparator you pass into it. For instance, you could easily create a ``black hole'' object by passing a TreeMap a comparator that never returns 0. You could add objects all day long and it would sort them properly--iterating over the objects in the Map would produce the proper ordering. But any object you tried to search for would be reported as not existing in the tree because the comparator is incapable of returning 0. The bulk of your first project will be tricking TreeMap into behaving like plenty of other things by playing tricks with the Comparators you pass it.