Layers of Logic

10.3

The Collection Interface

The dozen methods every collection in Java has, and the rule that decides which methods live here rather than in List or Set.

Core16 min read4 exercises
01

Previously on

Section 10.2 showed you Iterable, which promises exactly one thing: you can walk me.

That is not enough to be useful. You cannot add to an Iterable, remove from it, or ask how big it is. Collection is the next level down, and it adds all of that.

02

The problem

You are writing a method that reports on a group of things.

static void report(ArrayList<String> items) { ... }

That works, and it only works for one class. Somebody with a HashSet cannot call it. Neither can somebody with a LinkedList.

You could write the method three times. Or you could ask what all three have in common, and take that instead.

static void report(Collection<String> items) { ... }

Now every one of them fits. The question this section answers is: what exactly are you allowed to do with that parameter?

03

The idea

Collection holds the methods that make sense for every container, and nothing else.

Collection<Integer> c = new ArrayList<>();
c = new LinkedList<>();
c = new HashSet<>();
c = new ArrayDeque<>();      // all of these compile

Whatever is really behind the variable, the same methods are available. That is polymorphism from Section 7.2, applied across a whole framework.

The methods, in groups

GroupMethods
How big is itbasic questionssize(), isEmpty()
Is this in itsearchingcontains(o), containsAll(c)
Change itone at a timeadd(e), remove(o), clear()
Change it in bulkwhole collectionsaddAll(c), removeAll(c), retainAll(c), removeIf(p)
Walk itfrom 10.2iterator(), forEach(action)
Get it outconversiontoArray(), stream()

The rule for what belongs here

One question decides it: does this make sense for every collection?

MethodWhere it lives, and why
size()every container has a countCollection
contains(o)every container can be askedCollection
get(3)a Set has no positionsList only
add(3, e)insert at a positionList only
peek()who is next in lineQueue only

This keeps Collection small and honest. If a method were promoted here that some implementation cannot support, that implementation would have to throw an exception from a method it was forced to declare.

04

Under the hood

Core

The three bulk methods

These are worth knowing because they replace loops you would otherwise write by hand.

Collection<Integer> c = new ArrayList<>(List.of(1, 2, 3, 4, 5));

c.retainAll(List.of(2, 4, 9));      // [2, 4]        keep only what is in both
c.removeAll(List.of(2, 4));         // [1, 3, 5]     remove everything listed
c.containsAll(List.of(1, 3));       // true          are all of these present

retainAll is an intersection. removeAll is a difference. containsAll is a subset test. Three set operations, available on every collection.

Why add returns a boolean

List<Integer> list = new ArrayList<>();
list.add(3);       // true
list.add(3);       // true. A list takes duplicates.

Set<Integer> set = new HashSet<>();
set.add(3);        // true
set.add(3);        // false. Already there.

The boolean means did the collection change because of this call. On a List it is always true, which makes it look pointless until you meet a Set.

The overload trap, in a new place

You met this in Section 7.3. Here it is on a method you will genuinely call.

List<Integer> list = new ArrayList<>(List.of(10, 20, 30, 40));

list.remove(1);                    // removes position 1. Returns 20.
list.remove(Integer.valueOf(1));   // removes the value 1. Not present, returns false.

List has two remove methods:

E       remove(int index);      // from List
boolean remove(Object o);       // from Collection

Passing a plain int matches remove(int) in the first resolution pass from Section 5.1, using no conversion at all. Boxing is never considered.

Notice the return types differ too. One hands back the removed element, the other hands back a boolean. Same name, two completely different jobs.

Not every collection supports every method

List<Integer> fixed = List.of(1, 2, 3);
fixed.add(4);      // UnsupportedOperationException

List.of gives you an unmodifiable list. It implements List, so it must declare add. It cannot support it, so it throws.

This is the cost of a wide interface, and it is the exact problem the “does it make sense for everyone” rule exists to limit. add genuinely does make sense for most collections, so it stays on Collection, and the unmodifiable ones throw.

Worth knowing: List.of, Set.of and Map.of all produce unmodifiable collections. If you need to change one, wrap it:

List<Integer> changeable = new ArrayList<>(List.of(1, 2, 3));

That is why the exercises in this course keep writing new ArrayList<>(List.of(...)) rather than List.of(...) on its own.

Methods added later

