Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 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 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?

like image 901
BonyT Avatar asked Sep 09 '11 10:09

BonyT


2 Answers

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);
like image 101
Martin Liversage Avatar answered Oct 06 '22 03:10

Martin Liversage


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:

enter image description here

like image 38
Doctor Jones Avatar answered Oct 06 '22 03:10

Doctor Jones