Enumerando coleções que não são inerentemente IEnumerable?

Question

Quando você quiser enumerar de forma recursiva um objeto hierárquica, selecionar alguns elementos com base em alguns critérios, existem inúmeros exemplos de técnicas como "achatamento" e, em seguida, filtrando usando Linq: como os encontrados aqui:

texto do link

Mas, quando você está enumerando algo como a coleção Controls de um formulário, ou a coleção de nós de um TreeView, eu fui incapaz de usar esses tipos de técnicas, porque eles parecem exigir um argumento (para o método de extensão) que é uma coleção IEnumerable:. passando em SomeForm.Controls não compila

A coisa mais útil que eu encontrei foi isto:

link de texto

O que lhe dá um método de extensão para Control.ControlCollection com um resultado IEnumerable então você pode usar com Linq.

Eu modificado o exemplo acima para analisar os nós de uma TreeView sem nenhum problema.

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

Este é o tipo de código que estou escrevendo agora utilizando o método de extensão:

    var theNodes = treeView1.Nodes.GetNodesRecursively();

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

E eu acho que pode haver uma maneira mais elegante de fazer isso onde a restrição (s) são passados ??em.

O que eu quero saber se é possível definir esses procedimentos genericamente, de modo que: em tempo de execução eu posso passar no tipo de coleção, assim como a coleção real, a um parâmetro genérico, de modo que o código é independente de se tratar de um TreeNodeCollection ou Controls.Collection.

Ele também me interessa saber se há alguma outra maneira (mais barato? Fastser?) Do que o mostrado no segundo link (acima) para obter uma TreeNodeCollection ou Control.ControlCollection numa forma utilizável por Linq.

Um comentário por leppie sobre 'SelectMany no post SO ligada à primeira (acima) parece ser uma pista.

As minhas experiências com SelectMany foram: bem, chamá-los de "desastres". :)

aprecio qualquer ponteiros. Eu passei várias horas lendo todos os SO postar eu poderia achar que tocou sobre estas áreas, e divagar meu caminho para tal exotica como o "y-Combinator." Uma experiência "humilhante", devo acrescentar:)

Answer 1

Este código deve fazer o truque

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

Aqui está um exemplo de como usá-lo

TreeView view = new TreeView();

// ...

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

Update:. Em resposta ao post de Eric Lippert

Aqui está uma versão muito melhorada usando a técnica discutida em Tudo sobre 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);
            }
        }
    }
}

Eu fiz um teste de desempenho simples usando o seguinte técnica de benchmarking . Os resultados falam por si. A profundidade da árvore tem apenas um impacto marginal sobre o desempenho da segunda solução; ao passo que o desempenho diminui rapidamente para a primeira solução, eventualmente, leadning a um StackOverflowException quando a profundidade da árvore torna-se muito grande.

Answer 2

Você parece estar no caminho certo e as respostas acima têm algumas boas ideias. Mas note que todas estas soluções recursivas ter algumas falhas profundas.

Vamos supor que a árvore em questão tem um total de n nós com uma profundidade de árvore máximo de d <= n.

Primeiro, eles consomem espaço de pilha do sistema na profundidade da árvore. Se a estrutura da árvore é muito profundo, então este pode explodir a pilha e travar o programa. Árvore profundidade d é O (lg n), de acordo com o factor de ramificação da árvore. Pior caso não está ramificando em tudo - apenas uma lista ligada - caso em que uma árvore com apenas algumas centenas de nós vai explodir a pilha.

Em segundo lugar, o que você está fazendo aqui é a construção de um iterador que chama um iterador que chama um iterador ... para que cada MoveNext () na parte superior iterador realmente faz uma cadeia de chamadas que está novamente O (d) em custo. Se você fizer isso em todos os nós, então o custo total das chamadas é O (nd) que é pior caso O (n ^ 2) e melhor caso O (n lg n). Você pode fazer melhor do que ambos; não há nenhuma razão para que isso não pode ser linear no tempo.

O truque é parar de usar a pilha do sistema pequeno, frágil para acompanhar o que fazer a seguir, e para começar a usar uma pilha alocada-heap para manter explicitamente pista.

Você deve adicionar à sua lista de leitura artigo de Wes Dyer sobre isso:

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

Ele dá algumas boas técnicas no final para escrever iterators recursiva.

Answer 3

Eu não tenho certeza sobre TreeNodes, mas você pode fazer a coleção Controls de uma forma IEnumerable usando System.Linq e, por exemplo

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"

Desculpe dizer que eu não sei como fazer isso recursiva, em cima da minha cabeça.

Answer 4

Com base na solução das 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: para BillW

Answer 5

Eu acho que você está pedindo algo como isto.

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