CODEWITHSUNDEEP
c#linqrecursionextension-methodshierarchy
sushiBite
sushiBite

Reputation: 361

Linq extension method, how to find child in collection recursive

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.

Upvotes: 14

Views: 11929

Answers (6)

Jonathas Costa
Jonathas Costa

Reputation: 1016

I'm just refactoring dtb's solution to make it more generic. Try this Extension method:

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    return source.SelectMany(x => (recursion(x) != null && recursion(x).Any()) ? recursion(x).Flatten(recursion) : null)
                 .Where(x => x != null);
}

And you can use it like this:

productList.Flatten(x => x.Children).Where(x => x.ID == id);

Upvotes: 2

kampsj
kampsj

Reputation: 3149

An alternative solution using the yield to optimize the enumerations needed.

public static IEnumerable<T> SelectManyRecursive<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector)
{
    if (source == null)
        throw new ArgumentNullException("source");

    foreach (var i in source)
    {
        yield return i;
        var children = childrenSelector(i);
        if (children != null)
        {
            foreach (var child in SelectManyRecursive(children, childrenSelector))
            {
                yield return child;
            }
        }
    }
}

Then you can find a match by calling something like FirstOrDefault:

    var match = People.SelectManyRecursive(c => c.Children)
                      .FirstOrDefault(x => x.Id == 5);

Upvotes: 0

Jay
Jay

Reputation: 57959

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

Upvotes: 21

Jimmy Hoffa
Jimmy Hoffa

Reputation: 5967

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

Upvotes: 0

Dave Swersky
Dave Swersky

Reputation: 34810

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

Upvotes: -1

dtb
dtb

Reputation: 217341

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

Upvotes: 9

Related Questions