Comparator & Comparable - [OOP & Java #8]

Motivation

We often use collections such as a list in our program. By storing items into a list, for example, allows us to order the items. Naturally, we learn about sorting to deal with this need. I will not be covering sorting in this article, but the idea of comparing two or more items is central to the whole act of sorting.

First, we need to understand why do we need to define a way to compare two items. Collections such as Lists in Java can contain different types of objects. It ranges from the pre-defined int String Boolean etc to custom objects that we declare. Therefore, not every object has a natural order built-in. We can easily understand sorting a list of integers to be arranging them from smallest to largest(Or the reverse). However, it can be ambiguous when we deal with an object that we created. For example, if we create a class called Human without specifying the order/way to compare, it will be open to interpretations of different people/compilers. Computers do not like ambiguity.

Brief Overview

In a nutshell, there are two ways to compare items.

• Have an external function and pass it two items and ask it to compare based on some conditions.
• Have items themselves know their order. Then, ask the object directly if it is "larger" or "smaller" than another object.

In Java, the above is achieved with Comparator and Comparable.

Example

Let's walk through an example.

class Human {
  int age;
  double weight;

  Human(int age, double weight) {
    this.age = age;
    this.weight = weight;
  }

  @Override
  public String toString() {
    return age + " " + weight;
  }
}

Suppose we have a Human object, we can either compare two Human by their age, or by their weight. Given that we created this object without extending any of the default classes, the compiler has nothing to infer from to know how to compare two Human. One way to deal with this is by using the default Comparator interface.

Comparator

This Comparator<T> is a functional generic interface.

The interface part is about the fact that it describes a contract. This is done by having abstract methods within the interface. In this case, we have a compare(T o1, T o2) method that compares two arguments. All classes that implement this interface are saying to the compiler that they will become judges that can handle the comparison of two objects. The generic part is about the fact that we need to specify a type of object that this comparator is use for. The functional part is about the fact that it can become targets of lambda expressions.

The method compare(x, y) returns three possible integers.

class AgeComparator implements Comparator<Human> {
  @Override
  public int compare(Human a, Human b) {
    return a.age - b.age;
  }
}

Usage

Human h1 = new Human(30, 68.2);
Human h2 = new Human(25, 70.3);
AgeComparator ageComparator = new AgeComparator();

Human younger = ageComparator.compare(h1, h2) > 0 ? h1 : h2;
System.out.println(younger);
// output:
// 30 68.2

So, the steps are:

1. Declare a class that implements the Comparator interface, typically named as XXXComparator.
2. Fill in the compare method in the class with however we want to compare two items.
3. When using/passing the comparator, we initialize an instance of the class that we created.
4. Call the compare method through that instance.

Comparable

By letting objects know the order that we expect them to follow, they become "comparable" literally.

Example

class Human implements Comparable<Human> {
  int age;
  double weight;

  Human(int age, double weight) {
    this.age= age;
    this.weight= weight;
  }

  @Override
  public int compareTo(Human other) {
    // e.g. by age
    return this.age - other.age;
  }
}

After implementing the Comparable interface, the class will be known to have a "natural" order. Hence, such classes can be sorted just like how we sort integers or strings. We do not have to mention how to sort them since we already defined the order within the classes.

The steps are:

1. Let the class that we want implement Comparable.
2. Fill in the compareTo method similar to compare. The difference being that it compares this with the object that is being passed in.

Faster way to write Comparator

The creation of a comparator class is troublesome. We have to first create the blueprint of a comparator class, then during actual use, create a new instance of that class. This can be shortened due to the fact that it is a functional interface.

Functional interface (brief overview)

Functions are called first-class when they can be passed around like objects. For objects, they can take the place of both inputs and outputs of functions. However, functions themselves do not enjoy such privilege in Java. In order to make functions, which are more like "actions", to behave like objects, Java uses functional interfaces and also lambdas.
Functional interfaces in a nutshell are classes that represent functions. They specify the blueprint/ signatures of a function. Then we can use a lambda to associate an actual function to that interface.

Instead of declaring a comparator in an external class and used it like this:

// ... extracted from above
class AgeComparator implements Comparator<Human> {
  @override
  public int compare(Human a, Human b) {
    return a.age - b.age;
  }
}
Human h1 = new Human(30, 68.2);
Human h2 = new Human(25, 70.3);
AgeComparator ageComparator = new AgeComparator();
Human younger = ageComparator.compare(h1, h2) > 0 ? h1 : h2;

We can either immediately declare an anonymous comparator class:

Human younger = new Comparator<Human>() {
  public int compare(Human a, Human b) {
    return a.age - b.age;
  }
}.compare(h1, h2) > 0 ? h1 : h2;

Or, when functions are expecting a comparator as one of their parameters, we can use lambda expressions:

// e.g.
List<Human> humans = Arrays.asList(new Human(30, 68.2), new Human(23, 57.3));
// List.sort takes in a comparator
humans.sort((a, b) -> a.age - b.age);

Finishing

Comparator and Comparable are commonly used for

• Sorting of a collection e.g. Arrays.sort(Comparator t) or Collections.sort()
• Constructing of a priority queue. The data structure will call the compareTo method to maintain order internally.