用于生成层次结构的C＃算法 [英] C# algorithm for generating hierarchy

问题描述

我有一个文本文件，如下所示：

I've got a text file that looks like this:

{ Id = 1, ParentId = 0, Position = 0, Title = "root" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }

我正在寻找一种通用的C＃算法，该算法将从此算法创建对象层次结构。

I'm looking for a generic C# algorithm that will create an object hierarchy from this. A "Hierarchize" function, if you will, that turns this data into an object hierarchy.

有什么想法吗？

edit 我已经将文件解析为.NET对象：

edit I've already parsed the file into .NET objects:

class Node
{
    public int Id { get; }
    public int ParentId { get; }
    public int Position { get; }
    public string Title { get; }
}

现在我需要将对象实际排列到对象图中。

Now I need to actually arrange the objects into an object graph.

推荐答案

非常感谢Jon和mquander-你们给了我足够的信息，可以帮助我以适当的通用方式解决此问题。这是我的解决方案，它是一种将对象转换为层次结构形式的通用扩展方法：

Many thanks to Jon and to mquander - you guys gave me enough information to help me solve this in a proper, generic way. Here's my solution, a single generic extension method that converts objects into hierarchy form:

public static IEnumerable<Node<T>> Hierarchize<T, TKey, TOrderKey>(
    this IEnumerable<T> elements, 
    TKey topMostKey, 
    Func<T, TKey> keySelector, 
    Func<T, TKey> parentKeySelector, 
    Func<T, TOrderKey> orderingKeySelector)
{
    var families = elements.ToLookup(parentKeySelector);
    var childrenFetcher = default(Func<TKey, IEnumerable<Node<T>>>);
    childrenFetcher = parentId => families[parentId]
        .OrderBy(orderingKeySelector)
        .Select(x => new Node<T>(x, childrenFetcher(keySelector(x))));

    return childrenFetcher(topMostKey);
}

利用此小节点类：

public class Node<T>
{
    public T Value { get; private set; }
    public IList<Node<T>> Children { get; private set; }

    public Node(T value, IEnumerable<Node<T>> children)
    {
        this.Value = value;
        this.Children = new List<Node<T>>(children);
    }
}

它足够通用，可以解决各种问题，包括我的文本文件问题。

It's generic enough to work for a variety of problems, including my text file issue. Nifty!

**** UPDATE ****：使用方法如下：

****UPDATE****: Here's how you'd use it:

// Given some example data:
var items = new[] 
{
   new Foo() 
   {
      Id = 1,
      ParentId = -1, // Indicates no parent
      Position = 0
   },
   new Foo() 
   {
      Id = 2,
      ParentId = 1,
      Position = 0
   },
   new Foo() 
   {
      Id = 3,
      ParentId = 1,
      Position = 1
   }
};

// Turn it into a hierarchy! 
// We'll get back a list of Node<T> containing the root nodes.
// Each node will have a list of child nodes.
var hierarchy = items.Hierarchize(
    -1, // The "root level" key. We're using -1 to indicate root level.
    f => f.Id, // The ID property on your object
    f => f.ParentId, // The property on your object that points to its parent
    f => f.Position, // The property on your object that specifies the order within its parent
    );

这篇关于用于生成层次结构的C＃算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！