🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

toposort-class

Package Overview
Dependencies
Maintainers
1
Versions
11
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

toposort-class - npm Package Compare versions

Comparing version

0.2.1
to
0.3.0

.gitattributes
.jscs.json
.jshintrc
Gruntfile.js
test/amd.html

10

bower.json
{
"name": "toposort",
"version": "0.2.1",
"main": "./toposort.js",
"ignore": [ "scripts/**", "test/**" ],
"dependencies": {}
"name": "toposort",
"version": "0.3.0",
"main": "./toposort.js",
"ignore": [ "scripts/**", "test/**" ],
"dependencies": {}
}

66

package.json
{
"name": "toposort-class",
"version": "0.2.1",
"description": "Topological sort of directed acyclic graphs (like dependecy lists)",
"main": "./toposort.js",
"devDependencies": {
"mocha": "~1.12.x",
"chai": "~1.7.x"
},
"scripts": {
"test": "mocha",
"pretest": "node scripts/browser-test.js"
},
"repository": {
"type": "git",
"url": "https://github.com/gustavohenke/toposort.git"
},
"keywords": [
"topological",
"sort",
"sorting",
"graphs",
"graph",
"dependency",
"list",
"dependencies",
"acyclic",
"browser"
],
"author": ["Marcel Klehr <mklehr@gmx.net>", "Gustavo Henke <gustavo@injoin.com.br>"],
"license": "MIT",
"readmeFilename": "README.md"
"name": "toposort-class",
"version": "0.3.0",
"description": "Topological sort of directed acyclic graphs (like dependecy lists)",
"main": "./toposort.js",
"devDependencies": {
"requirejs": "~2.1.10",
"chai": "~1.8.1",
"grunt": "~0.4.2",
"grunt-jscs-checker": "~0.3.2",
"grunt-contrib-jshint": "~0.8.0",
"grunt-mocha-test": "~0.8.2",
"grunt-mocha": "~0.4.9"
},
"scripts": {
"test": "grunt"
},
"repository": {
"type": "git",
"url": "https://github.com/gustavohenke/toposort.git"
},
"keywords": [
"topological",
"sort",
"sorting",
"graphs",
"graph",
"dependency",
"list",
"dependencies",
"acyclic",
"browser"
],
"author": ["Marcel Klehr <mklehr@gmx.net>", "Gustavo Henke <gustavo@injoin.com.br>"],
"license": "MIT",
"readmeFilename": "README.md"
}

2

README.md

@@ -1,2 +0,2 @@

# Toposort [![Build Status](https://travis-ci.org/gustavohenke/toposort.png?branch=master)](https://travis-ci.org/gustavohenke/toposort)
# Toposort [![Build Status](https://travis-ci.org/gustavohenke/toposort.png?branch=master)](https://travis-ci.org/gustavohenke/toposort) [![Dependency Status](https://gemnasium.com/gustavohenke/toposort.png)](https://gemnasium.com/gustavohenke/toposort)
__Sorting directed acyclic graphs, for Node.js and the browser__

