Java Comparable compareTo method: Natural Order Of Things

22 Jul, 2024

java-compareto

Every time you want to make a class sortable in Java, you may want to implement the Comparable.compareTo method. Here is an Event class which will be sorted by its id:

// comparing events by their id in natural order 
public int compareTo(Event event) {
    // DON'T DO THIS
    return this.id - event.id; 
}

Unfortunately, if id happens to be negative for some events, ids will be compared incorrectly, which eventually will lead a bug in your code:

Event e1 = new Event(2000000000);
Event e2 = new Event(0);
Event e3 = new Event(-2000000000);
System.out.println(e1.compareTo(e2) > 0); //true (CORRECT)
System.out.println(e2.compareTo(e3) > 0); //true (CORRECT)
System.out.println(e1.compareTo(e3) > 0); //false (INCORRECT)

If you are interested in why this happens, let's refresh our knowledge about natural order and what the Java contract for compareTo method implementations is.

What is `compareTo` method

At its core, the compareTo method is defined in the Comparable interface and is used to compare the current object with another object of the same type. When you implement compareTo, you're essentially defining a natural ordering for your objects.

The compareTo method is used in various Java data structures to establish a natural ordering of elements:

TreeSet:
- A NavigableSet implementation uses compareTo to maintain its elements in sorted order.
TreeMap:
- A Red-Black tree based NavigableMap implementation.
- Uses compareTo to keep its keys sorted.
PriorityQueue:
- An unbounded priority heap.
- Uses compareTo to determine the order in which elements are dequeued.
Arrays:
- The Arrays.sort() method uses compareTo when sorting arrays of objects that implement Comparable.
Collections:
- The Collections.sort() method uses compareTo when sorting lists of Comparable objects.
LinkedList:
- While not inherently sorted, its sort() method uses compareTo when called.
ArrayList:
- Similar to LinkedList, its sort() method uses compareTo when called.
Vector:
- An older thread-safe dynamic array implementation.
- Its sort() method uses compareTo when called.
Stack:
- Extends Vector, so it inherits the same sorting capabilities.
PriorityBlockingQueue:
- A thread-safe unbounded blocking queue.
- Uses compareTo to order its elements.
ConcurrentSkipListSet:
- A scalable concurrent NavigableSet implementation.
- Uses compareTo to maintain its sorted order.
ConcurrentSkipListMap:
- A scalable concurrent NavigableMap implementation.
- Uses compareTo to keep its keys sorted.

Like the article? Support me by subscribing to the blog

How does `compareTo` work

The compareTo method in Java returns an integer value that indicates the relationship between the current object and the object being compared:

Negative integer: if the current object is less than the argument
Zero: if the current object is equal to the argument
Positive integer: if the current object is greater than the argument

So, moving back to our previous example, when we compared 2000000000 and -2000000000 we essentially executed code :2000000000 - -2000000000 which must be 4000000000, but in the case of Java Integer, an integer overflow will occur which will lead to -294967296 and according to the contract it's less than 0.

Let's look at a simple example using String objects:

String str1 = "apple";
String str2 = "banana";
System.out.println(str1.compareTo(str2)); // Output: -1

In this case, "apple" comes before "banana" lexicographically, so the method returns a negative integer.

Implementing Comparable in Your Custom Classes

To use compareTo with your own classes, you need to implement the Comparable interface. Here's a basic example:

Java 8:

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    @Override
    public int compareTo(Person other) {
        return Integer.compare(age, other.age);
    }
}

Or if you migrated to Java 14+ you can use records here:

public record Person(String name, int age) implements Comparable<Person> {
    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

In this example, we're comparing Person objects based on their age

Advanced compareTo Implementation

Sometimes, you might want to compare objects based on multiple criteria. Here's a more complex example:

public class Student implements Comparable<Student> {
    private String name;
    private double gpa;