Three of the methods in the table did not exist before Java 8: removeIf, forEach and stream.

They were added as default methods, from Section 8.5, which is the only reason they could be added at all. Every class implementing Collection anywhere in the world kept compiling.

Without that feature, stream() could never have been put on Collection, and Phase XI would look completely different.

05

What it costs

A wide interface forces every implementation to declare everything, even the parts it cannot do. List.of(1,2,3).add(4) compiles and throws, and no compiler warning tells you it will.

Collection also promises nothing about speed. contains is one check on a HashSet and a full walk on an ArrayList. Same method, same signature, wildly different cost, and the interface cannot say so.

Nor does it promise order. Walk a List twice and you get the same order. Walk a HashSet twice and you get whatever order the buckets happen to produce.

The remove overload is a genuine trap, and it is on one of the most used methods in the framework.

What you get is a method signature that accepts every container in Java. Write report(Collection<String>) once and it works for callers who have not chosen their data structure yet, or who change their mind later.

06

Check yourself

Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.

  1. What decides whether a method belongs on `Collection` rather than on `List` or `Set`?

    Show the answer

    One question: does it make sense for every collection?

    size() does. Every container has a count. contains() does. Every container can be asked whether something is in it. So both live on Collection.

    get(3) does not. A Set has no positions, so there is nothing for it to return. It lives on List.

    The rule keeps Collection small and honest. If a method were promoted here that some implementation cannot support, that implementation would have to throw an exception from a method it was forced to declare. The framework does have a few of those, and they are considered mistakes.

  2. `Collection.add` returns a `boolean`. When is it ever false?

    Show the answer

    When the collection refused the element.

    A List always accepts, so add is always true there. It is easy to conclude the return value is pointless.

    A Set rejects duplicates. set.add(3) on a set that already holds 3 returns false and changes nothing.

    The boolean means "did the collection change because of this call". That is genuinely useful: if (seen.add(x)) { } is a one line way to do something only the first time you meet a value.

  3. `list.remove(1)` and `list.remove(Integer.valueOf(1))` on a `List<Integer>`. What does each one do?

    Show the answer

    remove(1) removes the element at position 1. On [10, 20, 30, 40] it removes 20 and returns it.

    remove(Integer.valueOf(1)) tries to remove the value 1. It is not there, so it returns false and changes nothing.

    The cause is the overload rule from Section 5.1. List has both remove(int index) and remove(Object o). Passing a plain int matches remove(int) in the first resolution pass, using no conversion at all, so boxing is never considered.

    Notice the return types differ too: one gives you the removed element, the other gives you a boolean. Two methods, one name, completely different jobs.

07

Exercises

Write each solution in VS Code, predict its result, and then run the checks. Reading an example does not replace implementing it.

4 exercises70 pointsabout 80 minutes

The Layers of Logic VS Code extension runs the checks for exercises marked checked. For a manual exercise, run the program and compare its behaviour with the stated requirements and sample output.
A

The remove Overload, Again

Real work·20 min·20 points

checkedex-10-3-a

The overload trap from Phase VII, on a method you will call constantly.

Predict both lines, including what each one returns. The return types are the giveaway: one hands back the removed element, the other hands back a boolean. Two methods that happen to share a name.

Then do both operations deliberately and notice how differently the two calls have to look.

Finish with the Set case. The same call is unambiguous there, and working out why confirms you understand what the compiler is choosing between.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class RemoveTrap {
    static Integer removeAtPosition(List<Integer> l, int index)
    static boolean removeTheValue(List<Integer> l, int value)
    static boolean removeFromSet(Set<Integer> s, int value)
}

removeAtPosition returns the element that was there. removeTheValue returns whether anything was removed. Both change the list they are given.

What your program must do

  • Predict both results and both return types before running
  • Implement the three methods so value and position never get confused
  • Explain the choice using the three resolution passes from Phase V
  • Say why the same call on a Set has no ambiguity
RemoveTrap.java
import java.util.*;

public class RemoveTrap {

    // Take out whatever sits at this index, and return it.
    static Integer removeAtPosition(List<Integer> l, int index) {
        return null; // TODO
    }

    // Take out the element EQUAL to this value. Return whether anything went.
    static boolean removeTheValue(List<Integer> l, int value) {
        return false; // TODO
    }

