/**** * The MIT License (MIT) * * Copyright (c) 2015 Gustavo Henke and Aaron Trent * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal * in the Software without restriction, including without limitation the rights * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included in all * copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. * ****/ (function( global, factory ) { if( typeof define === "function" && define.amd ) { define( "Toposort", ["exports", "module"], factory ); } else if( typeof exports !== "undefined" && typeof module !== "undefined" ) { factory( exports, module ); } else { var mod = { exports: {} }; factory( mod.exports, mod ); global.Toposort = mod.exports; } })( this, function( exports, module ) { "use strict"; function _classCallCheck( instance, Constructor ) { if( !(instance instanceof Constructor) ) { throw new TypeError( "Cannot call a class as a function" ); } } var Toposort = (function() { function Toposort() { _classCallCheck( this, Toposort ); this.edges = []; this.Toposort = Toposort; } /** * 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 */ Toposort.prototype.add = function add( item, deps ) { if( typeof item !== "string" || !item ) { throw new TypeError( "Dependent name must be given as a not empty string" ); } deps = Array.isArray( deps ) ? deps : [deps]; if( deps.length > 0 ) { for( var _iterator = deps, _isArray = Array.isArray( _iterator ), _i = 0, _iterator = _isArray ? _iterator : _iterator[Symbol.iterator](); ; ) { var _ref; if( _isArray ) { if( _i >= _iterator.length ) { break; } _ref = _iterator[_i++]; } else { _i = _iterator.next(); if( _i.done ) { break; } _ref = _i.value; } var dep = _ref; if( typeof dep !== "string" || !dep ) { throw new TypeError( "Dependency name must be given as a not empty string" ); } this.edges.push( [item, dep] ); } } else { this.edges.push( [item] ); } return this; }; /** * Runs the toposorting and return an ordered array of strings * * @since 0.1.0 * @returns {String[]} The list of items topologically sorted. */ Toposort.prototype.sort = function sort() { var _this = this; var nodes = []; //accumulate unique nodes into a large list for( var _iterator2 = this.edges, _isArray2 = Array.isArray( _iterator2 ), _i2 = 0, _iterator2 = _isArray2 ? _iterator2 : _iterator2[Symbol.iterator](); ; ) { var _ref2; if( _isArray2 ) { if( _i2 >= _iterator2.length ) { break; } _ref2 = _iterator2[_i2++]; } else { _i2 = _iterator2.next(); if( _i2.done ) { break; } _ref2 = _i2.value; } var edge = _ref2; for( var _iterator3 = edge, _isArray3 = Array.isArray( _iterator3 ), _i3 = 0, _iterator3 = _isArray3 ? _iterator3 : _iterator3[Symbol.iterator](); ; ) { var _ref3; if( _isArray3 ) { if( _i3 >= _iterator3.length ) { break; } _ref3 = _iterator3[_i3++]; } else { _i3 = _iterator3.next(); if( _i3.done ) { break; } _ref3 = _i3.value; } var node = _ref3; if( nodes.indexOf( node ) === -1 ) { nodes.push( node ); } } } //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 ); //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: " + predecessors.join( " -> " ) + " => " + node ); } var index = nodes.indexOf( node ); //if the node still exists, traverse its dependencies if( index !== -1 ) { var copy = false; //mark the node as false to exclude it from future iterations nodes[index] = false; //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; } _ref4 = _iterator4[_i4++]; } else { _i4 = _iterator4.next(); if( _i4.done ) { break; } _ref4 = _i4.value; } var edge = _ref4; if( edge[0] === node ) { //lazily create a copy of predecessors with the current node concatenated onto it copy = copy || predecessors.concat( [node] ); //recurse to node dependencies visit( edge[1], copy ); } } //add the node to the next place in the sorted array sorted[--place] = node; } }; for( var i = 0; i < nodes.length; i++ ) { var node = nodes[i]; //ignore nodes that have been excluded if( node !== false ) { //mark the node as false to exclude it from future iterations nodes[i] = false; //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; } } return sorted; }; /** * Clears edges * * @since 0.4.0 * @returns {Toposort} The Toposort instance */ Toposort.prototype.clear = function clear() { this.edges = []; return this; }; return Toposort; })(); module.exports = Toposort; } );