@galaxar/algo - npm Package Compare versions

Comparing version 1.0.2 to 1.0.3

cjs/FiniteStateMachine.js

@@ -1,2 +0,146 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"default",{enumerable:true,get:function(){return _default}});const _utils=require("@galaxar/utils");const _types=require("@galaxar/types");function _define_property(obj,key,value){if(key in obj){Object.defineProperty(obj,key,{value:value,enumerable:true,configurable:true,writable:true})}else{obj[key]=value}return obj}class FiniteStateMachine{async getAllowedActions_(context,withDisallowedReason){const currentState=await this.stateFetcher_(this.app,context);const transitions=this.transitions[currentState];if(!transitions){throw new _types.InvalidArgument(`State "${currentState}" rules not found in the transition table.`)}const allowed=[];const disallowed=[];await (0,_utils.eachAsync_)(transitions,async(rule,action)=>{const[actionAllowed,disallowedReason]=rule.when&&await rule.when(this.app,context)||FiniteStateMachine.OK;if(actionAllowed){allowed.push({action,desc:rule.desc,targetState:rule.target})}else if(withDisallowedReason){disallowed.push({action,desc:rule.desc,targetState:rule.target,reason:disallowedReason})}});const ret={allowed};if(withDisallowedReason){ret.disallowed=disallowed}return ret}async performAction_(action,context,payload,updateOpts,connOpts){const currentState=await this.stateFetcher_(this.app,context,connOpts);const transitions=this.transitions[currentState];if(!transitions){throw new _types.InvalidArgument(`State "${currentState}" rules not found in the transition table.`)}const rule=transitions&&transitions[action];if(!rule){throw new _types.Forbidden(`Action "${action}" is not allowed in "${currentState}" state.`)}if(rule.when){const[allowed,disallowedReason]=await rule.when(this.app,context);if(!allowed){throw new _types.Forbidden(disallowedReason||`The current state does not meet the requirements of "${action}" action.`)}}const entityUpdate=rule.before&&await rule.before(this.app,context,payload)||{...payload};const[actuallyUpdated,updateResult]=await this.stateUpdater_(this.app,context,entityUpdate,rule.target,updateOpts,connOpts);if(actuallyUpdated&&rule.after){await rule.after(this.app,context,connOpts)}return updateResult}constructor(app,transitionTable,stateFetcher,stateUpdater){this.app=app;this.transitions=transitionTable;this.stateFetcher_=stateFetcher;this.stateUpdater_=stateUpdater}}_define_property(FiniteStateMachine,"OK",[true]);_define_property(FiniteStateMachine,"fail",reason=>[false,reason]);_define_property(FiniteStateMachine,"triggerAll_",array=>(...args)=>(0,_utils.eachAsync_)(array,action_=>action_(...args)));_define_property(FiniteStateMachine,"ifAny",array=>async(...args)=>{const l=array.length;const reason=[];for(let i=0;i<l;i++){const checker_=array[i];const[allowed,disallowedReason]=await checker_(...args);if(allowed){return FiniteStateMachine.OK}reason.push(disallowedReason)}return FiniteStateMachine.fail("None of the required conditions met.\n"+reason.join("\n"))});_define_property(FiniteStateMachine,"ifAll",array=>async(...args)=>{const l=array.length;for(let i=0;i<l;i++){const checker_=array[i];const[allowed,disallowedReason]=await checker_(...args);if(!allowed){return FiniteStateMachine.fail(disallowedReason)}}return FiniteStateMachine.OK});const _default=FiniteStateMachine;
+"use strict";
+Object.defineProperty(exports, "__esModule", {
+    value: true
+});
+Object.defineProperty(exports, "default", {
+    enumerable: true,
+    get: function() {
+        return _default;
+    }
+});
+const _utils = require("@galaxar/utils");
+const _types = require("@galaxar/types");
+function _define_property(obj, key, value) {
+    if (key in obj) {
+        Object.defineProperty(obj, key, {
+            value: value,
+            enumerable: true,
+            configurable: true,
+            writable: true
+        });
+    } else {
+        obj[key] = value;
+    }
+    return obj;
+}
+/**
+ *
+ * Action rule:
+ *  desc: description of this transition
+ *  when: pre transition condition check
+ *  target: target state
+ *  before: transforming before applying to the state
+ *  after: trigger another action after transition
+ */ class FiniteStateMachine {
+    /**
+     * Get a list of allowed actions based on the current state.
+     * @param {*} context
+     * @param {boolean} withDisallowedReason
+     */ async getAllowedActions_(context, withDisallowedReason) {
+        const currentState = await this.stateFetcher_(this.app, context);
+        // from state
+        const transitions = this.transitions[currentState];
+        if (!transitions) {
+            throw new _types.InvalidArgument(`State "${currentState}" rules not found in the transition table.`);
+        }
+        const allowed = [];
+        const disallowed = [];
+        await (0, _utils.eachAsync_)(transitions, async (rule, action)=>{
+            const [actionAllowed, disallowedReason] = rule.when && await rule.when(this.app, context) || FiniteStateMachine.OK;
+            if (actionAllowed) {
+                allowed.push({
+                    action,
+                    desc: rule.desc,
+                    targetState: rule.target
+                });
+            } else if (withDisallowedReason) {
+                disallowed.push({
+                    action,
+                    desc: rule.desc,
+                    targetState: rule.target,
+                    reason: disallowedReason
+                });
+            }
+        });
+        const ret = {
+            allowed
+        };
+        if (withDisallowedReason) {
+            ret.disallowed = disallowed;
+        }
+        return ret;
+    }
+    /**
+     * Perform the specified action.
+     * @param {*} action
+     * @param {*} context
+     * @param {*} payload
+     * @param {*} updateOpts
+     * @param {*} connOpts
+     */ async performAction_(action, context, payload, updateOpts, connOpts) {
+        const currentState = await this.stateFetcher_(this.app, context, connOpts);
+        const transitions = this.transitions[currentState];
+        if (!transitions) {
+            throw new _types.InvalidArgument(`State "${currentState}" rules not found in the transition table.`);
+        }
+        const rule = transitions && transitions[action];
+        if (!rule) {
+            throw new _types.Forbidden(`Action "${action}" is not allowed in "${currentState}" state.`);
+        }
+        if (rule.when) {
+            const [allowed, disallowedReason] = await rule.when(this.app, context);
+            if (!allowed) {
+                throw new _types.Forbidden(disallowedReason || `The current state does not meet the requirements of "${action}" action.`);
+            }
+        }
+        const entityUpdate = rule.before && await rule.before(this.app, context, payload) || {
+            ...payload
+        };
+        const [actuallyUpdated, updateResult] = await this.stateUpdater_(this.app, context, entityUpdate, rule.target, updateOpts, connOpts);
+        if (actuallyUpdated && rule.after) {
+            await rule.after(this.app, context, connOpts);
+        }
+        return updateResult;
+    }
+    constructor(app, transitionTable, stateFetcher, stateUpdater){
+        this.app = app;
+        this.transitions = transitionTable;
+        this.stateFetcher_ = stateFetcher;
+        this.stateUpdater_ = stateUpdater;
+    }
+}
+_define_property(FiniteStateMachine, "OK", [
+    true
+]);
+_define_property(FiniteStateMachine, "fail", (reason)=>[
+        false,
+        reason
+    ]);
+_define_property(FiniteStateMachine, "triggerAll_", (array)=>(...args)=>(0, _utils.eachAsync_)(array, (action_)=>action_(...args)));
+_define_property(FiniteStateMachine, "ifAny", (array)=>async (...args)=>{
+        const l = array.length;
+        const reason = [];
+        for(let i = 0; i < l; i++){
+            const checker_ = array[i];
+            const [allowed, disallowedReason] = await checker_(...args);
+            if (allowed) {
+                return FiniteStateMachine.OK;
+            }
+            reason.push(disallowedReason);
+        }
+        return FiniteStateMachine.fail('None of the required conditions met.\n' + reason.join('\n'));
+    });
+_define_property(FiniteStateMachine, "ifAll", (array)=>async (...args)=>{
+        const l = array.length;
+        for(let i = 0; i < l; i++){
+            const checker_ = array[i];
+            const [allowed, disallowedReason] = await checker_(...args);
+            if (!allowed) {
+                return FiniteStateMachine.fail(disallowedReason);
+            }
+        }
+        return FiniteStateMachine.OK;
+    });
+const _default = FiniteStateMachine;
+
 //# sourceMappingURL=FiniteStateMachine.js.map

