Thursday, June 12, 2014

Comparators

This post is part of a series on Comparing Objects.

Some things lend themselves to default ordering, such as sorting users by their alphabetized last names. Yet users are often sorted by other criteria, such as the number of purchases they make per year, the amount their account is in debit, or what time they clicked the "purchase" button during a limited promotion. To represent this in Java, simply define a comparator for each context:
enum UserByPromoClick implements Comparator<User> {
    INSTANCE;
    public int compare(User left, User right) {
        ...
    }
}

enum UserByPurchases implements Comparator<User> {
    ...

enum UserByDebit implements Comparator<User> {
    ...
Implementation note: compare(left, right) and compareTo(other) are both instance methods, which means you need to create an instance of the appropriate Comparator in order to use them.  Most comparators are immutable and unchanging.  This means they should be implemented as Enums with a single immutable instance shared and reused by all clients.

Various sort orders are often combined. Two accounts equally in debit could be sorted to show up next to each other on an expense report. Their names would only be used as the "tie breaker" in this ordering.
public int compare(User left, User right) {
    // Assuming getPromoClickMs returns Integer.MAX_VALUE
    // if the user didn't click on the promo.
    if (left.getPromoClickMs() > right.getPromoClickMs()) { return 1; }
    if (left.getPromoClickMs() < right.getPromoClickMs()) { return -1; }

    // In a tie, sort by name instead.
    return UserByName.compare(left, right);
}
The implementation of Objects.equals(left, right) performs a referential equality check for speed and to ensure that each object is equal to itself.  This has the side effect that if someone passes compare(null, null) it returns true, which makes sense some: undefined is undefined.  But should we ever compare anything to null? For a while I thought, "What harm could come from just sorting nulls last?"

Sortorder

What harm indeed!  Really, there is no meaningful way to compare a value to null because null represents "undefined." Well, isGreaterThan(other) can meaningfully return false if other is null, but the general-purpose compare(left, right) method cannot.  It must return less-than (any negative int), greater-than (any positive int), or equal (0). The only rational thing to do if either parameter to the compare(a, b) method is null is to throw an exception.
if (left == null) {
    throw new IllegalArgumentException("Can't compare nulls");
}
if (left == right) { return 0; } // Also ensures right != null
If your class can be represented as an integer, compare() could be implemented as a simple subtraction.  Just keep in mind that if your subtraction could exceed Integer.MIN_VALUE, it can roll and give you a positive result instead of a negative one. So if that could happen, you must use greater-than/less-than comparasions instead of subtraction.
int ret = left.getPromoClickMs() - right.getPromoClickMs();
if (ret != 0) { return ret; }

// In a tie, sort by name instead.
return UserByName.compare(left, right);
You can have as many repetitions of this kind of thing as you want:
ret = Xxxxx.compare(this, that);
if (ret != 0) { return ret; }

Persistence and Proxy Objects

When implementing a Comparator (as opposed to Comparable), then neither object can be trusted to be initialized and get/set should be used instead of direct access to instance fields on both objects. If you implement your Comparator as a separate class and your fields are private, the compiler will enforce this for you. But for Comparable and for Comparators implemented in the same class file as the object they are comparing, the compiler will NOT warn you, so you must be very careful.