treenode.js

(function(global) {

global.TreeNode = TreeNode;

/**
 * @constructor
 */
function TreeNode() {
  /** @type {Array.<TreeNode>} */
  this.childNodes = [];
  /** @type {function(TreeNode, TreeNode):number} */
  this.compare;
  /** @type {Object.<string,Array.<function>>} */
  this.procs = {};
  /** @type {TreeNode} */
  this.parentNode = null;
}

/**
 * @param {TreeNode} node
 */
TreeNode.prototype.appendChild = function(node) {
  /** @type {number} */
  var index;

  if (node.compare === void 0) {
    node.compare = this.compare;
  }

  if (node.parentNode !== null) {
    throw new Error('parent already exists');
  }

  // binary search
  index = this.binarySearch_(node);

  // insert child
  this.childNodes.splice(index, 0, node);
  node.parentNode = this;
};

/**
 * @param {TreeNode} node
 */
TreeNode.prototype.removeChild = function(node) {
  /** @type {number} */
  var index;
  /** @type {number} */
  var i;
  /** @type {number} */
  var il;
  /** @type {TreeNode} */
  var child;

  // binary search
  index = this.binarySearch_(node);
  child = this.childNodes[index];

  // remove
  for (i = 0, il = child.childNodes.length; i < il; ++i) {
    child.removeChild(child.childNodes[i]);
  }

  // remove child
  this.childNodes.splice(index, 1);
};

/**
 * @param {string} key
 * @param {function} func
 */
TreeNode.prototype.registerProcess = function(key, func) {
  /** @type {Array.<function>} */
  var procs = this.procs[key] || (this.procs[key] = []);

  procs.push(func);
};

/**
 * @param {string} key
 * @param {function} func
 */
TreeNode.prototype.removeProcess = function(key, func) {
  /** @type {Array.<function>} */
  var procs = this.procs[key];
  /** @type {number} */
  var i;
  /** @type {number} */
  var il;

  if (!procs) {
    return;
  }

  for (i = 0, il = procs.length; i < il; ++i) {
    if (procs[i] === func) {
      procs.splice(i--, 1);
      il--;
    }
  }
};

/**
 * @param {string} key
 */
TreeNode.prototype.processTopDown = function(key) {
  /** @type {Array.<function>} */
  var procs = this.procs[key];
  /** @type {Array.<TreeNode>} */
  var childNodes = this.childNodes;
  /** @type {number} */
  var i;
  /** @type {number} */
  var il;

  // current node
  if (procs) {
    for (i = 0, il = procs.length; i < il; ++i) {
      procs[i].call(this);
    }
  }

  // child nodes
  for (i = 0, il = childNodes.length; i < il; ++i) {
    childNodes[i].processTopDown(key);
  }
};

/**
 * @param {string} key
 */
TreeNode.prototype.processBottomUp = function(key) {
  /** @type {Array.<function>} */
  var procs = this.procs[key];
  /** @type {Array.<TreeNode>} */
  var childNodes = this.childNodes;
  /** @type {number} */
  var i;
  /** @type {number} */
  var il;

  // child nodes
  for (i = 0, il = childNodes.length; i < il; ++i) {
    childNodes[i].processTopDown(key);
  }

  // current node
  if (procs) {
    for (i = 0, il = procs.length; i < il; ++i) {
      procs[i].call(this);
    }
  }
};

/**
 * @param {TreeNode} node
 * @return {number}
 * @private
 */
TreeNode.prototype.binarySearch_ = function(node) {
  /** @type {number} */
  var index;
  /** @type {Array.<TreeNode>} */
  var childNodes = this.childNodes;
  /** @type {number} */
  var min = 0;
  /** @type {number} */
  var max = childNodes.length - 1;
  /** @type {number} */
  var cmp;

  if (max < 0) {
    return 0;
  }

  while (min < max) {
    index = (min + max) / 2 | 0;
    cmp = this.compare(node, childNodes[index]);

    if (cmp < 0) {
      max = index;
    } else if (cmp > 0) {
      min = index + 1;
    } else {
      return index;
    }
  }

  return this.compare(node, childNodes[min]) > 0 ? min + 1 : min;
};

})(this);