cjs/Graph.js

@@ -1,2 +0,83 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"default",{enumerable:true,get:function(){return _default}});const _utils=require("@galaxar/utils");const _TopoSort=_interop_require_default(require("./TopoSort"));function _interop_require_default(obj){return obj&&obj.__esModule?obj:{default:obj}}class Graph{hasNode(key){return key in this.nodes}getNode(key){return this.nodes[key]}setNode(key,value){this.nodes[key]=value;return this}setEdge(sourceNode,targetNode){if(!this.hasNode(sourceNode)){throw new Error(`Source node [${sourceNode}] not exists.`)}if(!this.hasNode(targetNode)){throw new Error(`Target node [${targetNode}] not exists.`)}this.topo.add(sourceNode,targetNode);return this}getTargetNodes(sourceNode){return Array.from(this.topo.mapOfDependents[sourceNode])}getSourceNodes(targetNode){return Array.from(this.topo.mapOfDependencies[targetNode])}calcStartEnd(){const seq=this.topo.sort();this.startNodes=_utils._.takeWhile(seq,e=>!this.topo.hasDependency(e));this.endNodes=_utils._.takeRightWhile(seq,e=>!this.topo.hasDependent(e));if(this.startNodes.length===0){this.startNodes=Object.keys(this.nodes)}if(this.endNodes.length===0){this.endNodes=Object.keys(this.nodes)}return this}toJSON(){return{nodes:this.nodes,edges:_utils._.mapValues(this.topo.mapOfDependents,nodes=>Array.from(nodes)),startNodes:this.startNodes,endNodes:this.endNodes}}constructor(json){this.topo=new _TopoSort.default;if(json){this.nodes=_utils._.cloneDeep(json.nodes);if(!_utils._.isEmpty(json.edges)){_utils._.forOwn(json.edges,(targets,source)=>{this.topo.add(source,targets)})}this.startNodes=json.startNodes;this.endNodes=json.endNodes}else{this.nodes={}}}}const _default=Graph;
+"use strict";
+Object.defineProperty(exports, "__esModule", {
+    value: true
+});
+Object.defineProperty(exports, "default", {
+    enumerable: true,
+    get: function() {
+        return _default;
+    }
+});
+const _utils = require("@galaxar/utils");
+const _TopoSort = /*#__PURE__*/ _interop_require_default(require("./TopoSort"));
+function _interop_require_default(obj) {
+    return obj && obj.__esModule ? obj : {
+        default: obj
+    };
+}
+class Graph {
+    hasNode(key) {
+        return key in this.nodes;
+    }
+    getNode(key) {
+        return this.nodes[key];
+    }
+    setNode(key, value) {
+        this.nodes[key] = value;
+        return this;
+    }
+    setEdge(sourceNode, targetNode) {
+        if (!this.hasNode(sourceNode)) {
+            throw new Error(`Source node [${sourceNode}] not exists.`);
+        }
+        if (!this.hasNode(targetNode)) {
+            throw new Error(`Target node [${targetNode}] not exists.`);
+        }
+        this.topo.add(sourceNode, targetNode);
+        return this;
+    }
+    getTargetNodes(sourceNode) {
+        return Array.from(this.topo.mapOfDependents[sourceNode]);
+    }
+    getSourceNodes(targetNode) {
+        return Array.from(this.topo.mapOfDependencies[targetNode]);
+    }
+    calcStartEnd() {
+        const seq = this.topo.sort();
+        this.startNodes = _utils._.takeWhile(seq, (e)=>!this.topo.hasDependency(e));
+        this.endNodes = _utils._.takeRightWhile(seq, (e)=>!this.topo.hasDependent(e));
+        if (this.startNodes.length === 0) {
+            this.startNodes = Object.keys(this.nodes);
+        }
+        if (this.endNodes.length === 0) {
+            this.endNodes = Object.keys(this.nodes);
+        }
+        return this;
+    }
+    toJSON() {
+        return {
+            nodes: this.nodes,
+            edges: _utils._.mapValues(this.topo.mapOfDependents, (nodes)=>Array.from(nodes)),
+            startNodes: this.startNodes,
+            endNodes: this.endNodes
+        };
+    }
+    constructor(json){
+        this.topo = new _TopoSort.default();
+        if (json) {
+            this.nodes = _utils._.cloneDeep(json.nodes);
+            if (!_utils._.isEmpty(json.edges)) {
+                _utils._.forOwn(json.edges, (targets, source)=>{
+                    this.topo.add(source, targets);
+                });
+            }
+            this.startNodes = json.startNodes;
+            this.endNodes = json.endNodes;
+        } else {
+            this.nodes = {};
+        }
+    }
+}
+const _default = Graph;
+
 //# sourceMappingURL=Graph.js.map

