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

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

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

参照用 記事

JavaScriptと、ある種のツリー構造 (3)レンダリングの方針

一昨日、昨日の続きです。

ツリーのデータ構造とその操作がまだ未完成ですが、先に「ツリーのレンダリングをどうするか?」の方針を説明しておきます。

最初にここで、言葉使いと表記法に関する注意を:

JavaScriptの言語仕様にクラスはありませんが、常識的に「クラス/インスタンス/メソッド/フィールド」と呼んでも差し支えないものはあるので、これらの言葉を遠慮なしに使います。

クラスCに備わったメソッド doThat(n) を C#doThat(n) のように書くことにします。var x = new C(...); とインスタンスを作った後で、x.doThat(3) のように呼び出せるってことです。引数仕様を省略して C#doThat(...) と書くこともありますが、C#foo のように書いたらフィールドだとします(今回はフィールドは出てきませんが)。

ツリー構造を更新するCommands

昨日の記事で、ブランクという概念を導入したのですが:

ブランクは、ツリーの一部に組み込まれるのですが、レイアウト上のフィラー埋め草)なので、その存在があまり目立たないようにする必要もあります。

ブランクは、レンダリングにテーブルを利用する都合から導入した道具で、裏方の仕掛けです。

目立たない存在ということで、「JavaScriptと、ある種のツリー構造 (1)」と同じインターフェイスでツリーを触っている限り、ブランクは見えないようにします。

黒子であるブランクは、オフィシャルなインターフェイスからは感知できなない存在です。ところで、オフィシャルなインターフェイスってなんだったでしょう? 「JavaScriptと、ある種のツリー構造 (1)」の時点で含まれるメソッドを列挙します。ただし、ツリー構造を更新(update)するものに限定します。メイヤー先生の「CommandとQuery」という分類のCommandだけです。

  1. Tree#createRoot(value)
  2. Tree#removeRoot()
  3. Node#createOneChild(value)
  4. Node#createTwoChildren(value1, value2)
  5. Node#removeChildren()
  6. Node#remove()

全部で6つです。このなかで、Node#remove() は、親の Node#removeChildren() を呼んでいるだけです。Tree#createRoot(value) と Tree#removeRoot() は、Node#createOneChild(value) と Node#removeChildren() と大差ありません。結局、本質的な操作は:

  1. 単一子ノードの生成
  2. 双子の子ノード達の生成
  3. 子ノード(達)の削除

この3つです。

テーブルによるツリーの描画はリバーシ

さて、テーブルを使ってツリーを描く方針ですが; リバーシ(オセロ)ゲームを思い出すといいでしょう。ただし、盤面のマスにはすべて石が置いてあります。ノードが生成されるときは、石が白から黒にひっくり返り、ノードが削除されるときは、黒から白への変化です。

リバーシ テーブルによる描画 ツリー
盤面 テーブル ツリー全体
黒石 ノードが描画されたセル ツリーのノード
白石 空欄のセル ブランク
白→黒 セル内容の描画 ブランク→ノード
黒→白 セル内容の消去 ノード→ブランク

描画に使うテーブルとセルに対応するクラスを Table、Cell としましょう。「セル内容の描画」と「セル内容の消去」は、例えば、Cell#draw(value)、Cell#clear() といったメソッドで表現できます。

ツリー描画がリバーシゲームと違うのは、盤面の形も時々刻々と変更されることです。ノードの生成とノードの削除(消滅)により、ツリーは成長と縮退をします。ツリーの成長と縮退が、盤面であるテーブル全体の形状の変更を引き起こすことがあります。

以下の絵は、ツリーの成長に伴うセルとテーブルの変更を表したものです。

空欄だったセルに何かを描くことは、先の Cell#draw(value) で表現されます。テーブルの一番下に新しい行(row)を追加することは、Table#addBottomRow() としましょう。列(column)を2つに分割する操作は Table#splitColumn(baseCell) とします。Table#splitColumn(baseCell) は、Cell#splitColumn() のほうが使いやすかも知れません。

ツリーの成長に必要なメソッド群をまとめると:

  1. Cell#draw(value)
  2. Table#addBottomRow()
  3. Table#splictColumn(baseCell) (または、Cell#splictColumn())

一方、ツリーの縮退に必要なメソッド群は:

  1. Cell#clear()
  2. Table#removeBottomRow()
  3. Table#mergeColumns(baseCell) (または、Cell#mergeColumns())

概念的には、ツリー構造からTable、Cellのメソッドを呼んでレンダリングすることになるのですが、実際上は、TreeとTable、Node/BlankとCellを一緒にしてしまってもいいのかな、と思います。もちろん、データ構造とその視覚的表現は完全に分離したほうがかっこいいしメリットもあります。しかし、テーブルを使う前提でデータ構造側を変更している時点で分離性が壊れているので、拘ってもしょうがないだろう、と。

テーブルによるツリーのレンダリングの方針はこんなです。