Linq-to-objects: creating a two-level hierarchy from a flat source

Let's say I have this simple structure

class FooDefinition
{
    public FooDefinition Parent { get; set; }
}

class Foo
{
    public FooDefinition Definition { get; set; }
}

class Bar
{
    public ICollection<Foo> Foos { get; set; }
}

A Bar has a list of Foos which can be simple (no parent/child relationships) or nested just one level (i.e. a parent Foo has many child Foos). As can be seen here, the relationships are specified in the FooDefinition, not the Foo itself.

What I need to do is generate a list of Foos properly grouped by this hierarchy. Consider the following source data:

var simpleDefinition = new FooDefinition();
var parentDefinition = new FooDefinition();
var childDefinition = new FooDefinition { Parent = pa开发者_开发问答rentDefinition };

var bar = new Bar { Foos = new[]
                           {
                               new Foo { Definition = simpleDefinition },
                               new Foo { Definition = parentDefinition },
                               new Foo { Definition = childDefinition }
                           }};

I'd like to get a collection of top-level items with their chilren. An adequate data structure would probably be IEnumerable<IGrouping<Foo, Foo>>.

The result would look like:

• Item 1 (simple)
• Item 2 (parent)
  • Item 3 (child)

And of course I'd like to do this with a purely-functional Linq query. I do lots of these, but my brain seems to be stuck today.

bar.Foos.Where(x => x.Definition.Parent == null)
        .Select(x => Tuple.Create(x, 
                                  bar.Foos.Where(c => c.Definition
                                                       .Parent == x.Definition
                                                ))); 

This will return an IEnumerable<Tuple<Foo, IEnumerable<Foo>>>, where Item2 of the Tuple contains the children for the parent in Item1. For your example, this returns two Tuples:

• Item1 = simpleDefinition and Item2 containing an empty enumerable
• Item1 = parentDefinition and Item2 containing an enumerable which contains childDefinition

There might be a more elegant or faster way, but I couldn't come up with it...

Oh well, I contradict my own comment a little bit with this, but it is possible with GroupBy - at least nearly:

bar.Foos.Where(x => x.Definition.Parent == null)
        .GroupBy(x => x,
                 x => bar.Foos.Where(c => c.Definition.Parent == x.Definition));

This will return an IEnumerable<IGrouping<Foo, IEnumerable<Foo>>>.

Update:
I wanted to know, if the solution you wanted is possible at all.
Yes, it is:

bar.Foos.Where(x => x.Definition.Parent != null)
        .GroupBy(x => bar.Foos.Where(y => y.Definition == x.Definition.Parent)
                              .Single(),
                 x => x)
        .Union(bar.Foos.Where(x => x.Definition.Parent == null && 
                                   !bar.Foos.Any(c => c.Definition.Parent == 
                                                      x.Definition))
                       .GroupBy(x => x, x => (Foo)null));

But I really don't want to know the big O of this and it really shouldn't be used ;-)

If you add a class and a method, you can get to IEnumerable<IGrouping<Foo,Foo>>.

    class FooRelation{
        public Foo Parent {get; set;}
        public Foo Child  {get; set;}
    }

    static IEnumerable<FooRelation> GetChildren(Bar source, Foo parent){
        var children = source.Foos.Where(c => c.Definition.Parent == parent.Definition);
        if(children.Any())
            return children.Select(c => new FooRelation{Parent = parent, Child = c});
        return new FooRelation[]{new FooRelation{Parent = parent}};
    }

You might even be able to fold that static method into this query...but it would get messy:

     var r = bar.Foos.Where(x => x.Definition.Parent == null)
                .SelectMany(x => GetChildren(bar, x))
                .GroupBy(fr => fr.Parent, fr => fr.Child);