Comparable

Comparable is how a class declares its natural order: one method, compareTo, that answers a negative number, zero or a positive number. Everything that sorts without being told how uses it, and two objects that compare as zero are, for a sorted collection, the same element. That last sentence is the part that surprises, and it is why the contract with equals matters.

The Comparable contract

compareTo returns a negative integer when the receiver comes before the argument, zero when the two are equal in the order, and a positive integer when it comes after. The number need not be -1 and 1: the program below prints -8, which is the difference of two characters of String.compareTo. A sort only reads the sign.

The contract says the order must be consistent with equals: x.compareTo(y) == 0 should mean x.equals(y). A TreeSet and a TreeMap break the rule when it is violated silently, because they decide equality by the comparison. Classes in the JDK that cannot follow it, such as BigDecimal, say so in their documentation.

A record that implements it

A record declares its components, so a natural order on one of them is three lines. The class below orders people by name, and Collections.sort uses it with no comparator:

import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Names { public static void main(String[] args) { List<Person> people = new ArrayList<>(List.of( new Person("Grace", 45), new Person("Ada", 36), new Person("Alan", 41))); Collections.sort(people); for (Person person : people) { System.out.println(person); } System.out.println(people.get(0).compareTo(people.get(1))); System.out.println(people.get(0).compareTo(people.get(0))); } } record Person(String name, int age) implements Comparable<Person> { @Override public int compareTo(Person other) { return name.compareTo(other.name()); } }

javac -Xlint:all Names.java
java Names

Person[name=Ada, age=36]
Person[name=Alan, age=41]
Person[name=Grace, age=45]
-8
0

The three names sort alphabetically because String is itself Comparable, and the record delegates to it. The last two lines are the contract read from the other side: a negative number for Ada against Alan, and zero for an element against itself.

An order on two fields

A real order usually compares one field and falls back to a second. Integer.compare is the primitive form and answers -1, 0 or 1, so the two comparisons compose without arithmetic on the difference, which would overflow for large numbers:

import java.util.Arrays; public class Ages { public static void main(String[] args) { Person[] people = { new Person("Grace", 45), new Person("Ada", 36), new Person("Alan", 41), new Person("Edsger", 36), }; Arrays.sort(people); for (Person person : people) { System.out.println(person.name() + " " + person.age()); } System.out.println(new Person("a", 36).compareTo(new Person("b", 36))); } } record Person(String name, int age) implements Comparable<Person> { @Override public int compareTo(Person other) { int byAge = Integer.compare(age, other.age()); if (byAge != 0) { return byAge; } return name.compareTo(other.name()); } }

javac -Xlint:all Ages.java
java Ages

Ada 36
Edsger 36
Alan 41
Grace 45
-1

Ada and Edsger share the age 36, and the second key puts Ada first because a comes before E. Without that fallback the sort would leave the two in whatever order they arrived in, which is stable but not sorted. The last line compares two people of the same age and gets the name comparison, -1 for a against b.

The order a TreeSet uses

A TreeSet and a TreeMap are the collections that use the natural order without being asked. The set of strings is alphabetical, and the set of points is ordered by x and then by y:

import java.util.Set; import java.util.TreeSet; public class Sets { public static void main(String[] args) { Set<String> words = new TreeSet<>(); words.add("pear"); words.add("apple"); words.add("fig"); System.out.println(words); Set<Point> points = new TreeSet<>(); points.add(new Point(2, 1)); points.add(new Point(1, 2)); points.add(new Point(1, 1)); System.out.println(points); System.out.println(points.contains(new Point(1, 2))); } } record Point(int x, int y) implements Comparable<Point> { @Override public int compareTo(Point other) { int byX = Integer.compare(x, other.x()); return byX != 0 ? byX : Integer.compare(y, other.y()); } }

javac -Xlint:all Sets.java
java Sets

[apple, fig, pear]
[Point[x=1, y=1], Point[x=1, y=2], Point[x=2, y=1]]
true

