Enumerare raccolte che non sono intrinsecamente IEnumerable?

Question

Quando si desidera enumerare ricorsivamente un oggetto gerarchico, selezionando alcuni elementi in base ad alcuni criteri, ci sono numerosi esempi di tecniche come " appiattimento " e poi filtrando usando Linq: come quelli trovati qui:

testo del link

Ma, 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 è una raccolta IEnumerable: il passaggio in SomeForm.Controls non viene compilato.

La cosa più utile che ho trovato è stata questa:

testo del link

Che ti dà un metodo di estensione per Control.ControlCollection con un risultato IEnumerable che puoi usare con Linq.

Ho modificato l'esempio sopra 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 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 potrebbe esserci un modo più elegante per farlo in cui i vincoli vengono superati.

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

Sarebbe anche interessante sapere se esiste un altro modo (più economico? più veloce?) di quello mostrato nel secondo link (sopra) per ottenere TreeNodeCollection o Control.ControlCollection in un modulo 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 puntatore. Ho trascorso diverse ore a leggere tutti i post SO che ho potuto trovare quelli che toccavano queste aree e mi sono fatto strada in esotiche come il & Quot; y-combinator. & Quot; Un & Quot; umiliante & Quot; esperienza, 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

TreeView view = new TreeView();

// ...

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

Aggiornamento: in risposta al post di Eric Lippert.

Ecco una versione molto migliorata usando 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 eseguito un semplice test delle prestazioni utilizzando la seguente tecnica di benchmarking . I risultati parlano da soli. La profondità dell'albero ha solo un impatto 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

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 nodi con una profondità massima dell'albero di d < = n.

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

In secondo luogo, quello che stai facendo qui è la creazione di un iteratore che chiama un iteratore che chiama un iteratore ... in modo che ogni MoveNext () sull'iteratore superiore esegua effettivamente una catena di chiamate che è di nuovo O (d) in costo. Se lo fai su ogni nodo, il costo totale delle chiamate è O (nd) che è il caso peggiore O (n ^ 2) e il caso migliore O (n lg n). Puoi fare di 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 in seguito e iniziare a utilizzare uno stack allocato in heap per tenere esplicitamente traccia.

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à alcune buone tecniche alla fine per scrivere iteratori ricorsivi.

Answer 3

Non sono sicuro di TreeNodes, ma puoi rendere la raccolta Controls di un modulo IEnumerable usando System.Linq e, ad 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"

Mi dispiace dire che non so come renderlo ricorsivo, fuori dalla mia testa.

Answer 4

Basato sulla soluzione di 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();

Modifica: per BillW

Answer 5

Suppongo che tu stia chiedendo qualcosa del genere.

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