'use strict';
|
|
const Assert = require('@hapi/hoek/lib/assert');
|
|
|
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
|
|
Assert(!before.includes(group), `Item cannot come before itself: ${group}`);
|
Assert(!before.includes('?'), 'Item cannot come before unassociated items');
|
Assert(!after.includes(group), `Item cannot come after itself: ${group}`);
|
Assert(!after.includes('?'), 'Item cannot come after unassociated items');
|
|
if (!Array.isArray(nodes)) {
|
nodes = [nodes];
|
}
|
|
for (const node of nodes) {
|
const item = {
|
seq: this._items.length,
|
sort,
|
before,
|
after,
|
group,
|
node
|
};
|
|
this._items.push(item);
|
}
|
|
// Insert event
|
|
const valid = this._sort();
|
Assert(valid, 'item', group !== '?' ? `added into group ${group}` : '', 'created a dependencies error');
|
|
return this.nodes;
|
}
|
|
merge(others) {
|
|
if (!Array.isArray(others)) {
|
others = [others];
|
}
|
|
for (const other of others) {
|
if (other) {
|
for (const item of other._items) {
|
this._items.push(Object.assign({}, item)); // Shallow cloned
|
}
|
}
|
}
|
|
// Sort items
|
|
this._items.sort(internals.mergeSort);
|
for (let i = 0; i < this._items.length; ++i) {
|
this._items[i].seq = i;
|
}
|
|
const valid = this._sort();
|
Assert(valid, '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 (const item of this._items) {
|
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'
|
|
for (const after of item.after) {
|
graphAfters[after] = graphAfters[after] || [];
|
graphAfters[after].push(seq);
|
}
|
}
|
|
// Expand intermediary graph
|
|
for (const node in graph) {
|
const expandedGroups = [];
|
|
for (const graphNodeItem in graph[node]) {
|
const group = graph[node][graphNodeItem];
|
groups[group] = groups[group] || [];
|
expandedGroups.push(...groups[group]);
|
}
|
|
graph[node] = expandedGroups;
|
}
|
|
// Merge intermediary graph using graphAfters into final graph
|
|
for (const group in graphAfters) {
|
if (groups[group]) {
|
for (const node of groups[group]) {
|
graph[node].push(...graphAfters[group]);
|
}
|
}
|
}
|
|
// Compile ancestors
|
|
const ancestors = {};
|
for (const node in graph) {
|
const children = graph[node];
|
for (const child of children) {
|
ancestors[child] = ancestors[child] || [];
|
ancestors[child].push(node);
|
}
|
}
|
|
// Topo sort
|
|
const visited = {};
|
const sorted = [];
|
|
for (let i = 0; i < this._items.length; ++i) { // Looping through 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 false;
|
}
|
|
const seqIndex = {};
|
for (const item of this._items) {
|
seqIndex[item.seq] = item;
|
}
|
|
this._items = [];
|
this.nodes = [];
|
|
for (const value of sorted) {
|
const sortedItem = seqIndex[value];
|
this.nodes.push(sortedItem.node);
|
this._items.push(sortedItem);
|
}
|
|
return true;
|
}
|
};
|
|
|
internals.mergeSort = (a, b) => {
|
|
return a.sort === b.sort ? 0 : (a.sort < b.sort ? -1 : 1);
|
};
|
