21

次のようなテキスト ファイルがあります。

{ 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# アルゴリズムを探しています。必要に応じて、このデータをオブジェクト階層に変換する「階層化」機能。

何か案は？

編集私はすでにファイルを.NETオブジェクトに解析しました:

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

次に、実際にオブジェクトをオブジェクト グラフに配置する必要があります。

4

7 に答える 7

27

Jon と mquander に感謝します。皆さんは、これを適切かつ一般的な方法で解決するのに役立つ十分な情報を提供してくれました。これが私の解決策です。オブジェクトを階層形式に変換する単一の汎用拡張メソッドです。

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

私のテキストファイルの問題を含め、さまざまな問題に対処するのに十分な汎用性があります。気の利いた！

****更新****: 使用方法は次のとおりです。

// 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
    );
于 2009-06-04T17:01:35.633 に答える
9

うーん...それがどのように機能するのかよくわかりません。2と5の両方がparent=1、position = 0を持つにはどうすればよいですか？5には親2、3、または4が必要ですか？

さて、この新しいバージョンはすべてのノードを3回通過します。

  • すべてのノードをロードして、マップに配置します
  • 各ノードをその親に関連付けます
  • 各ノードの子を位置で並べ替える

十分にカプセル化されておらず、エラーチェックなどもうまく機能していませんが、機能します。

using System;
using System.Collections.Generic;
using System.IO;

public class Node
{
    private static readonly char[] Braces = "{}".ToCharArray();
    private static readonly char[] StringTrim = "\" ".ToCharArray();

    public Node Parent { get; set; }
    public int ParentId { get; private set; }
    public int Id { get; private set; }
    public string Title { get; private set; }
    public int Position { get; private set; }
    private readonly List<Node> children = new List<Node>();
    public List<Node> Children { get { return children; } }

    public static Node FromLine(string line)
    {
        Node node = new Node();
        line = line.Trim(Braces);
        string[] bits = line.Split(',');
        foreach (string bit in bits)
        {
            string[] keyValue = bit.Split('=');
            string key = keyValue[0].Trim();
            string value = keyValue[1].Trim();
            switch (key)
            {
                case "Id":
                    node.Id = int.Parse(value);
                    break;
                case "ParentId":
                    node.ParentId = int.Parse(value);
                    break;
                case "Position":
                    node.Position = int.Parse(value);
                    break;
                case "Title":
                    node.Title = value.Trim(StringTrim);
                    break;
                default:
                    throw new ArgumentException("Bad line: " + line);
            }
        }
        return node;
    }

    public void Dump()
    {
        int depth = 0;
        Node node = this;
        while (node.Parent != null)
        {
            depth++;
            node = node.Parent;
        }
        Console.WriteLine(new string(' ', depth * 2) + Title);
        foreach (Node child in Children)
        {
            child.Dump();
        }
    }
}

class Test
{       
    static void Main(string[] args)
    {
        var dictionary = new Dictionary<int, Node>();

        using (TextReader reader = File.OpenText("test.txt"))
        {
            string line;
            while ((line = reader.ReadLine()) != null)
            {
                Node node = Node.FromLine(line);
                dictionary[node.Id] = node;
            }
        }
        foreach (Node node in dictionary.Values)
        {
            if (node.ParentId != 0)
            {
                node.Parent = dictionary[node.ParentId];
                node.Parent.Children.Add(node);
            }
        }

        foreach (Node node in dictionary.Values)
        {
            node.Children.Sort((n1, n2) =>
                               n1.Position.CompareTo(n2.Position));
        }

        Node root = dictionary[1];
        root.Dump();
    }
}

サンプルテキストファイル：

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

出力：

root
  child 1
  child 2
  child 3
    grandchild 1
于 2009-06-03T23:44:05.960 に答える
2

ファイルを解析したら、LINQを使用してオブジェクトを階層にアセンブルする方法についてこのブログをフォローできます。

于 2009-06-03T23:45:13.243 に答える
2 
class Node {
    public int Id { get;set;  }
    public int ParentId { get;set;  }
    public int Position { get;set;  }
    public string Title { get;set;  }
    public IEnumerable<Node> Children { get; set; }

    public override string ToString() { return ToString(0); }
    public string ToString(int depth) {
        return "\n" + new string(' ', depth * 2) + Title + (
            Children.Count() == 0 ? "" :
            string.Join("", Children
                .Select(node => node.ToString(depth + 1))
                .ToArray()
            );
    }
}
class Program {
    static void Main(string[] args) {
        var data = new[] {
            new Node{ Id = 1, ParentId = 0, Position = 0, Title = "root" },
            new Node{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" },
            new Node{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" },
            new Node{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" },
            new Node{ Id = 5, ParentId = 3, Position = 0, Title = "grandchild 1" }
        };
        Func<Node, Node> transform = null;
        transform = node => new Node {
            Title = node.Title,
            Id = node.Id,
            ParentId = node.ParentId,
            Position = node.Position,
            Children = (
                from child in data
                where child.ParentId == node.Id
                orderby child.Position
                select transform(child))
        };
        Console.WriteLine(transform(data[0]));
    }
}

結果：

root
  child 1
  child 2
    grandchild 1
  child 3
于 2009-06-03T23:58:29.987 に答える
2

あなたの例では、オブジェクト #5 に間違った親 ID が間違って与えられていると思います。これでカバーできるはずです。警告: 「最上位」ノードの親 ID は常に 0 であると想定しています。最終的に最上位ノードから派生しないノードは無視します。重複した ID が提示されると、動作がおかしくなります。

public class FlatObj
{
    public int Id;
    public int ParentId;
    public int Position;
    public string Title;
}

public class Node
{
    public int ID;
    public string Title;
    public IList<Node> Children;

    public Node(FlatObject baseObject, IList<Node> children)
    {
        this.ID = baseObject.Id;
        this.Title = baseObject.Title;
        this.Children = children;
    }
}

public static Node CreateHierarchy(IEnumerable<FlatObject> objects)
{
    var families = objects.ToLookup(x => x.ParentId);
    var topmost = families[0].Single();

    Func<int, IList<Node>> Children = null;

    Children = (parentID) => families[parentID]
        .OrderBy(x => x.Position)
        .Select(x => new Node(x, Children(x.Id))).ToList();

    return new Node(topmost, Children(topmost.Id));
}

public static void Test()
{
    List<FlatObj> objects = new List<FlatObj> {
    new FlatObj { Id = 1, ParentId = 0, Position = 0, Title = "root" },
    new FlatObj { Id = 2, ParentId = 1, Position = 0, Title = "child 1" },
    new FlatObj { Id = 3, ParentId = 1, Position = 1, Title = "child 2" },
    new FlatObj { Id = 4, ParentId = 1, Position = 2, Title = "child 3" },
    new FlatObj { Id = 5, ParentId = 2, Position = 0, Title = "grandchild" }};

    var nodes = CreateHierarchy(objects);
}
于 2009-06-03T23:58:45.917 に答える
0

最後の行のParentIDが1であることを確認しますか？タイトルは孫と書いてありますが、正しく読んでいれば「ルート」の子になります。

于 2009-06-03T23:38:06.940 に答える
0

@baran が要求した例を次に示します。

var lHierarchicalMenuItems = lMenuItemsFromDB.Hierarchize(0, aItem => aItem.Id, aItem => aItem.ParentId, aItem => aItem.Position);
于 2012-10-04T03:04:39.153 に答える