Iteration over sets

Discussion in 'Java' started by Swarat Chaudhuri, Sep 25, 2004.

  1. 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
     
    Swarat Chaudhuri, Sep 25, 2004
    #1
    1. Advertising

  2. Swarat Chaudhuri

    Jacob Guest

    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.
     
    Jacob, Sep 25, 2004
    #2
    1. Advertising

  3. 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
     
    Babu Kalakrishnan, Sep 25, 2004
    #3
  4. Swarat Chaudhuri

    Filip Larsen Guest

    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
     
    Filip Larsen, Sep 25, 2004
    #4
  5. 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,wherethehell'smypen???"
     
    Thomas G. Marshall, Sep 25, 2004
    #5
  6. 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
    >
     
    Swarat Chaudhuri, Sep 26, 2004
    #6
  7. Swarat Chaudhuri

    Filip Larsen Guest

    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
     
    Filip Larsen, Sep 26, 2004
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Schober

    rder of iteration over a map or a set

    Hendrik Schober, Feb 24, 2004, in forum: C++
    Replies:
    5
    Views:
    390
    Hendrik Schober
    Feb 24, 2004
  2. Amit
    Replies:
    3
    Views:
    497
    Jeff Flinn
    May 19, 2005
  3. Martin DeMello

    serial iteration over several lists

    Martin DeMello, Aug 21, 2004, in forum: Python
    Replies:
    4
    Views:
    311
    Martin DeMello
    Aug 23, 2004
  4. DeepBleu

    Iteration over Lists and Strings

    DeepBleu, Aug 28, 2004, in forum: Python
    Replies:
    10
    Views:
    454
    Alex Martelli
    Aug 30, 2004
  5. Rudi
    Replies:
    5
    Views:
    5,323
Loading...

Share This Page