    static boolean removeFromSet(Set<Integer> s, int value) {
        return false; // TODO
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(10, 20, 30, 40));
        List<Integer> b = new ArrayList<>(List.of(10, 20, 30, 40));

        // TODO: predict both, including the RETURN VALUES, before running
        System.out.println("a.remove(1)                  = " + a.remove(1) + "  -> " + a);
        System.out.println("b.remove(Integer.valueOf(1)) = " + b.remove(Integer.valueOf(1)) + "  -> " + b);

        // TODO: why does the same call on a Set have no ambiguity?
    }
}
Hint 1
There are two remove methods on List. remove(int) means the position. remove(Object) means the value.
Hint 2
Pass an int and the first pass finds an exact match on remove(int), so it never gets as far as considering boxing. To mean the value, box it yourself with Integer.valueOf(value).
Hint 3almost the answer
A Set has no positions, so Set declares only remove(Object). There is nothing for the compiler to choose between.
What this is really testing

Whether you can apply the Phase V resolution order to the most used method in the framework. Same name, two methods, two different jobs, and different return types.

B

The Bulk Methods Replace Loops

Warm up·20 min·15 points

checkedex-10-3-b

Three questions about two groups, and three methods that answer them in one line each.

Work on copies. Two of the three modify the collection you call them on, and that catches people who expect a new collection back.

Then write the intersection by hand and put the two versions next to each other. The hand version needs an iterator, because removing inside a for-each is the bug from Section 10.2.

That comparison is the argument for knowing these three exist.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Bulk {
    static List<String> onDutyAndInjured(List<String> onDuty, List<String> injured)
    static List<String> onDutyNotInjured(List<String> onDuty, List<String> injured)
    static boolean allInjuredAreOnDuty(List<String> onDuty, List<String> injured)
}

All three must leave both lists exactly as they were found. retainAll and removeAll change the list you call them on, so copy first.

What your program must do

  • Use retainAll, removeAll and containsAll for the three questions
  • Copy the list before each bulk call, since they change the list they are called on
  • Write the intersection as a hand loop and compare the two versions
  • Say which bulk method surprised you by changing its receiver
Bulk.java
import java.util.*;

public class Bulk {

    // Who is on duty AND injured. Order follows onDuty.
    static List<String> onDutyAndInjured(List<String> onDuty, List<String> injured) {
        return List.of(); // TODO: retainAll
    }

    // Who is on duty but NOT injured.
    static List<String> onDutyNotInjured(List<String> onDuty, List<String> injured) {
        return List.of(); // TODO: removeAll
    }

    // Is every injured unit also on duty?
    static boolean allInjuredAreOnDuty(List<String> onDuty, List<String> injured) {
        return false; // TODO: containsAll
    }

    public static void main(String[] args) {
        List<String> onDuty  = new ArrayList<>(List.of("Atlas", "Beacon", "Cipher", "Drift"));
        List<String> injured = List.of("Beacon", "Ember");

        // TODO: print all three answers
        // TODO: write the intersection as a hand loop too, and compare the code
    }
}
Hint 1
retainAll keeps only what is in both. removeAll takes out everything in the other list. containsAll just answers yes or no.
Hint 2
All three of those first two work on the list you call them on, not on a copy. new ArrayList<>(onDuty) first, then call the method on the copy, then return the copy.
Hint 3almost the answer
The hand loop is four lines and does the same as one. The bulk version also says what it means, which the loop does not: a reader has to work out that the loop is an intersection.
What this is really testing

Whether you know the three bulk operations exist. Each replaces a loop you would otherwise write, and each is a set operation with a name.

C

The Boolean add Actually Means Something

Warm up·20 min·15 points

checkedex-10-3-c

add returns a boolean. On a List it is always true, which is why most people never notice it.

Run the four lines and find the one that returns false. Then use that fact.

The one line idiom is worth memorising. if (seen.add(x)) does a check and an insert in a single lookup, and it appears in real code constantly.

Finish by saying why the contains version is worse. The answer is not style, it is that you pay for the lookup twice.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class AddReturns {
    static List<String> firstSightings(String[] log)
    static List<String> duplicates(String[] log)
}

firstSightings gives each name once, in the order it was first seen. duplicates gives each repeated name once, in the order the repeat happened. Neither may call contains.

