Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to use LINQ to select all descendants of a composite object

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.

like image 231
smartcaveman Avatar asked Mar 10 '11 15:03

smartcaveman


People also ask

How does Linq select work?

Select is used to project individual element from List, in your case each customer from customerList . As Customer class contains property called Salary of type long, Select predicate will create new form of object which will contain only value of Salary property from Customer class.

What does select return in Linq?

The Select() method invokes the provided selector delegate on each element of the source IEnumerable<T> sequence, and returns a new result IEnumerable<U> sequence containing the output of each invocation.

Is Linq select slow?

Let's start off by acknowledging that using the LINQ operators (such as Select and Where ) does typically result in very slighly slower code than if you wrote a for or foreach loop to do the same thing. This is acknowledged in the Microsoft documentation: LINQ syntax is typically less efficient than a foreach loop.


2 Answers

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);
}
like image 106
LukeH Avatar answered Sep 19 '22 16:09

LukeH


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.
like image 36
Chris Pitman Avatar answered Sep 20 '22 16:09

Chris Pitman