Collections Framework

Throughout the Object-Oriented Java course, one decision was always given by the language. The visibility level decided which member would be seen, final decided which variable could never be rebound, a checked exception decided which failure would stand in the signature. The closing lesson measured that none of the three contracts — precondition, postcondition, invariant — eliminates a flaw, they only move where it sits; but the decision was still inside the language, and the compiler could read it from the source every time.

This lesson starts by calling a written library, and the decision is now outside the language. List, Set, Queue, Map are each an interface, and an interface is a promise; but who makes that promise is not read from a single place. An observed behavior can belong to one of three sources — the interface itself, the chosen class, or a rule the caller follows — and the three cannot be told apart in any way by the call’s syntax. ArrayList and LinkedList both accept the same add(0) call, both answer the same get(0) call; which behavior stays the same across both, which changes when the class changes, cannot be seen from the source text. This lesson’s and this course’s question is: who gives the guarantee for an observation you are holding.

Three Implementations, One Question

The question’s answer cannot be found with a single implementation — someone watching one class alone confuses its behavior with the interface’s promise. The measurement therefore lines up three implementations that speak the same interface and asks all three the same question: if the answer is the same across all three, the observation comes from the interface; if the three diverge, the observation belongs to the implementation.

• CO1 — The Guarantee class below is not specific to any family. ask only compares the answers it gathers; being a list, set, queue, or map does not change the criterion.
• CO2 — If an implementation throws an exception during the call, its answer is counted as "error" and compared in the same column as the other two answers; the exception does not open a separate branch.

// Guarantee.java — who gives a behavior's guarantee: the interface, or the implementation
import java.util.*;
import java.util.function.*;

public class Guarantee {
    static int byInterface = 0;
    static int byImplementation = 0;

    final List<String> names = new ArrayList<>();
    final List<Supplier<Object>> suppliers = new ArrayList<>();

    Guarantee add(String name, Supplier<Object> supplier) {
        names.add(name);
        suppliers.add(supplier);
        return this;
    }

    void header(String family) {
        StringBuilder sb = new StringBuilder(String.format("%-36s", family));
        for (String name : names) sb.append(String.format("%-15s", name));
        sb.append("guarantee giver");
        System.out.println(sb);
    }

    void ask(String question, Function<Object, String> observe) {
        List<String> answers = new ArrayList<>();
        for (Supplier<Object> u : suppliers) {
            String y;
            try {
                y = observe.apply(u.get());
            } catch (RuntimeException e) {
                y = "error";
            }
            answers.add(y);
        }
        boolean shared = new HashSet<>(answers).size() == 1;
        if (shared) byInterface++; else byImplementation++;
        StringBuilder sb = new StringBuilder(String.format("%-36s", question));
        for (String y : answers) sb.append(String.format("%-15s", y));
        sb.append(shared ? "interface" : "implementation");
        System.out.println(sb);
    }

    static void summary() {
        System.out.printf("observations: %d interface guarantees, %d implementation behaviors%n",
                byInterface, byImplementation);
    }
}

add adds one implementation to a family; every family calls it three times. ask puts one question to all three implementations at once and runs a single counter: if the answer set drops to a single element (new HashSet<>(answers).size() == 1), the question is written into the interface column; if it does not drop, into the implementation column. The rule is mechanical and has no subject — it does not know which family is being asked, it only counts answers.

Four Families, Fifteen Observations

• CO3 — The source list SOURCE is five fixed elements and stays unchanged across all four families; it is written into the map in the same order too.
• CO4 — All fifteen counted rows come from a single run of the same program; summary gives that run’s total, counting no other row.

// Framework.java — separates the four families' observable promises
import java.util.*;

public class Framework {
    static final List<String> SOURCE = List.of("zulu", "delta", "alfa", "carli", "bravo");

