graphs-and-paths - npm Package Compare versions

Comparing version 0.1.3 to 0.1.4

dist/graph.d.ts

@@ -7,2 +7,3 @@ import { Edge, EdgeId, EdgePoint, Location, Node, NodeId, Path, SimpleEdge, SimpleNode } from "./types";
     static create(nodes: SimpleNode[], edges: SimpleEdge[]): Graph;
+    static advanceAlongLocations(locations: Location[], distance: number): Location[];
     private constructor(nodesById, edgesById, mesh?);
@@ -26,4 +27,6 @@ getAllNodes(): Node[];
      * dropped.
+     *
+     * Throws an error if distance is negative.
      */
-    advancePath(path: Path, distance: number): Path;
+    advanceAlongPath(path: Path, distance: number): Path;
     withClosestPointMesh(precision: number): Graph;
@@ -53,4 +56,5 @@ getClosestPoint(location: Location): EdgePoint;
     private getShortestPathOnSameEdge(start, end);
+    private getLocationsOnEdgeInterval(edgeId, startDistance, endDistance);
     private getClosestPointWithMesh(location, mesh);
     private getClosestPointWithoutMesh(location);
 }

dist/graph.js

@@ -40,3 +40,3 @@ "use strict";
             var locationDistances = Utils.getCumulativeDistances(locations);
-            var length = locationDistances[locationDistances.length - 1];
+            var length = Utils.last(locationDistances);
             start.edgeIds.push(id);
@@ -56,2 +56,26 @@ end.edgeIds.push(id);
     };
