使用Linq对具有路径和深度字段的层次结构进行排序 [英] Sort hierarchy with path and depth fields using Linq

问题描述

我已经实现了以下层次结构界面

I have implemented the following hierarchy interface

interface ITree<T>
{
    // Incremential unique key
    int Id { get; set; }
    string Name { get; set; }
    // Hierarchy classical pattern
    T Parent { get; set; }
    ICollection<T> Children { get; set; }
    // Computed values
    int Depth { get; }
    // Hierarchy path with dotted notation (e.g.: 12.45.554.23,
    // where each path segment is an Id)
    string Path { get; set; }
}

class TreeItem : ITree<TreeItem>
{
    public int Id { get; set; }
    public string Name { get; set; }
    public TreeItem Parent { get; set; }
    public ICollection<TreeItem> Children { get; set; }
    public string Path { get; set; }    
    public int Depth { get { return Path.Split('.').Length - 1; } }
}

这些项目是通过Entity Framework存储和检索的，因此我们可以假定所有关系字段都不为null且一致:

These items are stored and retrieved through Entity Framework, so we can assume that all the relation fields are not null and consistent :

• Path和Depth始终是最新的
• 连锁作品(例如:item.Parent?.Parent?.Parent)
• 遍历Children字段也可以递归进行.
• 使用Path和Depth是首选方法，因为它不需要在关系字段上进行计算.

• Path and Depth are always up to date
• Chaining works (e.g. : item.Parent?.Parent?.Parent)
• Traversing the Children field is also working recursively.
• Using Path and Depth is the preferred approach, since it does not need to compute on relation fields.

考虑到我具有以下层次结构:

Consider I have the following hierarchy :

- A (Depth = 0)
-- B (Depth = 1)
-- C (Depth = 1)
- D  (Depth = 0)
-- E (Depth = 1)

我所有的元素都是无序的平面数组，比方说[D，C，B，E，A]. 我想使用Linq表达式通过以下方式对其进行排序:

All my elements are in a unordered flat array, let's say [D,C,B,E,A]. I want to use a Linq expression to sort them out the following way:

• 第一个级别0，根据其名称字段
• 以前的所有1级子级，按名称排序
• 第二级0(仍然根据其名称字段)
• 上一个...的所有1级子级...

该示例给出了2个深度级别，但是我希望该表达式遍历层次结构，而不管其深度如何.

The example is given for 2 levels of depth, but I would like the expression to traverse a hierarchy whatever its depth.

请注意，我的数据结构的level和path字段可用于实现此目的，因为每当添加，移动或删除项目时都会重建树的所有路径，并且Depth字段是通过简单的Split计算的('.').

Note that the level and path fields of my data structure can be used to achieve this, since all the paths of the tree are rebuilt whenever an item is added, moved or removed, and the Depth field is computed with a simple Split('.') on the path.

测试样本:

var A = new TreeItem { Id = 1, Name = "A", Path = "1" };
var B = new TreeItem { Id = 2, Name = "B", Path = "1.2", Parent = A };
var C = new TreeItem { Id = 3, Name = "C", Path = "1.3", Parent = A };
var D = new TreeItem { Id = 4, Name = "D", Path = "4" };
var E = new TreeItem { Id = 5, Name = "E", Path = "4.5", Parent = D };

// populate children for the example.
// My actual code is automatic thanks to EF Inverse Relationship.
A.Children = new List<TreeItem> { B, C };
D.Children = new List<TreeItem> { E };

var listToSortHierarchically = new List<TreeItem> { D, C, B, E, A };
// I want the result of the hierarchical sort to be A B C D E

推荐答案

好的，首先您应该真正添加以下约束条件

Ok, first you should really add the following constraint

interface ITree<T>
    where T : class, ITree<T>
{
    // ...
}

，因此我们可以使用Parent和Children属性安全地导航层次结构，而无需强制转换.

so we can safely navigate the hierarchy using Parent and Children properties w/o casting.

第二，而不是重新发明轮子，我将重用通用树，以便从我对

Second, instead of reinventing the wheel, I'll reuse the general tree in order traversal helper method from my answer to How to flatten tree via LINQ? (and couple others):

public static partial class TreeUtils
{
    public static IEnumerable<T> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

有了这个助手，问题的方法就很简单:

With that helper in the pocket, the method in question is simple as that:

partial class TreeUtils
{
    public static IEnumerable<T> Ordered<T>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<T>> order = null)
        where T : class, ITree<T>
    {
        if (order == null) order = items => items.OrderBy(item => item.Name);
        return order(source.Where(item => item.Parent == null))
            .Expand(item => item.Children != null && item.Children.Any() ? order(item.Children) : null);
    }
}

样品用量:

List<TreeItem> flatList = ...;
var orderedList = flatList.Ordered().ToList();

更新:此处仅使用Path和Id属性是相同的:

UPDATE: Here is the same by using only Path and Id properties:

public static partial class TreeUtils
{
    public static IEnumerable<T> Ordered<T>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<T>> order = null)
        where T : class, ITree<T>
    {
        if (order == null) order = items => items != null && items.Any() ?  items.OrderBy(item => item.Name) : null;
        var chldrenByParentId = source
            .Select(item => new { item, path = item.Path.Split('.') })
            .ToLookup(e => e.path.Length >= 2 ? int.Parse(e.path[e.path.Length - 2]) : (int?)null, e => e.item);
        return (order(chldrenByParentId[null]) ?? Enumerable.Empty<T>())
            .Expand(item => order(chldrenByParentId[item.Id]));
    }
}

这篇关于使用Linq对具有路径和深度字段的层次结构进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！