Skip to content

Instantly share code, notes, and snippets.

@imaya
Created October 16, 2012 07:29
Show Gist options
  • Save imaya/3897792 to your computer and use it in GitHub Desktop.
Save imaya/3897792 to your computer and use it in GitHub Desktop.
(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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment