Modificando um conjunto durante a iteração java

Question

Eu estou olhando para fazer um método recursivo iterativo.

Eu tenho uma lista de objetos que eu quero iterar e verifique suas subobjects.

recursiva:

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

Eu quero alterá-lo para algo como isto

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

Desculpe o código pseudo pobres, mas basicamente eu quero iterar sobre subobjects enquanto acrescentando novos objetos para o final da lista para verificar.

Eu poderia fazer isso usando uma lista, e fazer algo como

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

Mas eu realmente gostaria de não adicionar subobjects duplicados. Claro que eu poderia apenas verificar se list.contains (cada Subobject) antes de eu adicionei-o.

Mas eu gostaria de usar um conjunto para conseguir isso mais limpo.

Então, basicamente, há de qualquer maneira para anexar a um conjunto enquanto Iterando sobre ele, ou há uma maneira mais fácil de fazer um ato lista como um conjunto, em vez de .Contains verificar manualmente ()?

Todos os comentários são apreciados.

Graças

Answer 1

eu usar duas estruturas de dados --- fila (por exemplo, ArrayDeque ) para armazenar objetos cuja subobjects estão a ser visitado, e um set (por exemplo, HashSet ) para armazenar todos os objetos visitados sem duplicação.

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

NOTAS:

• ArrayDeque é um espaço-eficiente fila. Ele é implementado como uma matriz cíclica, o que significa que você usa menos espaço do que um List que continua a crescer quando você adiciona elementos.
• "boolean fresh = visited.add(o)" combina "boolean fresh = !visited.contains(o)" e "if (fresh) visited.add(o)".

Answer 2

Eu acho que o problema é inerentemente um problema que precisa ser resolvido através de uma lista. Se você pensar sobre isso, a sua versão Set da solução é apenas converter os itens em uma lista, em seguida, operando sobre isso.

Claro, List.contains () é uma operação lenta em comparação com Set.contains (), então pode valer a pena a subir com um híbrido se a velocidade é uma preocupação:

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

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

Esta solução é rápido e também conceitualmente som - o conjunto pode ser pensado como uma lista de todos os itens observados, Considerando que a lista é uma fila de itens para trabalhar. Ele faz demorar mais memória do que usar uma lista sozinho, apesar de tudo.

Answer 3

Se você não usar uma lista, o iterador irá lançar uma exceção, logo que você lê-lo depois de modificar o set. Eu recomendaria usar uma lista e impor limites de inserção, em seguida, usando ListIterator como que lhe permitirá modificar a lista, enquanto Iterando sobre ele.

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

Eu acho que algo como isso vai fazer o que eu quero, eu não estou preocupado que o primeiro conjunto contém duplicatas, apenas que os sub-objetos podem apontar para os mesmos objetos.

Answer 5

Use mais de um conjunto e fazê-lo em "rodadas":

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

Por que não criar um conjunto adicional que contém todo o conjunto de objetos? Você pode usar isso para pesquisas.