Complex LINQ sorting with groups

Question

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

Each element has the following properties:

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

ParentID is an independent connection of ForeignKey to the identifier. If the item has a ParentId, then the parent will also exist in the list.

I need to sort the list so that all elements that have a parent element appear immediately after their parent. Then all 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 like them to be sorted as follows:

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

At the moment, the best thing I can find is sorting by name first and then group by ParentId as follows:

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

My initial plan was as follows: (in idle 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> 

therefore it will not work.

I feel that there is a simpler and more concise way to achieve this, but currently it is eluding me - can anyone help?

Answer 1

If you have only two levels, you can do it as follows:

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

Inside, items are sorted by name, ensuring that when they are later divided into groups, they will be sorted.

Then a lookup table is created, allowing you to search using ParentId . Parents identified by null ParentId then connect to their children using SelectMany , and the lookup table is used to find the children. A parent is inserted in front of the children to get the desired sequence.

If you want to solve a general case with more than two levels, you need to use recursion. The following is a way to recursively get a substring 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 example 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)); 

Using a recursive lambda, you can 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); 

Answer 2

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

This should do the trick:

Updated to resolve the issue mentioned by @Martin Liversage .

 var query = from item in itemsToSort let parent = itemsToSort.Where(i => i.Id == item.ParentId).FirstOrDefault() //get the name of the item 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 conclusion:

Answer 3

This can be achieved with:

 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) 

Real-time example: http://rextester.com/rundotnet?code=WMEZ40628

Output:

 2 21 22 1 12 11 

Answer 4

I would go with a DoctaJonez answer for level 2.

It can be expanded to n levels as follows:

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

Answer 5

it

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

will make parentGroup IEnumerable<Item> .

You will lose laziness at the top level, but I think this is good because of the context.

Answer 6

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, follow these steps:

 var sorted = f(null); 

Simple .:-)