How to use LINQ to select all descendants of a com

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

I don't know about better, but I think this performs the same logic:

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

It might be shorter, but there is nothing wrong with what you have. As I said above, this is supposed to perform the same thing and I doubt that the performance of the function is improved.

Answer 2

This is a good example for when you might want to implement an iterator. This has the advantage of lazy evaluation in a slightly more readable syntax. Also, if you need to add additional custom logic then this form is more extensible

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

Answer 3

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

When doing a translation from imperitive syntax to LINQ, it is usually pretty easy to take the translation one step at a time. Here is how this works:

1. This is looping over composite.Children, so that will be the collection we apply LINQ to.
2. There are two general operations occuring in the loop, so lets do one of them at a time
3. The "if" statement is performing a filter. Normally, we would use "Where" to perform a filter, but in this case the filter is based on type. LINQ has "OfType" built in for this.
4. For each child composite, we want to recursively call GetDescendants and add the results to a single list. Whenever we want to transform an element into something else, we use either Select or SelectMany. Since we want to transform each element into a list and merge them all together, we use SelectMany.
5. Finally, to add in the composite.Children themselves, we concatenate those results to the end.

Answer 4

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