The problem
We often see people asking question about entity management, involving removing items from a list, during iteration, or adding new items to them.
Naive attempts
A naive attempt usually results in a rather confusing ConcurrentModificationException, thrown by some of Java’s provided collections. When getting rid of this exception, more often than not, there is an hard to discover off-by-one bug lingering in there, leading to silent errors.
// attempt 1
for(Entity current: entities) {
if(current.isDead()) {
entities.remove(current); // exception
}
else if(current.isShooting()) {
entities.add(new BulletEntity()); // exception
}
}
// attempt 2
for(int i=0; i<entities.size(); i++) {
Entity current = entities.get(i);
if(current.isDead()) {
entities.remove(i); // silent error, skips the next element!
}
else if(current.isShooting()) {
entities.add(new BulletEntity()); // OK
}
}
Solution A
Normally helpful people are suggesting to ‘correct i’, after a removal of an element and all is well, except performance.
for(int i=0; i<list.size(); i++) {
Entity current = list.get(i);
if(current.isDead()) {
list.remove(i); // extremely slow
i--; // correct i
}
else if(current.isShooting()) {
list.add(new BulletEntity());
}
}
Solution B
Iterating the collection in the opposite order. This has a few downsides: first, you force yourself to visit entities in opposite order, which might alter logic. Second, it prevents you from visiting elements you add to the collection while iterating over it. Last but not least, when removing an element from a List, you trigger an array-shift, which is time consuming, especially as it is performed for every removed element.
for(int i=list.size()-1; i>=0; i--) {
Entity current = list.get(i);
if(current.isDead()) {
list.remove(i); // extremely slow
}
else if(current.isShooting()) {
list.add(new BulletEntity()); // will not be visited this iteration
}
}
Solution C (fast and correct, but deemed a hassle)
A fast solution is to create two lists, where you iterate over the first, while also adding new entities to the first, while copying enities that ‘survive’ to the second list. When all entities are visited, you clear the list that was just iterated, and swap both lists. This allows you to remove while iterating without any overhead, and adding items as you go, while processing those immediately during iteration. It however brings some bookkeeping, and requires twice the amount of memory. Clearing the list that was just iterated over is also less than optimal, as all array elements have to be nulled behind the scenes.
for(int i=0; i<curr.size(); i++) {
Entity current = curr.get(i);
if(!current.isDead()) {
next.add(current);
}
else if(current.isShooting()) {
curr.add(new BulletEntity()); // will be visited this iteration
}
}
curr.clear();
// swap lists
temp = curr;
curr = next;
next = temp;
Proposed Solution (fast and convenient)
We can use the strategy of Solution C and merge the two lists into one. We keep the support for the feature of iterating over new entities in the current loop, and removing entities without the overhead that is imposed by the typical List implementation. Then we use the Iterator/Iterable interfaces to support convenient syntax, while also retaining support for methods like remove() and add(...).
ReadWriteCollection<Entity> entities = ...;
for(Entity entity: entities) {
if(current.isDead()) {
entities.remove(); // very fast
}
else if(current.isShooting()) {
entities.add(new BulletEntity()); // will be visited this iteration
}
}
You can see that the ‘entities’ instance is stateful, so that while iterating, ‘entities.remove()’ knows which element to discard.
The following demo code will show how to use the class:
ReadWriteCollection<String> data = new ReadWriteCollection<>();
data.add("a");
data.add("b");
data.add("c");
data.add("d");
data.add("e");
data.add("f");
data.add("g");
for (String str : data) {
System.out.println("found: " + str);
}
System.out.println(data); // "[a, b, c, d, e, f, g]"
for (String str : data) {
// print the element
System.out.println("found: " + str);
if (str.equals("e")) {
// remove while iterating
data.remove();
// add while iterating
data.add("ee");
} else if (str.equals("ee")) {
System.out.println("encountered added item!");
}
}
System.out.println(data); // "[a, b, c, d, f, g, ee]"
// fast clearing of the collection while iterating over it
for (String str : data) {
data.remove();
}
// or use the clear method: both versions are O ( n )
data.clear();
System.out.println(data); // "[]"
Implementation
import java.util.*;
public class ReadWriteCollection<E> implements Iterator<E>, Iterable<E> {
private int iterateIndex, retainIndex, endIndex;
private E[] items;
private boolean doRetain;
@SuppressWarnings("unchecked")
public ReadWriteCollection() {
items = (E[]) new Object[4];
}
public void add(E item) {
if (endIndex == items.length) {
items = Arrays.copyOf(items, Math.max(4, items.length << 1));
}
items[endIndex++] = item;
}
@Override
public Iterator<E> iterator() {
this.prepareForAccess();
return this;
}
@Override
public boolean hasNext() {
if (doRetain) {
items[retainIndex++] = items[iterateIndex - 1];
doRetain = false;
}
if (iterateIndex == endIndex) {
flip();
return false;
}
return endIndex > 0;
}
@Override
public E next() {
if (iterateIndex == endIndex) {
throw new NoSuchElementException();
}
doRetain = true;
return items[iterateIndex++];
}
@Override
public void remove() {
if (iterateIndex == 0) {
throw new NoSuchElementException();
}
if (!doRetain) {
throw new IllegalStateException("already removed");
}
doRetain = false;
}
public void clear() {
retainIndex = 0;
flip();
}
public void trimToSize() {
this.prepareForAccess();
this.items = Arrays.copyOf(items, endIndex);
}
private void prepareForAccess() {
if ((iterateIndex | retainIndex) == 0) {
// no need to init
return;
}
// process any unprocessed value from the previous iteration
int off = iterateIndex + (doRetain ? 0 : 1);
int len = endIndex - off;
if (off != retainIndex) {
System.arraycopy(items, off, items, retainIndex, len);
}
retainIndex += len;
this.flip();
}
private void flip() {
Arrays.fill(items, retainIndex, endIndex, null);
endIndex = retainIndex;
retainIndex = 0;
iterateIndex = 0;
doRetain = false;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < retainIndex; i++) {
sb.append(items[i]).append(",");
}
for (int i = iterateIndex - (doRetain ? 1 : 0); i < endIndex; i++) {
sb.append(items[i]).append(",");
}
if (sb.length() > 1) {
sb.setLength(sb.length() - 1);
}
return sb.append("]").toString();
}
}