cjs/index.js

@@ -1,2 +0,91 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:true});function _export(target,all){for(var name in all)Object.defineProperty(target,name,{enumerable:true,get:all[name]})}_export(exports,{Tree:function(){return _Tree.default},KeyTree:function(){return _Tree.KeyTree},Graph:function(){return _Graph.default},FSM:function(){return _FiniteStateMachine.default},TopoSort:function(){return _TopoSort.default}});const _Tree=_interop_require_wildcard(require("./Tree"));const _Graph=_interop_require_default(require("./Graph"));const _FiniteStateMachine=_interop_require_default(require("./FiniteStateMachine"));const _TopoSort=_interop_require_default(require("./TopoSort"));_export_star(require("./Search"),exports);function _export_star(from,to){Object.keys(from).forEach(function(k){if(k!=="default"&&!Object.prototype.hasOwnProperty.call(to,k)){Object.defineProperty(to,k,{enumerable:true,get:function(){return from[k]}})}});return from}function _interop_require_default(obj){return obj&&obj.__esModule?obj:{default:obj}}function _getRequireWildcardCache(nodeInterop){if(typeof WeakMap!=="function")return null;var cacheBabelInterop=new WeakMap;var cacheNodeInterop=new WeakMap;return(_getRequireWildcardCache=function(nodeInterop){return nodeInterop?cacheNodeInterop:cacheBabelInterop})(nodeInterop)}function _interop_require_wildcard(obj,nodeInterop){if(!nodeInterop&&obj&&obj.__esModule){return obj}if(obj===null||typeof obj!=="object"&&typeof obj!=="function"){return{default:obj}}var cache=_getRequireWildcardCache(nodeInterop);if(cache&&cache.has(obj)){return cache.get(obj)}var newObj={};var hasPropertyDescriptor=Object.defineProperty&&Object.getOwnPropertyDescriptor;for(var key in obj){if(key!=="default"&&Object.prototype.hasOwnProperty.call(obj,key)){var desc=hasPropertyDescriptor?Object.getOwnPropertyDescriptor(obj,key):null;if(desc&&(desc.get||desc.set)){Object.defineProperty(newObj,key,desc)}else{newObj[key]=obj[key]}}}newObj.default=obj;if(cache){cache.set(obj,newObj)}return newObj}
+"use strict";
+Object.defineProperty(exports, "__esModule", {
+    value: true
+});
+function _export(target, all) {
+    for(var name in all)Object.defineProperty(target, name, {
+        enumerable: true,
+        get: all[name]
+    });
+}
+_export(exports, {
+    Tree: function() {
+        return _Tree.default;
+    },
+    KeyTree: function() {
+        return _Tree.KeyTree;
+    },
+    Graph: function() {
+        return _Graph.default;
+    },
+    FSM: function() {
+        return _FiniteStateMachine.default;
+    },
+    TopoSort: function() {
+        return _TopoSort.default;
+    }
+});
+const _Tree = /*#__PURE__*/ _interop_require_wildcard(require("./Tree"));
+const _Graph = /*#__PURE__*/ _interop_require_default(require("./Graph"));
+const _FiniteStateMachine = /*#__PURE__*/ _interop_require_default(require("./FiniteStateMachine"));
+const _TopoSort = /*#__PURE__*/ _interop_require_default(require("./TopoSort"));
+_export_star(require("./Search"), exports);
+function _export_star(from, to) {
+    Object.keys(from).forEach(function(k) {
+        if (k !== "default" && !Object.prototype.hasOwnProperty.call(to, k)) {
+            Object.defineProperty(to, k, {
+                enumerable: true,
+                get: function() {
+                    return from[k];
+                }
+            });
+        }
+    });
+    return from;
+}
+function _interop_require_default(obj) {
+    return obj && obj.__esModule ? obj : {
+        default: obj
+    };
+}
+function _getRequireWildcardCache(nodeInterop) {
+    if (typeof WeakMap !== "function") return null;
+    var cacheBabelInterop = new WeakMap();
+    var cacheNodeInterop = new WeakMap();
+    return (_getRequireWildcardCache = function(nodeInterop) {
+        return nodeInterop ? cacheNodeInterop : cacheBabelInterop;
+    })(nodeInterop);
+}
+function _interop_require_wildcard(obj, nodeInterop) {
+    if (!nodeInterop && obj && obj.__esModule) {
+        return obj;
+    }
+    if (obj === null || typeof obj !== "object" && typeof obj !== "function") {
+        return {
+            default: obj
+        };
+    }
+    var cache = _getRequireWildcardCache(nodeInterop);
+    if (cache && cache.has(obj)) {
+        return cache.get(obj);
+    }
+    var newObj = {};
+    var hasPropertyDescriptor = Object.defineProperty && Object.getOwnPropertyDescriptor;
+    for(var key in obj){
+        if (key !== "default" && Object.prototype.hasOwnProperty.call(obj, key)) {
+            var desc = hasPropertyDescriptor ? Object.getOwnPropertyDescriptor(obj, key) : null;
+            if (desc && (desc.get || desc.set)) {
+                Object.defineProperty(newObj, key, desc);
+            } else {
+                newObj[key] = obj[key];
+            }
+        }
+    }
+    newObj.default = obj;
+    if (cache) {
+        cache.set(obj, newObj);
+    }
+    return newObj;
+}
+
 //# sourceMappingURL=index.js.map

