File Manager

Editing File: /home/ubuntu/efiexchange-node-base/node_modules/@hapi/topo/lib/index.js

'use strict';

const Assert = require('@hapi/hoek/lib/assert');

const internals = {};

exports.Sorter = class {

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

if (!options.manual) {
            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() {

const valid = this._sort();
        Assert(valid, 'sort 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

// 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);
};

Back to Directory File Manager