Tumortisch-Dist/resources/app/node_modules/topo/lib/index.js
2021-06-15 16:00:08 +02:00

229 lines
6.3 KiB
JavaScript

'use strict';
// Load modules
const Hoek = require('hoek');
// Declare internals
const internals = {};
module.exports = class Topo {
constructor() {
this._items = [];
this.nodes = [];
}
add(nodes, options) {
options = options || {};
// Validate rules
const before = [].concat(options.before || []);
const after = [].concat(options.after || []);
const group = options.group || '?';
const sort = options.sort || 0; // Used for merging only
Hoek.assert(!before.includes(group), `Item cannot come before itself: ${group}`);
Hoek.assert(!before.includes('?'), 'Item cannot come before unassociated items');
Hoek.assert(!after.includes(group), `Item cannot come after itself: ${group}`);
Hoek.assert(!after.includes('?'), 'Item cannot come after unassociated items');
([].concat(nodes)).forEach((node, i) => {
const item = {
seq: this._items.length,
sort,
before,
after,
group,
node
};
this._items.push(item);
});
// Insert event
const error = this._sort();
Hoek.assert(!error, 'item', (group !== '?' ? `added into group ${group}` : ''), 'created a dependencies error');
return this.nodes;
}
merge(others) {
others = [].concat(others);
for (let i = 0; i < others.length; ++i) {
const other = others[i];
if (other) {
for (let j = 0; j < other._items.length; ++j) {
const item = Object.assign({}, other._items[j]); // Shallow cloned
this._items.push(item);
}
}
}
// Sort items
this._items.sort(internals.mergeSort);
for (let i = 0; i < this._items.length; ++i) {
this._items[i].seq = i;
}
const error = this._sort();
Hoek.assert(!error, 'merge created a dependencies error');
return this.nodes;
}
_sort() {
// Construct graph
const graph = {};
const graphAfters = Object.create(null); // A prototype can bungle lookups w/ false positives
const groups = Object.create(null);
for (let i = 0; i < this._items.length; ++i) {
const item = this._items[i];
const seq = item.seq; // Unique across all items
const group = item.group;
// Determine Groups
groups[group] = groups[group] || [];
groups[group].push(seq);
// Build intermediary graph using 'before'
graph[seq] = item.before;
// Build second intermediary graph with 'after'
const after = item.after;
for (let j = 0; j < after.length; ++j) {
graphAfters[after[j]] = (graphAfters[after[j]] || []).concat(seq);
}
}
// Expand intermediary graph
let graphNodes = Object.keys(graph);
for (let i = 0; i < graphNodes.length; ++i) {
const node = graphNodes[i];
const expandedGroups = [];
const graphNodeItems = Object.keys(graph[node]);
for (let j = 0; j < graphNodeItems.length; ++j) {
const group = graph[node][graphNodeItems[j]];
groups[group] = groups[group] || [];
for (let k = 0; k < groups[group].length; ++k) {
expandedGroups.push(groups[group][k]);
}
}
graph[node] = expandedGroups;
}
// Merge intermediary graph using graphAfters into final graph
const afterNodes = Object.keys(graphAfters);
for (let i = 0; i < afterNodes.length; ++i) {
const group = afterNodes[i];
if (groups[group]) {
for (let j = 0; j < groups[group].length; ++j) {
const node = groups[group][j];
graph[node] = graph[node].concat(graphAfters[group]);
}
}
}
// Compile ancestors
let children;
const ancestors = {};
graphNodes = Object.keys(graph);
for (let i = 0; i < graphNodes.length; ++i) {
const node = graphNodes[i];
children = graph[node];
for (let j = 0; j < children.length; ++j) {
ancestors[children[j]] = (ancestors[children[j]] || []).concat(node);
}
}
// Topo sort
const visited = {};
const sorted = [];
for (let i = 0; i < this._items.length; ++i) { // Really looping thru item.seq values out of order
let next = i;
if (ancestors[i]) {
next = null;
for (let j = 0; j < this._items.length; ++j) { // As above, these are item.seq values
if (visited[j] === true) {
continue;
}
if (!ancestors[j]) {
ancestors[j] = [];
}
const shouldSeeCount = ancestors[j].length;
let seenCount = 0;
for (let k = 0; k < shouldSeeCount; ++k) {
if (visited[ancestors[j][k]]) {
++seenCount;
}
}
if (seenCount === shouldSeeCount) {
next = j;
break;
}
}
}
if (next !== null) {
visited[next] = true;
sorted.push(next);
}
}
if (sorted.length !== this._items.length) {
return new Error('Invalid dependencies');
}
const seqIndex = {};
for (let i = 0; i < this._items.length; ++i) {
const item = this._items[i];
seqIndex[item.seq] = item;
}
const sortedNodes = [];
this._items = sorted.map((value) => {
const sortedItem = seqIndex[value];
sortedNodes.push(sortedItem.node);
return sortedItem;
});
this.nodes = sortedNodes;
}
};
internals.mergeSort = (a, b) => {
return a.sort === b.sort ? 0 : (a.sort < b.sort ? -1 : 1);
};