使用组进行复杂的LINQ排序

Question

我正在尝试根据以下(简化)规则对项目列表进行排序:

我将每个项目具有以下属性:

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

ParentID是Id的自联接ForeignKey.如果项目具有ParentId,则父项也将存在于列表中.

我需要对列表进行排序,以便所有具有父项的项目立即显示在其父项之后.然后所有项目将按名称排序.

如果我有以下内容:

 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

然后我希望它们排序如下:

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

目前,我能想到的最好的方法是首先按名称排序,然后按父母排序按如下方式排序:

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

我的起始计划如下:(在非功能代码中)

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

但是,parentGroup不是

 IEnumerable<Item> 

所以这不起作用.

我觉得有一种更简单,更简洁的方法来实现这一目标,但目前它正在逃避我 - 有人可以帮忙吗？

Answer 1

如果你只有两个级别，你可以这样做：

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

最初，项目按名称排序，确保稍后将它们分成组时它们保持排序。

然后创建一个查找表，允许通过 进行查找ParentId。然后使用 a 标识的父母null ParentId与他们的孩子一起使用SelectMany，并使用查找表来查找孩子。将父级插入到子级之前以获得所需的序列。

如果你想解决两层以上的一般情况，你需要使用递归。这是一种递归获取节点子树的方法：

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

代码与上面的更简单的情况几乎相同：

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

通过使用递归 lambda，您甚至可以“内联”完成这一切：

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