Skip to content

Instantly share code, notes, and snippets.

@logarytm
Last active August 11, 2018 19:55
Show Gist options
  • Select an option

  • Save logarytm/e59cf0df15a97c3e1018 to your computer and use it in GitHub Desktop.

Select an option

Save logarytm/e59cf0df15a97c3e1018 to your computer and use it in GitHub Desktop.
toposorting a dependency graph
'use strict';
function Node(value, dependencies) {
dependencies = (dependencies || []);
this.value = this.valueOf = this.toString = () => value;
this.dependencies = () => dependencies;
this.standalone = () => dependencies.length === 0;
this.equals = node => value === node.value();
}
function flatten(what) {
if (!Array.isArray(what)) {
return what;
} else {
return what.reduce((one, two) => {
return one.concat(flatten(two));
}, []);
}
}
function indexOf(set, value) {
// like Array#indexOf(), but for nodes
let index = -1;
while ((index += 1) < set.length) {
if (set[index].equals(value)) {
return index;
}
}
return -1;
}
function unique(set) {
return set.filter((value, index) => indexOf(set, value) === index);
}
function resolve(node) {
if (node.standalone()) {
return [node];
} else {
return unique(flatten([node].concat(
node.dependencies()
.map(resolve)
)));
}
}
console.log(resolve(
new Node('a', [
new Node('b', [
new Node('c', [
new Node('d'),
new Node('e'),
])
]),
new Node('c')
])
).reverse().join(', '));
// e, d, c, b, a
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment