Groundwork Groundwork

Practice: a lost property register

The station's lost property office keeps a register: what is being held, and how many of each. It is a map, item name to count, and printed it looks like this:

{umbrella=3, phone=1, scarf=2}

Things arrive and things get claimed, so the register changes all day. You are going to write the methods behind the counter.

Everything here uses Chapters 1 to 9: maps, getOrDefault, keySet(), values(), remove, sets and retainAll.

As in Chapter 7, none of these methods should change the register they are handed—they return a new one. An office where looking something up can quietly alter the records is not an office anyone can trust.

An item held zero times is not held. When the last one is claimed, its entry comes out of the register rather than sitting there as a zero.

Each step names the method exactly: its return type, its name and its parameters. Check calls it with the cases under "What it should do," and those cases write each register with Map.of, which makes a map that can never change: a method that changes the register it is handed stops there with an UnsupportedOperationException. So copy the register first, new LinkedHashMap<>(register), and change the copy. Step 7's cases write each list as new ArrayList<>(List.of(...)), as in Chapter 7. A case written " phone".strip() is the plain word "phone" made while the program runs, so an answer that compares item names with == fails it, as in Chapter 7's practice: compare text with .equals.

Steps

Step 1. Write int countOf(Map<String, Integer> register, String item), returning how many are held, and 0 for something that was never handed in. getOrDefault does this in one line.

What it should do:

  • countOf(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "phone") -> 1
  • countOf(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "umbrella") -> 3
  • countOf(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "hat") -> 0
  • countOf(Map.of(), "hat") -> 0
Show a solution
int countOf(Map<String, Integer> register, String item) {
    return register.getOrDefault(item, 0);
}

void main() {
    Map<String, Integer> register = new LinkedHashMap<>();
    register.put("umbrella", 3);
    register.put("phone", 1);
    register.put("scarf", 2);
    IO.println(countOf(register, "phone"));
    IO.println(countOf(register, "hat"));
}

getOrDefault with a default of 0 answers for something that was never handed in. get alone gives back null for it, and null is not an int.

Step 2. Write int totalItems(Map<String, Integer> register), returning how many objects are in the office altogether—6 for the register above, not 3.

What it should do:

  • totalItems(Map.of("umbrella", 3, "phone", 1, "scarf", 2)) -> 6
  • totalItems(Map.of()) -> 0
  • totalItems(Map.of("hat", 5)) -> 5
Show a solution
int totalItems(Map<String, Integer> register) {
    int total = 0;
    for (int count : register.values()) {
        total += count;
    }
    return total;
}

void main() {
    Map<String, Integer> register = new LinkedHashMap<>();
    register.put("umbrella", 3);
    register.put("phone", 1);
    register.put("scarf", 2);
    IO.println(totalItems(register));
}

values() gives the counts, so adding them gives every object in the office. size() is how many kinds of thing are held, which is a different number and looks plausible until someone hands in a second umbrella.

Step 3. Write Map<String, Integer> addItem(Map<String, Integer> register, String item), returning a new register with one more of that item, whether or not it was already there.

What it should do:

  • addItem(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "hat") -> Map.of("umbrella", 3, "phone", 1, "scarf", 2, "hat", 1)
  • addItem(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "phone") -> Map.of("umbrella", 3, "phone", 2, "scarf", 2)
  • addItem(Map.of(), "hat") -> Map.of("hat", 1)
Show a solution
Map<String, Integer> addItem(Map<String, Integer> register, String item) {
    Map<String, Integer> updated = new LinkedHashMap<>(register);
    updated.put(item, updated.getOrDefault(item, 0) + 1);
    return updated;
}

void main() {
    Map<String, Integer> register = new LinkedHashMap<>();
    register.put("umbrella", 3);
    register.put("phone", 1);
    register.put("scarf", 2);
    IO.println(addItem(register, "hat"));
    IO.println(register);
}

The copy is changed and handed back, and the register itself is left as it was. getOrDefault(item, 0) + 1 covers both cases at once: a new item starts from 0, an existing one carries on.

Step 4. Write Map<String, Integer> removeItem(Map<String, Integer> register, String item), returning a new register with one fewer. When the last one goes, drop the entry entirely with remove. Claiming something that is not held changes nothing.

What it should do:

  • removeItem(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "phone") -> Map.of("umbrella", 3, "scarf", 2)
  • removeItem(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "umbrella") -> Map.of("umbrella", 2, "phone", 1, "scarf", 2)
  • removeItem(Map.of("umbrella", 3, "phone", 1, "scarf", 2), "hat") -> Map.of("umbrella", 3, "phone", 1, "scarf", 2)
  • removeItem(Map.of(), "hat") -> Map.of()
  • removeItem(Map.of("umbrella", 3, "phone", 1, "scarf", 2), " phone".strip()) -> Map.of("umbrella", 3, "scarf", 2)
Show a solution
Map<String, Integer> removeItem(Map<String, Integer> register, String item) {
    Map<String, Integer> updated = new LinkedHashMap<>(register);
    if (!updated.containsKey(item)) {
        return updated;
    }
    int left = updated.get(item) - 1;
    if (left == 0) {
        updated.remove(item);
    } else {
        updated.put(item, left);
    }
    return updated;
}

void main() {
    Map<String, Integer> register = new LinkedHashMap<>();
    register.put("umbrella", 3);
    register.put("phone", 1);
    register.put("scarf", 2);
    IO.println(removeItem(register, "phone"));
    IO.println(removeItem(register, "umbrella"));
}

