やってみる

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

📌 ？
トップ > C# > C#ツリー構造のインタフェースを考える

C#ツリー構造のインタフェースを考える

C#

　なぜかC#にはツリー構造のコレクションがないので。

ググった

　ググったら個人が作成しているものがあった。

　参考にはなったが、使いづらそう。もっと簡単にツリー構造を表現できるインタフェースをしたライブラリはないものか？　まずはインタフェースについて考えてみよう。

データ構造

  • Graph
    • Tree
      • 二分木
        • B木
      • 多分木
      • ...

　実行速度を考えるとB木とか色々あると思われる。でもその辺のアルゴリズムは一切考慮しない。まずはとにかくツリー構造を構築することだけを考える。

インタフェース案

  1. node.Add(node);
  2. メソッドチェーン＆階層(tree(new Node().Add(new Node())).Add(new Node()))
  3. インデクサ
  4. Dictionary<K,V>

テスト構造

　以下のようなツリー構造を簡単につくれるインタフェースを探りたい。

  • A
    • A1
      • A11
    • A2
  • B
    • B1

1. node.Add(node);

var tree = new Tree<string>();
tree.Add("A");
tree.Add("B");

　上記だとリストのような1次元まで。もし階層も表現するとなると以下のように一気に複雑化する。

var tree = new Tree<string>();
var A = new Node("A");
var A1 = new Node("A1");
var A11 = new Node("A11");
var A2 = new Node("A2");
var B = new Node("B");
var B = new Node("B1");
A1.Add(A11);
A.Add(A1);
A.Add(A2);
B.Add(B1);
tree.Add(A);
tree.Add(B);

　コードの字面からツリー構造をイメージできない。こんなインタフェースは嫌だ。

2. メソッドチェーン＆階層(tree(new Node().Add(new Node())).Add(new Node()))

var tree = new Tree<string>()
    .Add(new Node<string>("A")
        .Add(new Node<string>("A1")
            .Add(new Node<string>("A11")))
        .Add(new Node<string>("A2")))
    .Add(new Node<string>(new Node<string>("B")
        .Add(new Node<string>("B1"))));

　NodeのAddは必ず子を追加するものとする。兄弟として加えたくば親のAddで追加するようにする。

　()の入れ子で親子関係を表すことになる。これが非常に見づらい。特に葉ノードに行き着いたとき、末尾にいくつ)を書けばいいかわからなくなる。なんとかインデントで見やすくしようと工夫しているが、そもそもこのインデントと階層表現に直接の関係はない。あくまで()の入れ子によって階層表現される。

　端的に表現すると以下のような感じ。

  • Tree(A(A1(A11()), A2()), B(B1()))

　1よりはマシだが、()の入れ子が苦痛。必ずミスするだろう。

3. インデクサ

　ツリーをインデックスで表現するなら以下。

  • [0]
    • [0][1]
      • [0][1][0]
    • [0][2]
  • [1]
    • [1][0]

　インデクサーを実装すれば、この表現ができるかも？

var tree = new Tree<string>();
tree[0].Add("A");
tree[0][0].Add("A1");
tree[0][0][0].Add("A11");
tree[0][1].Add("A2");
tree[1].Add("B");
tree[1][0].Add("B1");

　階層をインデクサで表現できるようになったので、()の入れ子が不要になった。一気にスッキリした。

　インデクサの表記を配列にすると以下。

var tree = new Tree<string>();
tree[0].Add("A");
tree[0,0].Add("A1");
tree[0,0,0].Add("A11");
tree[0,1].Add("A2");
tree[1].Add("B");
tree[1,0].Add("B1");

　さらにAdd(値)をインデクサの末尾に投入すると以下。

var tree = new Tree<string>();
tree[0,"A"];
tree[0,"A1"];
tree[0,0,"A11"];
tree[0,"A2"];
tree["B"];
tree[1,"B1"];

　インデクサが数値で値が文字列型だとわかりにくい。そこで、インデクサの型もstringにすると以下。

var tree = new Tree<string>();
tree["A"];
tree["A","A1"];
tree["A","A","A11"];
tree["A","A2"];
tree["B"];
tree["B","B1"];

　ようするに、葉ノードにいきつくまでのフルパスを表記する形式。

A
A.A1
A.A1.A11
A.A2
B
B.B1

　なら、それをテキストで受け取って生成できるようにしてしまってもいいか。初回でツリー構造だけを作り、値はあとで挿入するようにできる。

string tree_str = @"A
A.A1
A.A1.A11
A.A2
B
B.B1";
var tree = new Tree<string>(tree_str); // ツリー構造の生成
tree["A"] = "A"; // 値はあとから代入する
tree["A","A1"] = "A1";
...

　インデクサをいちいち,で区切るとクォートが増えて面倒。そこで区切り文字を使って1要素のみにしてみる。文字列中に.か/を区切り文字とする。これはインデクサが文字列型でないと不可能。

var tree = new Tree<string>(tree_str, '.'); // ツリー構造の生成
tree["A.A1.A11"] = "A11";
tree["B.B1"] = "B1";

var tree = new Tree<string>(tree_str, '/'); // ツリー構造の生成
tree["A/A1/A11"] = "A11";
tree["B/B1"] = "B1";

