Linq extension method, how to find child in collection recursive

Question

Hi, I'm already familiar with Linq but have little understanding of extension methods I'm hoping someone can help me out.

So I have this hierarchical collection pseudo code ie:

class Product
  prop name
  prop type
  prop id
  prop List<Product> children

And I have a list of products List products.

Is there any way I can look for product in this collection by the id with a extension method ? In other words I need one item somewhere within the hierarchy.

Help would be most appreciated

cheers /sushiBite

Answer 1

You can flatten your tree structure using this extension method:

static IEnumerable<Product> Flatten(this IEnumerable<Product> source)
{
    return source.Concat(source.SelectMany(p => p.Children.Flatten()));
}

Usage:

var product42 = products.Flatten().Single(p => p.Id == 42);

Note that this is probably not very fast. If you repeatedly need to find a product by id, create a dictionary:

var dict = products.Flatten().ToDictionary(p => p.Id);

var product42 = dict[42];

Answer 2

If you want to "sub-iterate" and find a child in a list of Products:

List<Product>
    Product
       Child
       Child
       Child
       Child
    Product
       Child
       Child *find this one
       Child

You can use the existing SelectMany extension method. SelectMany can be used to "flatten" a two-level hierarchy.

Here's a great explanation of SelectMany: http://team.interknowlogy.com/blogs/danhanan/archive/2008/10/10/use-linq-s-selectmany-method-to-quot-flatten-quot-collections.aspx

Your syntax would like like this:

List<Product> p = GetProducts(); //Get a list of products
var child = from c in p.SelectMany(p => p.Children).Where(c => c.Id == yourID);

Answer 3

Here is a generic solution that will short-circuit traversal of the hierarchy once a match is found.

public static class MyExtensions
{
    public static T FirstOrDefaultFromMany<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector,
        Predicate<T> condition)
    {
        // return default if no items
        if(source == null || !source.Any()) return default(T);

        // return result if found and stop traversing hierarchy
        var attempt = source.FirstOrDefault(t => condition(t));
        if(!Equals(attempt,default(T))) return attempt;

        // recursively call this function on lower levels of the
        // hierarchy until a match is found or the hierarchy is exhausted
        return source.SelectMany(childrenSelector)
            .FirstOrDefaultFromMany(childrenSelector, condition);
    }
}

To use it in your case:

var matchingProduct = products.FirstOrDefaultFromMany(p => p.children, p => p.Id == 27);

Answer 4

static IEnumerable<Product> FindProductById(this IEnumerable<Product> source, int id) 
{
    return source.FirstOrDefault(product => product.Id = id) ?? source.SelectMany(product => product.Children).FindProductById(id);
}