Re: HashSet: add() during iteration?
Bruce Feist wrote On 10/24/06 12:50,:
What happens when I add a new item to a HashSet during iteration? Will
the new item added eventually be included in the iteration, will it not
show up, or is it unpredictable?
The new item is added (if it wasn't already in the Set).
This modifies the Set and thus invalidates the Iterator:
"The iterators returned by this class' iterator method
are fail-fast: if the set is modified at any time after
the iterator is created, in any way except through the
iterator's own remove method, the iterator throws a
ConcurrentModificationException."
I *want* it to be included, so if it isn't I'm going to have to use more
complicated logic, where each time through an iteration I build the next
HashSet to be iterated over, and I use a loop to iterate through each of
the HashSets until I get to an empty one. Much nastier, but I suspect
I'll have to -- please tell me that I'm wrong!
You're doing some kind of a "completion" operation, maybe?
You apply a rule to each element of the Set to create zero or
more "direct descendants," add them to the Set and compute
their descendants in turn, and so on until nothing more can be
added? Sort of like the LR(k) parser generator algorithm?
If that's what you're doing, you'll need some fancier logic
anyhow. There's no ordering in a HashSet, so if you insert a
new item you don't know whether it landed "before" or "after"
the current position of the Iterator -- in other words, even if
the Iterator could somehow keep going, you couldn't be sure it
would visit the newly-inserted item.
Two simple approaches occur to me:
- Use a single Set, iterate over its elements, and add
their descendants. Whenever an element produces one
or more descendants that actually get added (weren't
already there), discard the now-invalid Iterator and
create a fresh one, thus restarting the traversal at
the beginning.
- Use a Set to hold "all elements" and something like
a Stack to hold "elements whose descendants have not
yet been found." While the Stack is non-empty, pop
an element, compute its descendants, add them to the
Set, and if set.add() returned true also push them
onto the Stack (they are new descendants, and need
to be explored).
I'd prefer the second, since you won't waste a lot of
effort computing and re-computing and re-re-computing the
descendants of already-visited elements. But if you really
want to use just one Collection, the first approach works.
--
Eric.Sosman@sun.com