+    Graph.advanceAlongLocations = function (locations, distance) {
+        if (distance < 0) {
+            throw new Error("Cannot advance path by negative distance");
+        }
+        else if (distance === 0) {
+            return locations;
+        }
+        else {
+            var remainingDistance = distance;
+            var locationIndex = 0;
+            while (locationIndex < locations.length - 1) {
+                var segmentStart = locations[locationIndex];
+                var segmentEnd = locations[locationIndex + 1];
+                var segmentLength = Utils.distanceBetween(segmentStart, segmentEnd);
+                if (remainingDistance < segmentLength) {
+                    var newStartPoint = Utils.getIntermediateLocation(segmentStart, segmentEnd, remainingDistance);
+                    return [newStartPoint].concat(locations.slice(locationIndex + 1));
+                }
+                locationIndex++;
+                remainingDistance -= segmentLength;
+            }
+            return [Utils.last(locations)];
+        }
+    };
     Graph.prototype.getAllNodes = function () {
@@ -121,14 +145,11 @@ return Array.from(this.nodesById.values());
                 var firstEdge = path[0];
-                var lastEdge = path[path.length - 1];
+                var lastEdge = Utils.last(path);
                 var startNodeId_1 = firstEdge.isForward ? firstEdge.edge.startNodeId : firstEdge.edge.endNodeId;
                 var endNodeId_1 = lastEdge.isForward ? lastEdge.edge.endNodeId : lastEdge.edge.startNodeId;
                 var minEdgeId = Utils.min(path.map(function (pathEdge) { return pathEdge.edge.id; }), Utils.compareIds);
-                var innerLocations = Utils.flatMap(path, function (pathEdge) {
-                    // Take the locations from each edge omitting the endpoint to avoid
-                    // double-counting nodes. Slice off the first location at the end to be left
-                    // with inner locations only.
+                var locations = Utils.dedupeLocations(Utils.flatMap(path, function (pathEdge) {
                     var locations = pathEdge.edge.locations, isForward = pathEdge.isForward;
-                    var orientedLocations = isForward ? locations : locations.slice().reverse();
-                    return orientedLocations.slice(0, orientedLocations.length - 1);
-                }).slice(1);
+                    return isForward ? locations : locations.slice().reverse();
+                }));
+                var innerLocations = locations.slice(1, locations.length - 1);
                 var newEdge = {
@@ -252,5 +273,7 @@ id: minEdgeId,
      * dropped.
+     *
+     * Throws an error if distance is negative.
      */
-    Graph.prototype.advancePath = function (path, distance) {
-        var start = path.start, end = path.end, orientedEdges = path.orientedEdges, nodes = path.nodes, length = path.length;
+    Graph.prototype.advanceAlongPath = function (path, distance) {
+        var start = path.start, end = path.end, orientedEdges = path.orientedEdges, nodes = path.nodes, locations = path.locations, length = path.length;
         if (distance === 0) {
@@ -263,7 +286,11 @@ return path;
                 end: end,
-                orientedEdges: [orientedEdges[orientedEdges.length - 1]],
+                orientedEdges: [Utils.last(orientedEdges)],
                 nodes: [],
+                locations: [Utils.last(path.locations)],
                 length: 0,
             };
         }
+        else if (distance < 0) {
+            throw new Error("Cannot advance path by a negative distance");
+        }
         else {
@@ -289,2 +316,3 @@ var _a = orientedEdges[0], startEdge = _a.edge, isStartEdgeForward = _a.isForward;
                 nodes: nodes.slice(edgeIndex),
+                locations: Graph.advanceAlongLocations(locations, distance),
                 length: length - distance,
@@ -307,3 +335,3 @@ };
         this.getAllEdges().forEach(function (edge) {
-            var edgeId = edge.id, length = edge.length, locations = edge.locations, locationDistances = edge.locationDistances;
+            var edgeId = edge.id, length = edge.length, locationDistances = edge.locationDistances;
             var numSegments = Math.ceil(length / precision);
@@ -357,3 +385,3 @@ var stepDistance = length / numSegments;
         var forwardPath = this.getOnlyPathInDirection({ edge: edge, isForward: true });
-        if (forwardPath.length > 1 && forwardPath[0] === forwardPath[forwardPath.length - 1]) {
+        if (forwardPath.length > 1 && forwardPath[0] === Utils.last(forwardPath)) {
             // We are in a loop.
@@ -404,4 +432,3 @@ return forwardPath.slice(0, forwardPath.length - 1);
             var endEdge = this.getEdgeOrThrow(end.edgeId);
-            // Build nodes and oriented edge lists starting from end, then reverse.
-            var nodes = [];
+            // Build nodes, oriented edge, and location lists starting from end, then reverse.
             var orientedEdges = [{
@@ -411,2 +438,4 @@ edge: endEdge,
                 }];
+            var nodes = [];
+            var locations = this.getLocationsOnEdgeInterval(end.edgeId, end.distance, endEdgeIsForward ? 0 : this.getEdgeOrThrow(end.edgeId).length);
             var currentNodeId_1 = endEdgeIsForward ? endEdge.startNodeId : endEdge.endNodeId;
@@ -422,2 +451,4 @@ while (true) {
                     orientedEdges.push({ edge: currentEdge, isForward: isForward });
+                    var newLocations = isForward ? currentEdge.locations.slice().reverse() : currentEdge.locations;
+                    Utils.pushAll(locations, newLocations);
                     currentNodeId_1 = this.getOtherEndpoint(currentEdge.id, currentNodeId_1).id;
@@ -436,5 +467,11 @@ }
             orientedEdges.push({ edge: startEdge_1, isForward: startEdgeIsForward });
-            nodes.reverse();
-            orientedEdges.reverse();
-            return { start: start, end: end, orientedEdges: orientedEdges, nodes: nodes, length: length };
+            Utils.pushAll(locations, this.getLocationsOnEdgeInterval(start.edgeId, startEdgeIsForward ? this.getEdgeOrThrow(start.edgeId).length : 0, start.distance));
+            return {
+                start: start,
+                end: end,
+                orientedEdges: orientedEdges.reverse(),
+                nodes: nodes.reverse(),
+                locations: Utils.dedupeLocations(locations).reverse(),
+                length: length,
+            };
         }
@@ -452,5 +489,25 @@ };
             nodes: [],
+            locations: this.getLocationsOnEdgeInterval(start.edgeId, start.distance, end.distance),
             length: Math.abs(start.distance - end.distance),
         };
     };
+    Graph.prototype.getLocationsOnEdgeInterval = function (edgeId, startDistance, endDistance) {
+        if (startDistance === endDistance) {
+            return [this.getLocation({ edgeId: edgeId, distance: startDistance })];
+        }
+        else {
+            var _a = this.getEdgeOrThrow(edgeId), locations = _a.locations, locationDistances = _a.locationDistances;
+            var minDistance = Math.min(startDistance, endDistance);
+            var maxDistance = Math.max(startDistance, endDistance);
+            var minLocationIndex = Utils.findFloorIndex(locationDistances, minDistance);
+            var maxLocationIndex = Utils.findFloorIndex(locationDistances, maxDistance);
+            var startLocation = this.getLocation({ edgeId: edgeId, distance: startDistance });
+            var endLocation = this.getLocation({ edgeId: edgeId, distance: endDistance });
+            var intermediateLocations = locations.slice(minLocationIndex + 1, maxLocationIndex + 1);
+            if (endDistance < startDistance) {
+                intermediateLocations.reverse();
+            }
+            return Utils.dedupeLocations([startLocation].concat(intermediateLocations, [endLocation]));
+        }
+    };
     Graph.prototype.getClosestPointWithMesh = function (location, mesh) {
@@ -457,0 +514,0 @@ var x = location.x, y = location.y;

dist/index.d.ts

@@ -0,3 +1,4 @@
+import "es6-shim";
 import Graph from "./graph";
 export default Graph;
 export * from "./types";

dist/index.js

 "use strict";
+require("es6-shim");
 var graph_1 = require("./graph");
@@ -3,0 +4,0 @@ Object.defineProperty(exports, "__esModule", { value: true });

dist/types.d.ts

@@ -38,3 +38,4 @@ export declare type NodeId = string | number;
     nodes: Node[];
+    locations: Location[];
     length: number;
 }

dist/utils.d.ts

 import { Location, OrientedEdge } from "./types";
+export declare function last<T>(ts: T[]): T;
 /**
@@ -28,1 +29,4 @@ * Given an array of locations representing a path, returns an array of the same size representing
 };
+export declare function areLocationsEqual(location1: Location, location2: Location): boolean;
+export declare function dedupeLocations(locations: Location[]): Location[];
+export declare function pushAll<T>(array: T[], toAdd: T[]): T[];

dist/utils.js

 "use strict";
+function last(ts) {
+    if (ts.length === 0) {
+        throw new Error("Cannot take last element of empty array");
+    }
+    return ts[ts.length - 1];
+}
+exports.last = last;
 /**
@@ -97,3 +104,3 @@ * Given an array of locations representing a path, returns an array of the same size representing
 function flatMap(array, f) {
-    return Array.prototype.concat.apply([], array.map(f));
+    return array.reduce(function (result, t) { return pushAll(result, f(t)); }, []);
 }
@@ -129,2 +136,25 @@ exports.flatMap = flatMap;
 exports.closestPointOnSegment = closestPointOnSegment;
+function areLocationsEqual(location1, location2) {
+    return location1.x === location2.x && location1.y === location2.y;
+}
+exports.areLocationsEqual = areLocationsEqual;
+function dedupeLocations(locations) {
+    return dedupe(locations, areLocationsEqual);
+}
+exports.dedupeLocations = dedupeLocations;
+function dedupe(ts, equals) {
+    if (equals === void 0) { equals = (function (t1, t2) { return t1 === t2; }); }
+    var result = [];
+    ts.forEach(function (t) {
+        if (result.length === 0 || !equals(last(result), t)) {
+            result.push(t);
+        }
+    });
+    return result;
+}
+function pushAll(array, toAdd) {
+    toAdd.forEach(function (t) { return array.push(t); });
+    return array;
+}
+exports.pushAll = pushAll;
 //# sourceMappingURL=utils.js.map

package.json

 {
   "name": "graphs-and-paths",
-  "version": "0.1.3",
+  "version": "0.1.4",
   "description": "Tools for graphs representing physical locations.",
@@ -39,3 +39,6 @@ "main": "dist/index.js",
   "devDependencies": {
+    "@types/es6-shim": "^0.31.32",
+    "@types/heap": "^0.2.28",
     "@types/jest": "^16.0.2",
+    "@types/rbush": "^2.0.2",
     "jest": "^18.0.0",
@@ -46,5 +49,2 @@ "tslint": "^4.1.1",
   "dependencies": {
-    "@types/es6-shim": "^0.31.32",
-    "@types/heap": "^0.2.28",
-    "@types/rbush": "^2.0.2",
     "es6-shim": "^0.35.2",
@@ -51,0 +51,0 @@ "heap": "^0.2.6",

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

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

65915

increased by14.41%

Dependency count

4

decreased by-42.86%

Lines of code

826

increased by13.46%

Number of medium supply chain risk alerts

0

decreased by-100%

Worsened metrics

Dev dependency count

7

increased by75%

Dependency changes

• - Removed@types/es6-shim@^0.31.32

• - Removed@types/heap@^0.2.28

• - Removed@types/rbush@^2.0.2

• - Removed@types/es6-shim@0.31.45(transitive)

• - Removed@types/heap@0.2.34(transitive)

• - Removed@types/rbush@2.0.7(transitive)