Collection implementations and fail-fast iterator problems.

[Daniel Pitts]

I have a simulation where I visit every element in a Collection. While
visiting these, I may find out that I want to add a new element, or
remove some later-occurring element before I get to it. I have a few
Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

The elements can (and do) have a flag on them to mark that they are
ready for deletion, but that still leaves a problem for the addition,
and I also have to explicitly check that flag during iteration (or after
the iteration). Not ideal IMO.

Is there a better approach? Is my design fundamentally flawed? Last time
I came across this program, I used toArray (basically, just to get a
copy), and iterated over that, and used a separate collection to hold
what needs to be added/removed. It was messy code and I'd rather avoid
that approach if possible.

Thanks,
Daniel.

 

[Eric Sosman]

Daniel Pitts wrote On 11/02/07 17:06,:

I have a simulation where I visit every element in a Collection. While
visiting these, I may find out that I want to add a new element, or
remove some later-occurring element before I get to it. I have a few
Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

The elements can (and do) have a flag on them to mark that they are
ready for deletion, but that still leaves a problem for the addition,
and I also have to explicitly check that flag during iteration (or after
the iteration). Not ideal IMO.

Is there a better approach? Is my design fundamentally flawed? Last time
I came across this program, I used toArray (basically, just to get a
copy), and iterated over that, and used a separate collection to hold
what needs to be added/removed. It was messy code and I'd rather avoid
that approach if possible.

If your Collection implements List, perhaps you could
use a ListIterator.

 

[Daniel Pitts]

Daniel Pitts wrote On 11/02/07 17:06,:

I have a simulation where I visit every element in a Collection. While
visiting these, I may find out that I want to add a new element, or
remove some later-occurring element before I get to it. I have a few
Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

[snip]
If your Collection implements List, perhaps you could
use a ListIterator.

How does that help? Adding and Removing STILL causes concurrent
modification errors, does it not?

 

[Lew]

Daniel Pitts wrote On 11/02/07 17:06,:

I have a simulation where I visit every element in a Collection.
While visiting these, I may find out that I want to add a new
element, or remove some later-occurring element before I get to it.
I have a few Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

[snip]
If your Collection implements List, perhaps you could
use a ListIterator.

How does that help? Adding and Removing STILL causes concurrent
modification errors, does it not?

Not if you use the Iterator to do the modifications:
From the ListIterator Javadocs:

 

[Knute Johnson]

Daniel Pitts wrote On 11/02/07 17:06,:
I have a simulation where I visit every element in a Collection.
While visiting these, I may find out that I want to add a new
element, or remove some later-occurring element before I get to it.
I have a few Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle
both those cases without getting a ConcurrentModificationError. [snip]
If your Collection implements List, perhaps you could
use a ListIterator.

How does that help? Adding and Removing STILL causes concurrent
modification errors, does it not?

Not if you use the Iterator to do the modifications:
From the ListIterator Javadocs:

An iterator for lists that allows the programmer to traverse the list
in either direction, modify the list during iteration, and obtain the
iterator's current position in the list.

Lew:

Can you add to a ListIterator while iterating over it? With Iterator I
thought you could only delete the current iterated item.

 

[Lew]

Can you add to a ListIterator while iterating over it? With Iterator I
thought you could only delete the current iterated item.

<http://java.sun.com/javase/6/docs/api/java/util/ListIterator.html#add(E)>

 

[Mike Schilling]

Daniel Pitts wrote On 11/02/07 17:06,:

I have a simulation where I visit every element in a Collection. While
visiting these, I may find out that I want to add a new
element, or remove some later-occurring element before I get to it.
I have a few Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle
both those cases without getting a ConcurrentModificationError.

[snip]
If your Collection implements List, perhaps you could
use a ListIterator.

How does that help? Adding and Removing STILL causes concurrent
modification errors, does it not?

The ConcurrentModificationException means "I'm an iterator and, oh crap,
someone's modified the collection behind my back and now I can't do my job."
Modifying the collection with the iterator's knowledge (that is, by using
the iterator) won't cause this problem.

 

[Knute Johnson]

<http://java.sun.com/javase/6/docs/api/java/util/ListIterator.html#add(E)>

Hey thanks that's excellent.

 

[Eric Sosman]

Daniel Pitts wrote On 11/02/07 17:06,:

I have a simulation where I visit every element in a Collection.
While visiting these, I may find out that I want to add a new
element, or remove some later-occurring element before I get to it.
I have a few Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

[snip]
If your Collection implements List, perhaps you could
use a ListIterator.

How does that help? Adding and Removing STILL causes concurrent
modification errors, does it not?

<shrug> I've never used one myself, but the Javadoc suggests
otherwise. No doubt it's wrong. <shrug**2>

 

[Roedy Green]

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

see http://mindprod.com/jgloss/iterator.html#REMOVE

 

[Daniel Pitts]

see http://mindprod.com/jgloss/iterator.html#REMOVE

