Énumération des collections qui ne sont pas intrinsèquement IEnumerable?

Question

Lorsque vous voulez énumérer récursive un objet hiérarchique, sélectionner certains éléments en fonction de certains critères, il existe de nombreux exemples de techniques comme « aplatissement » puis filtrer en utilisant Linq: comme ceux qu'on trouve ici:

link text

Mais, lorsque vous énumérez quelque chose comme la collection Controls d'un formulaire, ou la collection Nodes d'un TreeView, j'ai été incapable d'utiliser ces types de techniques car elles semblent nécessiter un argument (à la méthode d'extension) qui est un IEnumerable collection: transmettre dans SomeForm.Controls ne compile pas.

La chose la plus utile que j'ai trouvé ceci:

link text

qui ne vous donne une méthode d'extension pour Control.ControlCollection avec un résultat IEnumerable vous pouvez utiliser avec LINQ.

J'ai modifié l'exemple ci-dessus pour analyser les nœuds d'un TreeView sans problème.

public static IEnumerable<TreeNode> GetNodesRecursively(this TreeNodeCollection nodeCollection) 
{ 
    foreach (TreeNode theNode in nodeCollection) 
    { 
     yield return theNode; 

     if (theNode.Nodes.Count > 0) 
     { 
      foreach (TreeNode subNode in theNode.Nodes.GetNodesRecursively()) 
      { 
       yield return subNode; 
      } 
     } 
    } 
} 

C'est le genre de code que je vous écris en utilisant maintenant la méthode d'extension:

var theNodes = treeView1.Nodes.GetNodesRecursively(); 

    var filteredNodes = 
    (
     from n in theNodes 
      where n.Text.Contains("1") 
       select n 
    ).ToList(); 

Et je pense qu'il peut y avoir une façon plus élégante de le faire où la contrainte (s) sont Ce que je veux savoir s'il est possible de définir de telles procédures génériquement, de sorte que: lors de l'exécution, je puisse transmettre le type de collection, ainsi que la collection réelle, à un paramètre générique, le code est donc indépendant de si c'est un TreeNodeCollection ou Controls.Collection .

Il serait également intéressant de savoir s'il existe un autre moyen (moins cher? Fastser?) Que celui montré dans le deuxième lien (ci-dessus) pour obtenir un TreeNodeCollection ou Control.ControlCollection sous une forme utilisable par Linq.

Un commentaire de Leppie à propos de 'SelectMany dans le post SO lié au premier (ci-dessus) semble être un indice.

Mes expériences avec SelectMany ont été: bien, appelez-les "catastrophes". :)

Appréciez les pointeurs. J'ai passé plusieurs heures à lire tous les messages postaux que je pouvais trouver sur ces sujets, et je me frayais un chemin dans un exotica tel que le "y-combinator". Une expérience « leçon d'humilité », je pourrais ajouter :)

Answer 1

Ce code devrait faire l'affaire

public static class Extensions 
{ 
    public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection, 
     Func<T, IEnumerable> selector) 
    { 
     foreach (var item in collection.OfType<T>()) 
     { 
      yield return item; 

      IEnumerable<T> children = selector(item).GetRecursively(selector); 
      foreach (var child in children) 
      { 
       yield return child; 
      } 
     } 
    } 
} 

Voici un exemple de la façon de l'utiliser

TreeView view = new TreeView(); 

// ... 

IEnumerable<TreeNode> nodes = view.Nodes. 
    .GetRecursively<TreeNode>(item => item.Nodes); 

Mise à jour: En réponse au poste de Eric Lippert.

Voici une version beaucoup améliorée en utilisant la technique discutée dans All About Iterators.

public static class Extensions 
{ 
    public static IEnumerable<T> GetItems<T>(this IEnumerable collection, 
     Func<T, IEnumerable> selector) 
    { 
     Stack<IEnumerable<T>> stack = new Stack<IEnumerable<T>>(); 
     stack.Push(collection.OfType<T>()); 

     while (stack.Count > 0) 
     { 
      IEnumerable<T> items = stack.Pop(); 
      foreach (var item in items) 
      { 
       yield return item; 

       IEnumerable<T> children = selector(item).OfType<T>(); 
       stack.Push(children); 
      } 
     } 
    } 
} 

