Source: CS61B Textbook — 10/11. Subtype Polymorphism, Comparables, Comparators

1. The Problem: How Does Collections.max(anyList) Know How to Compare?

Collections.max is written once, in the Java standard library, and it works on a List<Dog>, a List<String>, a List<Puppy> — anything. But max can't possibly contain comparison logic for types that didn't exist when it was written. So it can't know "bigger size wins" or "later in the alphabet wins" on its own.

The solution is the same trick as the Iterator pattern: define a guaranteed protocol (an interface) that any class can implement, and have max call back into that protocol whenever it needs to compare two elements. max supplies the loop; you supply the comparison.

There are two such protocols, with two different jobs.

2. Comparable<T> — Defining a Type's Natural Order (compareTo)

public interface Comparable<T> {
    int compareTo(T other);   // ONE argument
}

Implementing Comparable means: "I know how to rank myself against another object of my type." It's embedded inside the object, and it defines the type's natural order — the one default ordering (for Dogs, say, by size).

Contract of the return value: a.compareTo(b) returns a negative int if a < b, zero if equal, positive if a > b.

Dog implements Comparable<Dog> → every Dog carries the ability to compare itself to another Dog, so Collections.max(dogs) (the no-comparator overload) will work.

3. Comparator<T> — A Third-Party Ordering (compare)

public interface Comparator<T> {
    int compare(T a, T b);    // TWO arguments
}

A Comparator is a separate object whose whole job is to compare two other things — it's not embedded in Dog, it's "a third-party machine." You use it when you want an ordering other than the natural one (e.g. by name instead of size), or when the type has no natural order at all.

Same return-value contract as compareTo, but now both operands are parameters (compare(a, b)), because the comparator isn't one of the things being compared.

The one thing to never mix up: Comparable → method named compareTo, one arg, lives in the object. Comparator → method named compare, two args, lives in a separate object. Same idea, different name and shape.

4. How Collections.max Uses Them (the callback)

Collections.max has two overloads, one per protocol:

Either way you never rewrite max. You provide compareTo or a Comparator, and max calls it. This is exactly the callback concept: max needs a helper function (comparison) that wasn't written when max was; you wrap that helper in an interface and hand it over.