One fewer, and the entry disappears only when the count reaches zero. An item that is not held comes back unchanged, in the copy.

Step 5. Write ArrayList<String> sortedItems(Map<String, Integer> register), returning the item names in alphabetical order. keySet() gives you the names.

What it should do:

  • sortedItems(Map.of("umbrella", 3, "phone", 1, "scarf", 2)) -> new ArrayList<>(List.of("phone", "scarf", "umbrella"))
  • sortedItems(Map.of()) -> new ArrayList<>()
  • sortedItems(Map.of("b", 1, "a", 1)) -> new ArrayList<>(List.of("a", "b"))
  • sortedItems(Map.of("umbrella", 3, "phone", 1, "scarf", 2, "hat", 5, "glove", 4, "book", 7)) -> new ArrayList<>(List.of("book", "glove", "hat", "phone", "scarf", "umbrella"))
Show a solution
ArrayList<String> sortedItems(Map<String, Integer> register) {
    ArrayList<String> names = new ArrayList<>(register.keySet());
    Collections.sort(names);
    return names;
}

void main() {
    Map<String, Integer> register = new LinkedHashMap<>();
    register.put("umbrella", 3);
    register.put("phone", 1);
    register.put("scarf", 2);
    IO.println(sortedItems(register));
}

keySet() gives the names, a new ArrayList holds them, and Collections.sort puts them in alphabetical order. The register's own order is no help: the cases' Map.of registers keep no order at all.

Step 6. Write String busiest(Map<String, Integer> register), returning the name of the item there are most of. Assume no ties.

What it should do:

  • busiest(Map.of("umbrella", 3, "phone", 1, "scarf", 2)) -> "umbrella"
  • busiest(Map.of("hat", 9, "zebra", 2)) -> "hat"
  • busiest(Map.of("a", 1)) -> "a"
  • busiest(Map.of("phone", 1, "scarf", 4, "umbrella", 3)) -> "scarf"
Show a solution
String busiest(Map<String, Integer> register) {
    String best = null;
    for (String item : register.keySet()) {
        if (best == null || register.get(item) > register.get(best)) {
            best = item;
        }
    }
    return best;
}

void main() {
    Map<String, Integer> register = new LinkedHashMap<>();
    register.put("umbrella", 3);
    register.put("phone", 1);
    register.put("scarf", 2);
    IO.println(busiest(register));
}

best starts as null, no item yet, and an item replaces it only with a higher count. Comparing the names themselves, with compareTo, would give the last name alphabetically instead: the zebra case is there to catch exactly that.

Step 7. Write ArrayList<String> inBoth(ArrayList<String> left, ArrayList<String> right), given two lists of item names, returning a sorted list of the names in both, each name once. Turn them into sets and use retainAll.

What it should do:

  • inBoth(new ArrayList<>(List.of("umbrella", "phone")), new ArrayList<>(List.of("phone", "hat"))) -> new ArrayList<>(List.of("phone"))
  • inBoth(new ArrayList<>(List.of("a")), new ArrayList<>(List.of("b"))) -> new ArrayList<>()
  • inBoth(new ArrayList<>(List.of("a", "a", "b")), new ArrayList<>(List.of("b", "a"))) -> new ArrayList<>(List.of("a", "b"))
  • inBoth(new ArrayList<>(List.of("scarf", "hat", "phone")), new ArrayList<>(List.of("phone", "scarf"))) -> new ArrayList<>(List.of("phone", "scarf"))
  • inBoth(new ArrayList<>(List.of("umbrella", "phone")), new ArrayList<>(List.of(" phone".strip(), "hat"))) -> new ArrayList<>(List.of("phone"))
Show a solution
ArrayList<String> inBoth(ArrayList<String> left, ArrayList<String> right) {
    Set<String> both = new TreeSet<>(left);
    both.retainAll(new HashSet<>(right));
    return new ArrayList<>(both);
}

void main() {
    ArrayList<String> left = new ArrayList<>(List.of("umbrella", "phone"));
    ArrayList<String> right = new ArrayList<>(List.of("phone", "hat"));
    IO.println(inBoth(left, right));
}

A TreeSet of the first list holds each name once, sorted, and retainAll keeps only the names the second has too. The repeated a collapses because a set holds one of each.

Step 8. Write Map<String, Integer> registerFrom(ArrayList<String> found), given a list of item names as they were handed in, returning the register that counts them.

What it should do:

  • registerFrom(new ArrayList<>(List.of("hat", "scarf", "hat"))) -> Map.of("hat", 2, "scarf", 1)
  • registerFrom(new ArrayList<>()) -> Map.of()
  • registerFrom(new ArrayList<>(List.of("a", "a", "a"))) -> Map.of("a", 3)
Show a solution
Map<String, Integer> registerFrom(ArrayList<String> found) {
    Map<String, Integer> register = new LinkedHashMap<>();
    for (String item : found) {
        register.put(item, register.getOrDefault(item, 0) + 1);
    }
    return register;
}

void main() {
    ArrayList<String> found = new ArrayList<>(List.of("hat", "scarf", "hat"));
    IO.println(registerFrom(found));
}

The same getOrDefault(item, 0) + 1 as step 3, now in a loop. This is the counting pattern, and it turns up everywhere once you have seen it.