C# algorithme pour générer de la hiérarchie

Hmm... je n'arrive pas à voir comment cela fonctionne. Comment puis 2 et 5, les deux ont des parent=1, position=0? Doit 5 parent 2, 3 ou 4?

D'accord, cette nouvelle version va à travers tous les nœuds à trois reprises:

• Charge de tous les nœuds et les mettre dans le une carte
• Associer à chaque nœud avec son parent
• De tri de chaque nœud de l'enfant en position

Ce n'est pas bien encapsulé, joliment erreur de vérification, etc, mais il fonctionne.

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

Exemple de fichier texte:

{ 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" }

De sortie:

root
child 1
child 2
child 3
grandchild 1

Je suppose que votre exemple incorrectement donne le mauvais parent de l'ID de l'objet #5. Cela devrait couvrir. Mises en garde: Suppose que le "premier" nœud a toujours un parent ID de zéro. Ignore toutes les nœuds qui ne sont pas finalement les descendants du nœud supérieur. Le comportement sera bizarre s'ils sont présentés avec des Id en double.

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

Êtes-vous certain que la dernière ligne du ParentID est 1? Le dit le titre d'un petit-enfant, mais il serait un enfant de la "racine" si je suis en train de lire les choses correctement.