@@ -3,0 +3,0 @@ _This was originally done by Marcel Klehr. [Why not checkout his original repo?](https://github.com/marcelklehr/toposort)_

118

test/spec.js

@@ -1,67 +0,77 @@

suite( "Toposort", function() {
"use strict";
"use strict";
var expect, Toposort;
!function( suiteSetup ) {
if ( typeof define === "function" && define.amd ) {
define( [ "../toposort", "./lib/chai" ], suiteSetup );
} else {
suiteSetup();
}
}(function( Toposort, chai ) {
var expect = chai ? chai.expect : null;
// Deal with browser/Node environments
if ( typeof window !== "undefined" ) {
expect = window.chai.expect;
Toposort = window.Toposort;
} else {
expect = require( "chai" ).expect;
Toposort = require( ".." );
}
suite( "Toposort", function() {
if ( !Toposort ) {
// Deal with browser/Node environments, if AMD support isn't available
if ( typeof window !== "undefined" ) {
expect = window.chai.expect;
Toposort = window.Toposort;
} else {
expect = require( "chai" ).expect;
Toposort = require( ".." );
}
}
test( "should sort correctly", function() {
var arr, i, fails;
var t = new Toposort();
t.add( "3", "2" )
.add( "2", "1" )
.add( "6", "5" )
.add( "5", [ "2", "4" ] );
test( "should sort correctly", function() {
var arr, fails, possibilities;
var t = new Toposort();
arr = t.sort();
fails = [];
t.add( "3", "2" )
.add( "2", "1" )
.add( "6", "5" )
.add( "5", [ "2", "4" ] );
expect( arr ).to.be.an( "array" );
arr = t.sort();
fails = [];
var possibilities = [
[ "3", "6", "5", "4", "2", "1" ],
[ "3", "6", "5", "2", "4", "1" ],
[ "6", "3", "5", "2", "4", "1" ],
[ "6", "3", "5", "2", "1", "4" ],
[ "6", "5", "3", "2", "1", "4" ],
[ "6", "5", "3", "2", "4", "1" ],
[ "6", "5", "4", "3", "2", "1" ]
];
expect( arr ).to.be.an( "array" );
possibilities.forEach(function( possibility ) {
try {
expect( arr ).to.deep.equal( possibility );
} catch ( e ) {
fails.push( e );
}
});
possibilities = [
[ "3", "6", "5", "4", "2", "1" ],
[ "3", "6", "5", "2", "4", "1" ],
[ "6", "3", "5", "2", "4", "1" ],
[ "6", "3", "5", "2", "1", "4" ],
[ "6", "5", "3", "2", "1", "4" ],
[ "6", "5", "3", "2", "4", "1" ],
[ "6", "5", "4", "3", "2", "1" ]
];
if ( fails.length === possibilities.length ) {
throw fails[ 0 ];
}
});
possibilities.forEach(function( possibility ) {
try {
expect( arr ).to.deep.equal( possibility );
} catch ( e ) {
fails.push( e );
}
});
if ( fails.length === possibilities.length ) {
throw fails[ 0 ];
}
});
test( "should find cyclic dependencies", function() {
var t = new Toposort();
t.add( "3", "2" )
.add( "2", "1" )
.add( "1", "3" )
expect( function() { t.sort(); }).to.throw( Error );
});
test( "should find cyclic dependencies", function() {
var t = new Toposort();
t.add( "3", "2" )
.add( "2", "1" )
.add( "1", "3" );
test( "#2 - should add the item if an empty array of dependencies is passed", function() {
var t = new Toposort();
var out = t.add( "1", [] ).sort();
expect( function() { t.sort(); }).to.throw( Error );
});
expect( out ).to.deep.equal([ "1" ]);
});
test( "#2 - should add the item if an empty array of dependencies is passed", function() {
var t = new Toposort();
var out = t.add( "1", [] ).sort();
expect( out ).to.deep.equal([ "1" ]);
});
});
});

201

toposort.js

@@ -1,108 +0,127 @@

/**
* Topological sort class.
* Original by Marcel Klehr, contributed by Gustavo Henke.
*
* @class
* @since 0.1.0
* @see https://github.com/marcelklehr/toposort
* @author Marcel Klehr <mklehr@gmx.net>
*
* @see https://github.com/gustavohenke/toposort
* @author Gustavo Henke <gustavo@injoin.com.br>
*/
function Toposort() {
"use strict";
var self = this,
edges = [];
!function() {
"use strict";
/**
* Adds dependency edges.
*
* @since 0.1.0
* @param {String} item An dependent name. Must be an string and not empty
* @param {String[]|String} [deps] An dependency or array of dependencies
* @returns {Toposort} The Toposort instance
*/
this.add = function( item, deps ) {
if ( typeof item !== "string" || !item ) {
throw new TypeError( "Dependent name must be given as a not empty string" );
}
/**
* Topological sort class.
* Original by Marcel Klehr, contributed by Gustavo Henke.
*
* @class
* @since 0.1.0
* @see https://github.com/marcelklehr/toposort
* @author Marcel Klehr <mklehr@gmx.net>
*
* @see https://github.com/gustavohenke/toposort
* @author Gustavo Henke <gustavo@injoin.com.br>
*/
function Toposort() {
var self = this;
var edges = [];
deps = Array.isArray( deps ) ? deps.slice() : [ deps ];
if ( deps.length ) {
deps.forEach(function( dep ) {
if ( typeof dep !== "string" || !dep ) {
throw new TypeError( "Dependency name must be given as a not empty string" );
}
/**
* Adds dependency edges.
*
* @since 0.1.0
* @param {String} item An dependent name. Must be an string and not empty
* @param {String[]|String} [deps] An dependency or array of dependencies
* @returns {Toposort} The Toposort instance
*/
self.add = function( item, deps ) {
if ( typeof item !== "string" || !item ) {
throw new TypeError( "Dependent name must be given as a not empty string" );
}
edges.push([ item, dep ]);
});
} else {
edges.push([ item ]);
}
deps = Array.isArray( deps ) ? deps.slice() : [ deps ];
if ( deps.length ) {
deps.forEach(function( dep ) {
if ( typeof dep !== "string" || !dep ) {
throw new TypeError(
"Dependency name must be given as a not empty string"
);
}
return self;
};
edges.push([ item, dep ]);
});
} else {
edges.push([ item ]);
}
/**
* Runs the toposorting and return an ordered array of strings
*
* @since 0.1.0
* @returns {String[]} The list of items topologically sorted.
*/
this.sort = function() {
var nodes = [];
var sorted = [];
return self;
};
edges.forEach(function( edge ) {
edge.forEach(function( n ) {
if ( nodes.indexOf( n ) === -1 ) {
nodes.push( n );
}
});
});
/**
* Runs the toposorting and return an ordered array of strings
*
* @since 0.1.0
* @returns {String[]} The list of items topologically sorted.
*/
self.sort = function() {
var nodes = [];
var sorted = [];
function visit( node, predecessors, i ) {
predecessors = predecessors || [];
edges.forEach(function( edge ) {
edge.forEach(function( n ) {
if ( nodes.indexOf( n ) === -1 ) {
nodes.push( n );
}
});
});
if ( predecessors.indexOf( node ) > -1 ) {
throw new Error( "Cyclic dependency found. '" + node + "' is dependent of itself." );
}
function visit( node, predecessors, i ) {
var index, predsCopy;
predecessors = predecessors || [];
var index = nodes.indexOf( node );
if ( index === -1 ) {
return i;
}
if ( predecessors.indexOf( node ) > -1 ) {
throw new Error(
"Cyclic dependency found. '" + node + "' is dependent of itself."
);
}
nodes.splice( index, 1 );
if ( predecessors.length === 0 ) {
i--;
}
index = nodes.indexOf( node );
if ( index === -1 ) {
return i;
}
var predsCopy = predecessors.slice();
predsCopy.push( node );
nodes.splice( index, 1 );
if ( predecessors.length === 0 ) {
i--;
}
edges.filter(function( e ) {
return e[ 0 ] === node;
}).forEach(function( e ) {
i = visit( e[ 1 ], predsCopy, i );
});
predsCopy = predecessors.slice();
predsCopy.push( node );
sorted.unshift( node );
return i;
}
edges.filter(function( e ) {
return e[ 0 ] === node;
}).forEach(function( e ) {
i = visit( e[ 1 ], predsCopy, i );
});
for ( var i = 0; i < nodes.length; i++ ) {
i = visit( nodes[ i ], null, i );
}
sorted.unshift( node );
return i;
}
return sorted;
};
for ( var i = 0; i < nodes.length; i++ ) {
i = visit( nodes[ i ], null, i );
}
}
return sorted;
};
if ( module && module.exports ) {
module.exports = exports.Toposort = Toposort;
} else if ( window ) {
window.Toposort = Toposort;
}
}
if ( typeof module === "object" && module && typeof module.exports === "object" ) {
// Expose toposort to CommonJS loaders (aka Node)
module.exports = exports.Toposort = Toposort;
} else {
// Expose toposort to AMD loaders (aka Require.js)
if ( typeof define === "function" && define.amd ) {
define(function() {
return Toposort;
});
}
// Expose toposort as a browser global
if ( typeof window === "object" ) {
window.Toposort = Toposort;
}
}
}();
scripts/browser-test.js
test/mocha.opts
.npmignore

Sorry, the diff of this file is not supported yet

.travis.yml

Sorry, the diff of this file is not supported yet

test/index.html

Sorry, the diff of this file is not supported yet