Comparator & Comparable - [OOP & Java #8]
Tags: computerscience, java, codenewbie
Published: 2020-10-17 15:33:28

### 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.
```java
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. 

| Integer  | Relationship   |
|----------|----------------|
| Positive | First > Second |
| Zero     | First = Second |
| Negative | First < Second |

```java
class AgeComparator implements Comparator<Human> {
  @Override
  public int compare(Human a, Human b) {
    return a.age - b.age;
  }
}
```
Usage
```java
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
```java
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:
```java
// ... 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:
```java
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:
```java
// 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.