Implementing an interface, such as Comparable

You already know how to sort a list of numbers or a list of strings. Java was built knowing how those go in order. It was not built knowing how you want a list of your own objects arranged, and it is not going to guess. Comparable is how you tell it, once, so that every sort in the standard library can read the answer back off your class.

Where it stops working without you

Take an ordinary small class: private fields, a constructor that checks its input, a toString.

public class Course
{
    private String dept;
    private int number;

    public Course(String dept, int number)
    {
        if (dept == null)
        {
            throw new IllegalArgumentException("dept required");
        }
        this.dept = dept;
        this.number = number;
    }
}

Put some in an array and sort it.

Arrays.sort(courses);

That compiles clean. Run it and it throws a ClassCastException saying a Course cannot be cast to Comparable. The sort was handed objects and asked each pair which one comes first, and nothing about Course has ever answered that question. Java cannot work out that CSCD comes before MATH, or that 210 comes before 211, or that the department matters more than the number. Those are your decisions about your class.

An interface is a promise, and implements signs it

An interface is a list of method headers with no bodies. It says what a type will be able to do and nothing at all about how. Comparable is one of the smallest in the library: 1 method.

public class Course implements Comparable<Course>
{
    @Override
    public int compareTo(Course other)
    {
        return this.dept.compareTo(other.dept);
    }
}

The word implements is the signature on the promise, and the compiler holds you to it: leave the method out and the file does not compile. That is the deal an interface offers. You accept a rule about what your class must contain, and in exchange every piece of code in the world that was written against the interface now works on your class without knowing anything else about it.

The <Course> inside the angle brackets matters. It says a Course compares itself against another Course, so the method takes a Course parameter and you never write a cast. Without it you are signing the older, raw form of the same promise, and then the method has to take an Object and check and cast it yourself. The 2 halves have to agree with each other:

Both failures are the same failure. The interface asks for a specific method header, you supplied a different one, and a different header is a different method, so the promise is unkept and the class is not finished. That is the same rule that makes a misspelled toString a new method rather than an override.

The answer is a sign, not a size

compareTo returns an int, and the only thing anybody reads from that int is which side of zero it fell on.

The size carries nothing. A return of -1, -9 and -4000 all say the identical thing to a sort: this one first. So read the sign and only the sign.

// wrong: assumes an exact value
if (a.compareTo(b) == -1)

// right: reads the sign
if (a.compareTo(b) < 0)

The first line often looks like it works, because Integer happens to hand back -1, 0 and 1 in its own version, while String hands back the difference between the first characters that differ, which can be 31 or -2. Nothing requires that, and a perfectly correct compareTo is allowed to return -47. Use < 0 for before, == 0 for a tie, > 0 for after, and let go of the rest of the number.

Comparing each kind of field

You almost never build a sign yourself. Every field type already has something that builds one for you.

• A String field: this.dept.compareTo(other.dept). String is itself Comparable and already knows dictionary order.
• An int field: Integer.compare(this.number, other.number).
• A double field: Double.compare(this.gpa, other.gpa), for the same reason as the int one.
• Any field whose own class implements Comparable: call its compareTo, the same as a String.

String.compareTo has one behavior worth knowing before it surprises you. It walks both strings looking for the first position where the characters differ and reports on that. If there is no such position, because one string is the whole of the other plus more letters, it falls back to the difference in lengths and the shorter one comes first. So "Jim" against "Jimm" is negative, and "Smithe" against "Smith" is positive, with a magnitude of 1 that means nothing.

int a = Integer.MAX_VALUE;   // 2147483647
int b = -1;
int diff = a - b;            // math says 2147483648
System.out.println(diff);    // prints -2147483648

More than 1 field: the cascade

Most classes need a second field to break a tie and sometimes a third to break that. compareTo still has to hand back exactly 1 int, so you need a way of folding several keys into that number without losing any of them. The rule is priority, not addition: compare a key, and the moment it is not a tie, return it and stop.

Give Course a third field, an int named section, so 2 sections of the same course can be told apart. The order is department first, then number, then section.

