Aufzählen von Sammlungen, die nicht von Natur aus IEnumerable sind?

Question

Wenn Sie wollen rekursiv ein hierarchisches Objekt aufzuzählen, einige Elemente der Auswahl nach bestimmten Kriterien, gibt es zahlreiche Beispiele für Techniken wie „Abflachung“ und dann Linq Filterung mit: wie die hier gefunden:

Link-Text

Aber, wenn Sie so etwas wie die Controls-Auflistung eines Formulars werden aufzählt, oder die Auflistung Knoten eines TreeView, war ich nicht in der Lage, diese Art von Techniken zu verwenden, weil sie scheinen ein Argument erfordern (zum Extension-Methode), die eine IEnumerable Sammlung ist. vorbei in SomeForm.Controls nicht kompiliert

Die nützlichste, was ich fand, war diese:

Link-Text

, die Sie mit einem IEnumerable Ergebnis eine Erweiterungsmethode für Control.ControlCollection nicht geben können Sie dann mit Linq verwenden.

Ich habe das obige Beispiel modifiziert, um die Knoten eines TreeView ohne Probleme zu analysieren.

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

Dies ist die Art von Code, den ich jetzt hier schreibe die Erweiterung Methode:

    var theNodes = treeView1.Nodes.GetNodesRecursively();

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

Und ich denke, es kann ein eleganter Weg, dies zu tun, wo die Einschränkung (en) in übergeben werden.

Was ich möchte wissen, ob es möglich ist, solche Verfahren allgemein zu definieren, so dass: zur Laufzeit ich in der Art der Sammlung passieren kann, sowie die aktuelle Kollektion, zu einem generischen Parameter, so wird der Code unabhängig davon, ob es ein TreeNodeCollection oder Controls.Collection.

Es würde mich auch interessieren zu wissen, ob es eine andere Möglichkeit ist (günstiger? Fastser?) Als die in dem zweiten Link (oben) gezeigt, die eine TreeNodeCollection oder Control.ControlCollection in einer Form verwendbar von Linq zu erhalten.

Ein Kommentar von leppie über ‚Select in der SO Post verknüpft ersten (oben) scheint wie ein Anhaltspunkt.

Meine Experimente mit Select waren: na ja, nennen sie „Katastrophen.“ :)

Schätzen Sie alle Hinweise. Ich habe mehrere Stunden damit verbracht, jeden SO Post Lesen ich, dass berührt auf diese Bereiche und weitläufig dem Weg in eine solche Exoten wie das finden konnten, „y-combinator.“ A "demütigend" Erfahrung, wie ich hinzufügen:)

Answer 1

Dieser Code sollte es tun

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

Hier ist ein Beispiel dafür, wie es zu benutzen

TreeView view = new TreeView();

// ...

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

Update:. Als Reaktion auf Eric Lippert Post

Hier ist eine stark verbesserte Version der Technik diskutiert in Alles über Iteratoren .

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

Ich habe einen einfachen Performance-Test der folgenden Benchmarking Technik verwenden. Die Ergebnisse sprechen für sich. Die Tiefe des Baumes hat nur geringen Einfluss auf die Leistung der zweiten Lösung; während der Leistung schnell für die erste Lösung verringert, was schließlich zu einem StackOverflowException leadning, wenn die Tiefe des Baumes zu groß wird.

Answer 2

Sie scheinen auf dem richtigen Weg zu sein und die Antworten oben haben einige gute Ideen. Aber ich stelle fest, dass all diese rekursive Lösungen einige tiefe Mängel haben.

Lassen Sie sich den Baum in Frage annehmen, insgesamt n Knoten mit einer max Baumtiefe von d hat <= n.

Zunächst einmal, sie verbrauchen Systemstapelraum in der Tiefe des Baumes. Wenn die Baumstruktur sehr tief ist, dann kann dies den Stapel bläst und das Programm zum Absturz bringen. Baumtiefe d ist O (lg n), abhängig von dem Verzweigungsfaktor des Baums. Schlimmer Fall ist gar keine Verzweigung - nur eine verkettete Liste - in diesem Fall ein Baum mit nur ein paar hundert Knoten den Stapel bläst.

Zweitens, was Sie tun, hier ist der Aufbau einen Iterator, der einen Iterator aufruft, die einen Iterator aufruft ... so dass jeder Movenext () auf dem oberen Iterator tut eigentlich eine Kette von Anrufen, die wieder O (d) in Kosten. Wenn Sie dies auf jedem Knoten tun, dann die Gesamtkosten im Anrufe O (nd), die schlechtesten Fall O (n ^ 2) und am besten Fall O (n lg n). Sie können als beide besser machen; es gibt keinen Grund, warum dies nicht in der Zeit linear sein kann.

Der Trick ist, den kleinen, fragile System-Stack zu verwenden zu stoppen, um zu verfolgen, was als nächstes zu tun, und explizit Spur mit einem Heap zugewiesenen Stack beginnen zu halten.

Sie sollten auf Ihre Leseliste Wes Dyer Artikel über hinzufügen:

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

Er gibt einige gute Techniken am Ende für rekursive Iteratoren schreiben.

Answer 3

Ich bin nicht sicher über TreeNodes, aber Sie können die Controls-Auflistung eines Formulars IEnumerable machen durch System.Linq verwenden und zum Beispiel

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"

Leider zu sagen, ich weiß nicht, wie diese rekursiv zu machen, aus der Spitze von meinem Kopf.

Answer 4

Basierend auf mrydengren Lösung:

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: für BillW

Answer 5

Ich denke, man für so etwas fragen.

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