Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Iteration over sets

Reply
Thread Tools

Iteration over sets

 
 
Swarat Chaudhuri
Guest
Posts: n/a
 
      09-25-2004

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
 
Reply With Quote
 
 
 
 
Jacob
Guest
Posts: n/a
 
      09-25-2004
Swarat Chaudhuri wrote:

> 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.

 
Reply With Quote
 
 
 
 
Babu Kalakrishnan
Guest
Posts: n/a
 
      09-25-2004
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?
>


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
 
Reply With Quote
 
Filip Larsen
Guest
Posts: n/a
 
      09-25-2004
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,
--
Filip Larsen


 
Reply With Quote
 
Thomas G. Marshall
Guest
Posts: n/a
 
      09-25-2004
Filip Larsen coughed up:
> 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,


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



> 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,


--
Onedoctortoanother:"Ifthisismyrectalthermometer,wh erethehell'smypen???"



 
Reply With Quote
 
Swarat Chaudhuri
Guest
Posts: n/a
 
      09-25-2004

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


On Sat, 25 Sep 2004, Babu Kalakrishnan wrote:

> 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?
> >

>
> 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
>

 
Reply With Quote
 
Filip Larsen
Guest
Posts: n/a
 
      09-26-2004
Thomas G. Marshall wrote

> Filip Larsen coughed up:
> > 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,

>
> 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,
--
Filip Larsen


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Struts - Problem with nested iteration or double iteration Rudi Java 5 10-01-2008 03:30 AM
VOIP over VPN over TCP over WAP over 3G Theo Markettos UK VOIP 2 02-14-2008 03:27 PM
Sets and level order iteration. Amit C++ 3 05-19-2005 12:08 PM
serial iteration over several lists Martin DeMello Python 4 08-23-2004 02:30 PM
rder of iteration over a map or a set Hendrik Schober C++ 5 02-24-2004 01:44 PM



Advertisments