Class 7 — Wednesday, September 16

A sort that compiles, starts, prints a line, and then dies. Then the one method that fixes it.

Section 1 runs on the projector — keyboards down, prediction in the Journal. From section 2 you are in your own A3 repo, in pairs.

  1. A sort that compiles and then dies — predict first
  2. compareTo
  3. Make the sort work
  4. compareTo when you did not write it
  5. What compareTo does with null
  6. Catch the bug yourself
  7. Sort it backwards

Sections 1 to 3 are the class. Sections 4 to 6 are short and independent — take them in any order if you get there, and do not rush section 2 to reach them.

1. A sort that compiles and then dies

Keyboards down. This one is on the projector.

Four matrices, an array, and one line that tries to sort it:

import java.util.Arrays;

public class SortMatrices {
    static void show(String tag, Matrix[] matrices) {
        System.out.print(tag);
        for (Matrix m : matrices) {
            System.out.print(" " + m.magnitude());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Matrix[] matrices = {
            new Matrix(new double[][] {{3, 4}}),        // magnitude 7
            new Matrix(new double[][] {{1, 1.6}}),      // magnitude 2.6
            new Matrix(new double[][] {{1, 1}}),        // magnitude 2
            new Matrix(new double[][] {{5, 12}}),       // magnitude 17
        };

        show("before:", matrices);
        Arrays.sort(matrices);
        show("after: ", matrices);
    }
}

Two questions, and write both answers in the Journal before it runs. One line is enough and a guess counts as a line.

Does this compile? If it runs, what happens, and if not, why?

It compiles. There is no warning. Then it prints

before: 7.0 2.6 2.0 17.0

and dies:

Exception in thread "main" java.lang.ClassCastException:
    class Matrix cannot be cast to class java.lang.Comparable
    at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(...)
    at java.base/java.util.Arrays.sort(Arrays.java:1042)
    at SortMatrices.main(SortMatrices.java:21)

The before: line is the whole point. The program compiled, started, and did real work before anything went wrong.

Arrays.sort takes an Object[]. Nothing about your Matrix was checked at any point — not until the sort reached inside the array for the first comparison and found it could not make one.

The message names its own fix. cannot be cast to ... Comparable: the sort is telling you which promise your class has not made.

2. compareTo

Keyboards up. Pairs.

Comparable is a promise with no code behind it. Making it is two edits to Matrix.java.

First, the class declaration:

public final class Matrix implements Comparable<Matrix> {

Then the one method that promise requires:

@Override
public int compareTo(Matrix other) {
    ...
}

Order matrices by magnitude(), smallest first. You wrote magnitude() in A3.

The int it returns is not a code. Any negative number means this comes first, any positive number means it comes second, zero means neither does. It does not have to be -1, 0 and 1.

Done when Matrix declares implements Comparable<Matrix> and the file compiles.

3. Make the sort work

Put SortMatrices.java in your src/ directory — the code is in section 1 — and run its main function.

Done when the after: line reads

after:  2.0 2.6 7.0 17.0

If your compareTo subtracts two magnitudes and casts the result to int, this is what prints instead:

after:  2.6 2.0 7.0 17.0

Magnitudes are doubles. 2.6 and 2.0 are 0.6 apart, and (int) 0.6 is 0 — so the sort is told those two are equal and leaves them in the order it found them. The other two are far enough apart to survive it, which is why three of the four look right.

Double.compare does the whole thing in one line and has no version of this problem. Look at what it returns before you use it.

4. compareTo when you did not write it

You are not the first person to implement this method. String did it long ago.

Predict all three numbers, then run the lines. Put them in any main you have open.

System.out.println("a".compareTo("b"));
System.out.println("a".compareTo("z"));
System.out.println("app".compareTo("apple"));
-1
-25
-2

All three are negative, and nothing else about them agrees. Negative is the whole answer: in all three cases the left string comes first. The rest is String telling you more than it had to — -25 is the distance from a to z, and -2 is the difference in length.

Your compareTo returns only -1, 0 and 1, because Double.compare does. That is just as correct. Both classes keep the same promise; they are simply not obliged to keep it in the same handwriting.

Done when you have your three guesses written down and can say which part of each number the sort actually uses.

5. What compareTo does with null

Two lines, and they do not do the same thing. Predict both.

Matrix m = new Matrix(new double[][] {{3, 4}});

System.out.println(m.equals(null));
System.out.println(m.compareTo(null));

The first prints

false

and the second does not print at all:

Exception in thread "main" java.lang.NullPointerException

Two contracts, the same argument, opposite answers. equals is required to return false for null — that is the rule you met on Monday. compareTo is required to throw, because there is no honest answer to “does this come before nothing?”

You wrote neither behaviour. The NullPointerException falls out of asking other for its magnitude(). Getting a contract right by accident still counts, but it is worth knowing which of the two you would have had to write by hand.

6. Catch the bug yourself

The callout in section 3 warns you about subtracting magnitudes and casting to int. Now write the check that finds it, instead of taking our word for it.

The property is one sentence: if compareTo says a and b are tied, and that b and c are tied, then a and c have to be tied too. Otherwise it is not an order.

Write src/ContractCheck.java:

public class ContractCheck {
    public static void main(String[] args) {
        Matrix[] ms = {
            new Matrix(new double[][] {{1, 1}}),    // magnitude 2
            new Matrix(new double[][] {{1, 1.6}}),  // magnitude 2.6
            new Matrix(new double[][] {{1, 2}}),    // magnitude 3
        };

        for (Matrix a : ms)
            for (Matrix b : ms)
                for (Matrix c : ms)
                    tiesAreTransitive(a, b, c);

        System.out.println("no violation found");
    }

    static void tiesAreTransitive(Matrix a, Matrix b, Matrix c) {
        if (a.compareTo(b) != 0 || b.compareTo(c) != 0) return;
        assert a.compareTo(c) == 0
            : a.magnitude() + ", " + b.magnitude() + ", " + c.magnitude();
    }
}

Run it against your own compareTo, then swap in the broken one — return (int) (this.magnitude() - other.magnitude()); — and run it again. The broken version gives you

Exception in thread "main" java.lang.AssertionError: 2.0, 2.6, 3.0

Three magnitudes less than one apart. 2.0 and 2.6 cast to a tie, 2.6 and 3.0 cast to a tie, and 2.0 against 3.0 does not.

If the broken version passes, you left off -ea

assert is switched off by default. Without the flag the JVM skips the line completely and prints no violation found whatever your compareTo does.

java -ea -cp out ContractCheck

A check you have to ask for is a check you can forget to ask for. Put it back in the habit now, not in November.

Done when ContractCheck prints no violation found for your compareTo and throws AssertionError for the broken one.

7. Sort it backwards

Largest magnitude first — without touching compareTo. It stays exactly as you wrote it, and the array still has to come out in the other order.

There is a way. You do not have what it needs yet, so spend five minutes on it and no more; we do it Monday. What is worth having by then is a clear idea of why this is hard, which you only get by trying.