ある種のツリー構造をJavaScriptで絵に描きたいわけです。キャンバスにグラフィカルに描こうか、とも考えましたが、レイアウトのための座標計算が大変そう。テーブルを使ってなんとかしよう、と。そういう話です。
このツリー構造には少し特殊な点があります。
- 親ノードに対して子ノードは1個または2個。
- 子ノードが2個のときは、これは双子で、必ず一緒に生成され一緒に削除される。
それで、ノードは次のようにしました。
function Node(value, tree) { value = value || ""; tree = tree || null; this.value = value; this.tree = tree; this.parent = null; this.child = null; this.child2 = null; }
子ノードが1個なら this.child に入ります。子ノードが2個なら this.child と this.child2 に入ります。this.tree は、このノードをホストしているツリー全体を意味します。ツリー全体は次の定義。
function Tree(title) { title = title || ""; this.title = title; this.root = null; }
ルートノード以外にタイトルがあるだけです。
ツリーとそのノードに対する操作は、ノードの生成(create)と削除(remove)です。他にプリティプリント(pprint)も付けました。下にソースを貼り付けてあるので、それを見てもらったほうが早いでしょう。
この時点では、データ構造もメソッドも普通のツリー構造です。テーブル(HTMLのtable要素)を使って描き出すために、ツリーのデータ構造も変更したのですが、それは次回以降に。
この下にソースコード↓ [追記]rootとchildを書き間違っていたので修正しました。[/追記]
/* -*- coding: utf-8 -*- */ /* tree01.js */ /** ツリー全体 */ function Tree(title) { title = title || ""; this.title = title; this.root = null; } Tree.prototype.createRoot = function(value) { value = value || ""; if (this.root) { throw new Error("already rooted."); } this.root = new Node(value, this); }; Tree.prototype.removeRoot = function() { if (this.root && !this.root.isLeaf()) { throw new Error("not a leaf."); } if (!this.root) { ; // do nothing return; } // 念のため、以前のルートをリセットしてから開放する this.root.reset(); this.root = null; }; Tree.prototype.pprint = function() { var s = "[" + this.title + "]\n"; if (this.root) { s += this.root.pprint(); } return s; } /** ノード */ function Node(value, tree) { value = value || ""; tree = tree || null; this.value = value; this.tree = tree; this.parent = null; this.child = null; this.child2 = null; } Node.prototype.reset = function() { this.tree = null this.parent = null; }; Node.prototype.isLeaf = function() { return (this.child === null); }; Node.prototype.createOneChild = function(value) { value = value || ""; if (this.child) { throw new Error("already has child."); } this.child = new Node(value, this.tree); this.child.parent = this; }; Node.prototype.createTwoChildren = function(value1, value2) { value1 = value1 || ""; value2 = value2 || ""; if (this.child) { throw new Error("already has child."); } // !this.child util.confirm( !this.child2 ); this.child = new Node(value1, this.tree); this.child.parent = this; this.child2 = new Node(value2, this.tree); this.child2.parent = this; }; Node.prototype.removeChildren = function() { if (this.child && !this.child.isLeaf() || this.child2 && !this.child2.isLeaf() ) { throw new Error("not a leaf."); } if (!this.child) { ; // do nothing util.confirm( !this.child2 ); return; } // this.child this.child.reset(); this.child = null; if (this.child2) { this.child2.reset(); this.child2 = null; } }; Node.prototype.remove = function() { if (!this.parent && !this.tree) { throw new Error("no parent no tree, can not remove."); } if (this.parent) { this.parent.removeChildren(); } else { this.tree.removeRoot(); } }; Node.prototype.pprint = function(indent) { indent = indent || 0; var s = ""; s += util.spaces(indent) + this.value + "\n"; if (this.child) { s += util.spaces(indent) + "{" + "\n"; s += this.child.pprint(indent + 1); } if (this.child2) { s += this.child2.pprint(indent + 1); } if (this.child) { s += util.spaces(indent) + "}" + "\n"; } return s; }; /* ======================================== */ var util = {}; util.spaces = function(n) { var s = ""; for (var i = 0; i < n; i++) { s += " "; } return s; }; util.confirm = function (cond, msg) { msg = msg || ""; if (!cond) { throw new Error("May be bug: " + msg); } };