　フルパス指定だけでなく、相対パス指定したい。つまりNodeからもインデクサによりパス指定したい。

var nodeA = tree["A"];
nodeA["A1/A11"] = "A11";

　ところで、もし子を指定していて親が未作成ならどうするか？　以下の2通りある。

  • 新規生成
  • 親が存在しないエラー
var tree = new Tree<string>('/'); // ツリー構造の生成
tree["A/A1/A11"] = "A11";
tree["B/B1"] = "B1";

　エラーにするなら以下。ミスを防げる。反面、いちいち親を1つずつ作成せねばならない面倒さがある。階層が深いと深刻。

tree["A/A1/A11"]: A11を生成しようとしましたが、親 A, A1 が存在しません。親を作ってから子を追加してください。
tree["B/B1"]: B1を生成しようとしましたが、親 B が存在しません。親を作ってから子を追加してください。

　自動で新規生成するなら以下。

var tree = new Tree<string>('/'); // ツリー構造の生成
tree["A/A1/A11"] = "A11"; // A,A1 はNodeインスタンスだけ存在する。Node.Value = null。
tree["B/B1"] = "B1";

// 親を子より後に宣言してもOK。親に値が不要なら以下は書かなくてOK
tree["A/A1"] = "A1"; // Node.Value = "A1"
tree["A"] = "A";

　ただし、もしタイプミスしたらそのまま生成されてしまう。

var tree = new Tree<string>('/'); // ツリー構造の生成
tree["A/A1/A11"] = "A11";
tree["a/A1"] = "A1"; // Aのつもりがタイポしてaにしてしまった！

　上記の場合、以下のようなツリー構造が作成されてしまう。

  • A
    • A1
      • A11
  • a
    • A1

　なので、新規生成かエラーにすべきか、選択の余地がある。

　また、インデクサに追加した名前は一意である。もし既存なのに新規作成のつもりで作成しても、なにも起こらない。もし代入すれば、新しい値がセットされる。

var tree = new Tree<string>('/'); // ツリー構造の生成
tree["A"] = "A";
...
tree["A"] = "AA"; // パス"A"に相当するNodeの値に"AA"がセットされる

　パスが既存であるか未存であるかのチェックがしたい。

var tree = new Tree<string>('/'); // ツリー構造の生成
tree["A"] = "A";
...
if (!Tree.IsExist("A")) tree["A"] = "AA";
else { throw new Exception("既存。新規作成のつもりで書いたので既存だったらエラーにする。"); }

　これならデフォルトではNodeを自動生成しつつ、もし既存・未存を知りたいならIsExistでチェックできる。

　最後に、TreeをテキストやTSVから取り込めるようにしてもいいかもしれない。

sample.tree

A
    A1
        A11
    A2
B
    B1

sample.tsv

A    Aの値
A.A1    A1の値
A.A1.A11    A11の値
B   Bの値
B.B1    B1の値

　値が多数あった場合どうするか。

sample.tsv

A    key1=val1, key2=val2
A.A1    key1=val1, key2=val2
A.A1.A11    key1=val1, key2=val2
B   key1=val1, key2=val2
B.B1    key1=val1, key2=val2

　さらに多数の場合、別ファイル化すべき。

sample.tsv

A    
A.A1    
A.A1.A11    
B   
B.B1

A.value

key1 value1
key2    val1, val2, val3
key3    {key1=val1, key2=val1, val2, val3}
key4    {key1=val1, key2=val1, val2, val3, key3={key1:val1, key2:val1,val2,val3}}

　値もツリー構造があったとき、その表現を{}や()でするのはどうかと思う。せっかくツリー構造があるのに。そこで1行あたりをKey\tValueの形式にしてしまう。以下のように。

A.value

key4.key1    val1
key4.key2   val1, val2, val3
key4.key3.key1  val1, val2, val3

　なんか、すごい面倒だな。別ファイル化する基準は「属性の多さ」や「文字の多さ」になってしまう。少なくともツリー構造がわからなくなるほど膨大な属性などは外出しすべき。

4. Dictionary<K,V>

　よく考えると3のインデクサはDictionaryと同じインタフェースだった。

　これにツリー構造専用のメソッドを足せば少し楽に作れるかも？

  • ノードの取得(["path/"])
  • ノードの追加/削除(Add/Remove)
  • ノードの移動(Move)
  • 値の取得/変更(["path"])

　親子、兄弟に関してはどういう名付けにするか？

次元方向 例1 例2
上下 親子
左右 兄弟
自分より上すべて 先祖
自分より下すべて 子孫
自分より左すべて 兄達
自分より右すべて 弟達
自分の最上端 起源
自分の最下端 末裔

　リストとしてはNext,Previous。これを親子と兄弟の2次元にしたとき、それぞれに別名をつけねば区別できない。

関係 指定方法
親 Parent
子 Child
兄
弟
長兄
末弟
元祖 Root
末裔 Leaf
兄弟 sibling
子孫 descendant
先祖 ancestor

　以下参考。

所感

　超面倒そう。なぜよく使うツリー構造がコレクションにないのか。たぶん実装が超大変だからだろう。それどころか、どういう場面でどのアルゴリズムの木を使うべきか判断することすら難しそう。

　それでも、1つくらいあってもいいんじゃない？

対象環境

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