 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / November 2007Collection implementations and fail-fast iterator problems.
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.  SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> 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 [quoted text clipped - 15 lines] > 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. SignatureEric.Sosman@sun.com > Daniel Pitts wrote On 11/02/07 17:06,: >> I have a simulation where I visit every element in a Collection. While [quoted text clipped - 5 lines] >> "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? SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> >> Daniel Pitts wrote On 11/02/07 17:06,: >>> I have a simulation where I visit every element in a Collection. [quoted text clipped - 11 lines] > 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. SignatureLew >>> Daniel Pitts wrote On 11/02/07 17:06,: >>>> I have a simulation where I visit every element in a Collection. [quoted text clipped - 17 lines] >> 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. SignatureKnute Johnson email s/nospam/knute/ > 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)> SignatureLew >> 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)> Hey thanks that's excellent. SignatureKnute Johnson email s/nospam/knute/ >> Daniel Pitts wrote On 11/02/07 17:06,: >>> I have a simulation where I visit every element in a Collection. While [quoted text clipped - 11 lines] > 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. >> Daniel Pitts wrote On 11/02/07 17:06,: >>> I have a simulation where I visit every element in a Collection. [quoted text clipped - 11 lines] > 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> SignatureEric Sosman esosman@ieee-dot-org.invalid On Fri, 02 Nov 2007 14:06:09 -0700, Daniel Pitts <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly quoted someone who said : >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 SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com > On Fri, 02 Nov 2007 14:06:09 -0700, Daniel Pitts > <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly [quoted text clipped - 5 lines] > > 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. SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> On Fri, 02 Nov 2007 22:02:13 -0700, Daniel Pitts <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly quoted someone who said : >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. SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com > On Fri, 02 Nov 2007 22:02:13 -0700, Daniel Pitts > <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly [quoted text clipped - 6 lines] > 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. On Sat, 3 Nov 2007 09:24:59 -0700, "Mike Schilling" <mscottschilling@hotmail.com> wrote, quoted or indirectly quoted someone who said : > 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. SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com > On Sat, 3 Nov 2007 09:24:59 -0700, "Mike Schilling" > <mscottschilling@hotmail.com> wrote, quoted or indirectly quoted [quoted text clipped - 7 lines] > 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. SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> >> On Fri, 02 Nov 2007 14:06:09 -0700, Daniel Pitts >> <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly [quoted text clipped - 32 lines] > 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 >>> On Fri, 02 Nov 2007 14:06:09 -0700, Daniel Pitts >>> <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or [quoted text clipped - 47 lines] > 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. >>> On Fri, 02 Nov 2007 14:06:09 -0700, Daniel Pitts >>> <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly [quoted text clipped - 49 lines] > > 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 SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> >>>> On Fri, 02 Nov 2007 14:06:09 -0700, Daniel Pitts >>>> <newsgroup.spamfilter@virtualinfinity.net> wrote, quoted or indirectly [quoted text clipped - 58 lines] > 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 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 [quoted text clipped - 15 lines] > 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.lang.java.programmer/browse_frm/thread/7ea61 7fea8573e03/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. SignatureHendrik 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 Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.