J'ai fait un simple test de performance en utilisant la benchmarking technique suivante. Les résultats parlent d'eux-mêmes. La profondeur de l'arbre n'a qu'un impact marginal sur la performance de la seconde solution; tandis que la performance diminue rapidement pour la première solution, conduisant finalement à StackOverflowException lorsque la profondeur de l'arbre devient trop grande.

Answer 2

Je ne suis pas sûr de TreeNodes, mais vous pouvez faire la collection Controls d'une forme IEnumerable en utilisant System.Linq et, par exemple

var ts = (from t in this.Controls.OfType<TextBox> 
       where t.Name.Contains("fish") 
       select t); 
//Will get all the textboxes whose Names contain "fish" 

Désolé pour dis que je ne sais pas comment rendre cela récursif, du haut de ma tête.

Answer 3

Je suppose que vous demandez quelque chose comme ça.

public static IEnumerable<T> <T,TCollection> GetNodesRecursively(this TCollection nodeCollection, Func<T, TCollection> getSub) 
where T, TCollection: IEnumerable 
{ 
    foreach (var theNode in) 
    { 
     yield return theNode; 
     foreach (var subNode in GetNodesRecursively(theNode, getSub)) 
     { 
      yield return subNode; 
     } 
    } 
} 

var all_control = GetNodesRecursively(control, c=>c.Controls).ToList(); 

Answer 4

Sur la base de la solution de mrydengren:

public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection, 
    Func<T, IEnumerable> selector, 
    Func<T, bool> predicate) 
{ 
    foreach (var item in collection.OfType<T>()) 
    { 
     if(!predicate(item)) continue; 

     yield return item; 

     IEnumerable<T> children = selector(item).GetRecursively(selector, predicate); 
     foreach (var child in children) 
     { 
      yield return child; 
     } 
    } 
} 


var theNodes = treeView1.Nodes.GetRecursively<TreeNode>(
    x => x.Nodes, 
    n => n.Text.Contains("1")).ToList(); 

Edit: pour BillW

Answer 5

Vous semblez être sur la bonne voie et les réponses ci-dessus ont quelques bonnes idées. Mais je note que toutes ces solutions récursives ont des défauts profonds.

Supposons que l'arbre en question ait un total de n nœuds avec une profondeur d'arbre maximale de d < = n. Tout d'abord, ils consomment de l'espace de pile système dans la profondeur de l'arborescence. Si la structure de l'arbre est très profonde, alors cela peut faire sauter la pile et planter le programme. La profondeur de l'arbre d est O (lg n), en fonction du facteur de ramification de l'arbre. Le pire des cas n'est pas du tout une ramification - juste une liste chaînée - auquel cas un arbre avec seulement quelques centaines de nœuds va souffler la pile. Deuxièmement, ce que vous faites ici est de construire un itérateur qui appelle un itérateur qui appelle un itérateur ... de sorte que chaque MoveNext() sur l'itérateur du haut fasse en fait une chaîne d'appels qui est encore O (d) en coût. Si vous faites cela sur chaque nœud, alors le coût total des appels est O (nd), ce qui est le cas le plus défavorable O (n^2) et le meilleur des cas O (n lg n). Vous pouvez faire mieux que les deux; il n'y a aucune raison que cela ne puisse pas être linéaire dans le temps. L'astuce consiste à arrêter d'utiliser la petite pile système fragile pour suivre ce qu'il faut faire ensuite et à commencer à utiliser une pile allouée par tas pour garder une trace explicite.

Vous devez ajouter à votre liste de lecture de l'article de Wes Dyer sur ce point:

https://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators/

Il donne quelques bonnes techniques à la fin pour l'écriture itérateurs récursifs.