c# - How to use LINQ to select all descendants of a composite object

Question

How can I make ComponentTraversal.GetDescendants() better using LINQ?

Question

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

Answer

I edited Chris's answer to provide a generic extension method that I've added to my Common library. I can see this being helpful for other people as well so here it is:

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

Thanks Chris!

Also,

Please look at LukeH's answer at http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx . His answer provides a better way to approach this problem in general, but I did not select it because it was not a direct answer to my question.

Answer 1

There are often good reasons to avoid (1) recursive method calls, (2) nested iterators, and (3) lots of throwaway allocations. This method avoids all of those potential pitfalls:

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

And here's the generic equivalent:

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