Comparators – part 2

In the post Comparators and sorted sets I discuss the “consistency with equals” rule, and the importance of following it when working with sorted sets.  Lately I saw a few cases of another faulty comparator implementation.  

As usual, I will demonstrate it with an example. Suppose we have a bank account class that encapsulates, among other things, the account id and the balance, in cents:  

 

public class Account {
    private int accountId;
    private int balanceCents;
 
    public Account(int accountId, int cents) {
        this.accountId = accountId;
        this.balanceCents = cents;
    }
 
    public int getBalanceCents() {
        return balanceCents;
    }
 
    public int getAccountId() {
        return accountId;
    }
 
    public String toString() {
        return accountId + ":" + balanceCents;
    }
}

We want to be able to sort accounts in ascending balance order, so we implement a comparator for that purpose:  

 

private class BalanceComparator implements Comparator<Account> {
    public int compare(Account o1, Account o2) {
        return o1.getBalanceCents() - o2.getBalanceCents();
    }
}

Since the compare method should return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second, we simply subtract the balances in order to determine which one is greater. 

Let’s test this implementation: 

 

Account[] items = {new Account(1,100),new Account(2,-200), new Account(3,1000),new Account(4,0)};
Arrays.sort(items, new BalanceComparator());
System.out.println(Arrays.toString(items));

The output is ordered correctly:

[2:-200, 4:0, 1:100, 3:1000]

However, there are some cases where Arrays.sort() fails to sort the array correctly. This happens with the following input array for example:

Account[] items = {new Account(1,2000000000),new Account(2,-2000000000), new Account(3,1000),new Account(4,0)};

Now the output is not as expected:

[1:2000000000, 2:-2000000000, 4:0, 3:1000]

What did we do wrong? The flaw lies in the comparator implementation. Although it is very tempting to use the elegant one-liner implementation instead of condition statements, it turns out to be wrong in our case. Like all numeric primitives, ints have a limited range (-2^31 to 2^31-1), so subtracting two values may result in an arithmetic overflow. When this happens, no runtime exception is thrown, and the returned value has a wrong magnitude and sign. For example, if we subtract the int -2147483648 from the int 2147483647 we get -1 (which is the unsigned interpretation of the correct result: 2^32-1). In the code above, a wrong sign means wrong decisions of the sorting algorithm.

If we know for sure that an int overflow is impossible (e.g. if the numbers being compared are always positive ints, or if we compare bytes), then we can use the one line comparison technique. In all other cases, we must use explicit conditions:

public int compare(Account o1, Account o2) {
    int balance1 = o1.getBalanceCents();
    int balance2 = o2.getBalanceCents();   
    if (balance1 > balance2)
        return 1;
    if (balance1 < balance2)
        return -1;
    return 0; 
}