    static Map<String, Integer> fill(Map<String, Integer> m) {
        for (int i = 0; i < SOURCE.size(); i++) m.put(SOURCE.get(i), i);
        return m;
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Guarantee list = new Guarantee()
                .add("ArrayList", () -> new ArrayList<>(SOURCE))
                .add("LinkedList", () -> new LinkedList<>(SOURCE))
                .add("List.of", () -> List.copyOf(SOURCE));
        list.header("list");
        list.ask("is insertion order preserved",
                o -> String.valueOf(new ArrayList<>((List<String>) o).equals(SOURCE)));
        list.ask("is indexed access available", o -> ((List<String>) o).get(1));
        list.ask("does equality look at content",
                o -> String.valueOf(o.equals(new ArrayList<>(SOURCE))));
        list.ask("can an element be added", o -> {
            try { ((List<String>) o).add("extra"); return "yes"; }
            catch (RuntimeException e) { return "no"; }
        });
        list.ask("can a null value be held", o -> {
            try { ((List<String>) o).add(null); return "yes"; }
            catch (RuntimeException e) { return "no"; }
        });
        System.out.println();

        Guarantee set = new Guarantee()
                .add("HashSet", () -> new HashSet<>(SOURCE))
                .add("LinkedHashSet", () -> new LinkedHashSet<>(SOURCE))
                .add("TreeSet", () -> new TreeSet<>(SOURCE));
        set.header("set");
        set.ask("is a duplicate element accepted", o -> {
            Set<String> s = (Set<String>) o;
            s.add("alfa");
            return String.valueOf(s.size());
        });
        set.ask("is iteration order insertion order",
                o -> String.valueOf(new ArrayList<>((Set<String>) o).equals(SOURCE)));
        set.ask("is a null value accepted", o -> {
            try { ((Set<String>) o).add(null); return "yes"; }
            catch (RuntimeException e) { return "no"; }
        });
        System.out.println();

        Guarantee queue = new Guarantee()
                .add("ArrayDeque", () -> new ArrayDeque<>(SOURCE))
                .add("LinkedList", () -> new LinkedList<>(SOURCE))
                .add("PriorityQueue", () -> new PriorityQueue<>(SOURCE));
        queue.header("queue");
        queue.ask("element coming out first", o -> ((Queue<String>) o).poll());
        queue.ask("what is returned when empty", o -> {
            Queue<String> q = (Queue<String>) o;
            while (q.poll() != null) { }
            return String.valueOf(q.poll());
        });
        queue.ask("is iteration order exit order", o -> {
            Queue<String> q = (Queue<String>) o;
            List<String> iteration = new ArrayList<>(q);
            List<String> exit = new ArrayList<>();
            String s;
            while ((s = q.poll()) != null) exit.add(s);
            return String.valueOf(iteration.equals(exit));
        });
        System.out.println();

        Guarantee map = new Guarantee()
                .add("HashMap", () -> fill(new HashMap<>()))
                .add("LinkedHashMap", () -> fill(new LinkedHashMap<>()))
                .add("TreeMap", () -> fill(new TreeMap<>()));
        map.header("map");
        map.ask("is the key unique", o -> {
            Map<String, Integer> m = (Map<String, Integer>) o;
            m.put("alfa", 99);
            return String.valueOf(m.size());
        });
        map.ask("is the key view live", o -> {
            Map<String, Integer> m = (Map<String, Integer>) o;
            Set<String> g = m.keySet();
            m.put("extra", 5);
            return String.valueOf(g.contains("extra"));
        });
        map.ask("is iteration order insertion order",
                o -> String.valueOf(new ArrayList<>(((Map<String, Integer>) o).keySet())
                        .equals(SOURCE)));
        map.ask("is a null key accepted", o -> {
            try { ((Map<String, Integer>) o).put(null, 0); return "yes"; }
            catch (RuntimeException e) { return "no"; }
        });
        System.out.println();

        Guarantee.summary();
    }
}

list                                ArrayList      LinkedList     List.of        guarantee giver
is insertion order preserved        true           true           true           interface
is indexed access available         delta          delta          delta          interface
does equality look at content       true           true           true           interface
can an element be added             yes            yes            no             implementation
can a null value be held            yes            yes            no             implementation

