Построить древовидное представление на основе общей части набора строк - PullRequest
Новая
       6

Построить древовидное представление на основе общей части набора строк

1 голос
/ 23 декабря 2010

Допустим, у меня есть следующие строки: 

"PW_ARAY$2V_BA_A$VOT"
"PW_ARAY$2V_BA_B$VOT"
"PW_ARAY$C0VP_15$HZ"
"PW_ARAY$C0VP_15$IB"
"PW_ARAY$C0VP_15$IN"
"PW_ARAY$C0VP_15$IR"
"PW_ARAY$C0VP_15$IW"
"PW_ARAY$C0VP_15$MVA"
"PW_ARAY$C0VP_15$MW"
"PW_ARAY$C0VP_15$MX"
etc...

Я хотел бы сделать что-то очень общее / интеллектуальное, которое может переставить мои строки в форме дерева на основе поставляемых разделителей (например: '_ 'и' $ '): 

PW
    - ARAY
        * 2V
            + BA
                - A
                    * VOT
                - B
                    * VOT
        * C0VP
            + 15
                - HZ
                - IB
                - IN
                - IR
                - IW
                - MVA
                - MW
                - MX

Следующий список также должен дать тот же результат 

"PW_ARAY$2V_BA_A$VOT"
"PW_ARAY$2V_BA_B$VOT"
"PW_ARAY$C0VP_15$HZ"
"PW_ARAY$C0VP_15$IB"
"PW_ARAY$C0VP_15$IN"
"PW_ARAY$C0VP_15$IR"
"C0VP_15$IW"
"C0VP_15$MVA"
"C0VP_15$MW"
"C0VP_15$MX"

Любая идея будет оценена.

Спасибо

Nic

1 Ответ

1 голос
/ 23 декабря 2010

Вот (рабочий) пример кода: 

private class Node
{
    public string Value { get; private set; }
    public Node Parent { get; private set; }
    public List<Node> Children { get; private set; }
    public Node(string c, Node parent)
    {
        this.Value = c;
        this.Parent = parent;
        this.Children = new List<Node>();
    }
    public override string ToString()
    {
        return "Value: " + this.Value;
    }
}

private static Node BuildTree(IEnumerable<string> tokens, char[] sep)
{
    var root = new Node(null, null);
    foreach (var token in tokens)
    {

#if OLDVERSION
        var current = root;
        var splits = token.Split(sep);
#else
        var splits = token.Split(sep);
        var current = FindFirstNodeWithValue(root, splits.First());
        if (current == null)
            current = root;
        else
            current = current.Parent;
#endif

        for (int i = 0; i < splits.Length; i++)
        {
            string split = splits[i];
            var node = current.Children.FirstOrDefault(x => x.Value == split);
            if (node == null)
            {
                node = new Node(split, current);
                current.Children.Add(node);
            }
            current = node;
        }
    }
    return root;
}

private static Node FindFirstNodeWithValue(Node root, string val)
{
    if (root.Value == val)
        return root;
    foreach (var child in root.Children)
    {
        var res = FindFirstNodeWithValue(child, val);
        if (res != null)
            return res;
    }
    return null;
}

Использование: 

static void Main(string[] args)
{
    string[] tokens = new[]
        {
            "PW_ARAY$2V_BA_A$VOT",
            "PW_ARAY$2V_BA_B$VOT",
            "PW_ARAY$C0VP_15$HZ",
            "PW_ARAY$C0VP_15$IB",
            "PW_ARAY$C0VP_15$IN",
            "PW_ARAY$C0VP_15$IR",
            "PW_ARAY$C0VP_15$IW",
            "PW_ARAY$C0VP_15$MVA",
            "PW_ARAY$C0VP_15$MW",
            "PW_ARAY$C0VP_15$MX",
        };

    var root = BuildTree(tokens, new[] { '_', '$' });
    // root has Value = null, but starting from the first child
    // of root you have exactly the same tree you draw in your question
}
...