Enumerazione di raccolte che non sono intrinsecamente IEnumerable?

Quando si desidera enumerare ricorsivamente un object gerarchico, selezionando alcuni elementi in base ad alcuni criteri, ci sono numerosi esempi di tecniche come “appiattimento” e quindi di filtraggio usando Linq: come quelli qui trovati:

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 è stata questa:

link text

Che fornisce un metodo di estensione per Control.ControlCollection con un risultato IEnumerable che è ansible utilizzare con Linq.

Ho modificato l’esempio precedente per analizzare i nodes di un TreeView senza problemi.

public static IEnumerable 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 usando 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 modo più elegante per farlo quando i vincoli sono passati.

Quello che voglio sapere se è ansible 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 è un TreeNodeCollection o Controls.Collection.

Mi interesserebbe anche sapere se c’è un 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”. 🙂

Apprezzo 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 🙂

Questo codice dovrebbe fare il trucco

 public static class Extensions { public static IEnumerable GetRecursively(this IEnumerable collection, Func selector) { foreach (var item in collection.OfType()) { yield return item; IEnumerable children = selector(item).GetRecursively(selector); foreach (var child in children) { yield return child; } } } } 

Ecco un esempio di come usarlo

 TreeView view = new TreeView(); // ... IEnumerable nodes = view.Nodes. .GetRecursively(item => item.Nodes); 

Aggiornamento: 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 GetItems(this IEnumerable collection, Func selector) { Stack> stack = new Stack>(); stack.Push(collection.OfType()); while (stack.Count > 0) { IEnumerable items = stack.Pop(); foreach (var item in items) { yield return item; IEnumerable children = selector(item).OfType(); stack.Push(children); } } } } 

Ho fatto un semplice test delle prestazioni usando la seguente tecnica di benchmarking . 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, conducendo infine a una StackOverflowException quando la profondità dell’albero diventa troppo grande.

analisi comparativa

Sembri essere sulla buona strada e le risposte 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 nodes con una profondità massima di albero d <= n.

Prima di tutto, consumano lo 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 nodes 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.

Dovresti 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/

Dà delle buone tecniche alla fine per scrivere iteratori ricorsivi.

Non sono sicuro di TreeNodes, ma puoi creare la collezione Control di un modulo IEnumerable usando System.Linq e, ad esempio

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

Mi dispiace dire che non so come rendere questo ricorsivo, in cima alla mia testa.

Basato sulla soluzione di mrydengren:

 public static IEnumerable GetRecursively(this IEnumerable collection, Func selector, Func predicate) { foreach (var item in collection.OfType()) { if(!predicate(item)) continue; yield return item; IEnumerable children = selector(item).GetRecursively(selector, predicate); foreach (var child in children) { yield return child; } } } var theNodes = treeView1.Nodes.GetRecursively( x => x.Nodes, n => n.Text.Contains("1")).ToList(); 

Modifica: per BillW

Immagino tu stia chiedendo qualcosa di simile.

 public static IEnumerable  GetNodesRecursively(this TCollection nodeCollection, Func 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();