Week 1: Comparable and Comparator, built from "what does 'in order' even mean?"

By the end you can give a type its own built-in order and ask for other orders on demand, the move Lab 1 and the catalog's three sort buttons both need. It builds straight on the Week 0 value-versus-reference idea.

The user story behind this. The registrar wants the catalog to come back in one canonical order every time it is published, so that a listing reads the same today and tomorrow; that is the type's one natural order, Comparable. A student wants to re-sort that same catalog by credits or by title without changing what the registrar published; that is a separate order supplied from outside, a Comparator. This lesson builds both moves, and Lab 1 is where you implement them.

Before you start

You should be able to tick each of these. If one is shaky, do the matching cs.jdoner.me Week 0 review first, then come back.

• [ ] I can explain the difference between a value and a reference.
• [ ] I can read an object as state (its fields) plus behavior (its methods).
• [ ] I can call a method on an object and use the value it returns.
• [ ] From CSCD 210: I can write a small class with private fields and a constructor.

The problem (sit with this before reading on)

You have a List<Course> from the catalog, and you want it in order, so you write:

Collections.sort(courses);

It will not compile. Java refuses, and the reason is the whole point of the week: Java has no idea what "in order" means for your Course. By course code? By title? By how full the section is? Every one of those is a reasonable order, and Java cannot guess which you meant.

Check yourself. Before reading on, answer in one sentence: what information is Java missing, and whose job is it to supply it?

Hold that question. Everything below is the answer to it, built one piece at a time.

Atom 1: comparing two things is a sign

The smallest piece of "order" is this: given two things, which comes first? You answer with a single int, and only its sign carries meaning:

• a negative number means the first comes before the second,
• zero means they tie,
• a positive number means the first comes after.

The size of the number is dead information. Returning -7 says exactly what -1 says.

Check yourself. A comparison returns -42 on one call and -1 on the next. Does the caller treat those two results differently? What does the sign tell it?

Atom 2: a type declares its one order with Comparable

The thing Java was missing is one method that answers Atom 1 for your type. A type supplies it by declaring implements Comparable<Course> and writing compareTo, which returns the sign. That single method is the type's one natural order, the order Collections.sort(list) and a TreeSet use when you say nothing else. Here it is on something tiny, a Book whose natural order is its title:

public final class Book implements Comparable<Book> {
    private final String title;
    // constructor and accessors omitted

    @Override
    public int compareTo(final Book other) {
        return this.title.compareTo(other.title);
    }
}

That is the entire idea: one method, returns a sign, defines the one order. A String already knows how to order itself, so you delegate to its compareTo.

Check yourself. Write the one-line body of compareTo for a Student whose natural order is by name (a String).

See it in the real Course (the platform is the textbook)

Open src/main/java/edu/ewu/cscd211/scheduler/Course.java. The class declaration is the first line of the file, and the methods you write are the TODO methods near the bottom. The first line is:

