　超適当。

成果物

github

テスト用ツリー

A
- A1
  - A11
- A2
B
- B1

　上記のようなツリー構造を作ってみた。

コード

run.sh

csc -nologo -nullable:enable -langversion:preview *.cs
chmod 755 ./Program.exe
./Program.exe

　インデクサでツリー構造のパスを指定している。

Program.cs

class Program
{
    static void Main(string[] args)
    {
        var tree = new Tree<string>();
        tree["A"] = "A";
        tree["A/A1"] = "A1";
        tree["A/A1/A11"] = "A11";
        tree["A/A2"] = "A2";
        tree["B"] = "B";
        tree["B/B1"] = "B1";
        Console.WriteLine($"tree.Root.Children.Count: {tree.Root.Children.Count}");
        ShowTree(tree);
    }
    static void ShowTree(Tree<string> tree)
    {
        foreach (var node in tree.Root.Children) { ShowNode(node); }
    }
    static void ShowNode(Node<string> node, int index=0)
    {
        if (null != node) { Console.WriteLine($"{(new string('*', index)).Replace("*", "    ")}{node.Value}"); }
        if (null != node?.Children) {
            index++;
            foreach (var n in node.Children) { ShowNode(n, index); }
        }
    }
}

CodeTree.cs

public class Tree<V>
{
    public static readonly char DELIMITER = '/';
    public char Delimiter { get; protected set; }
    protected IList<Node<V>> children { get; set; }
    public IReadOnlyList<Node<V>> Children { get; }
    public Node<V> Root { get; protected set; }
    public V this[string path] {
        set {
            // 未存なら新規生成
            // 既存なら指定値を代入する。インデクサで指定した位置にあるNodeに。
            FindAndNewNode(path).Value = value;
        }
        get {
            // 未存なら新規生成
            // 既存なら値を返す。インデクサで指定した位置にあるNodeの。
            return FindAndNewNode(path).Value;
        }
    }
    public Tree(char delimiter='/')
    {
        Delimiter = delimiter;
        children = new List<Node<V>>();
        Children = new ReadOnlyCollection<Node<V>>(children);
        Root = new Node<V>("Root");
    }
    private Node<V> FindAndNewNode(string path)
    {
        var first = path.Split(DELIMITER)[0];
        foreach (var child in Root.Children) {
            if (first == child.Key) { return child.FindAndNewNode(path, 0, child); }
        }
        return Root.FindAndNewNode(path, 0, Root);
    }
}

CodeNode.cs

public class Node<V>
{
    public string Key { get; protected set; }
    public virtual V Value { get; set; }
    public Node<V> Parent { get; set; }
    protected IList<Node<V>> children { get; set; }
    public IReadOnlyList<Node<V>> Children { get; }
    public Node<V> Add(string key, V value=default) {
        foreach (var child in Children) {
            if (child.Key == key) { return this; } // 既存なら何もしない
        }
        children.Add(new Node<V>(key, value, this)); // 未存なら新規生成する
        return this;
    }

    public V this[string path] {
        set {
            if (String.IsNullOrEmpty(path)) { throw new Exception("インデクサには1字以上の文字列を指定してください。"); } 
            // 未存なら新規生成または例外またはnull
            // 既存なら指定値を代入する。インデクサで指定した位置にあるNodeに。
            FindAndNewNode(path, 0, this).Value = value;
        }
        get {
            if (String.IsNullOrEmpty(path)) { throw new Exception("インデクサには1字以上の文字列を指定してください。"); } 
            // 未存なら新規生成または例外またはnull
            // 既存なら値を返す。インデクサで指定した位置にあるNodeの。
            return FindAndNewNode(path, 0, this).Value;
        }
    }
// https://www.infoq.com/jp/articles/csharp-nullable-reference-case-study/
#nullable disable
    public Node(string key, V value=default, Node<V> parent=default)
#nullable enable
    {
        Parent = parent; Key = key; Value = value;
        children = new List<Node<V>>();
        Children = new ReadOnlyCollection<Node<V>>(children);
    }
    public Node<V>? FindNode(in string path, int depth, in Node<V> node)
    {
        string[] keys = path.Split(Tree<V>.DELIMITER);
        if (depth == keys.Length -1) {
            if (node.Key == keys[depth]) { return node; }
//                else { throw new NotExist(); }
            else { return null; }
        }
        else {
            foreach (var child in node.Children) {
                if (child.Key == keys[depth]) {
                    FindNode(path, ++depth, child);
                }
            }
        }
//            throw new NotExist();
        return null;
    }
#nullable disable
    public Node<V> FindAndNewNode(in string path, int depth, in Node<V> node)
    {
        string[] keys = path.Split(Tree<V>.DELIMITER);
        Console.WriteLine($"{path} {depth} {node?.Key} {keys[depth]}");
        if (depth == keys.Length -1) {
            if (node.Key == keys[depth]) { return node; }
            else {
                // 未存なら新規生成
                var youngest_brother = new Node<V>(keys[depth], default(V), (null == node.Parent) ? node : node.Parent);
                if (null == node.Parent) { // nodeがルートなら
                    node.children.Add(youngest_brother);
                } else {
                    node.Parent.children.Add(youngest_brother);
                }
                return youngest_brother;
            }
        }
        else {
            depth++;
            Node<V> target = null;
            if (node.Key == keys[depth]) { target = FindNode(path, depth, node); }
            else {
                foreach (var child in node.Children) {
                    if (child.Key == keys[depth]) {
                        target = FindAndNewNode(path, depth, child);
                        break;
                    }
                }
                // 未存なら新規生成
                if (null == target) {
                    var child = new Node<V>(keys[depth]);
                    node.children.Add(child);
                    target = FindAndNewNode(path, depth, child);
                }
            }
            return target;
        }
    }
#nullable enable
}

出力結果

　デバッグ出力を取り除いた抜粋。それっぽくできている。

既存バグ

Program.cs

class Program
{
    static void Main(string[] args)
    {
        var tree = new Tree<string>();
//        tree["A"] = "A";
//        tree["A/A1"] = "A1";
        tree["A/A1/A11"] = "A11";
        tree["A/A2"] = "A2";
//        tree["B"] = "B";
        tree["B/B1"] = "B1";
        Console.WriteLine($"tree.Root.Children.Count: {tree.Root.Children.Count}");
        ShowTree(tree);
    }

　親を作らず、先に子をつくるとバグる。

所感

　コード汚すぎ。もう何書いているかわかんない。ハードルが高い。一旦C#ツアーに戻って基礎学習しよう。

対象環境

2019-11-12
Raspbierry pi 3 Model B+
Raspbian stretch 9.0 2018-11-13 ※
bash 4.4.12(1)-release ※
SQLite 3.29.0 ※
C# dotnet 3.0.100 ※

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1218 SMP Tue May 14 00:48:17 BST 2019 armv7l GNU/Linux

やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

ツリー構造の試作

成果物

テスト用ツリー

コード

出力結果

既存バグ

所感

対象環境