The problem is that the element to remove isn't necessarily the element
that the iterator is pointing to. For example.
class ItemHolder {
Collection<Item> items;
public void doAllSomething() {
for (Item item: items) {
item.doSomething();
}
}

class Item {
ItemHolder parent;
public void doSomething() {
for (Item item: parent.items) {
item.affectBy(this);
if (item.shouldBeRemovedNow()) {
parent.items.remove(item);
}
}
if (shouldAddNewItems()) {
parent.items.add(createNewItem());
}
}
}

This is the gist of what happens. As you can see, there are multiple
iterators to deal with.

 

[Roedy Green]

This is the gist of what happens. As you can see, there are multiple
iterators to deal with.

Ouch! In that case I guess you would need to write your own
Iterator-like thing that does not mind random elements being deleted
under its nose.

 

[Mike Schilling]

Ouch! In that case I guess you would need to write your own
Iterator-like thing that does not mind random elements being deleted
under its nose.

I suppose you would write a general List iterator that has methods to add
and delete elements at various indexes, and adjusts its current index
appropriately (e.g., if an element is deleted at an index prior to the
current one, decrement the current index.) . It would have crappy
performance iterating over LinkedLists, though (or any List implementation
that isn't direct access). There's no way to write such an iterator that
would work on arbitrary Collections, though.

 

[Patricia Shanahan]

The problem is that the element to remove isn't necessarily the element
that the iterator is pointing to. For example.
class ItemHolder {
Collection<Item> items;
public void doAllSomething() {
for (Item item: items) {
item.doSomething();
}
}

class Item {
ItemHolder parent;
public void doSomething() {
for (Item item: parent.items) {
item.affectBy(this);
if (item.shouldBeRemovedNow()) {
parent.items.remove(item);
}
}
if (shouldAddNewItems()) {
parent.items.add(createNewItem());
}
}
}

This is the gist of what happens. As you can see, there are multiple
iterators to deal with.

A few questions:

1. Is the underlying Collection large? (That affects whether it is
reasonable to make a working copy).

2. Does it have to work with arbitrary Collections?

3. How should added items be handled? Should they be processed in later
inner iterations of the same outer loop? Should they be processed in the
same run of the outer loop?

4. Similar questions for deleted items, but that is a simpler problem
because of the option of marking an item to indicate it is not really there.

Patricia

 

[Roedy Green]

There's no way to write such an iterator that
would work on arbitrary Collections, though.

I think you would write it only for a specific collection.

It might be easiest just to make a todo list of elements to delete,
and then delete them after you have finished your iteration.

 

[Mike Schilling]

A few questions:

1. Is the underlying Collection large? (That affects whether it is
reasonable to make a working copy).

2. Does it have to work with arbitrary Collections?

3. How should added items be handled? Should they be processed in
later inner iterations of the same outer loop? Should they be
processed in the same run of the outer loop?

4. Similar questions for deleted items, but that is a simpler problem
because of the option of marking an item to indicate it is not really
there.

There goes Patricia again, trying to actually understand the problem before
giving advice.

 

[Daniel Pitts]

A few questions:

1. Is the underlying Collection large? (That affects whether it is
reasonable to make a working copy).

2. Does it have to work with arbitrary Collections?

3. How should added items be handled? Should they be processed in later
inner iterations of the same outer loop? Should they be processed in the
same run of the outer loop?

4. Similar questions for deleted items, but that is a simpler problem
because of the option of marking an item to indicate it is not really
there.

Patricia

The lists aren't huge, but they are processed continuously. Basically,
the doAllSomething is called around 30-60 times a second.

Now that I think about it, items added in this case should be processed
on the next iteration only.

I suppose the best approach is to have a list of to-be-added, and a
marker for to-be-deleted. Then items.addAll(toBeAdded) can be used
after a look to delete the to-be-deleted.

The problem is a little more complex, because I really have List<Robot>
and List<Missile> and List<Mine>. They all interact and the Missile
list has a high turnover rate (missiles tend to explode when they hit
the edge of the fairly small arena). As a matter of fact, I'm probably
going to want to add some sort of spatial index for collision detection

Thanks,
Daniel

 

[Daniel Pitts]

I think you would write it only for a specific collection.

It might be easiest just to make a todo list of elements to delete,
and then delete them after you have finished your iteration.

Yeah, that is what I've decided to do. Still a little kludgey, but I
think it's just the nature of the problem.

 

[Patricia Shanahan]

The lists aren't huge, but they are processed continuously. Basically,
the doAllSomething is called around 30-60 times a second.

Now that I think about it, items added in this case should be processed
on the next iteration only.

I suppose the best approach is to have a list of to-be-added, and a
marker for to-be-deleted. Then items.addAll(toBeAdded) can be used
after a look to delete the to-be-deleted.

As an alternative to actually adding the short-lived entries to the
collection, consider having your own Iterator. It would scan both the
underlying Collection, and the supplemental elements. It would have
support for putting things in the added list.

[You could wrap the Collection in a subclass that only overrides Iterator]

Patricia

 

[Hendrik Maryns]

Daniel Pitts schreef:

I have a simulation where I visit every element in a Collection. While
visiting these, I may find out that I want to add a new element, or
remove some later-occurring element before I get to it. I have a few
Collections like this.

I'd like to avoid having to keep track of "to-be-deleted" and
"to-be-added" elements, but I don't see an elegant way to handle both
those cases without getting a ConcurrentModificationError.

The elements can (and do) have a flag on them to mark that they are
ready for deletion, but that still leaves a problem for the addition,
and I also have to explicitly check that flag during iteration (or after
the iteration). Not ideal IMO.

Is there a better approach? Is my design fundamentally flawed? Last time
I came across this program, I used toArray (basically, just to get a
copy), and iterated over that, and used a separate collection to hold
what needs to be added/removed. It was messy code and I'd rather avoid
that approach if possible.

I had this problem some time ago as well. You might want to read this
thread in this same group:
http://groups.google.com/group/comp...3/ee93ac22cfe8451d?lnk=st&q=#ee93ac22cfe8451d

However, you’ll notice that the solution also resulted in reformulating
the problem and solving it differently. Basically, I copied over the
list /while iterating over it/. That way the removal and addition are
solved at the same time, without needing to copy beforehand.

But to be honest, I do not see immediately how that could be applied to
your problem.

HTH, H.
--
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFHLzqJe+7xMGD3itQRAvBsAJ9s1EMgf0b1JGo2pKB0SEQMmGUeMwCeKbzm
V8wG51JLGA65dghdwXPYyxo=
=/Kaa
-----END PGP SIGNATURE-----