Wednesday, January 13, 2010

Rusty Java: in-place updating a collection while iterating

Some areas of my Java grow rusty with time, as with all things. This code looks nice, but completely fails:

public static void main(final String... args) {
    final Set<Foo> foos = new HashSet<Foo>(asList(FOO));

    for (final Foo foo : foos)
        foos.addAll(foo.more);

    System.out.println("foos = " + new HashSet<Foo>(foos));
}

enum Foo {
    QUUX,
    BAZ(QUUX),
    BAR(BAZ),
    FOO(BAR, BAZ);

    private final Set<Foo> more;

    Foo(final Foo... more) {
        this.more = new HashSet<Foo>(asList(more));
    }
}

The goal is to collect all transitive dependencies. What is wrong?

The iterator is not a "current picture" of the collection; it is a snapshot. This code prints only foos = [FOO], updates vanish. Changing to ArrayList only worsens things with the dreaded ConcurrentModificationException.

Correct is to use a list iterator and be careful with cursor position:

public static void main(final String... args) {
    final List<Foo> foos = new ArrayList<Foo>(asList(FOO));
    final ListIterator<Foo> lit = foos.listIterator();

    while (lit.hasNext())
        for (final Foo foo : lit.next().more) {
            lit.add(foo);
            lit.previous();
        }

    System.out.println("foos = " + new HashSet<Foo>(foos));
}

This prints foos = [QUUX, BAZ, BAR, FOO] with the happy side effect of depth-first ordering.

No comments: