116 lines
3.2 KiB
JavaScript
116 lines
3.2 KiB
JavaScript
// Generated by CoffeeScript 1.3.3
|
|
(function() {
|
|
var DepGraph, _,
|
|
__indexOf = [].indexOf || function(item) { for (var i = 0, l = this.length; i < l; i++) { if (i in this && this[i] === item) return i; } return -1; };
|
|
|
|
_ = require('underscore');
|
|
|
|
DepGraph = (function() {
|
|
|
|
function DepGraph() {
|
|
this.map = {};
|
|
}
|
|
|
|
DepGraph.prototype.add = function(id, depId) {
|
|
var _base, _ref;
|
|
if ((_ref = (_base = this.map)[id]) == null) {
|
|
_base[id] = [];
|
|
}
|
|
if (__indexOf.call(this.map[id], depId) >= 0) {
|
|
return false;
|
|
}
|
|
this.map[id].push(depId);
|
|
return this.map[id];
|
|
};
|
|
|
|
DepGraph.prototype.getChain = function(id) {
|
|
var chain, deps, leafNode, visit, visited, _i, _len, _ref,
|
|
_this = this;
|
|
deps = this.descendantsOf(id);
|
|
chain = [];
|
|
visited = {};
|
|
visit = function(node) {
|
|
var parent, _i, _len, _ref;
|
|
if (visited[node] || node === id) {
|
|
return;
|
|
}
|
|
visited[node] = true;
|
|
_ref = _this.parentsOf(node);
|
|
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
|
|
parent = _ref[_i];
|
|
if (__indexOf.call(deps, parent) >= 0) {
|
|
visit(parent);
|
|
}
|
|
}
|
|
return chain.unshift(node);
|
|
};
|
|
_ref = _.intersection(deps, this.leafNodes()).reverse();
|
|
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
|
|
leafNode = _ref[_i];
|
|
visit(leafNode);
|
|
}
|
|
return chain;
|
|
};
|
|
|
|
DepGraph.prototype.leafNodes = function() {
|
|
var allNodes, node, _i, _len, _ref, _results;
|
|
allNodes = _.uniq(_.flatten(_.values(this.map)));
|
|
_results = [];
|
|
for (_i = 0, _len = allNodes.length; _i < _len; _i++) {
|
|
node = allNodes[_i];
|
|
if (!((_ref = this.map[node]) != null ? _ref.length : void 0)) {
|
|
_results.push(node);
|
|
}
|
|
}
|
|
return _results;
|
|
};
|
|
|
|
DepGraph.prototype.parentsOf = function(child) {
|
|
var node, _i, _len, _ref, _results;
|
|
_ref = _.keys(this.map);
|
|
_results = [];
|
|
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
|
|
node = _ref[_i];
|
|
if (__indexOf.call(this.map[node], child) >= 0) {
|
|
_results.push(node);
|
|
}
|
|
}
|
|
return _results;
|
|
};
|
|
|
|
DepGraph.prototype.descendantsOf = function(parent, descendants, branch) {
|
|
var child, _i, _len, _ref, _ref1;
|
|
if (descendants == null) {
|
|
descendants = [];
|
|
}
|
|
if (branch == null) {
|
|
branch = [];
|
|
}
|
|
descendants.push(parent);
|
|
branch.push(parent);
|
|
_ref1 = (_ref = this.map[parent]) != null ? _ref : [];
|
|
for (_i = 0, _len = _ref1.length; _i < _len; _i++) {
|
|
child = _ref1[_i];
|
|
if (__indexOf.call(branch, child) >= 0) {
|
|
throw new Error("Cyclic dependency from " + parent + " to " + child);
|
|
}
|
|
if (__indexOf.call(descendants, child) >= 0) {
|
|
continue;
|
|
}
|
|
this.descendantsOf(child, descendants, branch.slice(0));
|
|
}
|
|
return descendants.slice(1);
|
|
};
|
|
|
|
return DepGraph;
|
|
|
|
})();
|
|
|
|
if ((typeof module !== "undefined" && module !== null ? module.exports : void 0) != null) {
|
|
module.exports = DepGraph;
|
|
} else {
|
|
this.DepGraph = DepGraph;
|
|
}
|
|
|
|
}).call(this);
|