topo - npm Package Compare versions
Comparing version 3.0.0 to 3.0.1
300
lib/index.js
@@ -13,217 +13,217 @@ 'use strict'; | ||
| exports = module.exports = internals.Topo = function () { | ||
| module.exports = class Topo { | ||
| this._items = []; | ||
| this.nodes = []; | ||
| }; | ||
| constructor() { | ||
| this._items = []; | ||
| this.nodes = []; | ||
| } | ||
| internals.Topo.prototype.add = function (nodes, options) { | ||
| add(nodes, options) { | ||
| options = options || {}; | ||
| options = options || {}; | ||
| // Validate rules | ||
| // 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 | ||
| 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'); | ||
| 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) => { | ||
| ([].concat(nodes)).forEach((node, i) => { | ||
| const item = { | ||
| seq: this._items.length, | ||
| sort, | ||
| before, | ||
| after, | ||
| group, | ||
| node | ||
| }; | ||
| const item = { | ||
| seq: this._items.length, | ||
| sort, | ||
| before, | ||
| after, | ||
| group, | ||
| node | ||
| }; | ||
| this._items.push(item); | ||
| }); | ||
| this._items.push(item); | ||
| }); | ||
| // Insert event | ||
| // Insert event | ||
| const error = this._sort(); | ||
| Hoek.assert(!error, 'item', (group !== '?' ? 'added into group ' + group : ''), 'created a dependencies error'); | ||
| const error = this._sort(); | ||
| Hoek.assert(!error, 'item', (group !== '?' ? `added into group ${group}` : ''), 'created a dependencies error'); | ||
| return this.nodes; | ||
| }; | ||
| return this.nodes; | ||
| } | ||
| merge(others) { | ||
| 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); | ||
| 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 | ||
| // Sort items | ||
| this._items.sort(internals.mergeSort); | ||
| for (let i = 0; i < this._items.length; ++i) { | ||
| this._items[i].seq = i; | ||
| } | ||
| 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'); | ||
| const error = this._sort(); | ||
| Hoek.assert(!error, 'merge created a dependencies error'); | ||
| return this.nodes; | ||
| }; | ||
| return this.nodes; | ||
| } | ||
| _sort() { | ||
| internals.mergeSort = function (a, b) { | ||
| // Construct graph | ||
| return a.sort === b.sort ? 0 : (a.sort < b.sort ? -1 : 1); | ||
| }; | ||
| 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; | ||
| internals.Topo.prototype._sort = function () { | ||
| // Determine Groups | ||
| // Construct graph | ||
| groups[group] = groups[group] || []; | ||
| groups[group].push(seq); | ||
| const graph = {}; | ||
| const graphAfters = Object.create(null); // A prototype can bungle lookups w/ false positives | ||
| const groups = Object.create(null); | ||
| // Build intermediary graph using 'before' | ||
| 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; | ||
| graph[seq] = item.before; | ||
| // Determine Groups | ||
| // Build second intermediary graph with 'after' | ||
| 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); | ||
| const after = item.after; | ||
| for (let j = 0; j < after.length; ++j) { | ||
| graphAfters[after[j]] = (graphAfters[after[j]] || []).concat(seq); | ||
| } | ||
| } | ||
| } | ||
| // Expand intermediary graph | ||
| // Expand intermediary graph | ||
| let graphNodes = Object.keys(graph); | ||
| for (let i = 0; i < graphNodes.length; ++i) { | ||
| const node = graphNodes[i]; | ||
| const expandedGroups = []; | ||
| 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] || []; | ||
| 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]); | ||
| for (let k = 0; k < groups[group].length; ++k) { | ||
| expandedGroups.push(groups[group][k]); | ||
| } | ||
| } | ||
| graph[node] = expandedGroups; | ||
| } | ||
| graph[node] = expandedGroups; | ||
| } | ||
| // Merge intermediary graph using graphAfters into final graph | ||
| // 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]; | ||
| 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]); | ||
| 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 | ||
| // 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]; | ||
| 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); | ||
| for (let j = 0; j < children.length; ++j) { | ||
| ancestors[children[j]] = (ancestors[children[j]] || []).concat(node); | ||
| } | ||
| } | ||
| } | ||
| // Topo sort | ||
| // Topo sort | ||
| const visited = {}; | ||
| const sorted = []; | ||
| 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; | ||
| 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[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] = []; | ||
| } | ||
| 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; | ||
| 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 (seenCount === shouldSeeCount) { | ||
| next = j; | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| if (next !== null) { | ||
| visited[next] = true; | ||
| sorted.push(next); | ||
| } | ||
| } | ||
| if (next !== null) { | ||
| visited[next] = true; | ||
| sorted.push(next); | ||
| if (sorted.length !== this._items.length) { | ||
| return new Error('Invalid dependencies'); | ||
| } | ||
| } | ||
| 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 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; | ||
| } | ||
| }; | ||
| const sortedNodes = []; | ||
| this._items = sorted.map((value) => { | ||
| internals.mergeSort = (a, b) => { | ||
| const sortedItem = seqIndex[value]; | ||
| sortedNodes.push(sortedItem.node); | ||
| return sortedItem; | ||
| }); | ||
| this.nodes = sortedNodes; | ||
| return a.sort === b.sort ? 0 : (a.sort < b.sort ? -1 : 1); | ||
| }; |
| { | ||
| "name": "topo", | ||
| "description": "Topological sorting with grouping support", | ||
| "version": "3.0.0", | ||
| "version": "3.0.1", | ||
| "repository": "git://github.com/hapijs/topo", | ||
@@ -14,3 +14,3 @@ "main": "lib/index.js", | ||
| "engines": { | ||
| "node": ">=8.0.0" | ||
| "node": ">=8.12.0" | ||
| }, | ||
@@ -22,3 +22,3 @@ "dependencies": { | ||
| "code": "5.x.x", | ||
| "lab": "14.x.x" | ||
| "lab": "17.x.x" | ||
| }, | ||
@@ -25,0 +25,0 @@ "scripts": { |
@@ -14,3 +14,3 @@ # topo | ||
| **Example** | ||
| ```node | ||
| ```js | ||
| const Topo = require('topo'); | ||
@@ -17,0 +17,0 @@ |
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by4.02%
9227
- Lines of code
- increased by1.22%
166
No dependency changes