Перечисление коллекций, которые по своей сути не являются IEnumerable?

Question

Если вы хотите рекурсивно перечислить иерархический объект, выбирая некоторые элементы на основе некоторых критериев, существует множество примеров таких методов, как " flatifying " а затем фильтрация с использованием Linq: как показано здесь:

текст ссылки

Но когда вы перечисляете что-то вроде коллекции Controls формы или коллекции Nodes TreeView, я не смог использовать эти типы методов, потому что они, кажется, требуют аргумента (для метода расширения), который коллекция IEnumerable: передача в SomeForm.Controls не компилируется.

Самым полезным, что я нашел, было следующее:

текст ссылки

Который дает вам метод расширения для Control.ControlCollection с результатом IEnumerable, который вы затем можете использовать с Linq.

Я изменил приведенный выше пример, чтобы без проблем проанализировать узлы TreeView.

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

Это код, который я пишу сейчас, используя метод расширения:

    var theNodes = treeView1.Nodes.GetNodesRecursively();

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

И я думаю, что может быть более элегантный способ сделать это, когда передаются ограничения.

Что я хочу знать, возможно ли определить такие процедуры универсально, чтобы: во время выполнения я мог передать тип коллекции, а также фактическую коллекцию, универсальному параметру, поэтому код независимо от того, является ли это TreeNodeCollection или Controls.Collection.

Мне также было бы интересно узнать, есть ли другой способ (более дешевый? более быстрый?), чем тот, который показан во второй ссылке (выше), для получения TreeNodeCollection или Control.ControlCollection в форме, используемой Linq.

Комментарий Леппи о «SelectMany» в посте SO, связанном с первым (выше), выглядит как подсказка.

Мои эксперименты с SelectMany были: ну, назовите их " бедствия. " :)

Цените любые указатели. Я потратил несколько часов на чтение каждого поста SO, который касался этих областей, и пробирался к такой экзотике, как & Quot; y-combinator. & Quot; & Quot; смирение & Quot; опыт, я мог бы добавить:)

Answer 1

Этот код должен сработать

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

Вот пример того, как его использовать

TreeView view = new TreeView();

// ...

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

Обновление: в ответ на сообщение Эрика Липперта.

Вот значительно улучшенная версия, использующая технику, описанную в Все об итераторах .

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

Я провел простой тест производительности, используя следующий метод бенчмаркинга . Результаты говорят сами за себя. Глубина дерева оказывает лишь незначительное влияние на производительность второго решения; в то время как производительность первого решения быстро снижается, что в конечном итоге приводит к StackOverflowException, когда глубина дерева становится слишком большой.

Answer 2

Похоже, вы на правильном пути, и в ответах выше есть несколько хороших идей. Но я отмечаю, что все эти рекурсивные решения имеют некоторые глубокие недостатки.

Предположим, что у рассматриваемого дерева есть всего n узлов с максимальной глубиной дерева d < = n.

Во-первых, они занимают место в системном стеке в глубине дерева. Если древовидная структура очень глубокая, это может привести к перегрузке стека и падению программы. Глубина дерева d составляет O (lg n), в зависимости от коэффициента ветвления дерева. В худшем случае это совсем не ветвление - это просто связанный список, и в этом случае дерево, содержащее всего несколько сотен узлов, разрушит стек.

Во-вторых, то, что вы делаете здесь, - это создание итератора, который вызывает итератор, который вызывает итератор ... так что каждый MoveNext () на верхнем итераторе фактически выполняет цепочку вызовов, которая снова является O (d) в Стоимость. Если вы делаете это на каждом узле, то общая стоимость вызовов составляет O (nd), что является наихудшим случаем O (n ^ 2) и наилучшим случаем O (n lg n). Вы можете сделать лучше, чем оба; нет никаких причин, почему это не может быть линейным во времени.

Хитрость заключается в том, чтобы прекратить использование небольшого хрупкого системного стека, чтобы отслеживать, что делать дальше, и начать использовать выделенный в куче стек, чтобы явно отслеживать.

Вы должны добавить в свой список чтения статью Уэса Дайера об этом:

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

В конце он дает несколько хороших приемов написания рекурсивных итераторов.

Answer 3

Я не уверен насчет TreeNodes, но вы можете сделать коллекцию Controls формы IEnumerable с помощью System.Linq и, например,

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"

Сожалею, что не знаю, как сделать это рекурсивным, от макушки головы.

Answer 4

На основании решения Мриденгрена:

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

Изменить: для BillW

Answer 5

Полагаю, вы просите что-то подобное.

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