cjs/Search.js

@@ -1,2 +0,80 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:true});function _export(target,all){for(var name in all)Object.defineProperty(target,name,{enumerable:true,get:all[name]})}_export(exports,{bfs:function(){return bfs},dfs:function(){return dfs}});function bfs(root,visit,getChildren){const queue=Array.isArray(root)?[...root]:[root];const visited=new Set;visited.add(root);let found;while(queue.length>0){const node=queue.shift();if(visit(node)){found=node;break}const children=getChildren(node);children?.forEach(child=>{if(!visited.has(child)){visited.add(child);queue.push(child)}})}return found}function dfs(root,visit,getChildren){const stack=Array.isArray(root)?[...root].reverse():[root];const visited=new Set;let found;while(stack.length>0){const node=stack.pop();if(!visited.has(node)){if(visit(node)){found=node;break}visited.add(node);const children=getChildren(node);if(!children||children.length===0){continue}const[leftNode,...right]=children;right.reverse().forEach(child=>{stack.push(child)});stack.push(leftNode)}}return found}
+/**
+ * Perform a breadth-first search on a graph or tree.
+ * @param {Object} root - The root node to start the search from.
+ * @param {Function} visit - A function to call for each visited node, return true to end up the search.
+ * @param {Function} getChildren - A function to get the children of a node.
+ * @returns {Object} The node found
+ */ "use strict";
+Object.defineProperty(exports, "__esModule", {
+    value: true
+});
+function _export(target, all) {
+    for(var name in all)Object.defineProperty(target, name, {
+        enumerable: true,
+        get: all[name]
+    });
+}
+_export(exports, {
+    bfs: function() {
+        return bfs;
+    },
+    dfs: function() {
+        return dfs;
+    }
+});
+function bfs(root, visit, getChildren) {
+    const queue = Array.isArray(root) ? [
+        ...root
+    ] : [
+        root
+    ];
+    const visited = new Set();
+    visited.add(root);
+    let found;
+    while(queue.length > 0){
+        const node = queue.shift();
+        if (visit(node)) {
+            found = node;
+            break;
+        }
+        const children = getChildren(node);
+        children?.forEach((child)=>{
+            if (!visited.has(child)) {
+                visited.add(child);
+                queue.push(child);
+            }
+        });
+    }
+    return found;
+}
+function dfs(root, visit, getChildren) {
+    const stack = Array.isArray(root) ? [
+        ...root
+    ].reverse() : [
+        root
+    ];
+    const visited = new Set();
+    let found;
+    while(stack.length > 0){
+        const node = stack.pop();
+        if (!visited.has(node)) {
+            if (visit(node)) {
+                found = node;
+                break;
+            }
+            visited.add(node);
+            const children = getChildren(node);
+            if (!children || children.length === 0) {
+                continue;
+            }
+            const [leftNode, ...right] = children;
+            right.reverse().forEach((child)=>{
+                stack.push(child);
+            });
+            stack.push(leftNode);
+        }
+    }
+    return found;
+}
+
 //# sourceMappingURL=Search.js.map

