Изменение набора во время итерации java

Question

Я ищу, чтобы сделать рекурсивный метод итеративным.

У меня есть список объектов, которые я хочу перебрать, а затем проверить их подобъекты.

Рекурсивный:

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

Я хочу изменить его на что-то вроде этого

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

Извините за плохой код псевдо, но в основном я хочу, чтобы перебрать подобъектов в то время как добавление новых объектов к конец списка для проверки.

Я мог бы сделать это с помощью списка, и сделать что-то вроде

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

Но я бы очень хотел, чтобы не добавлять дубликаты подобъектов. Конечно, я мог бы просто проверить, будет ли list.contains (каждый subObject), прежде чем я добавлю его.

Но я хотел бы использовать Набор, чтобы выполнить это очиститель.

В любом случае, в любом случае можно добавить к набору, итерации по нему, или есть ли более простой способ сделать список как набор, а не вручную проверять .contains()?

Любые комментарии оцениваются.

Благодаря

Answer 1

Я бы использовал две структуры данных --- очередь (например,ArrayDeque) для хранения объектов, которые должны быть посещены подобъекты, и (например, HashSet) для хранения всех посещенных объектов без дублирования.

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 

ПРИМЕЧАНИЕ:

• ArrayDeque является пространственно-эффективной очередью. Он реализуется как циклический массив, что означает, что вы используете меньше места, чем List, который продолжает расти, когда вы добавляете элементы.
• "boolean fresh = visited.add(o)" комбайны "boolean fresh = !visited.contains(o)" и "if (fresh) visited.add(o)".

Answer 2

Я думаю, ваша проблема по своей сути является проблемой, которая должна быть решена с помощью списка. Если вы думаете об этом, ваша версия версии решения просто преобразует элементы в список, а затем работает над этим.

Конечно, List.contains() является медленная работа по сравнению с Set.contains(), так что это может быть стоит придумать гибрид, если скорость является проблемой:

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

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

Это решение является быстрым, а также концептуально звуковым - набор можно рассматривать как список всех видимых элементов, тогда как список - это очередь элементов, над которыми нужно работать. Тем не менее, это занимает больше памяти, чем использование списка.

Answer 3

Если вы не используете Список, итератор будет генерировать исключение, как только вы его прочитаете после изменения набора. Я бы рекомендовал использовать List и принудительно ввести ограничения на вставку, а затем использовать ListIterator, так как это позволит вам изменить список, итерации по нему.

Answer 4

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

Я думаю, что что-то, как это будет делать то, что я хочу, я не обеспокоен тем, что первый набор содержит дубликаты, только что подобъекты могут указывать на те же объекты.

Answer 5

Использование более одного набора и сделать это в «раундов»:

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

Answer 6

Почему бы не создать дополнительный набор, который содержит весь набор объектов? Вы можете использовать это для поиска.