toposort-class - npm Package Compare versions

Comparing version 1.0.0 to 1.0.1

benchmark/README.md

@@ -8,5 +8,5 @@ Benchmarks
 |------------------------------|-----------------|-----------:|-----:|
-| simple dependency chains     | 0.3.1 version   | 65,897.92  | 17%  |
-|                              | current version | 378,468.10 | 100% |
-| slightly more complex chains | 0.3.1 version   | 25,827.17  | 16%  |
-|                              | current version | 165,029.58 | 100% |
+| simple dependency chains     | 0.3.1 version   | 66,722.22  | 8%   |
+|                              | current version | 837,416.60 | 100% |
+| slightly more complex chains | 0.3.1 version   | 24,530.85  | 6%   |
+|                              | current version | 386,620.50 | 100% |

build/toposort.js

@@ -27,3 +27,3 @@ /****
     if( typeof define === "function" && define.amd ) {
-        define( ["exports", "module"], factory );
+        define( "Toposort", ["exports", "module"], factory );
     } else if( typeof exports !== "undefined" && typeof module !== "undefined" ) {
@@ -36,3 +36,3 @@ factory( exports, module );
         factory( mod.exports, mod );
-        global.toposort = mod.exports;
+        global.Toposort = mod.exports;
     }
@@ -117,5 +117,4 @@ })( this, function( exports, module ) {
             var nodes = [];
-            var offset = 0,
-                place = 0;
 
+            //accumulate unique nodes into a large list
             for( var _iterator2 = this.edges, _isArray2 = Array.isArray( _iterator2 ), _i2 = 0, _iterator2 = _isArray2 ?
@@ -167,11 +166,12 @@ _iterator2 :
 
+            //initialize the placement of nodes into the sorted array at the end
+            var place = nodes.length;
+
+            //initialize the sorted array with the same length as the unique nodes array
             var sorted = new Array( nodes.length );
 
-            var visit = function visit( node, i ) {
-                var predecessors = arguments.length <= 2 || arguments[2] === undefined ? [] : arguments[2];
-
-                var index = undefined,
-                    copy = undefined;
-
-                if( predecessors.indexOf( node ) > -1 ) {
+            //define a visitor function that recursively traverses dependencies.
+            var visit = function visit( node, predecessors ) {
+                //check if a node is dependent of itself
+                if( predecessors.length !== 0 && predecessors.indexOf( node ) !== -1 ) {
                     throw new Error( "Cyclic dependency found. " + node + " is dependent of itself.\nDependency chain: "
@@ -181,50 +181,84 @@ + predecessors.join( " -> " ) + " => " + node );
 
-                index = nodes.indexOf( node );
+                var index = nodes.indexOf( node );
 
-                if( index === -1 || index < offset ) {
-                    return i;
-                } else if( index === 0 ) {
-                    offset++;
-                } else {
-                    nodes.splice( index, 1 );
-                }
+                //if the node still exists, traverse its dependencies
+                if( index !== -1 ) {
+                    var copy = false;
 
-                if( predecessors.length === 0 ) {
-                    i--;
-                }
+                    //mark the node as false to exclude it from future iterations
+                    nodes[index] = false;
 
-                for( var _iterator4 = _this.edges, _isArray4 = Array.isArray( _iterator4 ), _i4 = 0, _iterator4 = _isArray4 ?
-                                                                                                                  _iterator4 :
-                                                                                                                  _iterator4[Symbol.iterator](); ; ) {
-                    var _ref4;
+                    //loop through all edges and follow dependencies of the current node
+                    for( var _iterator4 = _this.edges, _isArray4 = Array.isArray( _iterator4 ), _i4 = 0, _iterator4 = _isArray4 ?
+                                                                                                                      _iterator4 :
+                                                                                                                      _iterator4[Symbol.iterator](); ; ) {
+                        var _ref4;
 
-                    if( _isArray4 ) {
-                        if( _i4 >= _iterator4.length ) {
-                            break;
+                        if( _isArray4 ) {
+                            if( _i4 >= _iterator4.length ) {
+                                break;
+                            }
+                            _ref4 = _iterator4[_i4++];
+                        } else {
+                            _i4 = _iterator4.next();
+                            if( _i4.done ) {
+                                break;
+                            }
+                            _ref4 = _i4.value;
                         }
-                        _ref4 = _iterator4[_i4++];
-                    } else {
-                        _i4 = _iterator4.next();
-                        if( _i4.done ) {
-                            break;
-                        }
-                        _ref4 = _i4.value;
-                    }
 
-                    var edge = _ref4;
+                        var edge = _ref4;
 
-                    if( edge[0] === node ) {
-                        copy = copy || predecessors.concat( [node] );
+                        if( edge[0] === node ) {
+                            //lazily create a copy of predecessors with the current node concatenated onto it
+                            copy = copy || predecessors.concat( [node] );
 
-                        i = visit( edge[1], i, copy );
+                            //recurse to node dependencies
+                            visit( edge[1], copy );
+                        }
                     }
+
+                    //add the node to the next place in the sorted array
+                    sorted[--place] = node;
                 }
+            };
 
-                sorted[sorted.length - ++place] = node;
+            for( var i = 0; i < nodes.length; i++ ) {
+                var node = nodes[i];
 
-                return i;
-            };
+                //ignore nodes that have been excluded
+                if( node !== false ) {
+                    //mark the node as false to exclude it from future iterations
+                    nodes[i] = false;
 
-            for( var i = 0; i < nodes.length - offset; i++ ) {
-                i = visit( nodes[i + offset], i );
+                    //loop through all edges and follow dependencies of the current node
+                    for( var _iterator5 = this.edges, _isArray5 = Array.isArray( _iterator5 ), _i5 = 0, _iterator5 = _isArray5 ?
+                                                                                                                     _iterator5 :
+                                                                                                                     _iterator5[Symbol.iterator](); ; ) {
+                        var _ref5;
+
+                        if( _isArray5 ) {
+                            if( _i5 >= _iterator5.length ) {
+                                break;
+                            }
+                            _ref5 = _iterator5[_i5++];
+                        } else {
+                            _i5 = _iterator5.next();
+                            if( _i5.done ) {
+                                break;
+                            }
+                            _ref5 = _i5.value;
+                        }
+
+                        var edge = _ref5;
+
+                        if( edge[0] === node ) {
+                            //recurse to node dependencies
+                            visit( edge[1], [node] );
+                        }
+                    }
+
+                    //add the node to the next place in the sorted array
+                    sorted[--place] = node;
+                }
             }
@@ -231,0 +265,0 @@

build/toposort.min.js

@@ -1,1 +0,1 @@
-!function(a,b){if("function"==typeof define&&define.amd)define(["exports","module"],b);else if("undefined"!=typeof exports&&"undefined"!=typeof module)b(exports,module);else{var c={exports:{}};b(c.exports,c),a.toposort=c.exports}}(this,function(a,b){"use strict";function c(a,b){if(!(a instanceof b))throw new TypeError("Cannot call a class as a function")}var d=function(){function a(){c(this,a),this.edges=[],this.Toposort=a}return a.prototype.add=function(a,b){if("string"!=typeof a||!a)throw new TypeError("Dependent name must be given as a not empty string");if(b=Array.isArray(b)?b:[b],b.length>0)for(var c=b,d=Array.isArray(c),e=0,c=d?c:c[Symbol.iterator]();;){var f;if(d){if(e>=c.length)break;f=c[e++]}else{if(e=c.next(),e.done)break;f=e.value}var g=f;if("string"!=typeof g||!g)throw new TypeError("Dependency name must be given as a not empty string");this.edges.push([a,g])}else this.edges.push([a]);return this},a.prototype.sort=function(){for(var a=this,b=[],c=0,d=0,e=this.edges,f=Array.isArray(e),g=0,e=f?e:e[Symbol.iterator]();;){var h;if(f){if(g>=e.length)break;h=e[g++]}else{if(g=e.next(),g.done)break;h=g.value}for(var i=h,j=i,k=Array.isArray(j),l=0,j=k?j:j[Symbol.iterator]();;){var m;if(k){if(l>=j.length)break;m=j[l++]}else{if(l=j.next(),l.done)break;m=l.value}var n=m;-1===b.indexOf(n)&&b.push(n)}}for(var o=new Array(b.length),p=function r(e,f){var g=arguments.length<=2||void 0===arguments[2]?[]:arguments[2],h=void 0,i=void 0;if(g.indexOf(e)>-1)throw new Error("Cyclic dependency found. "+e+" is dependent of itself.\nDependency chain: "+g.join(" -> ")+" => "+e);if(h=b.indexOf(e),-1===h||c>h)return f;0===h?c++:b.splice(h,1),0===g.length&&f--;for(var j=a.edges,k=Array.isArray(j),l=0,j=k?j:j[Symbol.iterator]();;){var m;if(k){if(l>=j.length)break;m=j[l++]}else{if(l=j.next(),l.done)break;m=l.value}var n=m;n[0]===e&&(i=i||g.concat([e]),f=r(n[1],f,i))}return o[o.length-++d]=e,f},q=0;q<b.length-c;q++)q=p(b[q+c],q);return o},a.prototype.clear=function(){return this.edges=[],this},a}();b.exports=d});
+!function(a,b){if("function"==typeof define&&define.amd)define("Toposort",["exports","module"],b);else if("undefined"!=typeof exports&&"undefined"!=typeof module)b(exports,module);else{var c={exports:{}};b(c.exports,c),a.Toposort=c.exports}}(this,function(a,b){"use strict";function c(a,b){if(!(a instanceof b))throw new TypeError("Cannot call a class as a function")}var d=function(){function a(){c(this,a),this.edges=[],this.Toposort=a}return a.prototype.add=function(a,b){if("string"!=typeof a||!a)throw new TypeError("Dependent name must be given as a not empty string");if(b=Array.isArray(b)?b:[b],b.length>0)for(var c=b,d=Array.isArray(c),e=0,c=d?c:c[Symbol.iterator]();;){var f;if(d){if(e>=c.length)break;f=c[e++]}else{if(e=c.next(),e.done)break;f=e.value}var g=f;if("string"!=typeof g||!g)throw new TypeError("Dependency name must be given as a not empty string");this.edges.push([a,g])}else this.edges.push([a]);return this},a.prototype.sort=function(){for(var a=this,b=[],c=this.edges,d=Array.isArray(c),e=0,c=d?c:c[Symbol.iterator]();;){var f;if(d){if(e>=c.length)break;f=c[e++]}else{if(e=c.next(),e.done)break;f=e.value}for(var g=f,h=g,i=Array.isArray(h),j=0,h=i?h:h[Symbol.iterator]();;){var k;if(i){if(j>=h.length)break;k=h[j++]}else{if(j=h.next(),j.done)break;k=j.value}var l=k;-1===b.indexOf(l)&&b.push(l)}}for(var m=b.length,n=new Array(b.length),o=function u(c,d){if(0!==d.length&&-1!==d.indexOf(c))throw new Error("Cyclic dependency found. "+c+" is dependent of itself.\nDependency chain: "+d.join(" -> ")+" => "+c);var e=b.indexOf(c);if(-1!==e){var f=!1;b[e]=!1;for(var g=a.edges,h=Array.isArray(g),i=0,g=h?g:g[Symbol.iterator]();;){var j;if(h){if(i>=g.length)break;j=g[i++]}else{if(i=g.next(),i.done)break;j=i.value}var k=j;k[0]===c&&(f=f||d.concat([c]),u(k[1],f))}n[--m]=c}},p=0;p<b.length;p++){var l=b[p];if(l!==!1){b[p]=!1;for(var q=this.edges,r=Array.isArray(q),s=0,q=r?q:q[Symbol.iterator]();;){var t;if(r){if(s>=q.length)break;t=q[s++]}else{if(s=q.next(),s.done)break;t=s.value}var g=t;g[0]===l&&o(g[1],[l])}n[--m]=l}}return n},a.prototype.clear=function(){return this.edges=[],this},a}();b.exports=d});

package.json

 {
-  "name": "toposort-class",
-  "version": "1.0.0",
-  "description": "Topological sort of directed acyclic graphs (like dependecy lists)",
-  "main": "./index.js",
+  "name":            "toposort-class",
+  "version":         "1.0.1",
+  "description":     "Topological sort of directed acyclic graphs (like dependecy lists)",
+  "main":            "./index.js",
   "devDependencies": {
-    "babel-eslint": "^4.0.5",
-    "eslint": "^0.24.1",
-    "grunt": "^0.4.5",
-    "grunt-babel": "^5.0.1",
-    "grunt-banner": "^0.4.0",
-    "grunt-contrib-clean": "^0.6.0",
+    "babel-eslint":         "^4.0.5",
+    "eslint":               "^1.0.0",
+    "grunt":                "^0.4.5",
+    "grunt-babel":          "^5.0.1",
+    "grunt-banner":         "^0.4.0",
+    "grunt-contrib-clean":  "^0.6.0",
     "grunt-contrib-uglify": "^0.9.1",
-    "matcha": "^0.6.0",
-    "mocha": "^2.2.5"
+    "matcha":               "^0.6.0",
+    "mocha":                "^2.2.5"
   },
-  "scripts": {
-    "test": "mocha -b test",
-    "eslint": "eslint src/toposort.js test/spec.js Gruntfile.js",
-    "benchmark": "matcha benchmark/general.js",
+  "scripts":         {
+    "test":           "mocha -b test",
+    "eslint":         "eslint src/toposort.js test/spec.js Gruntfile.js",
+    "benchmark":      "matcha benchmark/general.js",
     "benchmark-save": "matcha -R csv benchmark/general.js > benchmark/results.csv"
   },
-  "repository": {
+  "repository":      {
     "type": "git",
-    "url": "https://github.com/gustavohenke/toposort.git"
+    "url":  "https://github.com/gustavohenke/toposort.git"
   },
-  "keywords": [
+  "keywords":        [
     "topological",
@@ -39,3 +39,3 @@ "sort",
   ],
-  "author": [
+  "author":          [
     "Marcel Klehr <[e-mail]>",
@@ -45,4 +45,4 @@ "Gustavo Henke <[e-mail]>",
   ],
-  "license": "MIT",
-  "readmeFilename": "README.md"
+  "license":         "MIT",
+  "readmeFilename":  "README.md"
 }

README.md

 # Toposort
 [![Build Status](http://img.shields.io/travis/gustavohenke/toposort.svg?branch=master&style=flat)](https://travis-ci.org/gustavohenke/toposort)
-[![devDependency Status](https://img.shields.io/david/gustavohenke/toposort.svg?style=flat)](https://david-dm.org/gustavohenke/toposort#info=devDependencies)
-[![CodeClimate](https://img.shields.io/codeclimate/github/gustavohenke/toposort.svg?style=flat)](https://codeclimate.com/github/gustavohenke/toposort)
+[![Dependency Status](http://img.shields.io/gemnasium/gustavohenke/toposort.png?style=flat)](https://gemnasium.com/gustavohenke/toposort)
 
-__Sorting directed acyclic graphs, for Node.js and  the browser__
+__Sorting directed acyclic graphs, for Node.js, io.js and the browser__
 _This was originally done by Marcel Klehr. [Why not checkout his original repo?](https://github.com/marcelklehr/toposort)_
@@ -50,13 +49,26 @@
 
-## API
-First of all:
+## Usage
+CommonJS (Node.js and io.js):
 ```javascript
 var Toposort = require('toposort-class'),
 	t = new Toposort();
+```
 
-// If you prefer, you can do this way also:
-t = new require('toposort-class').Toposort();
+Browser with AMD:
+```javascript
+define("myModule", ["Toposort"], function(Toposort) {
+    var t = new Toposort();
+});
 ```
 
-### .add(item, deps)
+Browser without AMD:
+```javascript
+var t = new window.Toposort();
+```
+
+or whatever global object there is instead of `window`.
+
+## API
+
+#### `.add(item, deps)`
 * _{String}_ `item` - The name of the dependent item that is being added
@@ -67,3 +79,3 @@ * _{Array|String}_ `deps` - A dependency or list of dependencies of `item`
 
-### .sort()
+#### `.sort()`
 __Returns:__ _{Array}_ The list of dependencies topologically sorted.
@@ -73,3 +85,3 @@
 
-### .clear()
+#### `.clear()`
 __Returns:__ _{Toposort}_ The Toposort instance, for chaining.
@@ -79,3 +91,3 @@
 
-### .Toposort
+#### `.Toposort`
 
@@ -82,0 +94,0 @@ Reference to the Toposort constructor.

Fixed alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

27010

increased by8.62%

Lines of code

390

increased by8.33%

Number of lines in readme file

94

increased by14.63%

Number of medium supply chain risk alerts

0

decreased by-100%

Worsened metrics

Number of package files

13

decreased by-7.14%

No dependency changes