¿Enumeración de colecciones que no son inherentemente IEnumerable?

Question

Cuando se desea enumerar de forma recursiva un objeto jerárquico, seleccionando algunos elementos en función de algunos criterios, existen numerosos ejemplos de técnicas como el "aplanamiento" y luego filtrar utilizando LINQ: al igual que las que se encuentran aquí:

link text

Pero cuando enumera algo como la colección Controls de un Formulario, o la colección Nodos de un TreeView, no he podido utilizar este tipo de técnicas porque parecen requerir un argumento (al método de extensión) que es un IEnumerable colección: pasar en SomeForm.Controls no se compila.

Lo más útil que encontré fue esto:

link text

¿Qué te da un método de extensión para Control.ControlCollection con un resultado IEnumerable luego se puede utilizar con LINQ.

Modifiqué el ejemplo anterior para analizar los Nodos de un TreeView sin ningún 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 es el tipo de código que estoy escribiendo ahora utilizando el método de extensión:

var theNodes = treeView1.Nodes.GetNodesRecursively(); 

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

Y yo creo que puede ser una manera más elegante de hacer esto, donde la restricción (s) son pasado.

Lo que quiero saber si es posible definir tales procedimientos genéricamente, de modo que: en tiempo de ejecución puedo pasar el tipo de colección, así como la colección real, a un parámetro genérico, por lo que el código es independiente de si se trata de un TreeNodeCollection o Controls.Collection .

También me interesaría saber si hay alguna otra forma (¿más barata? Fastser?) Que la que se muestra en el segundo enlace (arriba) para obtener TreeNodeCollection o Control.ControlCollection en un formato que pueda utilizar Linq.

Un comentario de Leppie sobre 'SelectMany en la publicación SO vinculado al primero (arriba) parece una pista.

Mis experimentos con SelectMany han sido: bueno, llámelos "desastres". :)

Aprecie cualquier punteros. He pasado varias horas leyendo cada publicación SO que pude encontrar que tocaba en estas áreas, y adentrándome en un exotismo como el "y-combinator". Una experiencia "humillante", debo añadir :)

Answer 1

Este código debe hacer el truco

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

Aquí está un ejemplo de cómo usarlo

TreeView view = new TreeView(); 

// ... 

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

Actualización: En respuesta al mensaje de Eric Lippert.

Aquí hay una versión muy mejorada que utiliza la técnica descrita en 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); 
      } 
     } 
    } 
} 

Me hicieron una prueba de rendimiento simple utilizando la siguiente benchmarking technique. los resultados hablan por si mismos. La profundidad del árbol solo tiene un impacto marginal en el rendimiento de la segunda solución; mientras que el rendimiento disminuye rápidamente para la primera solución, lo que lleva a un StackOverflowException cuando la profundidad del árbol es demasiado grande.

Answer 2

No estoy seguro acerca de TreeNodes, pero se puede hacer la colección de controles de un formulario mediante el uso de IEnumerable System.Linq y, por ejemplo

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" 

Siento Digo que no sé cómo hacer que esto sea recursivo, fuera de mi cabeza.

Answer 3

supongo que está pidiendo algo como esto.

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

basado en la solución 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(); 

Editar: para billw

Answer 5

usted parece estar en el camino correcto y las respuestas anteriormente tienen algunas buenas ideas. Pero observo que todas estas soluciones recursivas tienen algunos defectos profundos.

Supongamos que el árbol en cuestión tiene un total de n nodos con una profundidad de árbol máxima de d < = n.

Primero, consumen el espacio de la pila del sistema en la profundidad del árbol. Si la estructura del árbol es muy profunda, esto puede hacer explotar la pila y bloquear el programa. La profundidad del árbol d es O (lg n), dependiendo del factor de ramificación del árbol. Peor aún es el caso de una bifurcación, solo una lista vinculada, en cuyo caso un árbol con solo unos pocos cientos de nodos volará la pila.

En segundo lugar, lo que estás haciendo aquí es construir un iterador que llama a un iterador que llama a un iterador ... para que cada MoveNext() en el iterador real haga una cadena de llamadas que sea O (d) en costo Si hace esto en cada nodo, entonces el costo total en llamadas es O (nd), que es el caso más desfavorable O (n^2) y el mejor caso O (n lg n). Puedes hacer mejor que ambos; no hay razón por la cual esto no pueda ser lineal en el tiempo.

El truco consiste en dejar de utilizar la pequeña y frágil pila del sistema para realizar un seguimiento de qué hacer a continuación y comenzar a utilizar una pila asignada en el montón para realizar un seguimiento explícito.

se debe añadir a su lista de leer el artículo de Wes Dyer en esto:

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

Se da algunas buenas técnicas al final para escribir iteradores recursivas.