switch to vuepress

1 files changed, 229 insertions, 0 deletions

diff --git a/node_modules/topo/lib/index.js b/node_modules/topo/lib/index.js
new file mode 100755
index 00000000..0aaa9f7e
--- /dev/null
+++ b/node_modules/topo/lib/index.js
@@ -0,0 +1,229 @@
+'use strict';
+
+// Load modules
+
+const Hoek = require('hoek');
+
+
+// Declare internals
+
+const internals = {};
+
+
+exports = module.exports = internals.Topo = function () {
+
+    this._items = [];
+    this.nodes = [];
+};
+
+
+internals.Topo.prototype.add = function (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.indexOf(group) === -1, 'Item cannot come before itself:', group);
+    Hoek.assert(before.indexOf('?') === -1, 'Item cannot come before unassociated items');
+    Hoek.assert(after.indexOf(group) === -1, 'Item cannot come after itself:', group);
+    Hoek.assert(after.indexOf('?') === -1, 'Item cannot come after unassociated items');
+
+    ([].concat(nodes)).forEach((node, i) => {
+
+        const item = {
+            seq: this._items.length,
+            sort: sort,
+            before: before,
+            after: after,
+            group: group,
+            node: 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;
+};
+
+
+internals.Topo.prototype.merge = function (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 = Hoek.shallow(other._items[j]);
+                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;
+};
+
+
+internals.mergeSort = function (a, b) {
+
+    return a.sort === b.sort ? 0 : (a.sort < b.sort ? -1 : 1);
+};
+
+
+internals.Topo.prototype._sort = function () {
+
+    // 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) {
+        let next = i;
+
+        if (ancestors[i]) {
+            next = null;
+            for (let j = 0; j < this._items.length; ++j) {
+                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 (sorted.indexOf(ancestors[j][k]) >= 0) {
+                        ++seenCount;
+                    }
+                }
+
+                if (seenCount === shouldSeeCount) {
+                    next = j;
+                    break;
+                }
+            }
+        }
+
+        if (next !== null) {
+            next = next.toString();         // Normalize to string TODO: replace with seq
+            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;
+};