What your program must do

  • Explain what the boolean from add actually means, for a List and for a Set
  • Implement both methods using add's return value and no contains call
  • Say why doing this with contains would be worse
  • Say why list.add always returns true
AddReturns.java
import java.util.*;

public class AddReturns {

    // Each name once, in the order it was first seen. Use add's return value.
    static List<String> firstSightings(String[] log) {
        return List.of(); // TODO
    }

    // Each repeated name once, in the order the repeat happened.
    static List<String> duplicates(String[] log) {
        return List.of(); // TODO
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        Set<String>  set  = new HashSet<>();

        System.out.println("list.add(\"a\") = " + list.add("a"));
        System.out.println("list.add(\"a\") = " + list.add("a"));
        System.out.println("set.add(\"a\")  = " + set.add("a"));
        System.out.println("set.add(\"a\")  = " + set.add("a"));

        String[] log = {"Atlas", "Beacon", "Atlas", "Cipher", "Beacon", "Atlas"};
        // TODO: print both answers
    }
}
Hint 1
set.add(x) returns false when the set already held x. That one boolean answers "have I seen this before" and does the recording at the same time.
Hint 2
For duplicates you need two sets: one for what you have seen, one for what you have already reported. Otherwise a name appearing three times gets reported twice.
Hint 3almost the answer
With contains you hash the name once to look it up and again to add it. The return value gives you the same answer for one hash instead of two, and there is no gap between checking and adding.
What this is really testing

Whether you have noticed that add returns something. On a List it is always true, which trains people to ignore it, and then a Set makes it useful.

D

Methods That Exist and Throw

Real work·20 min·20 points

checkedex-10-3-d

Nine combinations, and they do not all behave the same way.

Predict the whole grid before running. The middle column is the interesting one: Arrays.asList allows one operation and refuses another, and the reason is about what it is a view onto.

Then say what this shows about interface design. List promises add to everyone, and some implementations cannot keep that promise, so they throw instead.

That is the price of a wide interface, and it is exactly the problem the “does this make sense for everyone” rule was trying to limit.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Unsupported {
    static String tryAdd(List<Integer> l)
    static String trySet(List<Integer> l)
    static String tryRemove(List<Integer> l)
}

Each one attempts the operation and returns either "ok" or "UnsupportedOperationException". Nothing else. tryAdd adds 99, trySet replaces slot 0 with 99, tryRemove takes out position 0.

What your program must do

  • Try add, set and remove on List.of, Arrays.asList and ArrayList
  • Predict all nine before running, then record which work and which throw
  • Explain why Arrays.asList allows set but refuses add
  • Say what this shows about the cost of a wide interface
Unsupported.java
import java.util.*;

public class Unsupported {

    // Attempt it. Return "ok" or "UnsupportedOperationException".
    static String tryAdd(List<Integer> l) {
        return "ok"; // TODO: add 99
    }

    static String trySet(List<Integer> l) {
        return "ok"; // TODO: put 99 at slot 0
    }

    static String tryRemove(List<Integer> l) {
        return "ok"; // TODO: take out position 0
    }

    public static void main(String[] args) {
        // TODO: predict all nine before running
        // TODO: print the nine results as a table
        // TODO: explain why Arrays.asList allows set but not add
    }
}
Hint 1
Wrap each attempt in try and catch UnsupportedOperationException. Return the name of the exception from the catch.
Hint 2
Arrays.asList is a window onto a real array. Replacing a slot is something an array can do. Adding a slot is not, because an array's length never changes.
Hint 3almost the answer
The cost is that a method exists on the type and still refuses to run. You cannot tell from the type whether add will work, so the failure arrives when the program runs rather than when it compiles.
What this is really testing

Whether you understand the cost of a wide interface. Every implementation must declare every method, including the ones it cannot support.

08

After the credits

Collection left out everything about position. No get(3), no add(3, e), no indexOf.

Section 10.4 is where those come back, on List, along with the four implementations that support them: ArrayList, LinkedList, Vector and Stack.

That is also where the question from Section 4.2 finally gets settled. Contiguous memory against scattered nodes, random access against cheap insertion. You already have the theory, and you have already measured the 806 millisecond version in Section 10.2.

Two of the four implementations are historical mistakes that Java keeps for compatibility. Knowing which two, and why, separates people who use the framework from people who understand it.

Threads you opened in this section