CODEWITHSUNDEEP
javaiteratorhashset
Sheldon Ross
Sheldon Ross

Reputation: 5544

Modifying a set during iteration java

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

Upvotes: 2

Views: 7534

Answers (6)

Zach Scrivena
Zach Scrivena

Reputation: 29569

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

Upvotes: 5

Fortyrunner
Fortyrunner

Reputation: 12792

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

Upvotes: 0

bendin
bendin

Reputation: 9574

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();
    }
}

Upvotes: 0

Sheldon Ross
Sheldon Ross

Reputation: 5544

    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.

Upvotes: 0

Matthew Brubaker
Matthew Brubaker

Reputation: 3117

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.

Upvotes: 0

Dan Lew
Dan Lew

Reputation: 87440

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.

Upvotes: 1

Related Questions