Modifying a set during iteration java

Question

I'm looking to make a recursive method iterative.

I have a list of Objects I want to iterate over, and then check their subobjects.

Recursive:

doFunction(Object)
while(iterator.hasNext())
{
   //doStuff
   doFunction(Object.subObjects);
}

I want to change it to something like this

doFunction(Object)
iIterator = hashSet.iterator();
while(Iterator.hasNext()
{
   //doStuff
   hashSet.addAll(Object.subObjects);
}

Sorry for the poor psuedo code, but basically I want to iterate over subobjects while appending new objects to the end of the list to check.

I could do this using a list, and do something like

while(list.size() > 0)
{
   //doStuff
   list.addAll(Object.subObjects);
}

But I would really like to not add duplicate subObjects. Of course I could just check whether list.contains(each subObject) before I added It.

But I would love to use a Set to accomplish that cleaner.

So Basically is there anyway to append to a set while Iterating over it, or is there an easier way to make a List act like a set rather than manually checking .contains()?

Any comments are appreciated.

Thanks

Zach Scrivena · Accepted Answer · 2009-01-31 02:09:05Z

I would use two data structures --- a queue (e.g. ArrayDeque) for storing objects whose subobjects are to be visited, and a set (e.g. HashSet) for storing all visited objects without duplication.

Set visited = new HashSet();   // all visited objects
Queue next = new ArrayDeque(); // objects whose subobjects are to be visited

// NOTE: At all times, the objects in "next" are contained in "visited"

// add the first object
visited.add(obj);

Object nextObject = obj;

while (nextObject != null)
{
    // do stuff to nextObject

    for (Object o : nextObject.subobjects)
    {
        boolean fresh = visited.add(o);

        if (fresh)
        {
            next.add(o);
        }
    }

    nextObject = next.poll(); // removes the next object to visit, null if empty
}

// Now, "visited" contains all the visited objects

NOTES:

ArrayDeque is a space-efficient queue. It is implemented as a cyclic array, which means you use less space than a List that keeps growing when you add elements.
"boolean fresh = visited.add(o)" combines "boolean fresh = !visited.contains(o)" and "if (fresh) visited.add(o)".

Dan Lew · Accepted Answer · 2009-01-30 20:16:13Z

I think your problem is inherently a problem that needs to be solved via a List. If you think about it, your Set version of the solution is just converting the items into a List then operating on that.

Of course, List.contains() is a slow operation in comparison to Set.contains(), so it may be worth coming up with a hybrid if speed is a concern:

while(list.size() > 0)
{
   //doStuff

   for each subObject
   {
      if (!set.contains(subObject))
      {
         list.add(subObject);
         set.add(subObject)
      }
   }
}

This solution is fast and also conceptually sound - the Set can be thought of as a list of all items seen, whereas the List is a queue of items to work on. It does take up more memory than using a List alone, though.

Matthew Brubaker · Accepted Answer · 2009-01-30 20:17:10Z

0

If you do not use a List, the iterator will throw an exception as soon as you read from it after modifying the set. I would recommend using a List and enforcing insertion limits, then using ListIterator as that will allow you to modify the list while iterating over it.

answered Jan 30, 2009 at 20:17

Matthew Brubaker

3,1171 gold badge22 silver badges18 bronze badges

Comments

Sheldon Ross · Accepted Answer · 2009-01-30 20:35:49Z

0

    HashSet nextObjects = new HashSet();
    HashSet currentObjects = new HashSet(firstObject.subObjects);

    while(currentObjects.size() > 0)
    {
        Iterator iter = currentObjects.iterator();
        while(iter.hasNext())
        {
            //doStuff
            nextObjects.add(subobjects);
        }
        currentObjects = nextObjects;
        nextObjects = new HashSet();
    }

I think something like this will do what I want, I'm not concerned that the first Set contains duplicates, only that the subObjects may point to the same objects.

answered Jan 30, 2009 at 20:35

Sheldon Ross

5,5537 gold badges33 silver badges37 bronze badges

Comments

bendin · Accepted Answer · 2009-01-30 20:36:31Z

0

Use more than one set and do it in "rounds":

/* very pseudo-code */
doFunction(Object o) {
    Set processed = new HashSet();
    Set toProcess = new HashSet();
    Set processNext = new HashSet();

    toProcess.add(o);

    while (toProcess.size() > 0) {
        for(it = toProcess.iterator(); it.hasNext();) {
            Object o = it.next();
            doStuff(o);
            processNext.addAll(o.subObjects);
        }
        processed.addAll(toProcess);
        toProcess = processNext;
        toProcess.removeAll(processed);
        processNext = new HashSet();
    }
}

answered Jan 30, 2009 at 20:36

bendin

9,6041 gold badge42 silver badges37 bronze badges

1 Comment

Sheldon Ross Over a year ago

Thanks, this is pretty much the exact solution I came up with eventually. Not very space-happy, but it feels pretty clean.

Fortyrunner · Accepted Answer · 2009-01-30 20:37:37Z

0

Why not create an additional set that contains the entire set of objects? You can use that for lookups.

answered Jan 30, 2009 at 20:37

Fortyrunner

12.8k4 gold badges35 silver badges54 bronze badges

Collectives™ on Stack Overflow

Modifying a set during iteration java

6 Answers 6

Comments

Comments

Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related