Simple dependency tree

dependency-tree.js

var Dependency = (function () {
	"use strict";
	var Node = function () {
		var i, pub = {}, inst = this;
		for (i in inst) 
			if (inst[i] instanceof Function)
				pub[i] = (function (i) {
					return function () {
						return inst[i].apply(inst, arguments);
					};
				}(i));
		this.pub = pub;
		this.dependencies = [];
		
		return this.pub;
	};
	Node.prototype = {
		setNodeId: function (cid) { this.nodeId = cid; },
		getNodeId: function () { return this.nodeId; },
		setDependencies: function (deps) { 
			this.dependencies = Array.prototype.slice.apply(deps); 
		},
		getDependencies: function () {
			return this.dependencies;
		},
		getAllDependencies: function (completed) {
			if (this.inFlight) return [];
			this.inFlight = true;
			var i, subNode,
				deps = this.dependencies,
				ret = Array.prototype.slice.apply(deps),
				satisfied = {},
				len = deps.length;
				
			for (i=0; i<len; i++) {
				subNode = this.tree.getNode(deps[i]);
				if (!subNode) 
					throw new Error("Node "+deps[i]+", referenced as a dependency of "+this.nodeId+" does not exist in the Tree");
					
				ret = subNode.getAllDependencies().concat(ret);
			}
			this.inFlight = false;
			if (!completed || !completed.length)
				return ret;

			for (i=0; i<ret.length; i++) 
				satisfied[ret[i]] = false;
			for (i=0; i<completed.length; i++)
				satisfied[completed[i]] = true;
			
			ret = [];
			for (i in satisfied) {
				if (!satisfied[i])
					ret.push(i);
			}
			return ret;
		},
		getNextNodes: function (completed) {
			var i,
				requiredNodes = this.pub.getAllDependencies(completed),
				availableNodes = this.tree.getAvailableNodes(completed),
				availableAndRequired = {},
				ret = [];
			
			for (i=0; i<availableNodes.length; i++)
				availableAndRequired[availableNodes[i]] = false;
			for (i=0; i<requiredNodes.length; i++)
				if (availableAndRequired[availableNodes[i]]===false)
					availableAndRequired[availableNodes[i]] = true;
			for (i in availableAndRequired) {
				if (availableAndRequired[i] === true)
					ret.push(i);
			}
			return ret;
		},
		setTree: function (tree) { this.tree = tree; },
		getTree: function () { return this.tree; },
		setProperties: function (props) {
			var i, setter;
			for (i in props) {
				setter = 'set'+i.substr(0,1).toUpperCase()+i.substr(1)
				if (this.pub[setter] instanceof Function) 
					this.pub[setter](props[i]);
				else 
					this.pub[i] = props[i];
			}
			return this.pub;
		}
	};
	Tree = function () {
		var i, pub = {}, inst = this;
		for (i in inst) 
			if (inst[i] instanceof Function)
				pub[i] = (function (i) {
					return function () {
						return inst[i].apply(inst, arguments);
					};
				}(i));
		inst.pub = pub;
		
		this.nodes = {};
		return pub;
	};
	Tree.prototype = {
		add: function (node) {
			node.setTree(this.pub);
			this.nodes[node.getNodeId()] = node;
		},
		getNode: function (cid) {
			return this.nodes[cid];
		},
		each: function (nodeCallback) {
			for (var i in this.nodes) {
				nodeCallback(this.nodes[i]);
			}
		},
		getAvailableNodes: function (completed) {
			var ret = [];
			this.pub.each(function (node) {
				var deps = node.getAllDependencies(completed);
				if (deps.length === 0) {
					var i, 
						ok = true, 
						nodeId = node.getNodeId();
					for (i=0; i<completed.length; i++)
						ok = ok && !(nodeId == completed[i]);
					if (ok) ret.push(node.getNodeId());
				}
			});
			return ret;
		}
	};
	return {
		Node: Node,
		Tree: Tree
	};
}());

(function (Dependency) {
	"use strict";
	
	var courseBook = new Dependency.Tree();

	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'MAJOR-PHILOSOPHY', dependencies: [ 'STAT-101', 'PHIL-102' ] }));
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'MAJOR-MATHS', dependencies: [ 'STAT-101', 'CALC-102' ] }));
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'CALC-102', dependencies: [ 'CALC-101' ] }));
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'CALC-101', dependencies: [ 'STAT-100' ] }));
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'STAT-101', dependencies: [ 'STAT-100' ] }));
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'STAT-100', dependencies: [] }));
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'PHIL-102', dependencies: [ 'PHIL-101' ] }));
	//Describe nodes with arbitrary objects
	var philosophy101 = {
		fullName: 'Introduction to Philosophy',
		courseListing: 'http://miskatonic.edu/phil-101',
		instructor: 'Lovecraft, H.P.'
	};
	courseBook.add((new Dependency.Node()).setProperties({ nodeId: 'PHIL-101', dependencies: [], data: philosophy101 }));
	

	//See what nodes among the entire tree are available from your position
	courseBook.getAvailableNodes(['STAT-100']); // > ['STAT-101', 'PHIL-101']
	
	//See what nodes need to be completed before a node is available
	var course = courseBook.getNode('PHIL-102');
	course.getAllDependencies(); // > ['PHIL-101']
	

	//Get the immediate dependencies for a given course
	courseBook.getNode('MAJOR-PHILOSOPHY').getDependencies(); // ['STAT-101', 'PHIL-102']
	
	//Get all courses that must be completed for a given course
	courseBook.getNode('MAJOR-PHILOSOPHY').getAllDependencies(); // ['PHIL-101', 'STAT-100', 'STAT-101', 'PHIL-102']
	
	//Optionally, excluding a set of completed nodes
	courseBook.getNode('MAJOR-PHILOSOPHY').getAllDependencies(['PHIL-101', 'STAT-100']); // > [ 'STAT-101', 'PHIL-102' ]
	
	//Just get dependencies that are presently available given current accomplishments
	courseBook.getNode('MAJOR-MATHS').getNextNodes(['PHIL-101', 'STAT-100']); // > [ 'CALC-101', 'STAT-101', 'PHIL-102' ]
}(Dependency));