Assignment 7 — Generics and tests

One chain for every type, and a set that grows. Then a class with two type parameters, written from nothing, and the first tests of your own.

Due Oct 20, 2026

This one has its own repo. Accept it the same way you accepted A6, and clone it. It is laid out differently from the earlier ones: the code is under src/main/java, the tests under src/test/java, and a file called pom.xml tells IntelliJ what the project needs. Open the folder in IntelliJ, let it finish loading, and run ChainTest from the arrow beside its name. Some of its tests are green already and some are red. The red ones are the methods you are about to write, and a task is done when its tests are green.

Chain is the WordChain from A5 and the TimeChain from the midterm, written once for every type. BucketSet is the set from A6, holding one type instead of Object. Both are finished except for the methods named below.

Task 3 is the one to start early if you can. It asks you to read a compiler error and act on it, and that goes badly in a hurry.

Part 1 — one chain for every type

Chain<T> holds items of a type T that whoever makes the chain picks: new Chain<String>() holds words, new Chain<Integer>() holds numbers, and the compiler refuses a number put into the words. Inside the class, T is used like any other type: the node holds a T, addFirst takes one, get returns one.

  1. Write addLast and removeFirst. addLast walks to the last node and hangs a new one on it; an empty chain has no last node, and that case is separate, as it was for remove in A5. removeFirst hands back the front item and moves first past it. On an empty chain it throws NoSuchElementException, the exception Deque’s own removeFirst throws. Both keep size right: it is a field, counted up and down by every method that adds or removes, never walked for, and remove shows the shape.

    Done when addLastPutsItAtTheBack and removeFirstHandsBackTheFront are green.

  2. Write reversed. It is a static method with a type parameter of its own:

    public static <T> Chain<T> reversed(Chain<T> chain)

    The <T> before the return type declares it: a static method belongs to no chain, so it has no T to borrow and names one for itself. Walk the chain you are given and addFirst each item into a new chain; what comes out is back to front. The chain you were given does not change.

    Done when reversedTurnsACopyRound is green.

  3. Write isSorted, and give it the bound it needs. The header you are given says nothing about T:

    public static <T> boolean isSorted(Chain<T> chain)

    so T can be anything, and anything is not enough. The method has to ask each item whether it is larger than the one after it, and compareTo is not something every type has. Write the body first: walk the chain, and return false at the first pair of neighbours out of order. IntelliJ refuses the compareTo — read what it says. Then change the header to

    public static <T extends Comparable<T>> boolean isSorted(Chain<T> chain)

    which lets in only a T that can be compared with itself, and the body compiles. extends is the word even though Comparable is an interface.

    Done when both isSorted tests are green, and a line Chain.isSorted(new Chain<Object>()) is refused when you try it anywhere (then delete it).

Part 2 — a set that grows

  1. Make BucketSet grow. After Class 12, two of you guessed in the Journal what HashSet does that BucketSet did not: it gets more buckets as it fills, so the chains stay short. Write grow: make a new list of twice as many empty buckets, and file every item again, because an item’s bucket number changes when the count does. emptyBuckets and bucketFor are there to use. Then make add call grow when, after an item has gone in, size() is larger than bucketCount().

    Done when growsWhenTheItemsOutnumberTheBuckets is green: twenty words into four buckets end up in thirty-two — eight at the fifth word, sixteen at the ninth, thirty-two at the seventeenth — and all twenty are still found.

Part 3 — a class of your own

  1. Write Pair. A new file, src/main/java/Pair.java, holding public class Pair<A, B>: two things of any two types kept together, a word and its count, a time and a text. Two final fields, first of type A and second of type B; a constructor Pair(A first, B second); first() and second(), which return them; and swapped(), which returns a new Pair<B, A> with the two the other way round and leaves this one as it was.

    Done when new Pair<>("one", 1).swapped().first() is 1, .second() is "one", and the pair it was made from still says "one" first.

  2. Give Pair its equals, hashCode and toString. Equal when both parts are equal, in order: (one, 1) is not (1, one). hashCode agrees with equals, as it did in A3. toString is the two in parentheses with a comma between: (one, 1).

    One new thing. Inside equals, the other object’s type parameters cannot be checked while the program runs (Monday says why), so the test is other instanceof Pair<?, ?> that — a pair of something and something — and then that.first and that.second are compared with equals.

    Done when two pairs made from "one" and 1 are equal and share a hash code, and one of them prints as (one, 1).

Part 4 — tests of your own

A test is a method marked @Test that builds something, calls it, and checks a value with assertEquals, assertTrue or assertFalse. ChainTest is the model for the shape, imports included. A test checks a value, never a printed line.

  1. Write PairTest. A new file, src/test/java/PairTest.java, with at least three tests: one for swapped, one for equals and hashCode, one for toString. Each builds a pair or two and checks what comes back.

    Done when the arrow beside PairTest runs three green tests.

  2. Add one test to ChainTest. removeFirst on an empty chain throws NoSuchElementException, and no test says so. Write removeFirstOnAnEmptyChainThrows the way getPastTheEndThrows is written: the call inside try, fail(...) on the line after it, and a catch for the exception you expect. fail is reached only when nothing was thrown.

    Done when it is green, and goes red if you make removeFirst return null for an empty chain instead (then put it back).

Optional — a chain that keeps itself sorted

A bigger one, in a new file, src/main/java/SortedChain.java: a chain whose items are always in ascending order, so that toString prints them sorted without anyone sorting.

public class SortedChain<T extends Comparable<T>>

The bound is on the class this time: only a type that can be compared with itself may go in at all, so every method may call compareTo without asking. Its node class is Chain’s. Build it in this order:

  • insert(T item) puts the item after everything smaller and before the first larger one. The front is the separate case, as in addFirst: an empty chain, or an item smaller than the first. Otherwise walk, holding the node before the place, while the next node’s item is no larger than the new one, and hang the new node after it. [1, 4, 9] then insert(4) gives [1, 4, 4, 9].
  • size() and toString(), as in Chain.
  • merge(SortedChain<T> that) returns a new sorted chain holding everything in this one and in that one, and makes it in one pass down the two. Keep a walker on each chain, a and b, and a tail for the last node of the new chain. Each round, compare the two fronts, hang a new node holding the smaller one on the tail, and move that walker on; when one chain runs out, the rest of the other follows. For [1, 4, 9] and [2, 3, 10]: 1 against 2 gives 1; 4 against 2 gives 2; 4 against 3 gives 3; 4 against 10 gives 4; 9 against 10 gives 9; then [2, 3, 10]’s chain is empty and 10 follows: [1, 2, 3, 4, 9, 10], after five comparisons. Inserting one chain’s items into the other one at a time gives the same chain, but walks from the front for every item.
  • SortedChainTest, in src/test/java, with one test for insert and one for merge, each checking toString. The merge test also checks that the two chains it was made from did not change.

Handing in

Commit and push. The last commit before the deadline is what gets marked.

Every push is graded, one check at a time, and the result lands on your feedback pull request — so push early and read what failed, rather than saving it all for the last night. The checks are ChainTest and BucketSetTest again, with a few of their own; a green test on your machine is a green check there.

A student presents this one in class on Wednesday, October 21.