cjs/TopoSort.js

@@ -1,2 +0,161 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"default",{enumerable:true,get:function(){return _default}});const _utils=require("@galaxar/utils");function _define_property(obj,key,value){if(key in obj){Object.defineProperty(obj,key,{value:value,enumerable:true,configurable:true,writable:true})}else{obj[key]=value}return obj}class TopoSort{add(dependency,newDependents){newDependents=Array.isArray(newDependents)?newDependents:newDependents==null?[]:[newDependents];const dependents=this.mapOfDependents[dependency];newDependents.forEach(dependent=>{const dependencies=this.mapOfDependencies[dependent];if(!dependencies){this.mapOfDependencies[dependent]=new Set([dependency])}else{dependencies.add(dependency)}if(dependents){dependents.add(dependent)}});if(!dependents){this.mapOfDependents[dependency]=new Set(newDependents)}}depends(node,dependencies){dependencies=Array.isArray(dependencies)?dependencies:dependencies==null?[]:[dependencies];const _dependencies=this.mapOfDependencies[node];if(!_dependencies){this.mapOfDependencies[node]=new Set(dependencies)}else{dependencies.forEach(dependency=>{_dependencies.add(dependency)})}dependencies.forEach(dependency=>{const dependents=this.mapOfDependents[dependency];if(dependents){dependents.add(node)}else{this.mapOfDependents[dependency]=new Set([node])}})}hasDependency(node){return this.mapOfDependencies[node]&&this.mapOfDependencies[node].size>0||false}hasDependent(node){return this.mapOfDependents[node]&&this.mapOfDependents[node].size>0||false}sort(){const l=[];const nodesWithDependents=Object.keys(this.mapOfDependents);const nodesWithDependencies=Object.keys(this.mapOfDependencies);const initialNodes=new Set(nodesWithDependents);nodesWithDependencies.forEach(nodeHasDependency=>initialNodes.delete(nodeHasDependency));const s=[...initialNodes];const allNodes=new Set(nodesWithDependents.concat(nodesWithDependencies));let unsorted=allNodes.size;if(s.length===0&&(nodesWithDependencies.length===0||nodesWithDependents.length===0)){return Array.from(allNodes)}const numWithDependencies=_utils._.mapValues(this.mapOfDependencies,node=>node.size);while(s.length!==0){const n=s.shift();l.push(n);--unsorted;const dependentsOfN=this.mapOfDependents[n];if(dependentsOfN){for(const dependentOfN of dependentsOfN){if(--numWithDependencies[dependentOfN]===0){s.push(dependentOfN)}}}}if(unsorted!==0){const circular=[];for(const node in numWithDependencies){if(numWithDependencies[node]!==0){circular.push(node)}}throw new Error("At least 1 circular dependency in nodes: \n\n"+circular.join("\n")+"\n\nGraph cannot be sorted!")}return l}constructor(){_define_property(this,"mapOfDependents",{});_define_property(this,"mapOfDependencies",{})}}const _default=TopoSort;
+"use strict";
+Object.defineProperty(exports, "__esModule", {
+    value: true
+});
+Object.defineProperty(exports, "default", {
+    enumerable: true,
+    get: function() {
+        return _default;
+    }
+});
+const _utils = require("@galaxar/utils");
+function _define_property(obj, key, value) {
+    if (key in obj) {
+        Object.defineProperty(obj, key, {
+            value: value,
+            enumerable: true,
+            configurable: true,
+            writable: true
+        });
+    } else {
+        obj[key] = value;
+    }
+    return obj;
+}
+/**
+ * @class
+ */ class TopoSort {
+    /**
+     * Add edges(or one edge, if values is non-array).
+     * @param {string} dependency - Incoming node (dependency)
+     * @param {string|array} dependents - Outgoing node or nodes
+     */ add(dependency, newDependents) {
+        // cast to array
+        newDependents = Array.isArray(newDependents) ? newDependents : newDependents == null ? [] : [
+            newDependents
+        ];
+        // get the existing dependents
+        const dependents = this.mapOfDependents[dependency];
+        newDependents.forEach((dependent)=>{
+            // get the existing dependencies
+            const dependencies = this.mapOfDependencies[dependent];
+            if (!dependencies) {
+                // new set of dependencies
+                this.mapOfDependencies[dependent] = new Set([
+                    dependency
+                ]);
+            } else {
+                dependencies.add(dependency);
+            }
+            if (dependents) {
+                dependents.add(dependent);
+            }
+        });
+        if (!dependents) {
+            // new set of dependents
+            this.mapOfDependents[dependency] = new Set(newDependents);
+        }
+    }
+    depends(node, dependencies) {
+        // cast to array
+        dependencies = Array.isArray(dependencies) ? dependencies : dependencies == null ? [] : [
+            dependencies
+        ];
+        // get the existing dependencies
+        const _dependencies = this.mapOfDependencies[node];
+        if (!_dependencies) {
+            // new set of dependencies
+            this.mapOfDependencies[node] = new Set(dependencies);
+        } else {
+            dependencies.forEach((dependency)=>{
+                _dependencies.add(dependency);
+            });
+        }
+        // get the existing dependents
+        dependencies.forEach((dependency)=>{
+            const dependents = this.mapOfDependents[dependency];
+            if (dependents) {
+                dependents.add(node);
+            } else {
+                // new set of dependents
+                this.mapOfDependents[dependency] = new Set([
+                    node
+                ]);
+            }
+        });
+    }
+    hasDependency(node) {
+        return this.mapOfDependencies[node] && this.mapOfDependencies[node].size > 0 || false;
+    }
+    hasDependent(node) {
+        return this.mapOfDependents[node] && this.mapOfDependents[node].size > 0 || false;
+    }
+    /**
+     * Sort the graph. Circular graph throw an error with the circular nodes info.
+     * Implementation of http://en.wikipedia.org/wiki/Topological_sorting#Algorithms
+     * Reference: http://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf
+     * @return {Array} Sorted list
+     */ sort() {
+        // The list contains the final sorted nodes.
+        const l = [];
+        // Find all the initial 0 incoming edge nodes. If not found, this is is a circular graph, cannot be sorted.
+        const nodesWithDependents = Object.keys(this.mapOfDependents);
+        const nodesWithDependencies = Object.keys(this.mapOfDependencies);
+        const initialNodes = new Set(nodesWithDependents);
+        nodesWithDependencies.forEach((nodeHasDependency)=>initialNodes.delete(nodeHasDependency));
+        // List of nodes with no unsorted dependencies
+        const s = [
+            ...initialNodes
+        ];
+        const allNodes = new Set(nodesWithDependents.concat(nodesWithDependencies));
+        // number of unsorted nodes. If it is not zero at the end, this graph is a circular graph and cannot be sorted.
+        let unsorted = allNodes.size;
+        if (s.length === 0 && (nodesWithDependencies.length === 0 || nodesWithDependents.length === 0)) {
+            // only 1 node in the graph, no need to sort.
+            return Array.from(allNodes);
+        }
+        const numWithDependencies = _utils._.mapValues(this.mapOfDependencies, (node)=>node.size);
+        while(s.length !== 0){
+            const n = s.shift();
+            l.push(n);
+            // decrease unsorted count, node n has been sorted.
+            --unsorted;
+            // n node might have no dependency, so have to check it.
+            const dependentsOfN = this.mapOfDependents[n];
+            if (dependentsOfN) {
+                // decease n's adjacent nodes' incoming edges count. If any of them has 0 incoming edges, push them into s get them ready for detaching from the graph.
+                for (const dependentOfN of dependentsOfN){
+                    if (--numWithDependencies[dependentOfN] === 0) {
+                        // no unsorted dependencies
+                        s.push(dependentOfN);
+                    }
+                }
+            }
+        }
+        // If there are unsorted nodes left, this graph is a circular graph and cannot be sorted.
+        // At least 1 circular dependency exist in the nodes with non-zero incoming edges.
+        if (unsorted !== 0) {
+            const circular = [];
+            for(const node in numWithDependencies){
+                if (numWithDependencies[node] !== 0) {
+                    circular.push(node);
+                }
+            }
+            throw new Error('At least 1 circular dependency in nodes: \n\n' + circular.join('\n') + '\n\nGraph cannot be sorted!');
+        }
+        return l;
+    }
+    constructor(){
+        /**
+     * Map of nodes to a set of nodes as dependents, <string, Set.<string>>
+     * @member {object}
+     */ _define_property(this, "mapOfDependents", {});
+        /** -
+     * Map of nodes to a set of nodes as dependencies, <string, Set.<string>>
+     * @member {object}
+     */ _define_property(this, "mapOfDependencies", {});
+    }
+}
+const _default = TopoSort;
+
 //# sourceMappingURL=TopoSort.js.map

