Class 8 — Monday, September 21

Two collections holding the same two objects, disagreeing about how many they hold. Then the one change that settles it.

Sections 1 and 3 run on the projector — keyboards down, and section 3 wants a prediction in the Journal before anything runs. Sections 2 and 4 are in your own A4 repo, in pairs.

  1. One order, or many?
  2. A comparator of your own
  3. Two sets that disagree — predict first
  4. Make compareTo agree with equals
  5. Reverse it without writing a second one
  6. Two keys, one order
  7. A TreeSet that was told how to compare

Sections 1 to 4 are the class. Sections 5 to 7 go past anything you have been asked for — take them in order if you get there, and do not rush section 4 to reach them.

1. One order, or many?

Keyboards down.

Matrix has one compareTo. On Wednesday you named collections of your own that you would want sorted two different ways.

A class can only have one compareTo. So:

Where does the second order go?

It goes in a class of its own. That class implements Comparator<Matrix>, and the one method it requires takes two matrices rather than one:

public int compare(Matrix a, Matrix b)

Arrays.sort takes one as a second argument. Same array, same Matrix, a different order:

Arrays.sort(matrices);                      // the order Matrix has
Arrays.sort(matrices, new SomeComparator()); // an order you supplied

Matrix does not change between those two lines. The sorted order is not a property of the class.

2. A comparator of your own

Keyboards up. Pairs.

Write src/ByFirstEntry.java — a Comparator<Matrix> that orders matrices by their top-left number alone, smallest first.

import java.util.Comparator;

public class ByFirstEntry implements Comparator<Matrix> {

    @Override
    public int compare(Matrix a, Matrix b) {
        ...
    }
}

getEntry(0, 0) gets you the number. Sort this array with it and print the result:

Matrix[] ms = {
    new Matrix(new double[][] {{5, 1}}),
    new Matrix(new double[][] {{2, 9}}),
    new Matrix(new double[][] {{5, 30}}),
    new Matrix(new double[][] {{2, 0}}),
};

Done when you get

[2.0, 9.0] [2.0, 0.0] [5.0, 1.0] [5.0, 30.0]

Look at the two 2s. [2.0, 9.0] came before [2.0, 0.0] in the array you started with, and it still does. Your comparator said those two tie, and the sort left tied elements exactly where it found them. Keep that array around — sections 5 and 6 both use it.

3. Two sets that disagree

Keyboards down. Prediction before it runs.

Two matrices. They are not the same matrix, and they have the same magnitude:

Matrix a = new Matrix(new double[][] {{1, 0}, {0, 0}});
Matrix b = new Matrix(new double[][] {{0, 1}, {0, 0}});

Set<Matrix> hashed = new HashSet<>(List.of(a, b));
Set<Matrix> sorted = new TreeSet<>(List.of(a, b));

System.out.println(hashed.size() + " " + sorted.size());

A TreeSet is a Set that keeps its contents in order. It uses compareTo to do it.

Write your answer in the Journal before it runs. One line is enough and a guess counts as a line.

What two numbers does this print?

2 1

The HashSet kept both. The TreeSet threw one away.

Neither collection is broken. They asked different questions:

a.equals(b)    = false
a.compareTo(b) = 0

HashSet asked equals, got false, and kept both. TreeSet never called equals at all. It asked compareTo, got zero, and a zero means these two belong in the same place — so as far as it is concerned you handed it the same matrix twice.

Nothing warned you. The code compiled, ran, and quietly lost a matrix.

4. Make compareTo agree with equals

Keyboards up. Pairs.

Your compareTo returns zero for two matrices that equals says are different. That is the disagreement. Fix it in Matrix.java.

If your Matrix has no compareTo at all yet, give it one first — ordering by magnitude(), smallest first — and then carry on.

Compare the magnitudes first, exactly as now. When those come out equal, keep going rather than returning zero: compare the shapes, then the numbers, until you find something that differs. Two matrices that really are equals will run out of things to compare, and that is when zero is the right answer.

Done when the two lines from section 3 print

2 2

and one of you can say out loud which of the two collections changed its mind.

There are three things in a Matrix and you compare them in order, stopping at the first one that differs:

  1. the magnitude
  2. the number of rows, then the number of columns
  3. the cells, in whatever order you like, as long as it is the same order every time

Only when all three run out do you return zero. Double.compare and Integer.compare each do one step in one line.

The Comparable javadoc calls this being consistent with equals, and says it is “strongly recommended” rather than required. Section 3 is what the recommendation is protecting.

5. Reverse it without writing a second one

You want largest-first as well. You do not need another class.

Arrays.sort(ms, new ByFirstEntry().reversed());

reversed() is a method every Comparator already has. It hands you back another comparator that asks yours and flips the answer.

Done when you get

[5.0, 1.0] [5.0, 30.0] [2.0, 9.0] [2.0, 0.0]

The 5s moved ahead of the 2s, which is what you asked for.

But look inside the 5s. [5.0, 1.0] is still before [5.0, 30.0] — the same order they were in before. reversed() did not reverse the array. It reversed the rule, and two elements that tie under the rule are still tied under the reversed rule, so they stay where they were.

If you had reversed the array itself, the 5s would have come out the other way round.

There is a reason this is a method and not something you write by hand. The obvious way to reverse a comparator is to negate what it returns. That is wrong, and it is wrong rarely enough to survive testing: the most negative int has no positive counterpart, so negating it gives you back a negative number and the order silently breaks on exactly one pair of inputs.

6. Two keys, one order

Section 2 left [2.0, 9.0] and [2.0, 0.0] tied. Say you want the tie broken by magnitude instead of by luck.

Comparator<Matrix> chained =
    new ByFirstEntry().thenComparing(Comparator.naturalOrder());

Arrays.sort(ms, chained);

thenComparing builds one comparator out of two. It asks the first one; if the answer is zero it asks the second. Comparator.naturalOrder() is the order the class already has — the compareTo you fixed in section 4.

Done when you get

[2.0, 0.0] [2.0, 9.0] [5.0, 1.0] [5.0, 30.0]

Compare that with section 2’s line. The two 2s have swapped, and the two 5s have not — [5.0, 1.0] has magnitude 6 and [5.0, 30.0] has magnitude 35, so they were already in the right order for the tie-break.

You can keep going. thenComparing returns a comparator, so it has a thenComparing of its own, and a reversed(). Three keys is three calls.

7. A TreeSet that was told how to compare

This is the one to get to.

A TreeSet does not have to use the class’s own order. You can hand it a comparator when you build it, and then that is what it uses to decide what counts as a duplicate.

Two matrices, different, same top-left number:

Matrix p = new Matrix(new double[][] {{5, 1}});
Matrix q = new Matrix(new double[][] {{5, 30}});

Set<Matrix> told = new TreeSet<>(new ByFirstEntry());
told.addAll(List.of(p, q));

Predict all three numbers before you run them, then put the same two matrices into a HashSet and into a plain new TreeSet<>() as well, and print all three sizes.

HashSet          2
TreeSet natural  2
TreeSet told     1

Same two objects. Three collections. One of them is holding one matrix.

p.equals(q) is false and it was false in all three cases — nothing about the matrices changed. What changed is who was asked. The last one was told to use ByFirstEntry, ByFirstEntry only looks at the top-left number, and both matrices have a 5 there.

Section 4 made compareTo agree with equals and that fixed the middle line. It could not fix the last one, because the last one is not using compareTo. A comparator you hand to a collection becomes that collection’s definition of the same, and no method on Matrix gets a vote.