Modification d'un ensemble lors de l'itération java

Question

Je cherche à faire une méthode récursive itérative.

J'ai une liste d'objets que je veux parcourir, puis vérifier leurs sous-objets.

récursive:

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

Je veux changer quelque chose comme ceci

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

Désolé pour les pauvres pseudo-code, mais au fond, je veux itérer sur les sous-objets tout en ajoutant de nouveaux objets à la fin de la liste pour vérifier.

Je pourrais le faire à l'aide d'une liste, et faire quelque chose comme

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

Mais je voudrais vraiment pas ajouter en double sous-objets. Bien sûr, je pouvais vérifier si list.contains (chaque) avant Subobject je l'ai ajouté.

Mais j'aimerais utiliser un ensemble pour accomplir ce propre.

Alors, est essentiellement là de toute façon à ajouter à un ensemble tout en évoluant au-dessus, ou est-il un moyen plus facile de faire un acte de liste comme un ensemble plutôt que .contains vérifier manuellement ()?

Les commentaires sont appréciés.

Merci

Answer 1

je voudrais utiliser deux structures de données --- un (par exemple file ArrayDeque ) pour stocker des objets dont les sous-objets doivent être visités, et un set (par exemple HashSet ) pour mémoriser tous les objets visités sans 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:

• est un List espace -Efficace file d'attente. Il est utilisé comme une matrice cyclique, ce qui signifie moins d'espace qu'un boolean fresh = visited.add(o) qui ne cesse de croître lorsque vous ajoutez des éléments.
• "" moissonneuses-batteuses "boolean fresh = !visited.contains(o) if (fresh) visited.add(o)" et "<=>".

Answer 2

Je pense que votre problème est en soi un problème qui doit être résolu par le biais d'une liste. Si vous y pensez, votre version de jeu de la solution est tout simplement de convertir les éléments dans une liste fonctionnant alors sur ce point.

Bien sûr, List.contains () est une opération lente par rapport à Set.contains (), il peut être utile de venir avec un hybride si la vitesse est une préoccupation:

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

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

Cette solution est rapide et conceptuellement son - l'ensemble peut être considéré comme une liste de tous les éléments vus, alors que la liste est une file d'attente d'éléments à travailler. Il ne prend plus de mémoire que d'utiliser une seule liste, cependant.

Answer 3

Si vous n'utilisez pas une liste, l'itérateur lancera une exception dès que vous le lisez après avoir modifié le jeu. Je recommande l'utilisation d'une liste et de faire respecter les limites d'insertion, puis en utilisant comme ListIterator qui vous permettra de modifier la liste en itérer dessus.

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

Je pense que quelque chose comme ça va faire ce que je veux, je ne suis pas préoccupé par ce que le premier ensemble contient des doublons, seulement que les sous-objets peuvent pointer vers les mêmes objets.

Answer 5

Utilisez plus d'un ensemble et le faire en « rondes »:

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

Pourquoi ne pas créer un jeu supplémentaire qui contient l'ensemble des objets? Vous pouvez l'utiliser pour les recherches.