cjs/Tree.js

@@ -1,2 +0,244 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:true});function _export(target,all){for(var name in all)Object.defineProperty(target,name,{enumerable:true,get:all[name]})}_export(exports,{KeyTree:function(){return KeyTree},default:function(){return _default}});const _utils=require("@galaxar/utils");function _define_property(obj,key,value){if(key in obj){Object.defineProperty(obj,key,{value:value,enumerable:true,configurable:true,writable:true})}else{obj[key]=value}return obj}const Tree=Node=>{class _class extends Node{find(predicate){let queue=Node.cloneChildrenList(this);while(queue.length>0){const node=queue.shift();if(predicate(node))return node;queue=queue.concat(Node.cloneChildrenList(node))}return undefined}}_define_property(_class,"Node",Node);return _class};class DataNode{static cloneChildrenList(node){return node.children.concat()}get size(){return this.children.length}append(node){node.parent=this;this.children.push(node)}insert(i,node){node.parent=this;this.children.splice(Math.max(0,i),0,node)}remove(node){if(node.parent!==this){throw new Error("Removing a node which is not a child of the current node.")}this.children=_utils._.reject(this.children,n=>n===node);delete node.parent;return node}removeAtIndex(i){const[removed]=this.children.splice(i,1);if(removed){delete removed.parent}return removed}constructor(data){_define_property(this,"children",[]);this.data=data}}class KeyDataNode{static cloneChildrenList(node){return Object.values(node.children)}get size(){return Object.keys(this.children).length}findByKeyPath(keys){keys=keys.concat();if(keys.length===0||keys[0]!==this.key){return undefined}let value={children:{[this.key]:this}};_utils._.find(keys,key=>{value=value.children[key];return typeof value==="undefined"});return value}appendDataByKeyPath(keys,data){keys=keys.concat();if(keys.length===0||keys[0]!==this.key){throw new Error(`The given key path "${keys.join(" / ")}" is not starting from the correct initial key "${this.key}".`)}const lastKey=keys.pop();let lastNode={children:{[this.key]:this}};let node;_utils._.each(keys,key=>{if(key in lastNode.children){lastNode=lastNode.children[key]}else{node=new KeyDataNode(key);lastNode.append(node);lastNode=node}});node=new KeyDataNode(lastKey,data);lastNode.append(node);return node}append(node){node.parent=this;if(node.key in this.children){throw new Error(`Duplicate node key: ${node.key}`)}this.children[node.key]=node}remove(node){if(node.parent!==this||!(node.key in this.children)){throw new Error("Removing a node which is not a child of the current node.")}delete this.children[node.key];delete node.parent;return node}getKeyPath(){const paths=[this.key];let curr=this;while(curr.parent){curr=curr.parent;paths.push(curr.key)}return paths.reverse()}constructor(key,data){_define_property(this,"children",{});this.key=key;this.data=data}}const KeyTree=Tree(KeyDataNode);const _default=Tree(DataNode);
+"use strict";
+Object.defineProperty(exports, "__esModule", {
+    value: true
+});
+function _export(target, all) {
+    for(var name in all)Object.defineProperty(target, name, {
+        enumerable: true,
+        get: all[name]
+    });
+}
+_export(exports, {
+    KeyTree: function() {
+        return KeyTree;
+    },
+    default: function() {
+        return _default;
+    }
+});
+const _utils = require("@galaxar/utils");
+function _define_property(obj, key, value) {
+    if (key in obj) {
+        Object.defineProperty(obj, key, {
+            value: value,
+            enumerable: true,
+            configurable: true,
+            writable: true
+        });
+    } else {
+        obj[key] = value;
+    }
+    return obj;
+}
+/**
+ * A closure function to be called to check the data of each node whether meets certain condition
+ * @callback predicateFunction
+ * @param {Node} node
+ * @returns {boolean}
+ */ /**
+ * Tree factory.
+ * @param {Node} Node
+ * @returns {Tree}
+ */ const Tree = (Node)=>{
+    class _class extends Node {
+        /**
+         * Find a node by BFS.
+         * @param {predicateFunction} predicate
+         */ find(predicate) {
+            let queue = Node.cloneChildrenList(this);
+            while(queue.length > 0){
+                const node = queue.shift();
+                if (predicate(node)) return node;
+                queue = queue.concat(Node.cloneChildrenList(node));
+            }
+            return undefined;
+        }
+    }
+    _define_property(_class, "Node", Node);
+    return _class;
+};
+/**
+ * Tree node with data property.
+ * @class
+ */ class DataNode {
+    static cloneChildrenList(node) {
+        return node.children.concat();
+    }
+    /**
+     * Number of nodes.
+     * @member {number}
+     */ get size() {
+        return this.children.length;
+    }
+    /**
+     * Append the given node to the end of the children list.
+     * @param {DataNode} node
+     */ append(node) {
+        node.parent = this;
+        this.children.push(node);
+    }
+    /**
+     * Insert the given node at specified index in the children list.
+     * @param {number} i
+     * @param {DataNode} node
+     */ insert(i, node) {
+        node.parent = this;
+        this.children.splice(Math.max(0, i), 0, node);
+    }
+    /**
+     * Remove the given node from the branch.
+     * @param {DataNode} node
+     * @returns {DataNode}
+     */ remove(node) {
+        if (node.parent !== this) {
+            throw new Error('Removing a node which is not a child of the current node.');
+        }
+        this.children = _utils._.reject(this.children, (n)=>n === node);
+        delete node.parent;
+        return node;
+    }
+    /**
+     * Remove the node at the given index from the branch.
+     * @param {number} i
+     * @returns {DataNode}
+     */ removeAtIndex(i) {
+        const [removed] = this.children.splice(i, 1);
+        if (removed) {
+            delete removed.parent;
+        }
+        return removed;
+    }
+    /**
+     * Create a data node with given data.
+     * @param {*} data
+     */ constructor(data){
+        /**
+     * Array of children nodes.
+     * @member {array}
+     */ _define_property(this, "children", []);
+        /**
+         * Data property.
+         * @member {*}
+         */ this.data = data;
+    }
+}
+/**
+ * Tree node with key property and data property.
+ * @class
+ */ class KeyDataNode {
+    static cloneChildrenList(node) {
+        return Object.values(node.children);
+    }
+    /**
+     * Number of nodes.
+     * @member {number}
+     */ get size() {
+        return Object.keys(this.children).length;
+    }
+    /**
+     * Fina a node by path being an array of keys.
+     * @param {array.<string>} keys
+     */ findByKeyPath(keys) {
+        keys = keys.concat();
+        if (keys.length === 0 || keys[0] !== this.key) {
+            return undefined;
+        }
+        let value = {
+            children: {
+                [this.key]: this
+            }
+        };
+        _utils._.find(keys, (key)=>{
+            value = value.children[key];
+            return typeof value === 'undefined';
+        });
+        return value;
+    }
+    /**
+     * Append data by path being an array of keys.
+     * @param {array.<string>} keys
+     * @param {*} data
+     * @returns {KeyDataNode} The newly created node containing the data.
+     */ appendDataByKeyPath(keys, data) {
+        keys = keys.concat();
+        if (keys.length === 0 || keys[0] !== this.key) {
+            throw new Error(`The given key path "${keys.join(' / ')}" is not starting from the correct initial key "${this.key}".`);
+        }
+        const lastKey = keys.pop();
+        let lastNode = {
+            children: {
+                [this.key]: this
+            }
+        };
+        let node;
+        _utils._.each(keys, (key)=>{
+            if (key in lastNode.children) {
+                lastNode = lastNode.children[key];
+            } else {
+                node = new KeyDataNode(key);
+                lastNode.append(node);
+                lastNode = node;
+            }
+        });
+        node = new KeyDataNode(lastKey, data);
+        lastNode.append(node);
+        return node;
+    }
+    /**
+     * Append the given node to the end of the children list.
+     * @param {KeyDataNode} node
+     */ append(node) {
+        node.parent = this;
+        if (node.key in this.children) {
+            throw new Error(`Duplicate node key: ${node.key}`);
+        }
+        this.children[node.key] = node;
+    }
+    /**
+     * Remove the given node from the branch.
+     * @param {KeyDataNode} node
+     */ remove(node) {
+        if (node.parent !== this || !(node.key in this.children)) {
+            throw new Error('Removing a node which is not a child of the current node.');
+        }
+        delete this.children[node.key];
+        delete node.parent;
+        return node;
+    }
+    /**
+     * Get key path of current node (a key chain from root to itself).
+     * @returns {array}
+     */ getKeyPath() {
+        const paths = [
+            this.key
+        ];
+        let curr = this;
+        while(curr.parent){
+            curr = curr.parent;
+            paths.push(curr.key);
+        }
+        return paths.reverse();
+    }
+    /**
+     * Create a key-data node with key and given data.
+     * @param {string} key
+     * @param {*} data
+     */ constructor(key, data){
+        /**
+     * Map of keys to children nodes.
+     * @member {object}
+     */ _define_property(this, "children", {});
+        /**
+         * Node key.
+         * @member {string}
+         */ this.key = key;
+        /**
+         * Data property.
+         * @member {*}
+         */ this.data = data;
+    }
+}
+const KeyTree = Tree(KeyDataNode);
+const _default = Tree(DataNode);
+
 //# sourceMappingURL=Tree.js.map

