Как использовать LINQ для выбора всех потомков составного объекта

Question

Как я могу улучшить ComponentTraversal.GetDescendants() с помощью LINQ?

Вопрос

public static class ComponentTraversal
{
    public static IEnumerable<Component> GetDescendants(this Composite composite)
    {
        //How can I do this better using LINQ?
        IList<Component> descendants = new Component[]{};
        foreach(var child in composite.Children)
        {
            descendants.Add(child);
            if(child is Composite)
            {
                descendants.AddRange((child as Composite).GetDescendants());
            }
        }
        return descendants;
    }
}
public class Component
{
    public string Name { get; set; }
}
public class Composite: Component
{
    public IEnumerable<Component> Children { get; set; }
}
public class Leaf: Component
{
    public object Value { get; set; }
}

Ответ

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

    public static IEnumerable<T> GetDescendants<T>(this T component, Func<T,bool> isComposite, Func<T,IEnumerable<T>> getCompositeChildren)
    {
        var children = getCompositeChildren(component);
        return children
            .Where(isComposite)
            .SelectMany(x => x.GetDescendants(isComposite, getCompositeChildren))
            .Concat(children);
    }

Спасибо, Крис!

Кроме того,

Пожалуйста, посмотрите на ответ Люка в http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx.Его ответ обеспечивает лучший способ решения этой проблемы в целом, но я не выбрал его, поскольку он не был прямым ответом на мой вопрос.

Answer 1

Часто есть веские причины избегать (1) рекурсивных вызовов методов, (2) вложенных итераторов и (3) большого количества одноразовых выделений.Этот метод позволяет избежать всех этих потенциальных ловушек:

public static IEnumerable<Component> GetDescendants(this Composite composite)
{
    var stack = new Stack<Component>();
    do
    {
        if (composite != null)
        {
            // this will currently yield the children in reverse order
            // use "composite.Children.Reverse()" to maintain original order
            foreach (var child in composite.Children)
            {
                stack.Push(child);
            }
        }

        if (stack.Count == 0)
            break;

        Component component = stack.Pop();
        yield return component;

        composite = component as Composite;
    } while (true);
}

И вот общий эквивалент:

public static IEnumerable<T> GetDescendants<T>(this T component,
    Func<T, bool> hasChildren, Func<T, IEnumerable<T>> getChildren)
{
    var stack = new Stack<T>();
    do
    {
        if (hasChildren(component))
        {
            // this will currently yield the children in reverse order
            // use "composite.Children.Reverse()" to maintain original order
            // or let the "getChildren" delegate handle the ordering
            foreach (var child in getChildren(component))
            {
                stack.Push(child);
            }
        }

        if (stack.Count == 0)
            break;

        component = stack.Pop();
        yield return component;
    } while (true);
}

Answer 2

var result = composite.Children.OfType<Composite>().SelectMany(child => child.GetDescendants()).Concat(composite.Children);
return result.ToList();

При выполнении перевода из неидеального синтаксиса в LINQ обычно довольно легко выполнить перевод по одному шагу за раз.Вот как это работает:

1. Это цикл по композитному. Дети, так что это будет коллекция, к которой мы применим LINQ.
2. В цикле происходят две основные операции:поэтому давайте сделаем один из них за раз
3. Оператор if выполняет фильтр.Обычно мы используем «Где» для выполнения фильтра, но в этом случае фильтр основан на типе.Для этого в LINQ встроен «OfType».
4. Для каждого дочернего композита мы хотим рекурсивно вызвать GetDescendants и добавить результаты в один список.Всякий раз, когда мы хотим преобразовать элемент во что-то другое, мы используем либо Select, либо SelectMany.Поскольку мы хотим преобразовать каждый элемент в список и объединить их все вместе, мы используем SelectMany.
5. Наконец, чтобы добавить в составной файл. Дети сами объединяем эти результаты до конца.

Answer 3

Я не знаю о лучшем, но я думаю, что это выполняет ту же логику:

public static IEnumerable<Component> GetDescendants(this Composite composite)
{
    return composite.Children
                .Concat(composite.Children
                            .Where(x => x is Composite)
                            .SelectMany(x => x.GetDescendants())
                );
}

Это может быть короче, но в том, что у вас есть, все в порядке.Как я уже говорил выше, предполагается, что он выполняет то же самое , и я сомневаюсь, что производительность функции улучшается.

Answer 4

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

 public static IEnumerable<Component> GetDescendants(this Composite composite)
    {
        foreach(var child in composite.Children)
        {
            yield return child;
            if(!(child is Composite))
               continue;

            foreach (var subChild in ((Composite)child).GetDescendants())
               yield return subChild;
        }
    }