このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

JavaScriptと、ある種のツリー構造 (2)

昨日の記事「JavaScriptと、ある種のツリー構造 (1)」の続きです。HTMLのテーブル(table要素)を使ってツリーの絵を描く話です。

基本的なアイディアは単純で、次の図を眺めればすぐ分かるでしょう。

このような方法で描くことを想定して、ツリーのデータ構造を変えていこう、ということです。

内容:

  1. 実際にHTMLで試してみる
  2. ノードを描いてないセルをどう扱うか
  3. ノードとブランクの共通のインターフェイス
  4. ブランク特有のメソッド

実際に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)」と同じインターフェイスでツリーを触っている限り、ブランクは見えないようにします。ブランクの記述と操作は、新しく追加したフィールドやメソッドで行うことにします。 通常のノードとブランクは異なりますが似ています。こういう「異なるが似てる、似てるが異なる」ものを表現するとき、いくつかの方法があります。

  1. 同じクラスの(JavaScriptでは同じコンストラクターを持つ)インスタンスだが、フラグで区別する。
  2. スーパークラスとサブクラスのインスタンスとする。
  3. 同じスーパークラスから継承された2つの異なるサブクラスのインスタンスとする。

フラグを使うと、フラグのチェックが煩雑になりがちです。通常ノードとブランクでは、どっちがスーパークラスとも言えないので、スーパークラス/サブクラスの関係にするのも無理があります。三番目の「同じスーパークラスから継承された2つの異なるサブクラス」がふさわしいでしょう。

プログラマのためのJavaScript (号外):こんな継承はどう?」で紹介したような方法を使うと、JavaScriptでも継承はできるのですが、今回の場合、実装の再利用の恩恵がたいしてないので、気持ちの上で「共通のスーパークラス」を想定するだけにします。ノードとブランクのインターフェイスを「共通のスーパークラス」(脳内)に揃えるのは手でします。

ノードとブランクの共通のインターフェイス

ノードとブランクが共通に持つインターフェイスとは次のようなものです。

  1. フィールド tree -- ノード/ブランクをホストしているツリー全体
  2. フィールド parent -- 親のノード/ブランク
  3. フィールド child -- 子のノード/ブランク
  1. メソッド createBlankChild -- ブランクである子を生成する。
  2. メソッド removeBlankChild -- ブランクである子を削除する。
  3. メソッド remove -- 自分自身を削除する。
  4. メソッド pprint -- 自分から下のサブツリーをプリティプリントする。
  5. メソッド 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() {
    // 特に何もしない
  }
};