Parcourir des listes imbriquées avec une fonction Next(), sans utiliser un générateur

Question

Alors que j'aimerais résoudre ce problème en python, je suis bloqué en Delphi pour celui-ci. J'ai des listes imbriquées (en fait des objets avec des listes imbriquées en tant que propriétés, mais peu importe), et je veux les parcourir de manière générative. Autrement dit, je veux écrire une fonction Suivant, qui me donne l'élément suivant des feuilles de l'arbre décrit par les listes imbriquées.

Par exemple, supposons que j'ai

 [[1,2,3],[4,5],[],[6],[7,8]]

Je veux que 8 appels consécutifs à Suivant() retournent 1..8.

Comment puis-je faire cela dans un langage sans yield et générateurs ?

Remarquez que la profondeur de l'imbrication est fixe (2 dans cet exemple, 4 dans la vraie vie), mais les réponses qui résolvent le cas plus général où la profondeur est variable sont les bienvenues.

MODIFIER : Désolé, j'aurais dû mentionner que c'est Delphi 2007.

Answer 1

Si vous utilisez une liste Delphi qui a un énumérateur intégré, il peut être fait assez facilement avec un peu de récursion. Votre liste de base est une liste de nombres, comme une TList. Ensuite, vous avez des listes imbriquées implémentées comme TList>. (Je suppose que vous avez Delphi 2009 ou 2010. Sinon, cela devient un peu plus compliqué.)

Ce dont vous avez besoin est de créer votre propre classe de liste spécialisée descendant de TList et d'ajouter une fonction virtuelle Next() et un champ pour un énumérateur pour votre liste. Le compilateur utilise des énumérateurs en interne lorsque vous configurez une boucle for..in, mais vous pouvez les exécuter manuellement. La fonction Next() crée l'énumérateur s'il n'est pas déjà attribué et le place dans le champ, puis appelle MoveNext() dessus. Si cela réussit, appelez GetCurrent et obtenez votre nombre. Sinon, vous avez terminé. Libérez et nil l'énumérateur, et indiquez à la fonction appelante que vous n'avez rien à retourner. Probablement la manière la plus simple de faire cela est de mettre un paramètre booléen var dans Next() qui renvoie le résultat de son appel à MoveNext, et de faire en sorte que la fonction appelante vérifie sa valeur.

Pour les listes supérieures, c'est un peu plus compliqué, mais pas beaucoup. Descendez de la classe générique que vous venez de mettre en place, et remplacez Next(). Celui-ci obtiendra un énumérateur qui énumère les listes qu'il contient, et renverra la valeur de FEnumerator.GetCurrent.Next() jusqu'à ce que cette sous-liste soit épuisée, puis appellera MoveNext sur son énumérateur.

Cela devrait fonctionner pour n'importe quelle profondeur de listes imbriquées. Ne essayez tout simplement pas de faire une liste qui contient à la fois des nombres et des listes.

Answer 2

Méthode 1 : un "liste en couches" est un arbre, utilisez (ou écrivez) une classe arbre/nœud d'arbre, et faites une simple recherche en profondeur de ses valeurs.

Méthode 2 : écrivez explicitement la recherche en profondeur pour votre type de liste en couches :

TEnumerator = RECORD
  private
    FStack : Pile de TNestedList;  //une pile, contenant le niveau de l'arbre que vous explorez
    FIndexStack : Pile d'entiers; //une deuxième pile, contenant l'index de l'enfant que vous explorez à chaque couche

  public
    Init( AList : TNestedList );
    Next( var AVal : Integer ) : boolean;
end;

procedure TEnumerator.Init( AList );
begin
  SetLength(FStack, 1);
  FStack[0] := AList;
  SetLength( FIndexStack, 1 );
  FIndexStack[0] := 0;

  _GoToNextValue();
end;

procedure TEnumerator._GoToNextValue();
begin
  while FStack.notEmpty()
    and FIndexStack.last > FStack.last.length do
     begin
     //nous avons fini d'explorer FStack.last, nous devons explorer son prochain frère :
     //dépiler FStack.last :
       FIndexStack.pop;
       FStack.pop;
     //aller au frère suivant :
       FIndexStack.last := FIndexStack.last + 1;
     end;

  //rien de restant à explorer :
  if FStack.empty then Exit;

  //sinon :
  //  creuser à travers les couches de liste jusqu'à ce que vous atteigniez une valeur
  while FStack.last.isAList() do
  begin
    FStack.push( FStack.last[ FIndexStack.last ] );
    FIndexStack.push( 0 );    
  end;
end;

function Next( var AVal : Integer ) : boolean;
begin
  _GoToNextValue();

  Result := FStack.notEmpty();

  if Result then
  begin
    AVal := FStack.last[ FIndexStack.last ];
    FIndexSatck.last := FIndexSatck.last + 1;
  end;
end;

Essentiellement, vous faites explicitement ce qu'un "yield" ferait (c'est-à-dire : sauvegarder une "copie figée" de la pile d'appels, retourner la valeur actuelle)

Utilisation :

LEnum : TEnumerator;

LEnum.Init( myList );
while LEnum.Next( LVal ) do
begin

end;

Answer 3

Pour résoudre ce problème, j'ai fini par créer une liste à plat d'index et à me souvenir de ma position dedans : (en pythonesque, parce que c'est plus court)

class Nested:
    nestedList = [[1,2,3],[4,5],[],[6],[7,8]]
    positions = []
    curr = 0

    def Setup:
        for a in nestedList:
            for b in a:
               positions.add((a,b))

    def Next:
        p = positions[curr]
        curr += 1
        return nestedList[p[0]][p[1]]

Évidemment ma liste ne change pas pendant l'itération sinon cela ne fonctionnerait probablement pas...