Class 14 — Wednesday, October 14
A6 is presented first. Section 1 runs on the projector: 1.1 keyboards down, predicting, and 1.2 with everyone typing along. Section 2 is in pairs: 2.1 and 2.2 before the break, 2.3 and 2.4 after it. Section 3 is the first tests, on the projector after the break; then JUnit goes into your own project, and you write two of your own.
- One chain for every type: the chain that holds anything — predict first; then one type, chosen by whoever makes it — the room dictates
- The chain at work: finish it and use it twice and the last item; then the largest and take them all out
- A test is a method — on the projector; then JUnit in your own project and two of your own
The cores are the class. The “then” tasks go past anything you have been asked for — take them in order if you get there.
1. One chain for every type
You have written this chain twice: WordChain in A5 held words, and the midterm’s TimeChain held times. Two files, the same code, one word different. Here it is a third time, holding Object, so that it holds anything. Paste it into a new file, Chain.java, in any project you have open — not A7’s.
public class Chain {
private static class Node {
final Object item;
Node next;
Node(Object item, Node next) {
this.item = item;
this.next = next;
}
}
private Node first;
private int size;
public void addFirst(Object item) {
first = new Node(item, first);
size++;
}
public int size() {
return size;
}
public boolean contains(Object item) {
for (Node node = first; node != null; node = node.next) {
if (node.item.equals(item)) {
return true;
}
}
return false;
}
public Object get(int index) {
Node node = first;
for (int i = 0; i < index && node != null; i++) {
node = node.next;
}
if (node == null) {
throw new IndexOutOfBoundsException("index " + index);
}
return node.item;
}
@Override
public String toString() {
StringBuilder out = new StringBuilder("[");
for (Node node = first; node != null; node = node.next) {
if (node != first) {
out.append(", ");
}
out.append(node.item);
}
return out.append("]").toString();
}
}1.1 The chain that holds anything
Keyboards down. Predict each run before it happens.
A chain of Object takes anything, and promises nothing about what comes back out. On the projector, in a main:
Chain words = new Chain();
words.addFirst("cat");
words.addFirst("dog");
String front = words.get(0);Does the last line compile?
No: incompatible types: Object cannot be converted to String. get hands back an Object, and the compiler will not let you treat it as a String, because nothing says it is one. The way through is a cast:
You promise the compiler that this Object is a String, and the compiler takes your word. It compiles, and it prints dog.
The same chain holding numbers, summed:
Chain numbers = new Chain();
for (int i = 1; i <= 5; i++) {
numbers.addFirst(i);
}
int sum = 0;
for (int i = 0; i < numbers.size(); i++) {
sum += (Integer) numbers.get(i);
}
System.out.println(sum);A cast on every read, and the 7 on the next line goes into the chain of words without a word said:
Both lines compile. What happens when it runs?
addFirst(7) is accepted: 7 is boxed to an Integer, and an Integer is an Object. The cast compiles, because a cast is a promise. Then the program runs, prints 15, and stops:
Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer
cannot be cast to class java.lang.String
The mistake was made on the addFirst line and reported two lines later, after the program had started. In a bigger program the two lines are in different files, and the report comes from whoever was running it. Nothing stopped the 7 going in, and nothing could: the chain does not know what it holds. This is what every list in Java was until 2004, when ArrayList held Object and every get wore a cast.
1.2 One type, chosen by whoever makes the chain
Keyboards up, typing along. The room dictates and the projector types.
Make the chain hold one type, chosen by whoever makes it. The type gets a name, T, declared once after the class name, and T is then used wherever Object stood for “the item”. The top of the file, together:
public class Chain<T> {—Tis a type parameter: a name for a type that is filled in later, the way a method’s parameter is a name for a value that is filled in later.private static class Node<T> {— the node holds aTtoo. It is a static class, so it cannot borrow the chain’sTand declares its own.final T item;andNode<T> next;Node(T item, Node<T> next) {private Node<T> first;— andsizestays anint: it counts items, whatever they are.public void addFirst(T item) {and inside itfirst = new Node<>(item, first);— the empty brackets are the diamond: the type is already known from the left, so the right does not repeat it.
The rest of the file still says Object, and that is section 2. First, 1.1’s lines again, against Chain<String>:
Chain<String> words = new Chain<>();
words.addFirst("cat");
words.addFirst("dog");
String front = words.get(0);
words.addFirst(7);Which line does the compiler refuse now, and which line lost its cast?
String front = words.get(0); compiles with no cast: Chain<String> is a parameterized type, the chain with its T filled in, so the compiler knows what get hands back. And words.addFirst(7) is refused: incompatible types: int cannot be converted to String. The same mistake as in 1.1, reported on the line where it is made, before the program runs. That is the whole point: the check moved from the run to the compile, and the cast is gone.
Then Chain<int> — refused too: a type parameter takes a class, never a primitive. The class for int is Integer, and Java boxes on the way in:
compiles, and 7 goes in as an Integer.
2. The chain at work
Keyboards up. Pairs. 2.1 and 2.2 are the core before the break; 2.3 is the core after it, and 2.4 is for pairs that are done.
2.1 Finish it, and use it twice
The same file.
Replace the Object left in contains, get and toString the same way: a Node<T> in each loop, a T in contains’s parameter and get’s return type. Then this main:
Chain<String> words = new Chain<>();
words.addFirst("cat");
words.addFirst("dog");
words.addFirst("owl");
String front = words.get(0);
Chain<Integer> numbers = new Chain<>();
for (int i = 1; i <= 5; i++) {
numbers.addFirst(i);
}
int sum = 0;
for (int i = 0; i < numbers.size(); i++) {
sum += numbers.get(i);
}
System.out.println(front + " " + sum);Two things to notice. String front = words.get(0); has no cast: the compiler knows what a Chain<String> hands back. And sum += numbers.get(i) adds an Integer to an int: Java unboxes on the way out.
Done when it prints owl 15, and words.addFirst(7) is refused when you add the line (then delete it).
2.2 The last item
Same pair, same file.
Write last, which returns the item at the back of any chain. It is a static method, so it belongs to no chain and has no T to borrow: it declares one of its own, before the return type.
Walk to the node with no next and return its item. An empty chain has no last item: throw NoSuchElementException, from java.util.
Done when Chain.last(words) is cat and Chain.last(numbers) is 1.
2.3 The largest
After the break.
Write max, which returns the largest item in a chain, by compareTo. Start with the header last has, with max as the name, and write the body: keep the largest so far, and replace it whenever a node’s item compares larger.
IntelliJ refuses compareTo. Read what it says: T could be anything, and not everything can be compared. The header has to say what T must be:
A bound on the type parameter: only a T that can be compared with itself may come in, so compareTo is there to call. It says extends even though Comparable is an interface.
Done when Chain.max(words) is owl, Chain.max(numbers) is 5, and Chain.max(new Chain<Object>()) is refused (then delete the line).
2.4 Take them all out
The bigger one.
Write removeAll, which takes out every node holding an item equal to the one given, and returns how many came out.
The front may have to go more than once, so that is a while. Then every node after a kept one: holding a node, take out node.next as often as it is a match, before moving on. The midterm’s removeBefore had this shape. size has to come down by what went out.
Done when removeAll("owl") on [owl, dog, owl, cat, owl] returns 3 and leaves [dog, cat], and removeAll("elk") returns 0 and changes nothing.
3. A test is a method
Keyboards down. On the projector: a project with tests in it, and ChainTest run from the arrow beside the class name.
What comes up is a list: some green, some red. Each line is one test, a method marked @Test, and the arrow beside a method’s name runs that one alone. A red one’s message says what it expected and what it got; the red ones here are methods that are not written yet. Two of the green ones:
@Test
void addFirstPutsItAtTheFront() {
Chain<String> words = owlDogCat();
assertEquals("owl", words.get(0));
assertEquals(3, words.size());
assertEquals("[owl, dog, cat]", words.toString());
}
@Test
void getPastTheEndThrows() {
Chain<String> words = owlDogCat();
try {
words.get(3);
fail("get(3) on a chain of three should have thrown");
} catch (IndexOutOfBoundsException expected) {
// The right outcome. Nothing to check: reaching here is the pass.
}
}assertEquals(expected, actual) — what you expect first, then what the code gave. assertTrue and assertFalse take one boolean. A test checks a value, never a printed line: nothing here prints, and nobody reads output to decide. When the right outcome is an exception, the call sits inside try with fail on the line after it, and the catch names the exception you want; fail is reached only when nothing was thrown.
The project on the projector is A7’s, out today. The Chain in it is the one you just made, finished, with a few more methods.
3.1 JUnit in your own project
Pairs, in the project that holds your Chain.java.
A test needs JUnit, and IntelliJ fetches it for a project that says it needs it. Four steps:
A new file in the project’s root folder, the folder that holds
src, namedpom.xml, with this in it:<?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>cmsc230</groupId> <artifactId>class-14</artifactId> <version>1</version> <properties> <maven.compiler.release>17</maven.compiler.release> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> </properties> <dependencies> <dependency> <groupId>org.junit.jupiter</groupId> <artifactId>junit-jupiter</artifactId> <version>5.14.4</version> <scope>test</scope> </dependency> </dependencies> <build> <sourceDirectory>src</sourceDirectory> <testSourceDirectory>test</testSourceDirectory> </build> </project>The last block keeps your code where it is and names
testas the folder for tests.Right-click
pom.xmlin the project tree, then Add as Maven Project. IntelliJ reads it and fetches JUnit; a Maven tab appears on the right. If a Load Maven project notification shows up instead, click it.A new folder
testbesidesrc, and in it a new fileChainTest.javathat starts with the two imports from section 3 andclass ChainTest {.An arrow appears beside the class name and beside each
@Testmethod once the import has finished. That is how a test runs.
3.2 Two of your own
Pairs, in your ChainTest from 3.1, or in A7’s.
Add getWalksFromTheFront: build [owl, dog, cat] with three addFirst calls, and check that get(1) is dog and get(2) is cat.
Done when it is green, and goes red when you change dog to cat (then put it back).
Then removingTheLastItemLeavesTheRest: remove cat from [owl, dog, cat], and check that remove answered true, that the chain prints [owl, dog], and that size() is 2.
Done when both are green, and a wrong expected value turns the one test red and no other.