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

Question

Lorsque vous souhaitez énumérer de manière récursive un objet hiérarchique en sélectionnant certains éléments en fonction de certains critères, il existe de nombreux exemples de techniques telles que & "aplatissement &"; puis filtrer à l'aide de Linq: comme ceux trouvés ici:

texte du lien

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

La chose la plus utile que j'ai trouvée est la suivante:

texte du lien

Ce qui vous donne une méthode d'extension pour Control.ControlCollection avec un résultat IEnumerable que vous pouvez ensuite 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 j’écris en utilisant la méthode d’extension suivante:

    var theNodes = treeView1.Nodes.GetNodesRecursively();

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

Et je pense qu’il existe peut-être un moyen plus élégant de faire cela lorsque la ou les contraintes sont passées.

Ce que je veux savoir s’il est possible de définir de telles procédures de manière générique, de sorte que: au moment de l’exécution, je puisse transmettre le type de collection, ainsi que la collection réelle, à un paramètre générique, afin que le code soit indépendamment du fait qu'il s'agisse d'un TreeNodeCollection ou de Controls.Collection.

Cela m'intéresserait également de savoir s'il existe un autre moyen (moins cher? plus rapide?) que celui indiqué dans le deuxième lien (ci-dessus) pour obtenir un TreeNodeCollection ou un Control.ControlCollection sous une forme utilisable par Linq.

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

Mes expériences avec SelectMany ont été les suivantes: eh bien, appelez-les & "Catastrophes. &"; :)

Appréciez les pointeurs. J'ai passé plusieurs heures à lire tous les posts SO que je pouvais trouver qui touchaient à ces domaines et à me frayer un chemin dans un exotisme tel que le & "Y-combinator. &"; Un & Quot; humble & Quot; expérience, 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 d'utilisation.

TreeView view = new TreeView();

// ...

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

Mise à jour: En réponse au message d'Eric Lippert.

Voici une version bien améliorée utilisant la technique décrite dans Tout sur les itérateurs .

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 effectué un test de performance simple en utilisant la technique d'analyse comparative suivante. Les résultats parlent d'eux-mêmes. La profondeur de l'arbre n'a qu'un impact marginal sur les performances de la deuxième solution; alors que les performances diminuent rapidement pour la première solution, aboutissant finalement à un StackOverflowException lorsque la profondeur de l’arbre devient trop importante.

Answer 2

Vous semblez être sur la bonne voie et les réponses ci-dessus ont de bonnes idées. Mais je remarque que toutes ces solutions récursives présentent de profondes lacunes.

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 système dans la profondeur de l’arbre. Si l’arborescence est très profonde, cela peut détruire 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. Dans le pire des cas, il n'y a aucune ramification, mais seulement une liste chaînée. Dans ce cas, un arbre contenant seulement quelques centaines de nœuds fera exploser la pile.

Deuxièmement, vous construisez un itérateur qui appelle un itérateur qui appelle un itérateur ... de sorte que chaque MoveNext () situé sur le premier itérateur effectue en réalité une chaîne d'appels correspondant à O (d) dans Coût. Si vous faites cela sur chaque nœud, le coût total des appels est égal à O (nd), ce qui correspond au pire des cas O (n ^ 2) et au meilleur des cas O (n lg n). Vous pouvez faire mieux que les deux. il n'y a aucune raison pour que cela ne puisse pas être linéaire dans le temps.

Le truc, c’est d’arrêter d’utiliser la petite pile système fragile pour garder une trace de ce qu’il faut faire par la suite, et de commencer à utiliser une pile allouée par tas pour garder explicitement trace.

Vous devriez ajouter à votre liste de lecture l'article de Wes Dyer sur ceci:

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

Il donne quelques bonnes techniques à la fin pour écrire des itérateurs récursifs.

Answer 3

Je ne suis pas sûr à propos de TreeNodes, mais vous pouvez créer la collection Controls d'un formulaire 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é de dire que je ne sais pas comment rendre ceci récursif, par coeur.

Answer 4

Basé sur 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();

Modifier: pour BillW

Answer 5

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