ts-structures - npm Package Compare versions

Comparing version 0.5.6 to 0.5.7

graph/list-graph.d.ts

 import type { FilterFunction, ReduceFunction, TraverseCallback } from '../_shared/types';
 import type { Graph, GraphOptions } from '.';
 /**
- * Represents a single weight connection from one vertex to another.
+ * Represents a weighted and directed connection from one vertex to another.
  */
 declare class Edge {
     /**
-     * The origin vertex.
+     * The origin vertex id.
      */
     from: string;
     /**
-     * The destination vertex.
+     * The destination vertex id.
      */
@@ -20,3 +20,3 @@ to: string;
     /**
-     * Creates a new edge connecting two vertices with given weight.
+     * Creates a new weighted edge connecting two vertices.
      *
@@ -36,3 +36,3 @@ * @param from - The origin vertex.
 /**
- * Represents a node in a graph. It consists of a unique id, an associated data
+ * Represents a node in a graph. It consists of a unique id, a value
  * and a collection of edges connecting it to other vertices.
@@ -46,19 +46,19 @@ */
     /**
-     * Data carried by the vertex.
+     * The vertex value.
      */
-    data: T;
+    value: T;
     /**
      * A collection of edges stored in a Map for quick access
-     * a insert/remove operations.
+     * and insert/remove operations.
      */
     private _edges;
     /**
-     * Returns a new `Vertex`with a **unique id** and associated data.
+     * Returns a new `Vertex` with a **unique id** and associated value.
      *
      * @param id - Unique id in graph scope.
-     * @param data - The carried data.
+     * @param value - The vertex value.
      */
-    constructor(id: string, data: T);
+    constructor(id: string, value: T);
     /**
-     * Prevents from altering the vertex once create.
+     * Prevents from altering the vertex once created.
      * Might change strategy later?
@@ -102,10 +102,2 @@ */
     /**
-     * Whether the edges should be assigner a weight value.
-     * Note: unused for now. A weight can be added no matter
-     * this value, and if not a default value is used.
-     *
-     * @defaultValue `false`
-     */
-    private isWeighted;
-    /**
      * The default weight value to add to the edges.
@@ -116,3 +108,3 @@ *
     private defaultWeight;
-    constructor(options?: GraphOptions | undefined);
+    constructor(options?: GraphOptions);
     /**
@@ -161,16 +153,17 @@ * The number of vertices.
     /**
-     * Adds a new vertex, referenced with a **unique** id, holding given data.
+     * Adds a new vertex, referenced with a **unique** id, of given value.
      * If the given id is already used, the insertion is aborted.
      *
      * @param id - The vertex ID.  **Must be unique**
-     * @param data - Additionnal data.
+     * @param value - The vertex value.
      * @returns `true` or `false` if it failed to insert.
      */
-    addVertex(id: string, data: T): boolean;
+    addVertex(id: string, value: T): boolean;
     /**
-     * Adds new vertices from given tuples [id, data]
+     * Adds new vertices from given tuples [id, value]
      *
      * @param vertices - The tuples separated by a comma
+     * @returns The number of added vertices.
      */
-    addVertices(...vertices: [string, T][]): void;
+    addVertices(...vertices: [string, T][]): number;
     /**
@@ -184,3 +177,3 @@ * Removes vertex qith given id and its related edges.
     /**
-     * Removes all related edges to a vertex. The associated data persists.
+     * Removes all related edges to a vertex. Its value persists.
      *
@@ -187,0 +180,0 @@ * @param id - id if the vertex to be removed.

graph/list-graph.js

@@ -7,7 +7,7 @@ "use strict";
 /**
- * Represents a single weight connection from one vertex to another.
+ * Represents a weighted and directed connection from one vertex to another.
  */
 class Edge {
     /**
-     * Creates a new edge connecting two vertices with given weight.
+     * Creates a new weighted edge connecting two vertices.
      *
@@ -36,3 +36,3 @@ * @param from - The origin vertex.
 /**
- * Represents a node in a graph. It consists of a unique id, an associated data
+ * Represents a node in a graph. It consists of a unique id, a value
  * and a collection of edges connecting it to other vertices.
@@ -42,10 +42,10 @@ */
     /**
-     * Returns a new `Vertex`with a **unique id** and associated data.
+     * Returns a new `Vertex` with a **unique id** and associated value.
      *
      * @param id - Unique id in graph scope.
-     * @param data - The carried data.
+     * @param value - The vertex value.
      */
-    constructor(id, data) {
+    constructor(id, value) {
         this.id = id;
-        this.data = data;
+        this.value = value;
         this._edges = new Map();
@@ -55,3 +55,3 @@ this.lock();
     /**
-     * Prevents from altering the vertex once create.
+     * Prevents from altering the vertex once created.
      * Might change strategy later?
@@ -108,3 +108,3 @@ */
     constructor(options) {
-        var _a, _b, _c;
+        var _a, _b;
         /**
@@ -122,10 +122,2 @@ * The data source containing all vertices and edges, using
         /**
-         * Whether the edges should be assigner a weight value.
-         * Note: unused for now. A weight can be added no matter
-         * this value, and if not a default value is used.
-         *
-         * @defaultValue `false`
-         */
-        this.isWeighted = false;
-        /**
          * The default weight value to add to the edges.
@@ -138,4 +130,3 @@ *
             this.isDirected = (_a = options.directed) !== null && _a !== void 0 ? _a : this.isDirected;
-            this.isWeighted = (_b = options.weighted) !== null && _b !== void 0 ? _b : this.isWeighted;
-            this.defaultWeight = (_c = options.defaultWeight) !== null && _c !== void 0 ? _c : this.defaultWeight;
+            this.defaultWeight = (_b = options.defaultWeight) !== null && _b !== void 0 ? _b : this.defaultWeight;
         }
@@ -209,22 +200,25 @@ }
     /**
-     * Adds a new vertex, referenced with a **unique** id, holding given data.
+     * Adds a new vertex, referenced with a **unique** id, of given value.
      * If the given id is already used, the insertion is aborted.
      *
      * @param id - The vertex ID.  **Must be unique**
-     * @param data - Additionnal data.
+     * @param value - The vertex value.
      * @returns `true` or `false` if it failed to insert.
      */
-    addVertex(id, data) {
+    addVertex(id, value) {
         if (this.data.has(id))
             return false;
-        this.data.set(id, new Vertex(id, data));
+        this.data.set(id, new Vertex(id, value));
         return true;
     }
     /**
-     * Adds new vertices from given tuples [id, data]
+     * Adds new vertices from given tuples [id, value]
      *
      * @param vertices - The tuples separated by a comma
+     * @returns The number of added vertices.
      */
     addVertices(...vertices) {
-        vertices.forEach(([id, data]) => this.addVertex(id, data));
+        let c = 0;
+        vertices.forEach(([id, value]) => this.addVertex(id, value) && c++);
+        return c;
     }
@@ -244,3 +238,3 @@ /**
     /**
-     * Removes all related edges to a vertex. The associated data persists.
+     * Removes all related edges to a vertex. Its value persists.
      *
@@ -254,3 +248,3 @@ * @param id - id if the vertex to be removed.
             return false;
-        return this.removeVertex(id) && this.addVertex(vertex.id, vertex.data);
+        return this.removeVertex(id) && this.addVertex(vertex.id, vertex.value);
     }
@@ -269,12 +263,7 @@ /**
     addEdge(from, to, weight = this.defaultWeight) {
-        const { srcVertex, dstVertex, isSafeAdd, } = this.checkEdgeOps(from, to);
-        if (!isSafeAdd)
-            return false;
-        const srcAdded = srcVertex === null || srcVertex === void 0 ? void 0 : srcVertex.addEdge(new Edge(from, to, weight));
-        return this.isDirected
-            ? !!srcAdded
-            : !!srcAdded && !!(dstVertex === null || dstVertex === void 0 ? void 0 : dstVertex.addEdge(new Edge(to, from, weight)));
-        // return !!srcAdded && (this.isDirected
-        //     ? true
-        //     : !!dstVertex?.addEdge(new Edge(to, from, weight)))
+        const { srcVertex, dstVertex, isSafeAdd } = this.checkEdgeOps(from, to);
+        const add = (vtx, from, to) => vtx.addEdge(new Edge(from, to, weight));
+        return isSafeAdd
+            && !!add(srcVertex, from, to)
+            && (this.isDirected || !!add(dstVertex, to, from));
     }
@@ -292,10 +281,7 @@ /**
     removeEdge(from, to) {
-        const { srcVertex, dstVertex, isSafeRem, } = this.checkEdgeOps(from, to);
-        if (!isSafeRem)
-            return false;
-        const srcRemoved = srcVertex === null || srcVertex === void 0 ? void 0 : srcVertex.removeEdge(to);
-        if (this.isDirected)
-            return !!srcRemoved;
-        const dstRemoved = dstVertex === null || dstVertex === void 0 ? void 0 : dstVertex.removeEdge(from);
-        return !!srcRemoved && !!dstRemoved;
+        const { srcVertex, dstVertex, isSafeRem } = this.checkEdgeOps(from, to);
+        const remove = (vtx, to) => vtx.removeEdge(to);
+        return isSafeRem
+            && !!remove(srcVertex, to)
+            && (this.isDirected || !!remove(dstVertex, from));
     }
@@ -416,2 +402,3 @@ /**
         var _a;
+        const isExcluded = (vtx) => filter && !filter(vtx);
         const pqueue = new queue_1.PriorityQueue();
@@ -424,3 +411,5 @@ const distances = new Map();
         // initialize
-        this.data.forEach((_, id) => {
+        this.data.forEach((vtx, id) => {
+            if (isExcluded(vtx))
+                return;
             if (id === from) {
@@ -448,9 +437,9 @@ distances.set(id, 0);
             (_a = this.get(smallest)) === null || _a === void 0 ? void 0 : _a.forEachEdge(({ to, weight }) => {
-                if (filter && !filter(this.get(to)))
+                if (isExcluded(this.get(to)))
                     return;
-                const candidate = distances.get(smallest) + weight;
-                if (candidate < distances.get(to)) {
-                    distances.set(to, candidate);
+                const newDistance = distances.get(smallest) + weight;
+                if (newDistance < distances.get(to)) {
+                    distances.set(to, newDistance);
                     previous.set(to, smallest);
-                    pqueue.enqueue(to, candidate);
+                    pqueue.enqueue(to, newDistance);
                 }
@@ -463,3 +452,3 @@ });
     traverseDFSRecursive(rootId, callback) {
-        const visited = new Set();
+        const done = new Set();
         const recurse = (currentId) => {
@@ -470,5 +459,5 @@ const currentVertex = this.get(currentId);
             callback(currentVertex);
-            visited.add(currentVertex.id);
+            done.add(currentVertex.id);
             currentVertex.forEachEdge(({ to }) => {
-                if (!visited.has(to))
+                if (!done.has(to))
                     recurse(to);
@@ -505,13 +494,13 @@ });
             return;
-        const queue = new queue_1.Queue();
-        const visited = new Set();
-        queue.enqueue(rootId);
-        visited.add(rootId);
-        let currentId = rootId;
-        while (currentId = queue.dequeue()) { // eslint-disable-line no-cond-assign
+        const seen = new queue_1.Queue();
+        const done = new Set();
+        seen.enqueue(rootId);
+        done.add(rootId);
+        let currentId;
+        while (currentId = seen.dequeue()) { // eslint-disable-line no-cond-assign
             const currentVertex = this.get(currentId);
             currentVertex.forEachEdge(({ to }) => {
-                if (!visited.has(to)) {
-                    queue.enqueue(to);
-                    visited.add(to);
+                if (!done.has(to)) {
+                    seen.enqueue(to);
+                    done.add(to);
                 }
@@ -518,0 +507,0 @@ });

package.json

 {
   "name": "ts-structures",
-  "version": "0.5.6",
+  "version": "0.5.7",
   "description": "TypeScript implementation of common data structures",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

 # TypeScript Datastructures
 
 [![Build Status](https://img.shields.io/travis/gregoryalbouy/ts-datastructures/master)](https://travis-ci.org/GregoryAlbouy/ts-datastructures)
+[![Codacy](https://img.shields.io/codacy/grade/61dc898b0eaf4ba6bfea22eed767e74b/master)](https://www.codacy.com/)
 [![codecov](https://img.shields.io/codecov/c/github/gregoryalbouy/ts-datastructures)](https://codecov.io/gh/GregoryAlbouy/ts-datastructures/branch/master)
@@ -17,7 +18,7 @@ [![NPM version](https://img.shields.io/npm/v/ts-structures)](https://www.npmjs.org/package/ts-structures)
 
-- :dna:  Understanding data structures
-- :vertical_traffic_light:  Keeping clean code and good coding practices
-- :white_check_mark:  Making relevant tests with high coverage rate
-- :arrows_counterclockwise:  Using Continuous Integration tools
-- :blue_book:  Maintaining a fully documented codebase
+  - :dna:  Understanding data structures
+  - :vertical_traffic_light:  Keeping clean code and good coding practices
+  - :white_check_mark:  Making relevant tests with high coverage rate
+  - :arrows_counterclockwise:  Using Continuous Integration tools
+  - :blue_book:  Maintaining a fully documented codebase
 
@@ -45,9 +46,9 @@ Feedback of any kind is always appreciated!
 
-- [Doubly Linked List](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_list_doubly_linked_list_.doublylinkedlist.html)
-- [Queue](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_queue_queue_.queue.html)
-- [Priority Queue](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_queue_priority_queue_.priorityqueue.html)
-- [Stack](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_stack_stack_.stack.html)
-- [Binary Search Tree](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_tree_binary_search_tree_.binarysearchtree.html)
-- [Binary Heap](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_heap_binary_heap_.binaryheap.html)
-- [Graph](https://gregoryalbouy-ts-datastructures.netlify.app/interfaces/_graph_index_.graph.html)
+  - [Doubly Linked List](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_list_doubly_linked_list_.doublylinkedlist.html)
+  - [Queue](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_queue_queue_.queue.html)
+  - [Priority Queue](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_queue_priority_queue_.priorityqueue.html)
+  - [Stack](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_stack_stack_.stack.html)
+  - [Binary Search Tree](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_tree_binary_search_tree_.binarysearchtree.html)
+  - [Binary Heap](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_heap_binary_heap_.binaryheap.html)
+  - [Graph](https://gregoryalbouy-ts-datastructures.netlify.app/interfaces/_graph_index_.graph.html)
     - [List Graph](https://gregoryalbouy-ts-datastructures.netlify.app/classes/_graph_list_graph_.listgraph.html) (Adjacency list based graph, optionnally directed or weighted)
@@ -58,5 +59,5 @@ - Matrix Graph (Adjacency matrix based graph): *in progress*
 
-- Graph implementation
+  - Graph implementation
     - Refacto *in progress*
     - MatrixGraph
-- More data structures
+  - More data structures

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

Improved metrics

Number of lines in readme file

60

increased by1.69%

Worsened metrics

Total package byte prevSize

98989

decreased by-0.81%

Lines of code

2637

decreased by-0.68%

No dependency changes