Comparable vs Comparator

From Juneday education
Jump to: navigation, search

Full frontal - code up-front!

  @Override
  public int compare(String first, String second) {
    return first.length() - second.length();
  }

A Comparator has one job, to compare objects. In order to do so, it needs access to two objects to compare.

A Comparable object, needs to be able to respond when we want to take this object, and compareTo another object. In order to do so, we give the object access to one other object, and ask it to compareTo the other object.

// Juneday

Introduction

For some reason, it seems confusing to students to know when to implement java.lang.Comparable<T> and when to implement java.util.Comparator<T>. We'll explain the difference here, and try to give you a way to remember which is which.

First we'll start with some context. What is ordering objects all about?

Comparing objects

When we want some kind of ordering of our objects, we need to compare them somehow. Ordering is used for instance when sorting lists of objects, or simply when choosing between to objects according to some ordering rules.

The easiest thing to understand when talking about ordering, is the ordering of numbers. We have decided that numbers can be ordered and therefore compared to eachother. We know that 1 is less than 2, and therefore, we would write 1 before 2 if we were making an ordered list of numbers.

Another thing that we often order is words or even whole phrases. Imagine a phone book where all names were listed in no particular order, or a phone book where the order was given by the phone numbers. It would be very hard (and annoying) to use such a phone book when we want to look up the phone number of some person. Therefore, we know that the phone book is ordered according to the lexicographical order of the names. Text is often ordered like this, and this is something computers often are used for. Ordering stuff.

We can express that a class of objects has a natural order by letting the class implement an interface called Comparable. Then, we implement the only abstract method in the interface and code how and object would be ordered when compared to another object of the same class.

String is an example of such a class. Strings have a natural order, which makes it possible to sort lists of strings according to this default comparison scheme. Comparing a String with another String will give us a result (an int value) which corresponds to how these two Strings would be ordered, e.g. if they were names in a phone book (or words in an index in a course book etc).

A String s1 which is less than some other String s2 would come before s2 in a sorted list. For instance "Motörhead" is less than "WASP", so "Motörhead" would appear before "WASP" in a list of groups sorted on their names. This is of course because we are used to order letters in our alphabet in a way where "M" comes before "W". Computers often adhere to thise way of comparing letters and character sequences.

Text in a computer is nothing but sequences of binary coded numbers, and the numbers correspond to various characters in some character code table. The alphabetical characters come in the same order as in our alphabet (the one we learn in school). Note however that we have lower case letters and upper case letters. A lower case letter has a different code than its upper case equivalent. This means for instance that "A" is less than "b" (capital A comes before lower case "b" in the character code table).

All letters of the same case, however come in sequence in the character tables.

Another natural order of objects can be found in the wrapper classes like java.lang.Integer etc. An Integer object has a natural order according to the natural order of numbers that we learned in school. A smaller integer comes before a greater integer.

When we write our own classes, we can decided whether objects of the classes have a natural order or not. Often, the natural order of a domain object (an object representing something in the problem domain for our program) has a domain-specific ordering which suits the program. If you think about it, most objects in the real world (characters and numbers are not natural objects, they are invented by humans) don't have a natural order. How would you order two rocks you find on the beach? How would you order two meals you and your friend is eating?

This means that the thing or things we use as keys when implementing some kind of order between objects, either have a numerical value or a textual value.

Next, we've going to see what the difference is between the Comparable interface and the Comparator interface, and how to remember which is which.

The name of the interface is the key

It's all in the name. Comparable<T> is an adjective. It's an interface for enhancing your own class to become something more than it is, to become also a class for objects that are comparable with each other. An object of a Comparable class, can be asked to compare itself to and object of the same class, and return an int value with the result (where a negative value means that the object comes before the other object, a value of 0 means that they are equal with regards to order, and a positive value means that the object comes after the other object). The method the Comparable<T> interface guarantees that implementing classes have is thus called compareTo(T other).

One feature of a class being enhanced to also be Comparable<T>, is that collections of instances (references to instances, really) can be sorted with e.g. java.util.Collections.sort(...). Why? Because the only requirement from the sort method, for it to be able to sort a collection, is that all the elements are comparable to each other.

In order to sort e.g. a list, you need to compare the elements to each other in order to decide between two elements, which should come first? Comparable objects are helpful to the sorter. The sorter can ask an element "please, compare(yourself)To(someOtherElement)".

Comparator<T> on the other hand, is a noun which sounds almost like a job title. Just like "Terminator", "Operator", "Investigator", "Splitterator", ...

So, a class implementing Comparator<T> is for creating objects with a job, to compare stuff. In more detail, the Comparator<T> interface guarantees that a Comparator<T> object has the compare(T a, T b) method. For instance, a Comparator<String> can compare(String a, String b) and return an int value with the same semantics as above, where a negative value means "a comes before b", zero means "a and b are equal when it comes to ordering", and a positive value means "a comes after b".

