c# - 带组的复杂 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

目前我能想到的最好办法是先按 Name 排序，然后按 ParentId 分组，如下所示:

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 进行查找。然后使用 SelectMany 将通过 null ParentId 标识的 parent 与他们的 child 连接起来，并使用查找表来查找 child 。将父项插入到子项之前以获得所需的序列。

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

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