CMUQ 15-121 Comparators

If you want to be able to sort a set of objects, you need to specify the natural ordering for those objects. A natural ordering can be thought of as the default ordering for that kind of object. “When in doubt, order them like this.”

Now that we know what a natural order is, we need to look at how to specify it in Java.

In order to specify the natural ordering of an object, that object needs to be comparable to other objects of the same type. We do that by having the class implement the Comparable interface. As part of that interface, the class must have a compareTo method. Let’s look at an example that defines a natural ordering based on the age of the person:

public class Person implements Comparable<Person> {
    private String firstName;
    private String lastName;
    private int age;

    public Person(String firstName, String lastName, int age) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.age = age;
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public int getAge() {
        return age;
    }

    public String toString() {
        return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
    }

    /**
     * Compare this person to another Person.
     * 
     * @param p The other Person to compare to.
     * 
     * @returns -1 if this person is less-than the other person, 1 if this person is
     *          greater than the other person, and 0 otherwise.
     */
    public int compareTo(Person p) {
        if (this.age < p.age) {
            return -1;
        } else if (this.age > p.age) {
            return 1;
        } else {
            return 0;
        }
    }
}

There are a few important things to notice here.

1. The Person class now implements Comparable<Person>. This tells Java that a Person object can be compared to other Person objects.
2. The new compareTo method should compare the current object (this) to the object passed as a parameter (p) and return a negative number if this < p, a positive number if this > p, and 0 if this == p. In this case, since we’re going to compare based on age, this makes the implementation straight-forward.

Our compareTo method is actually not very good. It specifies that objects are equal based only on their age (which is bad) and ignores all the other fields. Let’s come up with a better way to order people. Here’s a simple proposal: Order by last name, then first name, then age. This means that last name is most important, but if those are equal than look at first name, too. If both last and first name are equal, then look at age. Here is an example with a better compareTo method:

public class Person implements Comparable<Person> {
    private String firstName;
    private String lastName;
    private int age;

    public Person(String firstName, String lastName, int age) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.age = age;
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public int getAge() {
        return age;
    }

    public String toString() {
        return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
    }

    /**
     * Compare this person to another Person.
     * 
     * @param p The other Person to compare to.
     * 
     * @returns -1 if this person is less-than the other person, 1 if this person is
     *          greater than the other person, and 0 otherwise.
     */
    public int compareTo(Person p) {
        // Check last name
        int ret = this.lastName.compareTo(p.lastName);
        if (ret != 0) {
            return ret;
        }

        // Last names were equal, now check first names
        ret = this.firstName.compareTo(p.firstName);
        if (ret != 0) {
            return ret;
        }

        // Both last and first names were equal, now do age
        if (this.age < p.age) {
            return -1;
        } else if (this.age > p.age) {
            return 1;
        } else {
            return 0;
        }
    }
}

Note that this method makes use of the existing compareTo method for String. (That’s because the String class implements Comparable<String>, so that method exists.)

If we do this, then the following code:

ArrayList<Person> theList = new ArrayList<Person>();
theList.add(new Person("Fred", "Jones", 40));
theList.add(new Person("Bob", "Jones", 25));
theList.add(new Person("Fred", "Jones", 15));
theList.add(new Person("Tamim", "AlKuwari", 35));
Collections.sort(theList);
System.out.println(theList);

Produces the following order:

Person [firstName=Tamim, lastName=AlKuwari, age=35]
Person [firstName=Bob, lastName=Jones, age=25]
Person [firstName=Fred, lastName=Jones, age=15]
Person [firstName=Fred, lastName=Jones, age=40]

Which is sorted exactly how we want.