10.2 Comparables and Comparators

Comparables

As a motivating example, consider the following Java code, where we want to try to find the largest dog in a list of dogs.

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxDog = Collections.max(dogs);

This code almost works, but there's one problem, Java doesn't know how to compare dogs. This will result in a fairly incomprehensible error message that "no instance(s) of type variable(s) T exist so that Dog conforms to Comparable<? super T>".

Unlike Python, where we defined a __gt__ method to allow for comparison, Java doesn't have operator overloading. Instead, we must utilize implementation inheritance. Specifically, we'll implement the Comparable interface, given below:

public interface Comparable<T> {
    int compareTo(T o);
}

As we saw earlier in class, the compareTo method returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. If you're curious you can also look at the source for Comparator.java, which can be seen at this link.

After implementing the Comparable interface, we end up with the code below:

public class Dog implements Comparable<Dog> {
   ...
   @Override
   public int compareTo(Dog uddaDog) {
       if (size > uddaDog.size) {
           return 1;
       }
       if (size < uddaDog.size) {
           return -1;
       }
       return 0;
   }
}

After implementing this interface, Collections.max(dogs) will now work.

While the code we wrote above works, it's a bit clumsy. An alternate approach is shown below:

public class Dog implements Comparable<Dog> {
   ...
   @Override
   public int compareTo(Dog uddaDog) {
       return this.size - uddaDog.size;
   }
}

Here, we save some lines of code by simply subtracting the sizes. Returning a difference between two numbers is a common way to implement compareTo methods in Java.

The flavor of polymorphism we’ve just employed is sometimes called subtype polymorphism.

The idea here is that a supertype (Comparable) specifies the capability (in this case, comparison). Then a subtype (Dog) overrides the supertype’s abstract method. At runtime, Java decides what to do based on the type of the object that is invoking the method.

To test your understanding of these ideas, try answering these two questions in the lecture slides:

1. Question 1
2. Question 2

Comparators

The term "Natural Order" is sometimes used to refer to the ordering implied by a Comparable's compareTo method. Our compareTo method thinks of the size as the natural for the dogs.

Sometimes we want to consider other ordering. For example, we might want to sort the dogs by name.

In pPython, we achieve this goal using function passing. For example, in the code below, we pass name_len as a key function to get_the_max.

def get_the_max(x, key):
  max_value = x[0]
  for item in x:
    if key(item) > key(max_value):
      max_value = item
  return max_value

def name_len(dog):
   return len(dog.name)

max_dog=get_the_max(doglist, name_len)

By contrast, Java code doesn't typically use function passing for handling alernate orders. Instead, we rely again on subtype polymorphism.

Specifically, we can implement the Comparator interface, given below:

public interface Comparator<T> {
    int compare(T o1, T o2);
}

An example Comparator that compares dogs based on name is given below:

public static class NameComparator implements Comparator<Dog> {
   @Override
   public int compare(Dog a, Dog b) {
       return a.name.compareTo(b.name);
   }
}

To test your understanding of these ideas, consider this problem. What is the output of the code below?

Dog a = new Dog("Frank", 1);
Dog b = new Dog("Zeke", 1);
Comparator<Dog> nc = new Dog.NameComparator();
System.out.println(nc.compare(a, b));

Is it a positive number? Negative number? Or zero?

Using a Comparator

The code below shows an example of how we can pass a Comparator to Collections.max.

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxNameDog = Collections.max(dogs, new Dog.NameComparator());

This is similar to how we can pass a key function to get_the_max in Python.

def length_of_name(dog):
   return len(dog.name)

dogs = [Dog("Grigometh", 10),
        Dog("Pelusa", 5),
        Dog("Clifford", 9000)]
max_dog = get_the_max(dogs, length_of_name)

Notice the difference here. In Java, we package our comparison function inside of a Comparator object, i.e. we rely on subtype polymorphism.

By contrast, in Python, we pass a comparison function to get_the_max, i.e. we rely on function passing.

Minor Improvements

The NameComparator instantiation is awkward and aesthetically unpleasant (to me). It seems strange to have to instantiate a class just to pass a comparison function.

One fix is to add a static variable reference to a pre-instantiated NameComparator. We do this in our Dog class.

public class Dog {
   ...
   public static final Comparator<Dog> NAME_COMPARATOR = new NameComparator();
}

This allows us to pass Dog.NAME_COMPARATOR to Collections.max without having to instantiate a new NameComparator object. This results in code that looks like this:

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxNameDog = Collections.max(dogs, Dog.NAME_COMPARATOR);

Is this actually better? You be the judge!

Bonus Content

It is also possible to implement a Comparator using a lambda expression. This is shown below:

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Comparator<Dog> dc = (a, b) -> a.name.compareTo(b.name);
Dog maxNameDog = Collections.max(dogs, dc);

This is a bit more concise, but it's also a bit more difficult to read. We won't expect you to learn lambda expression in this class.

Comparables vs. Comparators

The Comparable interface specifies that a “natural order” exists. Instances of the class can compare themselves to other objects. Only one such order is possible.

The Comparator interface is used to compare extrinsically (by other classes). May have many such classes, each specifying one such order.