Modifying a Set While Iterating
ArraySet<T> implements a set with a backing array. The items are at indices 0 through size - 1, in no particular order. remove closes the gap by moving the last item into it. The iterator is an inner class that traverses the array with a cursor:
public class ArraySet<T> implements Set<T> {
private T[] arr; // the backing array
private int size; // how many items the set holds
public boolean add(T item) {
if (item == null) {
throw new IllegalArgumentException();
}
if (indexOf(item) != -1) {
return false;
}
if (size == arr.length) {
grow();
}
arr[size] = item;
size++;
return true;
}
public boolean remove(T item) {
if (item == null) {
throw new IllegalArgumentException();
}
int i = indexOf(item);
if (i == -1) {
return false;
}
arr[i] = arr[size - 1];
arr[size - 1] = null;
size--;
return true;
}
public Iterator<T> iterator() {
return new ArraySetIterator();
}
// indexOf, grow, contains, and size are already implemented
private class ArraySetIterator implements Iterator<T> {
private int cursor = 0;
public boolean hasNext() {
return cursor < size;
}
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return arr[cursor++];
}
}
}
This loop is meant to remove every even number from set:
for (Integer x : set) {
if (x % 2 == 0) {
set.remove(x);
}
}
Solution
At the start, the array is [8, 5, 7, 6], size is 4, and cursor is 0.
next() returns 8 [8, 5, 7, 6] size 4 cursor 1
remove(8) [6, 5, 7, _] size 3 cursor 1
next() returns 5 [6, 5, 7, _] size 3 cursor 2
next() returns 7 [6, 5, 7, _] size 3 cursor 3
hasNext(): 3 < 3 is false, so the loop ends
The set holds 6, 5, and 7. remove(8) moved 6 into index 0, behind the cursor, so the loop never visited 6.
Solution
Add a counter of changes to the set:
private int modCount = 0; // counts structural changes
In add, put modCount++; right after size++;. In remove, put modCount++; right after size--;.
private class ArraySetIterator implements Iterator<T> {
private int cursor = 0;
private int expectedModCount = modCount;
public boolean hasNext() {
return cursor < size;
}
public T next() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
return arr[cursor++];
}
}