How to work around this ConcurrentModificationException

Question

I'm trying to implement an algorithm to generate BSP trees within my application. The problem I'm having is that I need to loop through all of the "children" of each "parent", and split them and add those children to a list, and continue to iterate through the children.

I'm lost on how to do this with using concurrent modification.

public void generate() {
    Parent root = new Parent(0, 0, width, height);
    parents.add(root);

    boolean did_split = true;

    while (did_split) {
        did_split = false;
        for (Parent p : parents) {
            if (p.leftChild == null && p.rightChild == null) {
                if (p.width > MAX_SIZE || p.height > MAX_SIZE || Math.random() > 0.25) {
                    if (p.split()) {
                        parents.add(p.leftChild);
                        parents.add(p.rightChild);
                        did_split = true;
                    }
                }
            }
        }
    }   
}

parents is an ArrayList that is defined earlier within the class.

This is not elegant... but may work...Maybe use a semaphore and put the section of the code that makes the modification inside a synchronized() { } block? See here how to use the synchronized keyword: http://stackoverflow.com/questions/5861894/how-to-synchronize-or-lock-upon-variables-in-java — João Rocha da Silva, Jun 28 '15 at 00:35
I actually tried that about 10 minutes after I posted the question. No luck. Surrounded it in a synchronized() {} block, as well as creating a synchronizedList() from the original list and using that, and making the function itself synchronized. — Darren, Jun 28 '15 at 00:37
This may not solve your problem, but look at [this](http://stackoverflow.com/a/http://stackoverflow.com/a/6916419) answer for some information about concurrent implmentations of lists. — Marco, Jun 28 '15 at 00:42
Also, when iterating over an iterable and editing the iterable simultaneously, using an Iterator is safer... or rather not using an iterator is not safe. — Marco, Jun 28 '15 at 00:45
1Darco1, I changed the parents list to a CopyOnWriteArrayList from the answer you posted and it works fine now, thank you! — Darren, Jun 28 '15 at 00:51

score 2 · Answer 1 · answered Jun 28 '15 at 00:46

Since you've got an ArrayList, you can use its ListIterator. As you can't add a new value to something you're iterating over with a plain Iterator (which is what the enhanced-for is using under the hood), using the ListIterator will give you access to an add method.

You'll also have to do a bit more work to get it to insert things in the places you expect it to; namely, you have to move the cursor back one position so that iteration can continue (since you're bounded by whether or not you have an element in your iterator to continue iteration with.

for (ListIterator<Parent> iterator = parents.listIterator(); iterator.hasNext(); ) {
    Parent p = iterator.next();
    if (p.leftChild == null && p.rightChild == null) {
        if (p.width > MAX_SIZE || p.height > MAX_SIZE || Math.random() > 0.25) {
            if (p.split()) {
                parents.add(p.leftChild);
                iterator.previous();
                parents.add(p.rightChild);
                iterator.previous();
                did_split = true;
            }
        }
    }
}

How to work around this ConcurrentModificationException

1 Answers1