package.json

 {
   "name": "@galaxar/algo",
-  "version": "1.0.2",
+  "version": "1.0.3",
   "description": "Galaxar algorithm",
@@ -8,2 +8,12 @@ "main": "cjs/index.js",
   "react-native": "lib/index.js",
+  "exports": {
+    ".": {
+      "import": "./lib/index.js",
+      "require": "./cjs/index.js"
+    },
+    "./*": {
+      "import": "./lib/*.js",
+      "require": "./cjs/*.js"
+    }
+  },
   "publishConfig": {
@@ -28,4 +38,4 @@ "access": "public"
   "dependencies": {
-    "@galaxar/types": "1.0.2",
-    "@galaxar/utils": "1.0.2"
+    "@galaxar/utils": "1.0.4",
+    "@galaxar/types": "1.0.3"
   },
@@ -32,0 +42,0 @@ "prettier": {

New alerts

License Policy Violation

License

This 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

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Minified code

Quality

This package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

85860

increased by17.24%

Lines of code

1413

increased by109.33%

Number of low quality alerts

1

decreased by-83.33%

Dependency changes

• + Added@galaxar/types@1.0.3(transitive)

• + Added@galaxar/utils@1.0.4(transitive)

• - Removed@galaxar/types@1.0.2(transitive)

• - Removed@galaxar/utils@1.0.2(transitive)

• Updated@galaxar/types@1.0.3

• Updated@galaxar/utils@1.0.4