article banner (priority)

Effective Kotlin Item 44: Respect the contract of compareTo

This is a chapter from the book Effective Kotlin. You can find it on LeanPub or Amazon.
The compareTo method is not in the Any class. It is an operator in Kotlin that translates into the mathematical comparison signs:
obj1 > obj2 // translates to obj1.compareTo(obj2) > 0
obj1 < obj2 // translates to obj1.compareTo(obj2) < 0
obj1 >= obj2 // translates to obj1.compareTo(obj2) >= 0
obj1 <= obj2 // translates to obj1.compareTo(obj2) <= 0
It is also located in the Comparable<T> interface. When an object implements this interface, or when it has an operator method named compareTo with one parameter, this means that this object has a natural order. Such an order needs to be:
  • Antisymmetric, meaning if a >= b and b >= a, then a == b. Therefore, there is a relation between comparison and equality, and they need to be consistent with each other.
  • Transitive, meaning if a >= b and b >= c, then a >= c. Similarly, when a > b and b > c, then a > c. This property is important because sorting elements without it might take literally forever in some sorting algorithms.
  • Connex, meaning there must be a relationship between every two elements: either a >= b or b >= a. In Kotlin, this relationship is guaranteed by the type system, because compareTo returns Int, and every Int is either positive, negative, or zero. This property is important because if there is no relationship between two elements, we cannot use classic sorting algorithms like quicksort or insertion sort. Instead, we need to use one of the special algorithms for partial orders, like topological sorting.

Do we need a compareTo?

In Kotlin we rarely implement compareTo ourselves. We get more freedom by specifying the order on a case-by-case basis than by assuming one global natural order. For instance, we can sort a collection using sortedBy and provide a key that is comparable. So, in the example below, we sort users by their surnames:
class User(val name: String, val surname: String)

val names = listOf<User>(/*...*/)

val sorted = names.sortedBy { it.surname }
What if we need a more complex comparison than just by a key? For that, we can use the sortedWith function, which sorts elements using a comparator. This comparator can be produced using the compareBy function. So, in the following example, we sort users by comparing them by their surname; if they match, we compare them by their name:
val sorted = names
    .sortedWith(compareBy({ it.surname }, { it.name }))
Surely, we might make User implement Comparable<User>, but what order should it choose? Is any order truly natural for this type? When this is not absolutely clear, it is better to not make such objects comparable, and the objects’ order should be specified for each sorting.
The natural order of String is alphanumeric, therefore it implements Comparable<String>. This is very useful because we often do need to sort text alphanumerically; however, it also has its downsides: for instance, we can compare two strings using a comparison sign, which seems highly unintuitive. Most people who see a comparison sign between two strings will be rather confused.
// DON'T DO THIS!
print("Kotlin" > "Java") // true
Surely there are objects with a clear natural order? Units of measure, date, and time are all perfect examples. However, if you are not sure about whether your object has a natural order, it is better to use comparators instead. If you use a few of them often, you can place them in the companion object of your class:
class User(val name: String, val surname: String) {
   // ...

   companion object {
       val DISPLAY_ORDER =
           compareBy(User::surname, User::name)
   }
}

val sorted = names.sortedWith(User.DISPLAY_ORDER)

Implementing compareTo

When we do need to implement compareTo ourselves, we have top-level functions that can help us. If all you need is to compare two values, you can use the compareValues function:
class User(
   val name: String,
   val surname: String
) : Comparable<User> {
   override fun compareTo(other: User): Int =
       compareValues(surname, other.surname)
}
If you need to use more values, or if you need to compare them using selectors, use compareValuesBy:
class User(
    val name: String,
    val surname: String
) : Comparable<User> {
    override fun compareTo(other: User): Int =
        compareValuesBy(this, other,
            { it.surname },
            { it.name }
        )
}
This function helps us create most of the comparators we might need. If you need to implement one with a special logic, remember that it should return:
  • 0 if the receiver and other are equal
  • a positive number if the receiver is greater than other
  • a negative number if the receiver is smaller than other
If you do this, don't forget to verify that your comparison is antisymmetric, transitive, and connex.

Summary

  • Classes with a clear natural order should implement Comparable<T>, that is, they should have a compareTo method. If you are not sure whether your class has a natural order, it is better to not implement Comparable<T>.
  • The compareTo method is used to decide which of two objects is considered greater. We can use it with comparison operators (>, <, >=, <=). compareTo should be antisymmetric, transitive, and connex.
  • When you implement custom compareTo, we often use helper methods from Kotlin stdlib. If you need to compare two comparable values, use the compareValues function. If you need to compare values by a few of their comparable properties, use compareValuesBy.