public final class Course implements Comparable<Course> {

That implements Comparable<Course> is the same promise the Book made: a Course has one natural order, and you owe it a compareTo. Note the angle brackets. The parameterized form Comparable<Course> is the one the course standard requires; the raw form Comparable with no type compiles but makes compareTo take an Object, which is a step backward into casting.

Check yourself. Find the one line in Course.java that proves a Course has a natural order.

Atom 3: a second order has to come from outside (Comparator)

Now a new problem. The catalog page has three sort buttons: by code, by title, by how full a section is. But a type has only one compareTo, so it has only one natural order. The second and third orders cannot live in the type. Where do they go?

They go in a separate object whose whole job is "how to compare two courses": a Comparator. You build the order you want and hand it to the sort. The sort algorithm stays the same; the part that varies, the order, is passed in as an object. That is a named idea in software, the Strategy pattern, and the Scheduler's three buttons are not three sort algorithms, they are one sort handed three comparators:

courses.sort(Comparator.comparing(Course::courseCode));   // by code
courses.sort(Comparator.comparing(Course::title));        // by title
courses.sort(Comparator.comparingInt(Course::credits));   // by an int key

Comparator.comparing(Course::courseCode) reads as "order by the course code," and Course::courseCode is a method reference, a compact way to name the accessor.

Check yourself. You want to order books by author, and separately by page count. How many compareTo methods can Book have, and how many comparators?

A failure that makes a rule: never subtract to compare

Here is a comparator that looks fine and is a real bug:

Comparator<Course> byCredits = (a, b) -> a.credits() - b.credits();   // WRONG

Subtraction overflows. On a 32-bit int, 2_000_000_000 - (-2_000_000_000) is not four billion; it wraps around to a negative number, so the larger value sorts first. This exact line happens not to overflow on small credits, but it is still wrong: write the rule, not the lucky case, because the same pattern silently breaks on timestamps and file sizes where the values are large. The rule the failure teaches: return a sign, never a subtraction.

Comparator<Course> byCredits = (a, b) -> Integer.compare(a.credits(), b.credits());   // RIGHT

For a text key, call the field's own compareTo, for example a.courseCode().compareTo(b.courseCode()).

Check yourself. Name one pair of int values for which a - b gives the wrong sign, and rewrite the comparison the safe way.

A failure that makes a rule: compareTo must agree with equals

Put two sections of the same course, CSCD 211-001 and CSCD 211-002, into a TreeSet. If your compareTo looks only at the course code, it returns 0 for them, because the code is the same. The TreeSet reads 0 as "these are the same course" and silently throws one away. You get a missing section and no error at all. Read the warning in the compareTo JavaDoc inside Course.java; it describes this exact trap.

The rule the failure teaches: compareTo returns 0 exactly when equals is true, which means both must key on the same fields, the identity fields. In the Scheduler a Course is really a section, so its identity is course code, section, and term together; two sections of the same course are different objects. So equals and hashCode key on those three fields, and the natural order ends on them too, which keeps the two in agreement.

Check yourself. A list loses an item when you load it into a TreeSet. State the most likely cause in terms of compareTo and equals.

One note on Course's natural order: it uses three fields in sequence, course code, then section, then term. Chaining keys like that is Comparator.comparing(...).thenComparing(...), which is the Session 2 tool. For now, just see that the order is multi-key; Session 2 gives you the clean way to stack it.

The decision: when to reach for which

You now have both tools, so the real skill is choosing, and the choice is not a coin flip. The requirement tells you which one fits, if you read it for the right signal.

• Reach for Comparable when the order is the identity of the type: one canonical order everyone agrees on and that rarely changes, like the registrar's published catalog order. The cost you accept is that a type gets exactly one natural order, so you spend it on the order that defines the thing, and every later reader inherits that choice.
• Reach for a Comparator when the order varies by who is asking, or when you do not own the type and cannot add a method to it, like the student's by-credits and by-title views. The cost is that every caller who wants that order has to pass the comparator in, because it does not live on the type.

That is the design decision behind Lab 1, and it is worth saying out loud the way you would in a code review: does Course deserve a natural order at all, and if so, which single order earns it? Course has a real claim, because the registrar's code-then-section-then-term order is institutional and stable, so it earns the natural order. A type with no defensible default (order a Movie by title, by year, or by rating, where none is the one order) is often better with no Comparable at all and only comparators, so no caller is misled into treating one order as canonical.

Why this is worth your attention beyond the grade. Writing a comparator that does not overflow is a common technical-interview question, and the never-subtract rule is the answer interviewers listen for. The same multi-key ordering is the kind of task the Applied Programming Exam scores, the timed gate later in the major. The habit you build this week is the one tested cold under time, not the one you look up.

Check yourself (the decision, stretched). You own an Employee type. HR sorts by hire date, payroll by salary, the org chart by last name. Should Employee have a Comparable at all, and if so which order earns it? Defend your answer.

Show what you can do

Make this small artifact, then write the reflection. It is neutral on purpose, so Lab 1 stays yours to write on Course.

• Artifact. Write a Movie class that implements Comparable<Movie> with a natural order by title, and write one Comparator<Movie> that orders by year using Integer.compare.
• Reflection ("I can ..."). Write one line for each, in your own words: I can give a type one natural order with Comparable; I can ask for another order with a Comparator without touching the type; I can say why a - b is the wrong way to compare and what to write instead; I can say why compareTo must agree with equals and name the one bug it prevents. Then name one bug you could now catch that you could not catch this morning.

Where this goes next

Lab 1 has you write Course.compareTo, equals, and hashCode keyed on the three identity fields, plus one Comparator, and sort the catalog. Session 2 gives you thenComparing, the clean way to stack the tie-breakers Course's natural order needs. On the drive in, The Commute Episode 1, "Who decides what 'sorted' means?", sets up this exact question before class.