Assignment 6 — Hash sets and queues

Build a hash set of your own, and make a key that cannot move. Then three collections that do not look anything up: a stack, a queue and a priority queue.

Due Oct 6, 2026

This one has its own repo. Accept it the same way you accepted A5, and clone it. Inside are six short classes. BucketSet is the set we started building in class on Wednesday, with the constructor and toString written and every other method throwing until you write it. Point is the point from Class 6, except that this one can move, and LostKey is Wednesday’s demo. Brackets, HotPotato and ShortestFirst are Monday’s: each has a main that tries it out, and a method that throws until you write it.

A floor, if you run out of time. Tasks 1, 2 and 3 are the ones to get working: a set that can hold, find and forget, and a key that cannot move. Everything else is measured on top of them. Push what you have even if it is only the floor. Partial work you pushed beats finished work you did not.

Task 6 is the one to start early if you can. It asks you to write a guess down before you run the code, and that goes badly in a hurry.

Part 1 — a set of your own

BucketSet is a list of buckets, and each bucket is an ArrayList of the things in it. The five list methods you need are add, contains, remove, get and size; contains and remove find things with equals.

It holds Objects, so it holds anything and promises nothing about what comes back out. Making it hold one type is generics, and it is not this week.

Write bucketFor, add and contains. We started these in class.

bucketFor turns an object into the one bucket it can be in: ask the object for its hashCode, and use that to pick an index. add puts the object in that bucket unless an equal one is already there, and returns whether it did. contains looks in that bucket and nowhere else.

A hash code can be negative, and % of a negative number is negative. "bucket".hashCode() is one such word. Math.floorMod does what % was supposed to do.
Write size and remove. size counts across every bucket. remove takes out the object equal to the one you pass, and returns whether there was one.

Part 2 — the key that cannot move

Make Point unable to change. Wednesday’s LostKey put a point into a map, moved it, and the map could not find it again. Nothing in hashCode changed; the point did. Take that ability away.

Make both fields final. Then moveTo can no longer change anything, so change what it does instead: it returns a new Point at the new coordinates and leaves this one exactly as it was. Matrix.add and Fraction.add have both worked this way since A2.

LostKey stops compiling the moment you do this, because it was written to move a point that can now not be moved. Fix its one line so that it keeps the new point in a variable, and run it.

Done when LostKey prints true and then home on its first two lines. The line that used to lose the key cannot lose it any more, because there is no longer any way to change a key.

Part 3 — collections that do not look anything up

A stack hands back what went in last. A queue hands back what went in first. A priority queue hands back the smallest, by whatever order you give it. None of them is for asking whether something is there; each is for taking things out in an order. All three are Monday’s, and Monday’s reading describes them.

Check that brackets match. In Brackets, write balanced. It returns whether every (, [ and { in the string is closed by its own partner, the innermost first. Every other character is ignored.

Use a Deque<Character> made with new ArrayDeque<>() as a stack. push each opening bracket. At a closing bracket, pop the last one opened and check that the two are partners. Whatever is still open at the end is a failure too.

A closing bracket with nothing open is the case to think about: pop on an empty deque throws.

Done when main prints
```
true  f(a[i]) { }
false  ([)]
false  (()
false  ())
true
```
Pass the hot potato. The names stand in a line, and the one at the front holds the potato. It is passed passes times, and each pass takes the name at the front and puts it at the back. Whoever holds it after the passes leaves the line, and the game goes on until nobody is left.

In HotPotato, write order, which returns the names in the order they leave. Use a Queue<String> made with new ArrayDeque<>(names): poll takes from the front and offer puts at the back. Leave the list you were given as it was.

Done when main prints
```
[grace, ada, barbara, alan, linus]
[ada, alan, grace, linus, barbara]
```
Take the shortest first. In ShortestFirst, write shortest. It returns the n shortest words, shortest first, or all of them if there are fewer than n. Two words of the same length come out alphabetically.

Put the words into a PriorityQueue<String> made with a comparator of your own, the way you sorted matrices in A4: length first, and the words themselves when the lengths are equal. Then poll it n times.

Done when main prints [hat, sea, ship, ocean].

Then write a guess in a comment above main: what would printing the queue itself show, right after the words go in? Add that print inside shortest and run it. Leave the guess in when the run disagrees with it — especially then — and add one line saying what you think the queue is doing.

Part 4 — say what it does

Give every public method of BucketSet a Javadoc block. The constructor and toString already have one; write the other four in the same shape. Each block says what the method returns, and add and remove say what they return when the object was already there, or was not.

A block starts with /** on its own line, ends with */, and sits directly above the method. That is the whole format, and it is what the checker looks for.

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.

A student presents this one in class on Wednesday, October 14, the Wednesday after fall break.