Therefore, a Comparator<T> isn't modifying any existing classes at all. It is there for creating new classes for objects that have one job, to compare two Ts.

This is also good news! Now, a second version of java.util.Collections.sort(...), that takes a collection and a Comparator, can sort anything. Why? Because with the help of a Comparator, it can ask the Comparator to compare pairs of elements and thus find out the order of the sorted collections.

They way both the int compareTo(T other) method of the java.lang.Comparable<T> interface, and the int compare(T first, T second) method of the java.util.Comparator<T> is defined to work, is to return an int with a value representing the result of the comparison. The contract from the description of the methods is that the methods should return a negative number signifying "less than", zero signifying "equal", and, a positive number signifying "greater than".

For the compareTo(T other) method in java.lang.Comparable<T>, it is the object we are querying that has the instance method, so the object is responding with the int value according to whether it is greater than, equal to or less than the T other argument.

For the int compare(T first, T second) method of the java.util.Comparator<T>, on the other hand, we are asking a Comparator object to compare two objects of type T. The object will respond with the int value signifying whether the first argument is greater than, equal to or less than the second argument.

It is quite easy to remember that the Comparator interface has the compare() method, once we learn to think about a comparator as a job title. A comparator does one thing, it compares objects. How can you compare objects? You will need to look at two objects and decide which one is greater, or if they are to be considered the same (equal) in terms of ordering.

When we learn to think about Comparable as a property for some class (an adjective giving the class some extra capabilities), it is easy to remember that the method we need to implement is compareTo(), because an object which is not only of some class but also comparable, can compare itself to some other object of the same class. The method then requires one single argument, a reference to an object of the same class - something we want to compare the object To, hence the name compareTo.

If we have an object of class String, which is comparable to other String objects (java.lang.String implements Comparable<String>), then we can tell our object to compare itself to some other object (as long as the other object also is a String).

String first = args[0];
String second = args[1];

// Ask first to compare itself to second:
int result = first.compareTo(second);

// Now we know which string is greatest, if according to the lexicographical order of Strings:
if (result < 0) {
  System.out.println(first + " comes before " + second + " because it is lexicographically less."); 
} else if (result > 0) {
  System.out.println(first + " comes after " + second + " because it is lexicographically greater."); 
} else { // result must be 0
  System.out.println(first + " is lexicographically the same as " + second);
}

Now, since String is comparable, we have to live with the way the authors of java.lang.String have defined the comparison method compareTo(String other). They have chosen a natural way, using the lexicographical order of texts, i.e. how computers typically order text (using some kind of alphabet or character set as defining the order).

But, what if we want to compare strings according to some other rules, like the length of the strings, so that we can order texts from shortest to longest strings?

Then we need to hire a Comparator<String>! If we can't find one on the job market, we will have to write our own class for such a comparator:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
  @Override
  public int compare(String first, String second) {
    return first.length() - second.length();
  }
}

Our Comparator holds up his end of the contract for the compare() method. If the first string is shorter (less than) the second string, it returns a negative number. If they are equal in length, it returns zero. If the first string is longer than the second string, it returns a positive number (it is greater in length).

Now, we can use an object of our class StringLengthComparator as an argument to some sorting method along with a list of strings to sort according to the length. The sorting method will look at two strings at the time in order to decide (using our comparator) which one should come before the other. Yes, sorting algorithms are a little bit more complex than that, but you can imagine that the algorithm needs to compare the strings to each other in some fashion in order to sort the list.

This is what it could look like:

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/* Sorts the arguments on their length, shortest first
 * and prints the out.
 */
public class LengthSorter {

  public static void main(String[] args) {
    List<String> list = Arrays.asList(args);
    list.sort(new StringLengthComparator());
    System.out.println(list);
  }

}

class StringLengthComparator implements Comparator<String> {

  @Override
  public int compare(String first, String second) {
    return first.length() - second.length();
  }

}

/*
$ javac LengthSorter.java && java LengthSorter Ironman am I
[I, am, Ironman]
*/

Comparator is a functional interface

A great thing about Comparator, is that it is a functional interface, since it only declares one abstract method which we need to implement when constructing a comparator. This means that we can use a lambda in place of a comparator. You can read about lambdas here: Java:Language - Streams and Lambdas.

In short, it means that we can shorten the code shown in the example to one single expression, meaning that we don't need to write the StringLengthComparator class even:

    list.sort( (s1, s2) -> s1.length() - s2.length() );

The compiler will accept the lambda as satisfying an object of type Comparator<String> because it can use the expression as the int compare(String, String) method such an object must have.

Links

Further reading

Videos

We have a live video here:

Where to go next

  • To be decided