Построение иерархического списка HTML на основе текста с точками

Question

Я ищу алгоритм, который преобразует структуру данных, подобную следующей, где каждый уровень отделен точкой:

child1
child1.child9
child4.child10.child11
child4.child10.child12

в допустимый элемент иерархического списка HTML, например:

<ul>
<li>child1
    <ul><li>child9</li></ul></li>
<li>child4
    <ul><li>child10
        <ul><li>child11</li><li>child12</li></ul></li></ul></li>
</ul>

Есть предложения?

Обновление

Проблема Из этого вида структуры (ниже) легко построить иерархический список

child
child.child1
child.child2
child.child2.child3

но моя структура

child.child2.child3
child7
child10.child14.child15
child10.child14.child16

поэтому у меня нет отдельной строки для создания родительского элемента :( Я должен построить дерево из одной строки, если нет родителя

Answer 1

using System;
using System.Xml;
using System.Collections.Generic;

class Sample{
    static void Main(string[] args){
        var doc = new XmlDocument();
        doc.LoadXml(@"
            <!DOCTYPE root [
              <!ELEMENT root (ul*) > 
              <!ELEMENT ul (li+) > 
              <!ELEMENT li ANY >
              <!ATTLIST root id ID #REQUIRED>
              <!ATTLIST li   id ID #REQUIRED>]>
            <root id='root'></root>");
        var relation = new List<String>(){
            "child.child2.child3",
            "child7",
            "child10.child14.child15",
            "child10.child14.child16"
        };
/* output(by hand made pretty):
  <ul>
    <li>child<ul><li>child2<ul><li>child3</li></ul></li></ul></li>
    <li>child7</li>
    <li>child10<ul><li>child14<ul><li>child15</li><li>child16</li></ul></li></ul></li>
  </ul>
*/
/*
        var relation = new List<String>(){
            "child1",
            "child1.child9",
            "child4.child10.child11",
            "child4.child10.child12"
        };
        var relation = new List<String>(){
            "child",
            "child.child1",
            "child.child2",
            "child.child2.child3"
        };
*/
        foreach(var path in relation){
            MakeTree(doc, path);
        }
        DeleteId(doc.DocumentElement);
        string result = doc.DocumentElement.InnerXml;
        Console.WriteLine(result);
//      doc.Save(Console.Out);
    }
    static void MakeTree(XmlDocument doc, string path){
        string parent = "root";
        foreach(var node in path.Split('.')){
            AppendChild(doc, parent, node);
            parent = node;
        }
    }
    static void DeleteId(XmlElement el){
        el.RemoveAttribute("id");
        if(el.HasChildNodes){
            foreach(XmlNode node in el.ChildNodes){
                if(node.NodeType == XmlNodeType.Element){
                    DeleteId((XmlElement)node);
                }
            }
        }
    }
    static void AppendChild(XmlDocument doc, string parent, string child){
        var childElement = doc.GetElementById(child);
        if(childElement == null){
            var li   = doc.CreateElement("li");
            var text = doc.CreateTextNode(child);
            li.SetAttribute("id", child);
            li.AppendChild(text);
            var parentElement = doc.GetElementById(parent);
            if(parent == "root"){
                if(parentElement.HasChildNodes){
                    parentElement.FirstChild.AppendChild(li);
                } else {
                    var ul   = doc.CreateElement("ul");
                    ul.AppendChild(li);
                    parentElement.AppendChild(ul);
                }
            } else {
                if(parentElement.LastChild.NodeType == XmlNodeType.Text){
                    var ul   = doc.CreateElement("ul");
                    ul.AppendChild(li);
                    parentElement.AppendChild(ul);
                } else {
                    parentElement.LastChild.AppendChild(li);
                }
            }
        }
    }
}

Answer 2

Вы можете превратить список в матрицу, а затем использовать группировку / рекурсию.Вот пример.Он не очень хорошо печатает HTML, но должен давать правильный результат.

    static void Main(string[] args)
    {
        var list = new List<String>()
        {
            "child.child2.child3",
            "child7",
            "child10.child14.child15",
            "child10.child14.child16"
        };

        var matrix = new List<List<String>>();
        foreach (var line in list)
        {
            matrix.Add(line.Split('.').ToList());
        }
        StringBuilder html = new StringBuilder();
        WriteLevel(html, matrix, 0);
        Console.WriteLine(html.ToString());
    }

    static void WriteLevel(StringBuilder html, List<List<String>> matrix, int level)
    {
        var nodes = from node in matrix
                    where node.Count > level
                    group node by node[level] into grouping
                    select grouping;
        if (nodes.Count() > 0)
        {
            html.Append("<ul>");
            foreach (var node in nodes)
            {
                html.Append("<li>");
                html.Append(node.Key);
                WriteLevel(html, node.ToList(), level + 1);
                html.Append("</li>");
            }
            html.Append("</ul>");
        }
    }