Iteration over sets

S

Swarat Chaudhuri

Hi everyone,

I am encountering concurrent modification exceptions while using the
class "Iterator" to iterate over a Java "HashSet". I kind of know *why*
I am getting them, but cannot quite figure out a strategy that would let
me avoid them. And assistance from experienced people always being
wonderful...

I have a set S over which I would like to iterate. While iterating, in
certain cases, I want to add elements to the set. I would like the
iterator to treat these new elements as if they have not been seen so
far. However, doing so seems to guarantee that concurrent modification
exception will be thrown.

So the question is, is there a way to achieve what I want to do? Without
needing to restart the iteration every time an "update" occurs?

I am willing to use a list instead of a set. But, for efficiency
reasons, I also want fast membership queries. So my second question:
does anyone know of an implementation of the List interface with a
"contains" method of sublinear complexity?

Thanks in advance,
Swarat
 
J

Jacob

Swarat said:
I am encountering concurrent modification exceptions while using the
class "Iterator" to iterate over a Java "HashSet".

There are two common approaches:

o Loop over a *copy* of the list. Then your iteration and
insertion will be done on different objects.

o Iterate backwards over the list. If additions are done at
the end, then this will not interfer with the iteration
process.
 
B

Babu Kalakrishnan

Swarat said:
I have a set S over which I would like to iterate. While iterating, in
certain cases, I want to add elements to the set. I would like the
iterator to treat these new elements as if they have not been seen so
far. However, doing so seems to guarantee that concurrent modification
exception will be thrown.

So the question is, is there a way to achieve what I want to do? Without
needing to restart the iteration every time an "update" occurs?

The standard HashSet implementation and the Iterator returned by it
cannot do this job (as you already found out). Also since the Iterator
returned by a HashSet does not guarantee any specific order in which it
returns its elements, making the newly added elements appear later in
the iteration order isn't guaranteed either (even assuming that you
manage to somehow get rid of the ConcurrentModificationException)

The easiest thing to do would be to use the combination of a List and a
HashSet and write your own ListIterator implementation. Check out the
code sample below. You can use the add/remove methods of the
ListIterator to add/remove elements.

// Warning - untested : provided only as sample

// ListIterator implementation does not check for concurrent
// modification. Code for this should be added . (See the
// API docs for "modCount" field in the AbstractList class)


import java.util.ArrayList;
import java.util.HashSet;
import java.util.ListIterator;

public class MyHashSet extends HashSet
{

private ArrayList list = new ArrayList();

public boolean add(Object o)
{
if (super.add(o))
{
list.add(o);
return true;
} else
return false;
}

public boolean remove(Object o)
{
if (super.remove(o))
{
list.remove(o);
return true;
} else
return false;
}

// Do similar stuff with other HashSet methods if necessary
// ensuring that the contents of "list" matches that of the set

public ListIterator listIterator()
{
return new MyListIterator();
}

public class MyListIterator implements ListIterator
{
private int nextIndex;
private Object lastReturned;

public int nextIndex()
{
return nextIndex;
}

public boolean hasNext()
{
return nextIndex < size();
}

public Object next()
{
return lastReturned = list.get(nextIndex++);
}

public int previousIndex()
{
return nextIndex - 1;
}

public boolean hasPrevious()
{
return nextIndex > 0;
}

public Object previous()
{
return lastReturned = list.get(--nextIndex);
}

public void add(Object o)
{
MyHashSet.this.add(o);
}

public void remove()
{
if (lastReturned == null)
throw new IllegalStateException(
"Cannot remove before a next or previous call");
MyHashSet.this.remove(lastReturned);
}

public void set(Object o)
{
throw new UnsupportedOperationException("Unsupported");
}
}
}

BK
 
F

Filip Larsen

Swarat Chaudhuri wrote
I have a set S over which I would like to iterate. While iterating, in
certain cases, I want to add elements to the set. I would like the
iterator to treat these new elements as if they have not been seen so
far. However, doing so seems to guarantee that concurrent modification
exception will be thrown.

So the question is, is there a way to achieve what I want to do? Without
needing to restart the iteration every time an "update" occurs?

I see two fairly common ways of doing it:

- Iterate over a list copy of S and add directly to S, or
- Iterate over S and add to a list, then when iteration is done add the
list to S and (optionally, depending what your algorithm is doing)
iterate S (or the list) again if list was non-empty.

The first way is good if S is fairly small and you expect a lot of
modifications to the set. The second is good in all other cases even
though it is slightly more complex to implement. The following method
should show an example of it could be done (the processElement method
returns a collection of new elements that needs to be added to the se):

public void processSet(Set s) {
Iterator i = s.iterator();
while (i.hasNext()) {
Collection adds = new LinkedList();
while (i.hasNext()) {
adds.addAll(processElement(i.next()));
}
s.addAll(adds);
i = adds.iterator();
}
}


Regards,
 
T

Thomas G. Marshall

Filip Larsen coughed up:
Swarat Chaudhuri wrote


I see two fairly common ways of doing it:

- Iterate over a list copy of S and add directly to S, or
- Iterate over S and add to a list,

This approach would only require a second set, not a list, AFAICT. IMBW.
 
S

Swarat Chaudhuri

This solves my problem. Warm thanks to you and everyone else who
responded on this thread.
 
F

Filip Larsen

Thomas G. Marshall wrote
Filip Larsen coughed up:

This approach would only require a second set, not a list, AFAICT.
IMBW.

You are correct that my post did not address the uniqueness problem. The
background for my example was a breadth-first search where I assumed
the uniqueness of the candidate elements was determined by the generator
function somehow.

If you expect that the candidate generator function will return many
equal candidiates for different items in the set (that is, your search
graph has many short cycles) you are right that a set probably should be
used instead of a list to avoid to store too many equal candidates. And
any candidate already in the main set should of course be removed from
the added list or set before iterating over it.


Regards,
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top