Enumerazione di raccolte che non sono intrinsecamente IEnumerable?

Question

Quando si desidera elencare ricorsivamente un oggetto gerarchico, selezionando alcuni elementi sulla base di alcuni criteri, ci sono numerosi esempi di tecniche come "appiattimento" e quindi il filtraggio utilizzando Linq: come quelli trovati qui:

link text

Tuttavia, quando si enumera qualcosa come la raccolta Controls di un Form o la raccolta Nodes di un TreeView, non sono stato in grado di utilizzare questi tipi di tecniche perché sembrano richiedere un argomento (al metodo di estensione) che è un IEnumerable collezione: il passaggio in SomeForm.Controls non viene compilato.

La cosa più utile che ho trovato è stato questo:

link text

che ti dà un metodo di estensione per Control.ControlCollection con un risultato IEnumerable è possibile utilizzare con LINQ.

Ho modificato l'esempio precedente per analizzare i nodi di un TreeView senza problemi.

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

Questo è il tipo di codice che sto scrivendo ora utilizzando il metodo di estensione:

var theNodes = treeView1.Nodes.GetNodesRecursively(); 

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

e penso che ci possa essere un più elegante modo per fare questo in cui il vincolo (s) sono passato.

Che cosa voglio sapere se è possibile definire genericamente tali procedure, in modo che: in fase di esecuzione posso passare il tipo di raccolta, così come la raccolta effettiva, ad un parametro generico, quindi il codice è indipendente dal fatto che si tratti di TreeNodeCollection o Controls.Collection .

Mi piacerebbe anche sapere se c'è altro modo (più economico? Fastser?) Di quello mostrato nel secondo link (sopra) per ottenere un TreeNodeCollection o Control.ControlCollection in una forma utilizzabile da Linq.

Un commento di Leppie su "SelectMany nel post SO collegato al primo (sopra) sembra un indizio.

I miei esperimenti con SelectMany sono stati: beh, chiamali "disastri". :)

Apprezzare qualsiasi suggerimento. Ho passato molte ore a leggere ogni post SO che ho potuto trovare toccato in queste aree, e vagare per la mia strada in una tale esotismo come "y-combinator". Un'esperienza "umiliante", potrei aggiungere :)

Answer 1

Questo codice dovrebbe fare il trucco

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

Ecco un esempio di come usarlo Aggiornamento

TreeView view = new TreeView(); 

// ... 

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

: In risposta al post di Eric Lippert.

Ecco una versione molto migliorata utilizzando la tecnica discussa in 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); 
      } 
     } 
    } 
} 

ho fatto un semplice test delle prestazioni utilizzando la seguente benchmarking technique. I risultati parlano da soli. La profondità dell'albero ha un impatto solo marginale sulle prestazioni della seconda soluzione; mentre le prestazioni diminuiscono rapidamente per la prima soluzione, portando infine a un StackOverflowException quando la profondità dell'albero diventa troppo grande.

Answer 2

io non sono sicuro di TreeNodes, ma si può fare Controls di una forma IEnumerable utilizzando System.Linq e, per esempio

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" 

Spiace dimmi che non so come renderlo ricorsivo, in cima alla mia testa.

Answer 3

Credo che si sta chiedendo qualcosa di simile.

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

Sulla base della soluzione 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: per BillW

Answer 5

ti sembra di essere sulla strada giusta e le risposte di cui sopra hanno alcune buone idee. Ma noto che tutte queste soluzioni ricorsive hanno alcuni difetti profondi.

Supponiamo che l'albero in questione abbia un totale di n nodi con una profondità massima di albero d < = n.

Prima di tutto, consumano spazio di stack di sistema nella profondità dell'albero. Se la struttura ad albero è molto profonda, questo può far saltare la pila e far crashare il programma. La profondità dell'albero d è O (lg n), a seconda del fattore di ramificazione dell'albero. Il caso peggiore non è affatto una ramificazione - solo una lista collegata - nel qual caso un albero con solo poche centinaia di nodi farà esplodere la pila.

In secondo luogo, quello che stai facendo qui è la costruzione di un iteratore che chiama un iteratore che chiama un iteratore ... in modo che ogni MoveNext() sull'iteratore in alto faccia effettivamente una catena di chiamate che è nuovamente O (d) nel costo. Se lo fai su ogni nodo, il costo totale nelle chiamate è O (nd), che è il caso peggiore O (n^2) e il caso migliore O (n lg n). Puoi fare meglio di entrambi; non c'è motivo per cui questo non possa essere lineare nel tempo.

Il trucco è smettere di usare lo stack di sistema piccolo e fragile per tenere traccia di cosa fare dopo e iniziare a utilizzare uno stack allocato all'heap per tenere traccia in modo esplicito.

si dovrebbe aggiungere alla tua lista di lettura l'articolo di Wes Dyer su questo:

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

egli dà alcune buone tecniche alla fine per la scrittura di iteratori ricorsive.