@Override
public int compareTo(Course other)
{
    int byDept = this.dept.compareTo(other.dept);
    if (byDept != 0)
    {
        return byDept;
    }
    int byNumber = Integer.compare(this.number, other.number);
    if (byNumber != 0)
    {
        return byNumber;
    }
    return Integer.compare(this.section, other.section);
}

Two lines per key: work out the comparison, and return it immediately if it decided anything. If byDept is not zero, the departments already settled the order, so nothing below that line ever runs and the numbers are never looked at. If it is zero, the 2 courses share a department and you fall through to the key that gets to speak next.

The last key is written differently, and that difference is the part people miss. It has no if and no local variable. It just returns. There is nothing to fall through to, so whatever it hands back is the final answer, zero included. A zero there does not mean keep looking. It means these 2 tied on every key there is, which is a legitimate result and not a signal.

Notice what you do not write. There is no if (everything matches) return 0; at the top. The exact zero for 2 identical courses comes out of the last line on its own, because every comparison above it returned a tie and the last one did too.

Some keys run the other way: largest salary first, most recent date first. Do not negate the result to get that. Swap the 2 arguments instead, so Integer.compare(other.salary, this.salary) puts the larger salary first. Swapping says what you mean on the line itself. Negating is also less safe than it looks, because a compareTo may return any negative number, the most negative int included, and negating that one gives it back unchanged.

Private is private to the class, not to the object

Look again at that method. It reads other.dept and other.number, which are private fields on a different object, and it compiles. Private means private to the class. Your compareTo is code inside Course, so it can see any Course's fields, including one it was handed. Do not go writing a getter to climb a wall that is not there.

What a sort does with it

Collections.sort(courses);

That is the whole call. Collections.sort knows nothing about departments or course numbers. It calls compareTo on pairs of the elements it was handed, over and over, and arranges them by the signs that come back. So every field you read inside compareTo, and the order you read them in, is the entire definition of the order the list ends up in. Arrays.sort reads the same method the same way when the data is in an array. The container changes; the order does not.

One more thing your answer is promising. Returning zero tells everything downstream that these 2 objects tie, and some collections take that as meaning they are the same element and keep only 1 of them. A TreeSet is one: it decides whether an element is already present by calling compareTo, not equals, so add 3 different students whose comparison looks only at last names, 2 of them Smiths, and the set holds 2. So the last key in a cascade should be something that always separates 2 different things, which is why an id makes a good one and a name does not.

In the practice APE

The compareTo problem in Practice exams 1 and 2 applies this lesson to a Student whose fields, constructor and toString are already written. The class line already says implements Comparable<Student>. You write the 1 method. The specification is the comment at the top of the file:

Implement the Comparable interface to specifically compare against another student.
Follow the rules from the Java API for Comparable behavior.

Students should first be compared by last name for order. If the last names are the same,
compare by first name.  If first names are the same, compare by studentId.

Three keys, in that order, and "follow the rules from the Java API" is the sentence that makes the sign rule part of the specification rather than advice.

Two details of the file are worth reading before you write anything. The constructor takes its arguments in the order first name, last name, id, which is not the order you compare in, so a test case that reads new Student("Jim", "Smith", 12345) is a student whose last name is Smith. And the only getter in the class is the one for the id. There is no getter for either name, and you do not need one, for the reason in the section above.

Practice exam 2 also has a StudentComparator problem: a separate class that orders 2 Student objects (a comparator), with a 2-parameter compare(a, b). compareTo and compare, worked on a scoreboard teaches compare in its section on a second order.

Readiness check

Work each one on paper and write the answer down before you open it.

new Course("CSCD", 211, 2)
new Course("CYBR", 211, 2)
new Course("CSCD", 300, 2)
new Course("CSCD", 211, 1)

CSCD 211-1
CSCD 211-2
CSCD 300-2
CYBR 211-2

The one thing to keep

A class declares its 1 natural order by implementing Comparable of its own type and writing compareTo. The return is a sign and nothing else: negative before, zero tied, positive after. With more than 1 key, compare in priority order and return the first result that is not zero, 2 lines per key, except the last key which just returns. Compare a String with its own compareTo and an int with Integer.compare, and never subtract, because subtraction overflows and lies about the sign. Collections.sort and Arrays.sort then read that order straight off your class and ask for nothing else.