Avoid subtraction based comparison between integers

Before I say anything I want to share with you a code snippet that is a simplified version of something I have recently wrote in my work. There is a small, yet painful bug in this code… can you see it?

public static class Point implements Comparable<Point> {
    private int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point other) {
        if (this.x != other.x) {
            return this.x - other.x;
        } else {
            return this.y - other.y;
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return (this.x == other.x && this.y == other.y);
    }

    @Override
    public int hashCode() {
        return 31 * x + y;
    }
}

This is a simple value class represanting a point. At first glance everything is good with it: the hash function is not sophisticated, but it is correct and legal. The equals() method is written ‘by the book’ so it is probably OK. The class implements Comparable interface and defines a lexicographic order of the points – the code of compareTo() is standard and fulfills the contract of the interface. All three methods are compatible with each other: hash codes of equal points are equal, comparisons are transitive, if A.compareTo(B) == 0 then A.equals(B)… Basically all is fine, so where is the bug? Is there any bug at all?
Unfortunatelly there is a bug in this code. What is worse you probably read about it many times (’Effective Java’ item 11, ‘Java Puzzlers’ puzzle 65, the list goes on an on…). The problem with this code is that substraction based comparators are BAD as they often exposes you to danger of an overflow. This is what happens in this case – see the following:

public static void main(String[] args) {
    Point pZero  = new Point(0, 0);
    Point pPlus  = new Point(2000000000, 0);
    Point pMinus = new Point(-2000000000, 0);

    System.out.println( pPlus.compareTo(pZero) > 0 );
    System.out.println( pZero.compareTo(pMinus) > 0 );
    System.out.println( pPlus.compareTo(pMinus) > 0 );
  }

We are comparing in this code three points. When you look at the declaration of those object you can already see the order of them: pPlus > pZero > pMinus. Just to be sure we check it by printing to console the result of compareTo() function. If you execute this code you’ll get that as expected ‘true’ for pPlus > pZero and ‘true’ for pZero > pMinus. The suprizing thing is the last comparison that evaluates to false. This is because of the integer overflow: in pPlus.compareTo(pMinus) the result value is 2000000000 – (-2000000000) == -294967296! Scary, right?

Implementing compareTo() : Sorting in natural ordering using compareTo()

Defining the criteria for sorting

Suppose we have list of Employees. We have to sort them. By default, you can't sort it, until you define some criteria. Say you define sorting as first name of employee, or you may say sort on the basis of employee id or their salary. So first thing is we have to define some criteria for sorting. This defines "natural ordering" on which sort can be done.

How to define "natural order" in java?

For this, we have to implement Comparable interface, which has compareTo method, which decides how we put natural ordering on the object.

Example:

Employee’s natural ordering would be done according to the employee id. For that, above Employee class must be altered to add the comparing ability as follows.

public class Employee implements Comparable<Employee> {
    private int empId;
    private String name;
    private int age;
    
    /**
     * Compare a given Employee with this object.
     * If employee id of this object is 
     * greater than the received object,
     * then this object is greater than the other.
     */
    public int compareTo(Employee o) {
        return this.empId - o.empId ;
    }
    ….
}

So this compareTo() method does the trick of implementing natural ordering. So if we have 2 Employees, emp1.id – emp2.id is negative, then emp1 falls before emp2 in this ordering. We can say it like this:

emp1.id < emp2.id – emp1 falls before emp2 in natural ordering

emp1.id == emp2.id – emp1 falls with emp2 in natural ordering

emp1.id > emp2.id – emp1 falls after emp2 in natural ordering

 

Sorting the employee list:

 

We’ll write a class to test this natural ordering mechanism. Following class use the Collections.sort(List) method to sort the given list in natural order.

import java.util.*;

public class TestEmployeeSort {
    
    public static void main(String[] args) {     
        List coll = Util.getEmployees();
        Collections.sort(coll); // sort method
        printList(coll);
    }
    
    private static void printList(List<Employee> list) {
        System.out.println("EmpId\tName\tAge");
        for (Employee e: list) {
            System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
        }
    }
}

Similarly to sort on the basis of name : write compareTo like this:

public int compareTo(Employee other) {
    return name.compareTo(o2.getName());
//here compareTo() method of String is called
}

Implementing compareTo() using commons-lang

Here CompareToBuilder is used to implement compareTo();

public int compareTo(Person person) {
    return new CompareToBuilder()
    append(this.firstName, person.firstName)
    append(this.lastName, person.firstName)
    toComparison();
}

Also, there is yet another reflection option:

public int compareTo(Object o) {
    return CompareToBuilder.reflectionCompare(this, o);
}

Implementing null-safe compareTo

// primarily by name, secondarily by value; null-safe; case-insensitive
public int compareTo(final Metadata other) {
    int result = nullSafeStringComparator(this.name, other.name);
    if (result != 0) {
        return result;
    }

    return nullSafeStringComparator(this.value, other.value);
}

public static int nullSafeStringComparator(final String one, final String two) {
    if (one == null ^ two == null) {
        return (one == null) ? -1 : 1;
    }

    if (one == null && two == null) {
        return 0;
    }

    return one.compareToIgnoreCase(two);
}