    @Override
    public int compareTo(Student other) {
        return Comparator.comparingDouble(Student::getGpa).reversed()
                         .thenComparing(Student::getName)
                         .compare(this, other);
    }
}

This implementation first compares students by GPA (in descending order), and if GPAs are equal, it compares by name:

Original list:
Student{name='Alice', gpa=3.8}
Student{name='Bob', gpa=3.5}
Student{name='Charlie', gpa=3.8}
Student{name='David', gpa=3.9}
Student{name='Eve', gpa=3.5}

Sorted list:
Student{name='David', gpa=3.9}
Student{name='Alice', gpa=3.8}
Student{name='Charlie', gpa=3.8}
Student{name='Bob', gpa=3.5}
Student{name='Eve', gpa=3.5}

`compareTo` with Java's Built-in Classes

Many of Java's built-in classes, such as Integer, String, LocalDate, BigDecimal and others, already implement the Comparable interface, for example:

// Integer comparison
Integer num1 = 5;
Integer num2 = 10;
System.out.println(num1.compareTo(num2)); // Output: -1

Comparing Primitive Types

When dealing with primitive types like int, you can't use compareTo directly. Instead, use the static compare method of the corresponding wrapper class:

int a = 5;
int b = 10;
System.out.println(Integer.compare(a, b)); // Output: -1

Similar method exists for other common Java classes:

        Integer.compare(int a, int b)
        Long.compare(long a, long b)
        Short.compare(short a, short b)
        Byte.compare(byte a, byte b)
        Float.compare(float a, float b)
        Double.compare(double a, double b)
        Character.compare(char a, char b)
        Boolean.compare(boolean a, boolean b)

Best Practices and Common Pitfalls

Consistency with equals: Ensure that your compareTo implementation is consistent with equals. If x.equals(y) is true, then x.compareTo(y) should return 0.
Transitive comparison: If x.compareTo(y) > 0 and y.compareTo(z) > 0, then x.compareTo(z) should be > 0.
Handle null values: Decide how your compareTo method should handle null values and document it clearly.
Use existing comparison methods: Utilize methods like Integer.compare(), Double.compare(), etc., for comparing primitive types to avoid issues with subtraction overflow.
Consider using Comparator: For complex comparison logic or when you need multiple ways to compare objects, consider using the Comparator interface instead of or in addition to Comparable and write exhaustive tests around this implementation.

Lexicographical Order Explained

Lexicographic Comparison: "adam" vs "adamantium"

Index	"adam"	"adamantium"	Comparison Result
1	a	a	Equal, continue
2	d	d	Equal, continue
3	a	a	Equal, continue
4	m	m	Equal, continue
5		a	Empty < 'a' (Comparison stops)
6		n	Not compared
7		t	Not compared
8		i	Not compared
9		u	Not compared
10		m	Not compared

Result: "adam" comes before "adamantium" lexicographically

Explanation:

Compare characters from left to right
The first 4 characters are identical
At index 5, "adam" has no character (end of string)
An empty position comes before any character
Therefore, "adam" < "adamantium" lexicographically

Key Points:

Lexicographic ordering compares strings character by character from left to right.
If all characters match up to the end of the shorter string, the shorter string comes first.
An empty position (end of string) is considered to come before any character.
"adam" is a prefix of "adamantium", so it automatically comes first in lexicographic order (prefix rule).

Conclusion

The compareTo method is a fundamental tool in Java for establishing order among objects. By implementing the Comparable interface and overriding compareTo, you can define custom ordering for your classes, enabling them to be easily sorted and compared. Whether you're working with Java's built-in classes or creating your own, mastering compareTo is essential for any Java developer dealing with ordered data or custom object comparisons.

Remember, the power of compareTo lies in its flexibility – you can define any ordering that makes sense for your objects. So the next time you need to sort a collection of custom objects or implement a binary search tree, you'll know exactly how to leverage compareTo to get the job done efficiently and effectively.

Happy coding!

#java