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.
Write
addLastandremoveFirst.addLastwalks 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 forremovein A5.removeFirsthands back the front item and movesfirstpast it. On an empty chain it throwsNoSuchElementException, the exceptionDeque’s ownremoveFirstthrows. Both keepsizeright: it is a field, counted up and down by every method that adds or removes, never walked for, andremoveshows the shape.Done when
addLastPutsItAtTheBackandremoveFirstHandsBackTheFrontare green.Write
reversed. It is a static method with a type parameter of its own:The
<T>before the return type declares it: a static method belongs to no chain, so it has noTto borrow and names one for itself. Walk the chain you are given andaddFirsteach item into a new chain; what comes out is back to front. The chain you were given does not change.Done when
reversedTurnsACopyRoundis green.Write
isSorted, and give it the bound it needs. The header you are given says nothing aboutT:so
Tcan be anything, and anything is not enough. The method has to ask each item whether it is larger than the one after it, andcompareTois not something every type has. Write the body first: walk the chain, and returnfalseat the first pair of neighbours out of order. IntelliJ refuses thecompareTo— read what it says. Then change the header towhich lets in only a
Tthat can be compared with itself, and the body compiles.extendsis the word even thoughComparableis an interface.Done when both
isSortedtests are green, and a lineChain.isSorted(new Chain<Object>())is refused when you try it anywhere (then delete it).
Part 2 — a set that grows
Make
BucketSetgrow. After Class 12, two of you guessed in the Journal whatHashSetdoes thatBucketSetdid not: it gets more buckets as it fills, so the chains stay short. Writegrow: 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.emptyBucketsandbucketForare there to use. Then makeaddcallgrowwhen, after an item has gone in,size()is larger thanbucketCount().Done when
growsWhenTheItemsOutnumberTheBucketsis 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
Write
Pair. A new file,src/main/java/Pair.java, holdingpublic class Pair<A, B>: two things of any two types kept together, a word and its count, a time and a text. Twofinalfields,firstof typeAandsecondof typeB; a constructorPair(A first, B second);first()andsecond(), which return them; andswapped(), which returns a newPair<B, A>with the two the other way round and leaves this one as it was.Done when
new Pair<>("one", 1).swapped().first()is1,.second()is"one", and the pair it was made from still says"one"first.Give
Pairitsequals,hashCodeandtoString. Equal when both parts are equal, in order:(one, 1)is not(1, one).hashCodeagrees withequals, as it did in A3.toStringis 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 isother instanceof Pair<?, ?> that— a pair of something and something — and thenthat.firstandthat.secondare compared withequals.Done when two pairs made from
"one"and1are 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.
Write
PairTest. A new file,src/test/java/PairTest.java, with at least three tests: one forswapped, one forequalsandhashCode, one fortoString. Each builds a pair or two and checks what comes back.Done when the arrow beside
PairTestruns three green tests.Add one test to
ChainTest.removeFirston an empty chain throwsNoSuchElementException, and no test says so. WriteremoveFirstOnAnEmptyChainThrowsthe waygetPastTheEndThrowsis written: the call insidetry,fail(...)on the line after it, and acatchfor the exception you expect.failis reached only when nothing was thrown.Done when it is green, and goes red if you make
removeFirstreturnnullfor 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.
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 inaddFirst: 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]theninsert(4)gives[1, 4, 4, 9].size()andtoString(), as inChain.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,aandb, and atailfor 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, insrc/test/java, with one test forinsertand one formerge, each checkingtoString. Themergetest 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.