set                                 HashSet        LinkedHashSet  TreeSet        guarantee giver
is a duplicate element accepted     5              5              5              interface
is iteration order insertion order  false          true           false          implementation
is a null value accepted            yes            yes            no             implementation

queue                               ArrayDeque     LinkedList     PriorityQueue  guarantee giver
element coming out first            zulu           zulu           alfa           implementation
what is returned when empty         null           null           null           interface
is iteration order exit order       true           true           false          implementation

map                                 HashMap        LinkedHashMap  TreeMap        guarantee giver
is the key unique                   5              5              5              interface
is the key view live                true           true           true           interface
is iteration order insertion order  false          true           false          implementation
is a null key accepted              yes            yes            no             implementation

observations: 7 interface guarantees, 8 implementation behaviors

Seven of the fifteen rows gathered in the interface column, eight in the implementation column. The split is not arbitrary, and a line can be drawn cutting the table in two: what is held stands in the interface, how and in what order it is held is left to the implementation. That a list preserves insertion order, gives back what it holds by index, and that its equality looks at content — all three are the same across the three classes. That adding the same element a second time will not grow a set, that pulling from an empty queue gives null — these are the same too. By contrast, which order a set or map is walked in, which element comes out of the front of a queue, and whether a container accepts a null value diverge row by row. Most of a behavior list drawn by watching a single class — just HashMap, just PriorityQueue — is not the promise the interface gives.

Optional Operation: The Interface’s Own Reservation

Two rows in the table deserve a separate reading: “can an element be added” and “can a null value be held” were both marked implementation, because the container List.of produces rejects both, ArrayList and LinkedList accept both. But the Collection interface’s own definition calls the add method an optional operation: the interface defines the method, and at the same time says an implementation may reject it. This splits the guarantee question in two — whether the call will succeed is one question, what happens when it fails is a separate question. The first’s answer, in the table above, depended on the implementation; the second is measured below.

• CO5 — All four container kinds share the same trial: try adding a single element, if rejected write the exception’s class name, if accepted write "succeeded".

// Rejection.java — do all rejecting implementations throw the same exception
import java.util.*;

public class Rejection {
    static String attempt(Runnable action) {
        try { action.run(); return "succeeded"; }
        catch (RuntimeException e) { return e.getClass().getSimpleName(); }
    }

    public static void main(String[] args) {
        List<String> mutableList = new ArrayList<>(List.of("a"));
        List<String> fixedList = List.of("a");
        Set<String> fixedSet = Set.of("a");
        Map<String, Integer> fixedMap = Map.of("a", 1);

        System.out.println("ArrayList.add     : " + attempt(() -> mutableList.add("b")));
        System.out.println("List.of(...).add  : " + attempt(() -> fixedList.add("b")));
        System.out.println("Set.of(...).add   : " + attempt(() -> fixedSet.add("b")));
        System.out.println("Map.of(...).put   : " + attempt(() -> fixedMap.put("b", 2)));
    }
}

ArrayList.add     : succeeded
List.of(...).add  : UnsupportedOperationException
Set.of(...).add   : UnsupportedOperationException
Map.of(...).put   : UnsupportedOperationException

Three separate container kinds, three separate packages, give the same rejection with the same class. If this row entered the table above, it would be marked interface because of the shared answer — yet the rejection itself never happens at all for ArrayList, it only happens for the three fixed containers. The contradiction stays only apparent, because two separate questions are getting mixed up. The answer to “is the addition accepted” depends on the implementation, and was counted that way in the previous table. The answer to “which exception falls if it is not accepted” is bound to a single class named in the Collection interface’s javadoc, and does not change across the three packages. The interface does not guarantee a behavior here, it guarantees the form of a rejection: every implementation that rejects, rejects with the same name, the same unchecked exception class. This is why the phrase “optional operation” means not “the operation does not exist” but “the operation may exist, or fall with its name.”

The Bounding Measurement: Agreement Is Weak Evidence

