ツリー構造を持ったレコードをクラス化する

なんだか、表現がややっこしいんだけど…ツリー構造を持ったレコード群をクラス化してみるよ。

ツリー構造を持ったレコード

ツリー構造をＲＤＢに持たせるときに良くやる方法で、１つのフィールドに親のレコードのキーを設定するってことをやるんだよね。イメージ的には以下の様な感じ…

root　┬　親１　┬　子１－１
　　　│　　　　│
　　　│　　　　├　子１－２
　　　│　　　　│
　　　│　　　　└　子１－３
　　　│
　　　└　親２　┬　子２－１　┬　孫２－１－１
　　　　　　　　│　　　　　　│
　　　　　　　　│　　　　　　└　孫２－１－２
　　　　　　　　└　子２－２

って構造の場合…

ＩＤ(key)	名前	親ＩＤ
0	root	-1
1	親１	0
2	子１－１	1
3	子１－２	1
4	子１－３	1
5	親２	0
6	子２－１	5
7	孫２－１－１	6
8	孫２－１－２	6
9	子２－２	5

ってレコードを作製するのが定石なんだよ。初めてこれを見ると「レコードに子供をもてばいいじゃん！」ってなりがちなんだけど…そうすると１つのノードで複数レコード（たとえば「親１」で３レコード）必要になっちゃうんだよね…だから、一般的にＲＤＢに階層構造を保存するときは、「親のＩＤを持つ」ってことをするんだよ。

で、このレコードを上の階層化されたクラス群に復元しようとすると…(?o?)ってなっちゃうんだ。上記の表の様にレコードの順番がきれいに並んでいれば問題ないけど…これが…

ＩＤ(key)	名前	親ＩＤ
0	子１－３	2
1	親２	3
2	親１	3
3	root	-1
4	子１－１	2
5	孫２－１－２	7
6	子１－２	2
7	子２－１	1
8	孫２－１－１	7
9	子２－２	1

ってなっちゃってたら、「親がなかったら親ができるまで待って、親ができたら保留にしてた分を全部登録して…」なんてことになっちゃう… これをＣ＃でさくっと綺麗に作ろうと思うんだ。

レコードのクラス

型付データセットを利用していることを前提にするよ。

OyakoTable
ID : int	Name : String	ParentID : int
0	子１－３	2
1	親２	3
2	親１	3
3	root	-1
4	子１－１	2
5	孫２－１－２	7
6	子１－２	2
7	子２－１	1
8	孫２－１－１	7
9	子２－２	1

このテーブルのレコードクラスをはOyakoTableRowってことにするよ。それぞれのフィールドの名前や型は上の表のとおりって仮定するよ。

ノードのクラス

ノードのクラスは以下のようにするよ。あえて、ＩＤは持たないようにしているんだ。これは、クラス化するとＩＤを持たなくてもインスタンスをそれぞれが持てばよくなるからなんだよ。

public class Node
{
    private List<Node> m_NodeList;
    public String Name { get; set; }

    public Node()
    {
        this.m_NodeList = new List<Node>();
    }

    public Node AddNode(Node p_Node)
    {
        this.m_NodeList.Add(p_Node);
        return p_Node;
    }
}

サンプルは上位階層から下位階層への参照しかできない構造にしているよ。もし、下位から上位への参照がほしい場合は親のインスタンスが持てるようにしてね。

階層構造の生成

ポイントはDictionaryクラスを使うことかな…（致命的なロジックミスがあったので修正しました - 2015/01/30）

public Node Create(OyakoTableRow[] p_OyakoTableRow)
{
    Dictionary<Int32, Node> l_NodeDic = new Dictionary<int, Node>();
    Node l_ResultNode = null;

    foreach(OyakoTableRow f_OyakoTableRow in p_OyakoTableRow)
    {
        Node l_Node = null;
        if (l_NodeDic.TryGetValue(f_OyakoTableRow.ID, out l_Node) == false)
        {
            l_Node = new Node();
            l_NodeDic.Add(f_OyakoTableRow.ID, l_Node);

        }
        l_Node.Name = f_OyakoTableRow.Name;
        

        if (f_OyakoTableRow.ParentID == -1)
        {
            l_ResultNode = l_Node;
        }
        else
        {
            Node l_ParentNode = null;
            if (l_NodeDic.TryGetValue(f_OyakoTableRow.ParentID, out l_ParentNode) == false)
            {
                l_ParentNode = new Node();
                l_NodeDic.Add(f_OyakoTableRow.ParentID, l_ParentNode);
            }
            l_ParentNode.AddNode(l_Node);
        }

    }

    return l_ResultNode;
}

ただ…ツリーが小さいときは良いんだけど…馬鹿でかくなったときにはこの方法は勧めません…（すべてのクラスがDictionaryクラスに入っているし、すべてのクラスを生成しちゃっているので…）