topological-sort - npm Package Compare versions

Comparing version 0.0.2 to 0.1.0

index.js

@@ -35,12 +35,14 @@ 'use strict';
     sort() {
-        const visitedNodes = new Set;
-        const sortedKeysStack = [];
+        this._visitedNodes = new Set;
+        this._sortedKeysStack = [];
+        this._pickNodes = new Set;
         const output = new Map;
 
         for (const [key] of this._nodes) {
-            this._exploreNode(key, visitedNodes, sortedKeysStack);
+            this._pickNodes.add(key);
+            this._exploreNode(key, [key], true);
         }
 
-        for (let i = sortedKeysStack.length - 1; i >= 0; i--) {
-            output.set(sortedKeysStack[i], this._nodes.get(sortedKeysStack[i]));
+        for (let i = this._sortedKeysStack.length - 1; i >= 0; i--) {
+            output.set(this._sortedKeysStack[i], this._nodes.get(this._sortedKeysStack[i]));
         }
@@ -51,6 +53,9 @@
 
-    _exploreNode(nodeKey, visitedNodesRef, stackRef) {
+    _exploreNode(nodeKey, explorePath, skipCurrentNodeCheck = false) {
+        if (!skipCurrentNodeCheck) {
+            assert(!this._pickNodes.has(nodeKey), `Node ${nodeKey} forms circular dependency: ${explorePath.join(' -> ')}`);
+        }
+
         const node = this._nodes.get(nodeKey);
-
-        if (visitedNodesRef.has(node)) {
+        if (this._visitedNodes.has(node)) {
             return;
@@ -61,9 +66,12 @@ }
         // won't be explored next time
-        visitedNodesRef.add(node);
+        this._visitedNodes.add(node);
 
         for (const [childNodeKey] of node.children) {
-            this._exploreNode(childNodeKey, visitedNodesRef, stackRef);
+            this._exploreNode(
+                childNodeKey,
+                [...explorePath, childNodeKey]
+            );
         }
 
-        stackRef.push(nodeKey);
+        this._sortedKeysStack.push(nodeKey);
     }
@@ -70,0 +78,0 @@

package.json

 {
   "name": "topological-sort",
-  "version": "0.0.2",
+  "version": "0.1.0",
   "description": "Topological sort implemented in Javascript",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -29,3 +29,4 @@ # Topological sort implemented in Javascript (ES2016)
 
-// sorting is simple: it returns a new map wih sorted elements:
+// sorting is simple: it returns a new map wih sorted elements
+// if circular dependency is found, sort() operation throws an AssertionError
 const sorted = sortOp.sort();
@@ -32,0 +33,0 @@ const sortedKeys = [...res.keys()]; // ['variables', 'mixins', 'block', 'block_mod_val1', 'block_mod_val2']

No alert changes

Improved metrics

Total package byte prevSize

5905

increased by7.42%

Lines of code

72

increased by12.5%

Number of lines in readme file

41

increased by2.5%

No dependency changes