Complex LINQ sorting with groups

I am trying to sort a list of items according to the following (simplified) rules:

I'll each item has the following properties:

 Id (int), 
 ParentId (int?), 
 Name (string)

ParentID is a self-join ForeignKey to Id. If an item has a ParentId, then the parent will also exist in the list.

I need to sort the list so that all items which have a parent, appear immediately after their parent. Then 开发者_如何学Call items will be sorted by Name.

So if I had the following:

 Id: 1, ParentId: null, Name: Pi
 Id: 2, ParentId: null, Name: Gamma
 Id: 11, ParentId: 1, Name: Charlie
 Id: 12, ParentId: 1, Name: Beta
 Id: 21, ParentId: 2, Name: Alpha
 Id: 22, ParentId: 2, Name: Omega

Then I would want them sorted as follows:

Ids: 2, 21, 22, 1, 12, 11

At the moment the best I can come up with is to sort by Name first, and then Group by ParentId as follows:

var sortedItems = itemsToSort.OrderBy(x=> x.Name).GroupBy(x=> x.ParentId);

My starting plan was then as follows: (in non functioning code)

var finalCollection = new List<Item>

var parentGroup = sortedItems.Where(si => si.Key == null);

foreach(parent in parentGroup)
{
   finalCollection.Add(parent);
   foreach(child in sortedItems.Where(si => si.Key == parent.Id)
   {
      finalCollection.Add(child);
   }
}

However, parentGroup is not

 IEnumerable<Item> 

so this does not work.

I feel there is an simpler, more concise way of achieving this, but currently it's eluding me - can anyone help?

If you only have two levels you can do it like this:

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
var parents = lookup[null];
var sortedItems = parents.SelectMany(x => new[] { x }.Concat(lookup[x.Id]));

Intially items are sorted by name ensuring that when they are later split into groups they stay sorted.

Then a lookup table is created allowing to lookup by ParentId. The parents identified by having a null ParentId are then joined with their children using SelectMany and the lookup table is used to find the children. The parent is inserted before the children to get the desired sequence.

If you want to solve the general case with more than two levels you need to employ recursion. Here is a way to recursively get the substree for a node:

IEnumerable<Item> GetSubtreeForParent(Item parent, ILookup<Int32?, Item> lookup) {
  yield return parent;
  foreach (var child in lookup[parent.Id])
    foreach (var descendant in GetSubtreeForParent(child, lookup))
      yield return descendant;
}

The code is almost the same as the simpler case above:

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
var parents = lookup[null];
var sortedItems = parents.SelectMany(x => GetSubtreeForParent(x, lookup));

By using a recursive lambda you can even do it all "inline":

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
// Declare Func to allow recursion.
Func<Int32?, IEnumerable<Item>> getSubTreeForParent = null;
getSubTreeForParent =
  id => lookup[id].SelectMany(x => new[] { x }.Concat(getSubTreeForParent(x.Id)));
var sortedItems = getSubTreeForParent(null);

As I understand your question you want to order the results by parent name (if it's a parent) and then by child name (if it's a child), but you want all children to appear in the list after their respective parent.

This should do the trick:

Updated to address the issue that @Martin Liversage mentioned.

var query = from item in itemsToSort
            let parent = itemsToSort.Where(i => i.Id == item.ParentId).FirstOrDefault()
            //get the name of the item's parent, or the item itself if it is a parent
            let parentName = (parent != null) ? parent.Name : item.Name
            //get the name of the child (use null if the item isn't a child)
            let childName = (parent != null) ? item.Name : null
            orderby parentName, childName
            select item;

var finalCollection = query.ToList();

Here's the output:

This can be achieved using:

list.Select(i => 
      new {Parent=list.Where(x => x.Id == i.ParentId).FirstOrDefault(), Item = i})
    .OrderBy(i => i.Parent == null ? i.Item.Name : i.Parent.Name + i.Item.Name)
    .Select(i => i.Item)

Live example: http://rextester.com/rundotnet?code=WMEZ40628

Output is:

2
21
22
1
12
11

I'd go with DoctaJonez's answer for 2 level.

It can be extended to n levels like so:

Func<int?,Item> lookup = id => list.Where(i => i.Id == id).FirstOrDefault();

Func<Item,string> makeSortString = null;
makeSortString = i => i.ParentId == null ? i.Name : makeSortString(lookup(i.ParentId)) + i.Name;

list.OrderBy(makeSortString).ToList();

This

var parentGroup = sortedItems.Where(si => si.Key == null).ToList()

will make parentGroup IEnumerable<Item> .

You will loose laziness on the top level, but i think it's fine due to the context.

How about this?

var lookup = items.ToLookup(x => x.ParentId);

Func<int?, IEnumerable<Item>> f =  null;
f = ni =>
    from a in lookup[ni].OrderBy(x => x.Name)
    from b in (new [] { a }).Concat(f(a.Id))
    select b;

And then to get the sorted list do this:

var sorted = f(null);

Simple. :-)