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

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

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

参照用 記事

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

ある種のツリー構造をJavaScriptで絵に描きたいわけです。キャンバスにグラフィカルに描こうか、とも考えましたが、レイアウトのための座標計算が大変そう。テーブルを使ってなんとかしよう、と。そういう話です。


このツリー構造には少し特殊な点があります。

  1. 親ノードに対して子ノードは1個または2個。
  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);
  }
};