The points are in the order the comparison defines, and contains finds a new object with the same coordinates because the tree compares it on the way down. Here the order agrees with the record's equals, so the set behaves as a reader expects; a compareTo that compared only x would make two different points the same element.

A type without an order

A class that does not implement Comparable cannot be sorted without a comparator, and the failure is at run time because Arrays.sort(Object[]) only finds out what the elements are when it compares them:

public class NoOrder { public static void main(String[] args) { Object[] values = {new Box(2), new Box(1)}; java.util.Arrays.sort(values); System.out.println(java.util.Arrays.toString(values)); } } class Box { private final int size; Box(int size) { this.size = size; } @Override public String toString() { return "Box(" + size + ")"; } }

javac -Xlint:all NoOrder.java
java NoOrder
echo "status: $?"

Exception in thread "main" java.lang.ClassCastException: class Box cannot be cast to class java.lang.Comparable (Box is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
at java.base/java.util.Arrays.sort(Arrays.java:1042)
at NoOrder.main(NoOrder.java:4)
status: 1

The message names the class and the interface it is not, and the frames are the sort implementation. The build printed no warning at all, which is the uncomfortable part: an Object[] accepts anything, and the mistake is found only when the sort compares. A typed array Box[] gives the same failure, and the compiler cannot see it either; only a comparator can fix it, which is the next lesson.

Exercises

  1. Order Person by age alone and print the list twice to see which of two equal ages comes first.
  2. Make Point compare y before x and print the set again.
  3. Sort a list of strings with Collections.reverseOrder() and print it.
  4. Give Box a Comparable and remove the exception from NoOrder.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What must compareTo answer for the receiver coming before the argument?

    Answer

    A negative number

    Only the sign is read, so any negative number means before.

  2. What should be true when x.compareTo(y) is zero?

    Answer

    x and y are equal in the order, and ideally x.equals(y)

    A sorted collection treats a zero comparison as the same element, so the two should agree.

  3. Which collections use the natural order without a comparator?

    Answer

    TreeSet and TreeMap

    The sorted collections keep their elements in the order compareTo defines.

  4. What does this program print? import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Q1 { public static void main(String[] args) { List<String> words = new ArrayList<>(List.of("pear", "apple", "fig")); Collections.sort(words); System.out.println(words); } }

    Answer

    [apple, fig, pear]

    String implements Comparable, so the sort puts the words in alphabetical order.

  5. What does this program print? public class Q2 { public static void main(String[] args) { System.out.println(new P(1).compareTo(new P(2))); System.out.println(new P(2).compareTo(new P(2))); } } record P(int v) implements Comparable<P> { public int compareTo(P other) { return Integer.compare(v, other.v()); } }

    Answer

    -1 / 0

    A smaller value compares negative and an equal one compares zero.

  6. What does this program print? import java.util.Set; import java.util.TreeSet; public class Q3 { public static void main(String[] args) { Set<String> set = new TreeSet<>(); set.add("b"); set.add("a"); set.add("b"); System.out.println(set); System.out.println(set.size()); } }

    Answer

    [a, b] / 2

    The set drops the duplicate and iterates in the sorted order.

  7. What does this program print? import java.util.Arrays; public class Q4 { public static void main(String[] args) { Integer[] numbers = {3, 1, 2}; Arrays.sort(numbers); System.out.println(Arrays.toString(numbers)); } }

    Answer

    [1, 2, 3]

    Integer implements Comparable, so the array is sorted numerically.

  8. What happens when a class without Comparable is sorted?

    Answer

    A ClassCastException at the sort, when the first comparison runs

    The sort casts an element to Comparable when it compares, and that cast fails.

  9. Why do the two-key comparisons use Integer.compare?

    Answer

    It answers -1, 0 or 1 without subtracting, so it cannot overflow

    The difference of two large ints can wrap around, while compare is defined for every pair.

  10. What does a stable sort do with two elements that compare as equal?

    Answer

    It keeps them in the order they arrived in

    Stability is the promise that equal elements keep their relative order.

The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.

Article author: Arthur Isaev