昨日の記事「JavaScriptと、ある種のツリー構造 (1)」の続きです。HTMLのテーブル(table要素)を使ってツリーの絵を描く話です。
基本的なアイディアは単純で、次の図を眺めればすぐ分かるでしょう。
このような方法で描くことを想定して、ツリーのデータ構造を変えていこう、ということです。
内容:
- 実際にHTMLで試してみる
- ノードを描いてないセルをどう扱うか
- ノードとブランクの共通のインターフェイス
- ブランク特有のメソッド
実際にHTMLで試してみる
上の手描きの絵に対応するHTMLマークアップは次のようになります。
<table style="text-align:center"> <tbody> <tr> <td colspan=4>●</td> </tr> <tr><td>●</td> <td colspan=3>●</td> </tr> <tr><td>×</td><td colspan=2>●</td> <td>●</td></tr> <tr><td>×</td><td>●</td><td>●</td><td>×</td></tr> <tbody> </table>
このHTML断片を、日記エントリー内にそのまま埋め込んでみます。
● | |||
● | ● | ||
× | ● | ● | |
× | ● | ● | × |
ノードを描いてないセルをどう扱うか
先の図で、ツリーのノードが入ってない空欄のセルがあります。わかりやすいようにバッテンが記入されています。空欄セルをどうしよか? と考えて; ブックキーピングの目的からは空欄もデータとして持っておいたほうが良さそうだ、と結論しました。空欄に対応するダミーのデータをブランクと呼ぶことにします。ブランクは、ツリーの一部に組み込まれるのですが、レイアウト上のフィラー(埋め草)なので、その存在があまり目立たないようにする必要もあります。 目立たない存在ということで、「JavaScriptと、ある種のツリー構造 (1)」と同じインターフェイスでツリーを触っている限り、ブランクは見えないようにします。ブランクの記述と操作は、新しく追加したフィールドやメソッドで行うことにします。 通常のノードとブランクは異なりますが似ています。こういう「異なるが似てる、似てるが異なる」ものを表現するとき、いくつかの方法があります。- 同じクラスの(JavaScriptでは同じコンストラクターを持つ)インスタンスだが、フラグで区別する。
- スーパークラスとサブクラスのインスタンスとする。
- 同じスーパークラスから継承された2つの異なるサブクラスのインスタンスとする。
フラグを使うと、フラグのチェックが煩雑になりがちです。通常ノードとブランクでは、どっちがスーパークラスとも言えないので、スーパークラス/サブクラスの関係にするのも無理があります。三番目の「同じスーパークラスから継承された2つの異なるサブクラス」がふさわしいでしょう。
「プログラマのためのJavaScript (号外):こんな継承はどう?」で紹介したような方法を使うと、JavaScriptでも継承はできるのですが、今回の場合、実装の再利用の恩恵がたいしてないので、気持ちの上で「共通のスーパークラス」を想定するだけにします。ノードとブランクのインターフェイスを「共通のスーパークラス」(脳内)に揃えるのは手でします。
ノードとブランクの共通のインターフェイス
ノードとブランクが共通に持つインターフェイスとは次のようなものです。
- フィールド tree -- ノード/ブランクをホストしているツリー全体
- フィールド parent -- 親のノード/ブランク
- フィールド child -- 子のノード/ブランク
- メソッド createBlankChild -- ブランクである子を生成する。
- メソッド removeBlankChild -- ブランクである子を削除する。
- メソッド remove -- 自分自身を削除する。
- メソッド pprint -- 自分から下のサブツリーをプリティプリントする。
- メソッド dispose -- ツリーから削除される支度をする。
最後のdisposeは、昨日の記事ではresetという名前だったのをリネームしました。ノード/ブランクをツリーから切り離すときにはdisposeを呼ぶようにはしてますが、今回は特に必要ないですね。
ブランク特有のメソッド
一般的には、ツリーのリーフノードの下にはブランクが数珠状にぶら下がっていることになります。そのような状態でノードの生成とかノードの削除とかするときは、子ノードの位置にあるブランクを通常ノードに“変身”させてしまったほうが良さそうです。2個の子ノードが必要なときは、ブランクの数珠(チェーン)を2本に増やしてから、「ブランク→ノード」の“変身”を2回実行します。
以下の図は、「ブランク→ノード」という“変身”と、ブランクのチェーンを2本に増やす操作を表しています。
これらの操作は、内部的に使用する予定なので、名前の先頭にアンダースコアを付けて、_mutateToNode と _dupChain とします。_mutateToNode と _dupChain を含めた、ブランク(Blank)のソースを以下に載せます。ノード(Node)の定義が少し変わっているので、先に示すと:
/** ノード */ function Node(value, tree) { value = value || ""; tree = tree || null; this.value = value; this.tree = tree; this.parent = null; this._child = null; this._child2 = null; }
child, child2にアンダースコアが付いた理由は後日説明します。それと、プリティプリント pprint の引数仕様が変わって、第1引数にtrueを入れるとブランクも含めて表示します。
以下に今日の時点のソースコード、Blankクラスだけです。テストもしてないし、「今日の」なので、明日には変わっているかも。
/** ブランク */ function Blank(tree) { tree = tree || null; this.tree = tree; this.parent = null; this.child = null; } Blank.prototype = { /** 子を持たない末端かどうかを返す */ isBottom : function() { return (this.child === null); }, /** ブランクな子ノードを作る */ createBlankChild : function() { if (this.child) { throw new Error("already has child."); } this.child = new Blank(this.tree); this.child.parent = this; }, /** ブランクな子ノードを削除する */ removeBlankChild : function() { if (!this.child) { throw new Error("no child."); } if (!(this.child instanceof Blank)) { throw new Error("no a blnak."); } if (!this.child.isBottom()) { throw new Error("no a bottom."); } this.child.dispose(); this.child = null; }, /** 自分自身を削除する */ remove : function() { if (!this.parent) { throw new Error("no parent, can not remove"); } // 親に依頼する this.parent.removeBlankChild() }, /** プリティプリントする */ pprint : function(all, indent) { all = all || false; indent = indent || 0; if (!all) { return ""; } var s = ""; s += util.spaces(indent) + "(* BLANK *)" + "\n"; if (this.child) { s += util.spaces(indent) + "{" + "\n"; s += this.child.pprint(all, indent + 1); s += util.spaces(indent) + "}" + "\n"; } return s; }, /** ノードに変身する */ _mutateToNode : function(v) { if (!this.parent || !(this.parent instanceof Node)) { throw new Error("bad parent, can not mutate."); } var node = new Node(v, this.tree); node.parent = this.parent; node._child = this.child; // 親の「自分への参照」をすり替える var c1 = this.parent._child; var c2 = this.parent._child2; if (this === c1) { this.parent._child = node; } else if (this === c2) { this.parent._child2 = node; } else { throw new Error("Something wrong."); } // 子の「自分への参照」をすり替える if (this.child) { this.child.parent = node; } // ツリーからの離脱 this.dispose(); }, /** 自分自身から下のチェーンの、新しいコピーを作って返す */ _dupChain : function() { if (!this.parent || !(this.parent instanceof Node)) { throw new Error("bad parent, can not dup chain."); } util.confirm( this.parent._child2 === null); var dup = firstDup = new Blank(this.tree); // 生成したブランクに親を設定 firstDup.parent = this.parent // 親の「第二子への参照」を追加する this.parent._child2 = firstDup; var orig = this while (orig) { if (orig.child) { dup.createBlankChild(); dup = dup.child; } orig = orig.child; } return firstDup; }, dispose : function() { // 特に何もしない } };