The framework’s rule is a simple inference: if the three answers are the same, it is the interface. This is an inference, it does not look at documentation — and the inference itself can be wrong. The queue table’s third row (is iteration order exit order) gave false for PriorityQueue; for ArrayDeque and LinkedList, true. This row’s divergence with the five-element source was already seen. What happens if the same question is asked of a smaller, four-element source?

• CO6 — The four-element source is five-element SOURCE with its first element (zulu) removed; once the fifth element is added back, the source returns to being byte-for-byte SOURCE again.

// Coincidence.java — observed agreement is not proof of a guarantee
import java.util.*;

public class Coincidence {
    static final List<String> SOURCE = List.of("zulu", "delta", "alfa", "carli", "bravo");

    static boolean iterationEqualsExit(List<String> source) {
        PriorityQueue<String> pq = new PriorityQueue<>(source);
        List<String> iteration = new ArrayList<>(pq);
        List<String> exit = new ArrayList<>();
        String s;
        while ((s = pq.poll()) != null) exit.add(s);
        return iteration.equals(exit);
    }

    public static void main(String[] args) {
        List<String> fourElements = SOURCE.subList(1, 5);
        System.out.println("four-element source            : " + fourElements);
        System.out.println("is iteration order exit order  : " + iterationEqualsExit(fourElements));

        List<String> fiveElements = new ArrayList<>(fourElements);
        fiveElements.add(0, "zulu");
        System.out.println("source once fifth element added: " + fiveElements);
        System.out.println("is iteration order exit order  : " + iterationEqualsExit(fiveElements));
    }
}

four-element source            : [delta, alfa, carli, bravo]
is iteration order exit order  : true
source once fifth element added: [zulu, delta, alfa, carli, bravo]
is iteration order exit order  : false

With the four-element source, PriorityQueue‘s iteration order matches its exit order exactly — by the inference’s own rule, this would count as an interface guarantee. But once the fifth element is added and the source becomes SOURCE itself again, the same question gives false: the result already seen in the queue table. The only difference is the elements themselves; the queue interface never promised anything about iteration order, neither at four elements nor at five. The match that appeared in the four-element case was not a promise the library gave, it was those five names coincidentally lining up with the heap’s layout.

This is how to read the criterion built through the lesson in reverse: agreement observed weakly supports a guarantee, divergence observed proves the absence of a guarantee for certain. Three implementations giving the same answer could be an interface’s promise, or it could equally well be a coincidence born from the data set’s smallness; the only way to tell them apart is to change the data set and ask the same question again. Divergence’s evidentiary power is higher than this, because no coincidence can force three separate classes into three separate answers — a diverging row always shows a real implementation difference.

Summary

• Who gives a behavior’s guarantee cannot be seen from the call’s syntax; three implementations have to be run side by side and their answers compared. If the answer is the same across all three, the observation comes from the interface; if it diverges, it comes from the chosen class.
• Of fifteen questions asked across four families (list, set, queue, map), seven came out as interface guarantees, eight as implementation behavior. What is held stands in the interface; how and in what order it is held is left to the implementation.
• The Collection interface defines methods like add as optional operations: whether they are accepted depends on the implementation, but which exception falls when rejected stays the same across three separate packages — not the rejection itself, but the rejection’s form, is the interface’s promise.
• Bounding measurement: on a four-element source, PriorityQueue’s iteration order matches its exit order by coincidence; once a fifth element is added, the distinction becomes visible again. Observed agreement is not proof of a guarantee; observed divergence proves the absence of one for certain.
• The Gauge core (the class-file information reader) is not used in this lesson; the measurement rests only on run-time observation, because the question asked concerns the promise the library gives, not the compiler.

Next Step

This lesson measured four families as a whole and counted how many of each family’s promises come from the interface. But the distinction between “list,” “set,” and “queue” itself was never questioned — all three are collections, all three can accept the same workload. The next lesson gives the same data to all three interfaces at once and measures which promise each one gives and which information each one silently drops; it is there that LinkedList being both a list and a queue is seen to give the same call two separate meanings.