使用LINQ对路径和深度字段进行分类层次结构[英] Sort hierarchy with path and depth fields using Linq

本文是小编为大家收集整理的关于使用LINQ对路径和深度字段进行分类层次结构的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。

问题描述

我已经实现了以下层次结构接口

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

这些项目是通过实体框架存储和检索的,因此我们可以假设所有关系字段均不为空和一致:

  • Path和Depth始终是最新的
  • 链接作品(例如:item.Parent?.Parent?.Parent)
  • 遍历Children字段也正在递归工作.
  • 使用Path和Depth是首选方法,因为它不需要在关系字段上计算.

考虑我有以下层次结构:

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

我的所有元素都在无序的平板阵列中,假设[d,c,b,e,a]. 我想使用linq表达式以以下方式对其进行整理:

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

给出了2个深度级别的示例,但是我希望该表达式遍历层次结构.

请注意,我的数据结构的级别和路径字段可用于实现此目的,因为每当添加,移动或删除项目时,树的所有路径都会重建,并且使用简单的拆分计算深度场('.')在路径上.

测试样本:

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

推荐答案

好吧,首先,您应该真正添加以下约束

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

因此,我们可以使用Parent和Children属性安全地导航层次结构.

第二,我不会从回答如何通过linq?(还有其他):

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

用口袋里的那个助手,所讨论的方法很简单:

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属性:

是相同的
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]));
    }
}

本文地址:https://www.itbaoku.cn/post/1557117.html

问题描述

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

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

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

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:

  • First level 0, according to its name field
  • All level 1 children of the previous, sorted by name
  • Second level 0 (still according to its name field)
  • All level 1 children of the previous...

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

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.

Test sample :

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>
{
    // ...
}

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

Sample usage:

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

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