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

### 问题描述

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

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

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

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

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

### 问题描述

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