{"version":3,"file":"terra-route.cjs","sources":["../src/distance/haversine.ts","../src/heap/four-ary-heap.ts","../src/terra-route.ts","../src/distance/cheap-ruler.ts"],"sourcesContent":["import { Position } from \"geojson\";\n\nconst DEG_TO_RAD = Math.PI / 180;\nconst EARTH_RADIUS_KM = 6371;\n\n/** Distance measured in kilometers */\nexport const haversineDistance = (pointOne: Position, pointTwo: Position): number => {\n const phiOne = pointOne[1] * DEG_TO_RAD;\n const lambdaOne = pointOne[0] * DEG_TO_RAD;\n const phiTwo = pointTwo[1] * DEG_TO_RAD;\n const lambdaTwo = pointTwo[0] * DEG_TO_RAD;\n const deltaPhi = phiTwo - phiOne;\n const deltalambda = lambdaTwo - lambdaOne;\n const sinDeltaPhi = Math.sin(deltaPhi / 2);\n const sinDeltaLambda = Math.sin(deltalambda / 2);\n\n const a =\n sinDeltaPhi * sinDeltaPhi +\n Math.cos(phiOne) *\n Math.cos(phiTwo) *\n sinDeltaLambda *\n sinDeltaLambda;\n const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));\n\n return EARTH_RADIUS_KM * c;\n}\n","import { Heap } from \"./heap\";\n\ninterface Node {\n key: number;\n value: number;\n index: number; // insertion order for stable tie-breaking\n}\n\n/**\n * A 4-ary min-heap with stable tie-breaking on insertion order.\n * Parent(i) = floor((i - 1) / 4)\n * Children(i) = 4*i + 1 .. 4*i + 4\n */\nexport class FourAryHeap implements Heap {\n // Parallel arrays for fewer object allocations and faster property access\n private keys: number[] = [];\n private values: number[] = [];\n private idxs: number[] = [];\n private length = 0; // number of valid elements\n private insertCounter = 0;\n\n insert(key: number, value: number): void {\n // Bubble-up using local variables (avoid temporary node object)\n let i = this.length;\n this.length = i + 1;\n\n let ck = key;\n let cv = value;\n let ci = this.insertCounter++;\n\n while (i > 0) {\n const p = (i - 1) >>> 2; // divide by 4\n const pk = this.keys[p];\n const pi = this.idxs[p];\n if (ck > pk || (ck === pk && ci > pi)) break;\n\n // move parent down\n this.keys[i] = pk;\n this.values[i] = this.values[p];\n this.idxs[i] = pi;\n i = p;\n }\n\n // place the new node\n this.keys[i] = ck;\n this.values[i] = cv;\n this.idxs[i] = ci;\n }\n\n extractMin(): number | null {\n const n = this.length;\n if (n === 0) return null;\n\n const minValue = this.values[0];\n const last = n - 1;\n this.length = last;\n\n if (last > 0) {\n // Move last element to root then bubble down\n this.keys[0] = this.keys[last];\n this.values[0] = this.values[last];\n this.idxs[0] = this.idxs[last];\n this.bubbleDown(0);\n }\n\n return minValue;\n }\n\n peekMinKey(): number {\n return this.length === 0 ? Number.POSITIVE_INFINITY : this.keys[0];\n }\n\n clear(): void {\n // Keep backing arrays to avoid allocations; just reset counters.\n this.length = 0;\n this.insertCounter = 0;\n }\n\n size(): number {\n return this.length;\n }\n\n private bubbleDown(i: number): void {\n const n = this.length;\n const k = this.keys;\n const v = this.values;\n const idx = this.idxs;\n\n const nodeK = k[i];\n const nodeV = v[i];\n const nodeI = idx[i];\n\n while (true) {\n const c1 = (i << 2) + 1; // 4*i + 1\n if (c1 >= n) break; // no children\n\n // find smallest among up to 4 children\n let smallest = c1;\n let sK = k[c1];\n let sI = idx[c1];\n let sV = v[c1];\n\n const c2 = c1 + 1;\n if (c2 < n) {\n const k2 = k[c2];\n const i2 = idx[c2];\n if (k2 < sK || (k2 === sK && i2 < sI)) {\n smallest = c2;\n sK = k2;\n sI = i2;\n sV = v[c2];\n }\n }\n\n const c3 = c1 + 2;\n if (c3 < n) {\n const k3 = k[c3];\n const i3 = idx[c3];\n if (k3 < sK || (k3 === sK && i3 < sI)) {\n smallest = c3;\n sK = k3;\n sI = i3;\n sV = v[c3];\n }\n }\n\n const c4 = c1 + 3;\n if (c4 < n) {\n const k4 = k[c4];\n const i4 = idx[c4];\n if (k4 < sK || (k4 === sK && i4 < sI)) {\n smallest = c4;\n sK = k4;\n sI = i4;\n sV = v[c4];\n }\n }\n\n if (sK < nodeK || (sK === nodeK && sI < nodeI)) {\n k[i] = sK;\n v[i] = sV;\n idx[i] = sI;\n i = smallest;\n } else {\n break;\n }\n }\n\n k[i] = nodeK;\n v[i] = nodeV;\n idx[i] = nodeI;\n }\n}\n","import { FeatureCollection, LineString, Point, Feature, Position } from \"geojson\"; // Import GeoJSON types\nimport { haversineDistance } from \"./distance/haversine\"; // Great-circle distance function (default heuristic/edge weight)\nimport { createCheapRuler } from \"./distance/cheap-ruler\"; // Factory for faster planar distance (exported for consumers)\nimport { HeapConstructor } from \"./heap/heap\"; // Heap interface so users can plug custom heaps\nimport { FourAryHeap } from \"./heap/four-ary-heap\";\n\ninterface Router {\n buildRouteGraph(network: FeatureCollection): void;\n expandRouteGraph(network: FeatureCollection): void;\n getRoute(start: Feature, end: Feature): Feature | null;\n}\n\nclass TerraRoute implements Router {\n private network: FeatureCollection | null = null; // The last network used to build the graph\n private distanceMeasurement: (a: Position, b: Position) => number; // Distance function used for edges and heuristic\n private heapConstructor: HeapConstructor; // Heap class used by A*\n\n // Map from longitude → (map from latitude → index) to deduplicate coordinates and get node indices quickly\n private coordinateIndexMap: Map> = new Map(); // Nested map for exact coord lookup\n private coordinates: Position[] = []; // Array of all unique coordinates by index\n // Sparse adjacency list used during build and for any nodes added dynamically later\n private adjacencyList: Array> = []; // Per-node neighbor arrays used only pre-CSR or for dynamic nodes\n\n // Compressed Sparse Row adjacency representation for fast neighbor iteration in getRoute\n private csrOffsets: Int32Array | null = null; // Row pointer: length = nodeCount + 1, offsets into indices/distances\n private csrIndices: Int32Array | null = null; // Column indices: neighbor node IDs, length = totalEdges\n private csrDistances: Float64Array | null = null; // Edge weights aligned to csrIndices, length = totalEdges\n private csrNodeCount = 0; // Number of nodes captured in the CSR arrays\n // ALT-style landmark heuristic data (query-time lower bounds via triangle inequality)\n private landmarkNodeCount = 0;\n private landmarkCount = 0;\n private landmarkDistancesFlat: Float64Array | null = null; // Layout: [landmark0 distances..., landmark1 distances...]\n private readonly maxLandmarks = 4;\n private landmarksDirty = true;\n\n // Reusable typed scratch buffers for shortest-path search\n private gScoreScratch: Float64Array | null = null; // gScore per node (cost from start)\n private cameFromScratch: Int32Array | null = null; // Predecessor per node for path reconstruction\n private visitedScratch: Uint8Array | null = null; // Visited set to avoid reprocessing\n private heuristicScratch: Float64Array | null = null; // Cached h(node) per query for A*\n private heuristicStampScratch: Uint32Array | null = null; // Query-stamp per node for heuristic cache validity\n private heuristicQueryStamp = 1; // Monotonic stamp to avoid clearing heuristic cache each query\n private scratchCapacity = 0; // Current capacity of scratch arrays\n\n // Reused open set to avoid heap allocations during repeated getRoute calls.\n // (If a custom heap doesn't implement `clear()`, we fall back to constructing anew.)\n private openForward: InstanceType | null = null;\n\n constructor(options?: {\n distanceMeasurement?: (a: Position, b: Position) => number; // Optional distance function override\n heap?: HeapConstructor; // Optional heap implementation override\n }) {\n this.distanceMeasurement = options?.distanceMeasurement ?? haversineDistance; // Default to haversine\n this.heapConstructor = options?.heap ?? FourAryHeap; // Default to MinHeap\n }\n\n /**\n * Builds a graph (CSR) from a LineString FeatureCollection.\n * Two-pass build: pass 1 assigns node indices and counts degrees; pass 2 fills CSR arrays.\n */\n public buildRouteGraph(network: FeatureCollection): void {\n this.network = network; // Keep a reference to the network\n\n // Reset internal structures for a fresh build\n this.coordinateIndexMap = new Map(); // Clear coordinate index map\n this.coordinates = []; // Clear coordinates array\n this.adjacencyList = []; // Will not be populated during build; reserved for dynamic nodes post-build\n // Reset CSR structures (will rebuild below)\n this.csrOffsets = null;\n this.csrIndices = null;\n this.csrDistances = null;\n this.csrNodeCount = 0;\n this.landmarkNodeCount = 0;\n this.landmarkCount = 0;\n this.landmarkDistancesFlat = null;\n this.landmarksDirty = true;\n\n // Hoist to locals for speed (avoid repeated property lookups in hot loops)\n const coordIndexMapLocal = this.coordinateIndexMap; // Local alias for coord map\n const coordsLocal = this.coordinates; // Local alias for coordinates array\n const measureDistance = this.distanceMeasurement; // Local alias for distance function\n\n // Assign indices, count degrees and capture edges in one pass\n const degree: number[] = []; // Dynamic degree array; grows as nodes are discovered\n const edgeFrom: number[] = [];\n const edgeTo: number[] = [];\n const edgeDistance: number[] = [];\n\n const features = network.features;\n for (let f = 0, featureLength = features.length; f < featureLength; f++) {\n const lineCoords = features[f].geometry.coordinates;\n for (let i = 0, segmentLength = lineCoords.length - 1; i < segmentLength; i++) {\n const from = lineCoords[i] as Position;\n const to = lineCoords[i + 1] as Position;\n\n const indexA = this.indexCoordinate(from, coordIndexMapLocal, coordsLocal);\n const indexB = this.indexCoordinate(to, coordIndexMapLocal, coordsLocal);\n\n degree[indexA] = (degree[indexA] ?? 0) + 1;\n degree[indexB] = (degree[indexB] ?? 0) + 1;\n\n edgeFrom.push(indexA);\n edgeTo.push(indexB);\n edgeDistance.push(measureDistance(from, to));\n }\n }\n\n // Build CSR arrays from degree counts\n const nodeCount = this.coordinates.length; // Total nodes discovered\n this.csrNodeCount = nodeCount; // CSR covers all built nodes\n const offsets = new Int32Array(nodeCount + 1); // Row pointer array\n for (let i = 0; i < nodeCount; i++) {\n const deg = degree[i] ?? 0; // Degree of node i\n offsets[i + 1] = offsets[i] + deg; // Prefix sum\n }\n const totalEdges = offsets[nodeCount]; // Total adjacency entries\n const indices = new Int32Array(totalEdges); // Neighbor indices array\n const distances = new Float64Array(totalEdges); // Distances array aligned to indices\n\n // Fill CSR arrays using a write cursor per node\n const cursor = offsets.slice(); // Current write positions per node\n for (let i = 0, edgeLength = edgeFrom.length; i < edgeLength; i++) {\n const indexA = edgeFrom[i];\n const indexB = edgeTo[i];\n const segmentDistance = edgeDistance[i];\n\n let pos = cursor[indexA]++;\n indices[pos] = indexB;\n distances[pos] = segmentDistance;\n pos = cursor[indexB]++;\n indices[pos] = indexA;\n distances[pos] = segmentDistance;\n }\n\n // Commit CSR to instance\n this.csrOffsets = offsets;\n this.csrIndices = indices;\n this.csrDistances = distances;\n\n // Prepare sparse shell only for dynamically added nodes later (no prefilled neighbor arrays)\n this.adjacencyList = new Array(nodeCount);\n }\n\n /**\n * Expands (merges) the existing graph with an additional LineString FeatureCollection.\n */\n public expandRouteGraph(network: FeatureCollection): void {\n if (this.network === null) {\n throw new Error(\"Network not built. Please call buildRouteGraph(network) first.\");\n }\n\n // Merge the feature arrays for reference/debugging. We avoid copying properties deeply.\n this.network = {\n type: \"FeatureCollection\",\n features: [...this.network.features, ...network.features],\n };\n\n const coordIndexMapLocal = this.coordinateIndexMap;\n const coordsLocal = this.coordinates;\n const measureDistance = this.distanceMeasurement;\n const adj = this.adjacencyList;\n\n // Ensure we have adjacency arrays for any existing CSR-only nodes.\n // (During buildRouteGraph, adjacencyList is sized but entries are undefined.)\n for (let i = 0; i < adj.length; i++) {\n if (adj[i] === undefined) adj[i] = [];\n }\n\n // Add new edges into the adjacency list (sparse), then rebuild CSR from adjacency.\n this.forEachSegment(network, (a, b) => {\n const indexA = this.indexCoordinate(a, coordIndexMapLocal, coordsLocal, (idx) => { adj[idx] = []; });\n const indexB = this.indexCoordinate(b, coordIndexMapLocal, coordsLocal, (idx) => { adj[idx] = []; });\n\n const segmentDistance = measureDistance(a, b);\n\n adj[indexA].push({ node: indexB, distance: segmentDistance });\n adj[indexB].push({ node: indexA, distance: segmentDistance });\n });\n\n this.rebuildCsrFromAdjacency();\n }\n\n /**\n * Rebuild CSR arrays for the full node set, using:\n * - Existing CSR edges (from the last build/expand)\n * - Any additional edges stored in `adjacencyList`\n */\n private rebuildCsrFromAdjacency(): void {\n const nodeCount = this.coordinates.length;\n const adj = this.adjacencyList;\n\n // Compute degree using CSR degree + adjacency degree\n const degree = new Int32Array(nodeCount);\n\n if (this.csrOffsets && this.csrIndices && this.csrDistances) {\n const csrOffsets = this.csrOffsets;\n const covered = Math.min(this.csrNodeCount, nodeCount);\n for (let i = 0; i < covered; i++) {\n degree[i] += (csrOffsets[i + 1] - csrOffsets[i]);\n }\n }\n\n for (let i = 0; i < nodeCount; i++) {\n const neighbors = adj[i];\n if (neighbors && neighbors.length) degree[i] += neighbors.length;\n }\n\n const offsets = new Int32Array(nodeCount + 1);\n for (let i = 0; i < nodeCount; i++) {\n offsets[i + 1] = offsets[i] + degree[i];\n }\n const totalEdges = offsets[nodeCount];\n const indices = new Int32Array(totalEdges);\n const distances = new Float64Array(totalEdges);\n const cursor = offsets.slice();\n\n // Copy existing CSR edges first\n if (this.csrOffsets && this.csrIndices && this.csrDistances) {\n const csrOffsets = this.csrOffsets;\n const csrIndices = this.csrIndices;\n const csrDistances = this.csrDistances;\n const covered = Math.min(this.csrNodeCount, nodeCount);\n for (let n = 0; n < covered; n++) {\n const startOff = csrOffsets[n];\n const endOff = csrOffsets[n + 1];\n let pos = cursor[n];\n for (let i = startOff; i < endOff; i++) {\n indices[pos] = csrIndices[i];\n distances[pos] = csrDistances[i];\n pos++;\n }\n cursor[n] = pos;\n }\n }\n\n // Append adjacency edges\n for (let n = 0; n < nodeCount; n++) {\n const neighbors = adj[n];\n if (!neighbors || neighbors.length === 0) continue;\n let pos = cursor[n];\n for (let i = 0, len = neighbors.length; i < len; i++) {\n const nb = neighbors[i];\n indices[pos] = nb.node;\n distances[pos] = nb.distance;\n pos++;\n }\n cursor[n] = pos;\n }\n\n // Commit and reset adjacency (we've absorbed edges into CSR)\n this.csrOffsets = offsets;\n this.csrIndices = indices;\n this.csrDistances = distances;\n this.csrNodeCount = nodeCount;\n this.landmarksDirty = true;\n this.landmarkNodeCount = 0;\n this.landmarkCount = 0;\n this.landmarkDistancesFlat = null;\n\n // Keep adjacency list for *future* dynamic additions, but clear existing edges to avoid duplication.\n this.adjacencyList = new Array(nodeCount);\n }\n\n /**\n * Computes the shortest route between two points in the network using the A* algorithm.\n * \n * @param start - A GeoJSON Point Feature representing the start location.\n * @param end - A GeoJSON Point Feature representing the end location.\n * @returns A GeoJSON LineString Feature representing the shortest path, or null if no path is found.\n * \n * @throws Error if the network has not been built yet with buildRouteGraph(network).\n */\n public getRoute(\n start: Feature, // Start point feature\n end: Feature // End point feature\n ): Feature | null {\n if (this.network === null) { // Guard: graph must be built first\n throw new Error(\"Network not built. Please call buildRouteGraph(network) first.\");\n }\n\n // Ensure start/end exist in index maps\n const startIndex = this.getOrCreateIndex(start.geometry.coordinates); // Get or insert start node index\n const endIndex = this.getOrCreateIndex(end.geometry.coordinates); // Get or insert end node index\n\n // Trivial case: same node\n if (startIndex === endIndex) {\n return null; // No path needed\n }\n\n // Local aliases\n const coordinates = this.coordinates; // Alias to coordinates array\n const adjacency = this.adjacencyList; // Alias to sparse adjacency list (for dynamic nodes)\n const csrOffsets = this.csrOffsets;\n const csrIndices = this.csrIndices;\n const csrDistances = this.csrDistances;\n const csrNodeCount = this.csrNodeCount;\n const hasCsr = !!csrOffsets; // indices/distances should exist whenever offsets exist\n const PositiveInfinity = Number.POSITIVE_INFINITY;\n const measureDistance = this.distanceMeasurement;\n const endCoordinates = end.geometry.coordinates;\n\n this.ensureLandmarkHeuristicData();\n const landmarkDistancesFlat = this.landmarkDistancesFlat;\n const landmarkNodeCount = this.landmarkNodeCount;\n const landmarkCount = this.landmarkCount;\n\n // Ensure and init scratch buffers\n const nodeCount = coordinates.length; // Current number of nodes (may be >= csrNodeCount if new nodes added)\n this.ensureScratch(nodeCount); // Allocate scratch arrays if needed\n\n // Non-null after ensure\n const gF = this.gScoreScratch!; // gScore from start\n const prevF = this.cameFromScratch!; // predecessor for reconstruction\n const visF = this.visitedScratch!;\n const heuristic = this.heuristicScratch!;\n const heuristicStamp = this.heuristicStampScratch!;\n\n gF.fill(PositiveInfinity, 0, nodeCount);\n prevF.fill(-1, 0, nodeCount);\n visF.fill(0, 0, nodeCount);\n\n // Increment query stamp for heuristic cache validity; handle wraparound.\n let queryStamp = (this.heuristicQueryStamp + 1) >>> 0;\n if (queryStamp === 0) {\n heuristicStamp.fill(0, 0, nodeCount);\n queryStamp = 1;\n }\n this.heuristicQueryStamp = queryStamp;\n\n const getHeuristic = (node: number): number => {\n if (heuristicStamp[node] !== queryStamp) {\n heuristicStamp[node] = queryStamp;\n\n if (landmarkDistancesFlat && landmarkCount > 0 && node < landmarkNodeCount && endIndex < landmarkNodeCount) {\n let lowerBound = 0;\n for (let l = 0, offset = 0; l < landmarkCount; l++, offset += landmarkNodeCount) {\n const distanceToNode = landmarkDistancesFlat[offset + node];\n const distanceToEnd = landmarkDistancesFlat[offset + endIndex];\n\n if (!Number.isFinite(distanceToNode) || !Number.isFinite(distanceToEnd)) {\n continue;\n }\n\n const landmarkLowerBound = distanceToEnd >= distanceToNode\n ? distanceToEnd - distanceToNode\n : distanceToNode - distanceToEnd;\n\n if (landmarkLowerBound > lowerBound) {\n lowerBound = landmarkLowerBound;\n }\n }\n heuristic[node] = lowerBound;\n } else {\n heuristic[node] = measureDistance(coordinates[node], endCoordinates);\n }\n }\n return heuristic[node];\n };\n\n // Prefer reusing heaps if supported.\n const openFReuse = this.openForward ?? (this.openForward = new this.heapConstructor());\n const openFAny = openFReuse as unknown as { clear?: () => void };\n const canReuse = !!openFAny.clear;\n\n const openF2 = canReuse ? openFReuse : new this.heapConstructor();\n\n if (canReuse) {\n openFAny.clear!();\n }\n\n gF[startIndex] = 0;\n openF2.insert(getHeuristic(startIndex), startIndex);\n\n while (openF2.size() > 0) {\n const current = openF2.extractMin();\n if (current === null) {\n break;\n }\n if (visF[current] !== 0) {\n continue;\n }\n if (current === endIndex) {\n break;\n }\n\n visF[current] = 1;\n const currentDistance = gF[current];\n\n const isCsrNode = hasCsr && current < csrNodeCount;\n if (!isCsrNode) {\n const neighbors = adjacency[current];\n if (!neighbors || neighbors.length === 0) {\n continue;\n }\n\n for (let i = 0, n = neighbors.length; i < n; i++) {\n const nb = neighbors[i];\n const nbNode = nb.node;\n const tentativeG = currentDistance + nb.distance;\n if (tentativeG >= gF[nbNode]) {\n continue;\n }\n\n gF[nbNode] = tentativeG;\n prevF[nbNode] = current;\n openF2.insert(tentativeG + getHeuristic(nbNode), nbNode);\n }\n continue;\n }\n\n for (let i = csrOffsets![current], endOff = csrOffsets![current + 1]; i < endOff; i++) {\n const nbNode = csrIndices![i];\n const tentativeG = currentDistance + csrDistances![i];\n if (tentativeG >= gF[nbNode]) {\n continue;\n }\n\n gF[nbNode] = tentativeG;\n prevF[nbNode] = current;\n openF2.insert(tentativeG + getHeuristic(nbNode), nbNode);\n }\n }\n\n if (gF[endIndex] === PositiveInfinity) {\n return null;\n }\n\n // Reconstruct path from end back to start through predecessor links.\n const path: Position[] = [];\n\n let cur = endIndex;\n while (cur !== startIndex && cur >= 0) {\n path.push(coordinates[cur]);\n cur = prevF[cur];\n }\n path.push(coordinates[startIndex]);\n path.reverse();\n\n return {\n type: \"Feature\",\n geometry: { type: \"LineString\", coordinates: path },\n properties: {},\n };\n }\n\n // Build ALT heuristic tables by running shortest-path trees from selected landmarks.\n private buildLandmarkHeuristicData(): void {\n const offsets = this.csrOffsets;\n const indices = this.csrIndices;\n const distances = this.csrDistances;\n const nodeCount = this.csrNodeCount;\n\n if (!offsets || !indices || !distances || nodeCount === 0) {\n this.landmarkNodeCount = 0;\n this.landmarkCount = 0;\n this.landmarkDistancesFlat = null;\n return;\n }\n\n const targetLandmarkCount = Math.min(this.maxLandmarks, nodeCount);\n const selected = new Uint8Array(nodeCount);\n const allDistances: Float64Array[] = [];\n\n let source = 0;\n for (let landmarkIndex = 0; landmarkIndex < targetLandmarkCount; landmarkIndex++) {\n selected[source] = 1;\n\n const computedDistances = this.computeShortestDistancesFrom(source, nodeCount, offsets, indices, distances);\n allDistances.push(computedDistances);\n\n let farthestDistance = -1;\n let farthestIndex = -1;\n for (let node = 0; node < nodeCount; node++) {\n if (selected[node] !== 0) {\n continue;\n }\n\n const distanceAtNode = computedDistances[node];\n if (!Number.isFinite(distanceAtNode)) {\n continue;\n }\n\n if (distanceAtNode > farthestDistance) {\n farthestDistance = distanceAtNode;\n farthestIndex = node;\n }\n }\n\n if (farthestIndex < 0) {\n break;\n }\n source = farthestIndex;\n }\n\n const landmarkCount = allDistances.length;\n\n const flat = new Float64Array(landmarkCount * nodeCount);\n for (let i = 0; i < landmarkCount; i++) {\n flat.set(allDistances[i], i * nodeCount);\n }\n\n this.landmarkNodeCount = nodeCount;\n this.landmarkCount = landmarkCount;\n this.landmarkDistancesFlat = flat;\n this.landmarksDirty = false;\n }\n\n // Build landmark tables only when needed by getRoute.\n private ensureLandmarkHeuristicData(): void {\n if (!this.landmarksDirty) {\n return;\n }\n this.buildLandmarkHeuristicData();\n }\n\n // Dijkstra over CSR to compute all-pairs distances from one source node.\n private computeShortestDistancesFrom(\n source: number,\n nodeCount: number,\n offsets: Int32Array,\n indices: Int32Array,\n distances: Float64Array,\n ): Float64Array {\n const PositiveInfinity = Number.POSITIVE_INFINITY;\n const bestDistance = new Float64Array(nodeCount);\n const visited = new Uint8Array(nodeCount);\n bestDistance.fill(PositiveInfinity);\n bestDistance[source] = 0;\n\n const openSet = new this.heapConstructor();\n openSet.insert(0, source);\n\n while (openSet.size() > 0) {\n const current = openSet.extractMin();\n if (current === null) {\n break;\n }\n if (visited[current] !== 0) {\n continue;\n }\n\n visited[current] = 1;\n const currentDistance = bestDistance[current];\n\n for (let i = offsets[current], endOffset = offsets[current + 1]; i < endOffset; i++) {\n const neighbor = indices[i];\n const tentativeDistance = currentDistance + distances[i];\n if (tentativeDistance >= bestDistance[neighbor]) {\n continue;\n }\n\n bestDistance[neighbor] = tentativeDistance;\n openSet.insert(tentativeDistance, neighbor);\n }\n }\n\n return bestDistance;\n }\n\n /**\n * Helper to index start/end in getRoute.\n */\n private getOrCreateIndex(coord: Position): number { // Ensure a coordinate has a node index, creating if absent\n const lng = coord[0]; // Extract longitude\n const lat = coord[1]; // Extract latitude\n\n let latMap = this.coordinateIndexMap.get(lng); // Get lat→index map for this longitude\n if (latMap === undefined) { // Create if missing\n latMap = new Map();\n this.coordinateIndexMap.set(lng, latMap);\n }\n\n let index = latMap.get(lat); // Lookup index by latitude\n if (index === undefined) { // If not found, append new node\n\n index = this.coordinates.length; // New index at end\n this.coordinates.push(coord); // Store coordinate\n latMap.set(lat, index); // Record mapping\n\n // Ensure sparse adjacency slot for dynamically added nodes\n this.adjacencyList[index] = []; // Init empty neighbor array\n\n // Extend CSR offsets to keep indices consistent (no neighbors for new node)\n if (this.csrOffsets) { // Only adjust if CSR already built\n\n // Only need to expand offsets by one; indices/distances remain unchanged\n const oldCount = this.csrNodeCount; // Nodes currently covered by CSR\n\n // Appending exactly one new node at the end\n if (index === oldCount) {\n const newOffsets = new Int32Array(oldCount + 2); // Allocate offsets for +1 node\n newOffsets.set(this.csrOffsets, 0); // Copy previous offsets\n\n // Last offset repeats to indicate zero neighbors\n newOffsets[oldCount + 1] = newOffsets[oldCount]; // Replicate last pointer\n this.csrOffsets = newOffsets; // Swap in new offsets\n this.csrNodeCount = oldCount + 1; // Increment CSR node count\n }\n }\n }\n\n return index;\n }\n\n // Ensure scratch arrays are allocated with at least `size` capacity.\n private ensureScratch(size: number): void {\n const ifAlreadyBigEnough = this.scratchCapacity >= size\n && this.gScoreScratch\n && this.cameFromScratch\n && this.visitedScratch\n && this.heuristicScratch\n && this.heuristicStampScratch;\n\n if (ifAlreadyBigEnough) {\n return; // Nothing to do\n }\n const capacity = size | 0; // Ensure integer\n this.gScoreScratch = new Float64Array(capacity);\n this.cameFromScratch = new Int32Array(capacity);\n this.visitedScratch = new Uint8Array(capacity);\n this.heuristicScratch = new Float64Array(capacity);\n this.heuristicStampScratch = new Uint32Array(capacity);\n this.scratchCapacity = capacity;\n }\n\n\n // Iterate all consecutive segment pairs in a LineString FeatureCollection.\n // Kept as a simple loop helper to avoid repeating nested iteration logic.\n private forEachSegment(\n network: FeatureCollection,\n fn: (a: Position, b: Position) => void,\n ): void {\n const features = network.features;\n for (let f = 0, fLen = features.length; f < fLen; f++) {\n const lineCoords = features[f].geometry.coordinates;\n for (let i = 0, len = lineCoords.length - 1; i < len; i++) {\n // GeoJSON coordinates are compatible with Position (number[]), and the project assumes [lng,lat]\n fn(lineCoords[i] as Position, lineCoords[i + 1] as Position);\n }\n }\n }\n\n // Hot-path coordinate indexer used by both build/expand.\n // Accepts explicit maps/arrays so callers can hoist them once.\n private indexCoordinate(\n coord: Position,\n coordIndexMapLocal: Map>,\n coordsLocal: Position[],\n onNewIndex?: (index: number) => void,\n ): number {\n const lng = coord[0];\n const lat = coord[1];\n\n let latMap = coordIndexMapLocal.get(lng);\n if (latMap === undefined) {\n latMap = new Map();\n coordIndexMapLocal.set(lng, latMap);\n }\n\n let idx = latMap.get(lat);\n if (idx === undefined) {\n idx = coordsLocal.length;\n coordsLocal.push(coord);\n latMap.set(lat, idx);\n if (onNewIndex) onNewIndex(idx);\n }\n\n return idx;\n }\n\n}\n\nexport { TerraRoute, createCheapRuler, haversineDistance } ","import { Position } from \"geojson\";\n\n// This code is based on Mapbox's cheap-ruler library:\n\n// ISC License\n\n// Copyright (c) 2024, Mapbox\n\n// Permission to use, copy, modify, and/or distribute this software for any purpose\n// with or without fee is hereby granted, provided that the above copyright notice\n// and this permission notice appear in all copies.\n\n// THE SOFTWARE IS PROVIDED \"AS IS\" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH\n// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND\n// FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,\n// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS\n// OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER\n// TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF\n// THIS SOFTWARE.\n\n/**\n * Creates a function for fast geodesic distance approximation using local scaling constants\n * based on a reference latitude. Useful for city-scale distances.\n *\n * @param {number} lat - Reference latitude in degrees\n * @returns {(a: Position, b: Position) => number} - Function that computes distance between two points\n * \n * @example\n * const distance = createCheapRuler(50.5);\n * const d = distance([30.5, 50.5], [30.51, 50.49]);\n * \n */\nexport function createCheapRuler(lat: number): (a: Position, b: Position) => number {\n const RE = 6378.137; // Earth's equatorial radius in kilometers\n const FE = 1 / 298.257223563; // Earth's flattening\n const E2 = FE * (2 - FE);\n const RAD = Math.PI / 180;\n\n const cosLat = Math.cos(lat * RAD);\n const w2 = 1 / (1 - E2 * (1 - cosLat * cosLat));\n const w = Math.sqrt(w2);\n\n const m = RAD * RE;\n const kx = m * w * cosLat; // scale for longitude\n const ky = m * w * w2 * (1 - E2); // scale for latitude\n\n return function distance(a: Position, b: Position): number {\n let deltaLng = a[0] - b[0];\n\n while (deltaLng < -180) deltaLng += 360;\n while (deltaLng > 180) deltaLng -= 360;\n\n const dx = deltaLng * kx;\n const dy = (a[1] - b[1]) * ky;\n\n return Math.sqrt(dx * dx + dy * dy);\n };\n}"],"names":["DEG_TO_RAD","Math","PI","haversineDistance","pointOne","pointTwo","phiOne","phiTwo","deltalambda","sinDeltaPhi","sin","sinDeltaLambda","a","cos","atan2","sqrt","FourAryHeap","keys","this","values","idxs","length","insertCounter","_proto","prototype","insert","key","value","i","ck","cv","ci","p","pk","pi","extractMin","n","minValue","last","bubbleDown","peekMinKey","Number","POSITIVE_INFINITY","clear","size","k","v","idx","nodeK","nodeV","nodeI","c1","smallest","sK","sI","sV","c2","k2","i2","c3","k3","i3","c4","k4","i4","TerraRoute","options","_options$distanceMeas","_options$heap","network","distanceMeasurement","heapConstructor","coordinateIndexMap","Map","coordinates","adjacencyList","csrOffsets","csrIndices","csrDistances","csrNodeCount","landmarkNodeCount","landmarkCount","landmarkDistancesFlat","maxLandmarks","landmarksDirty","gScoreScratch","cameFromScratch","visitedScratch","heuristicScratch","heuristicStampScratch","heuristicQueryStamp","scratchCapacity","openForward","heap","buildRouteGraph","coordIndexMapLocal","coordsLocal","measureDistance","degree","edgeFrom","edgeTo","edgeDistance","features","f","featureLength","lineCoords","geometry","segmentLength","_degree$indexA","_degree$indexB","from","to","indexA","indexCoordinate","indexB","push","nodeCount","offsets","Int32Array","_degree$_i","deg","totalEdges","indices","distances","Float64Array","cursor","slice","edgeLength","segmentDistance","pos","Array","expandRouteGraph","_this","Error","type","concat","adj","undefined","forEachSegment","b","node","distance","rebuildCsrFromAdjacency","covered","min","neighbors","endOff","len","nb","getRoute","start","end","startIndex","getOrCreateIndex","endIndex","adjacency","hasCsr","PositiveInfinity","endCoordinates","ensureLandmarkHeuristicData","ensureScratch","gF","prevF","visF","heuristic","heuristicStamp","fill","queryStamp","getHeuristic","lowerBound","l","offset","distanceToNode","distanceToEnd","isFinite","landmarkLowerBound","openFReuse","_this$openForward","openFAny","canReuse","openF2","current","currentDistance","nbNode","tentativeG","path","cur","reverse","properties","buildLandmarkHeuristicData","targetLandmarkCount","selected","Uint8Array","allDistances","source","landmarkIndex","computedDistances","computeShortestDistancesFrom","farthestDistance","farthestIndex","distanceAtNode","flat","set","bestDistance","visited","openSet","endOffset","neighbor","tentativeDistance","coord","lng","lat","latMap","get","index","oldCount","newOffsets","capacity","Uint32Array","fn","fLen","onNewIndex","FE","E2","RAD","cosLat","w2","w","m","kx","ky","deltaLng","dx","dy"],"mappings":"AAEA,IAAMA,EAAaC,KAAKC,GAAK,IAIhBC,EAAoB,SAACC,EAAoBC,GAClD,IAAMC,EAASF,EAAS,GAAKJ,EAEvBO,EAASF,EAAS,GAAKL,EAGvBQ,EAFYH,EAAS,GAAKL,EAFdI,EAAS,GAAKJ,EAK1BS,EAAcR,KAAKS,KAFRH,EAASD,GAEc,GAClCK,EAAiBV,KAAKS,IAAIF,EAAc,GAExCI,EACFH,EAAcA,EACdR,KAAKY,IAAIP,GACTL,KAAKY,IAAIN,GACTI,EACAA,EAGJ,OAFU,EAAIV,KAAKa,MAAMb,KAAKc,KAAKH,GAAIX,KAAKc,KAAK,EAAIH,IAnBjC,IAsBxB,ECZaI,eAAW,WAAA,SAAAA,IAEZC,KAAAA,KAAiB,GAAEC,KACnBC,OAAmB,QACnBC,KAAiB,GACjBC,KAAAA,OAAS,EAACH,KACVI,cAAgB,CAAC,KAAAC,EAAAP,EAAAQ,iBAAAD,EAEzBE,OAAA,SAAOC,EAAaC,GAEhB,IAAIC,EAAIV,KAAKG,OACbH,KAAKG,OAASO,EAAI,EAMlB,IAJA,IAAIC,EAAKH,EACLI,EAAKH,EACLI,EAAKb,KAAKI,gBAEPM,EAAI,GAAG,CACV,IAAMI,EAAKJ,EAAI,IAAO,EAChBK,EAAKf,KAAKD,KAAKe,GACfE,EAAKhB,KAAKE,KAAKY,GACrB,GAAIH,EAAKI,GAAOJ,IAAOI,GAAMF,EAAKG,EAAK,MAGvChB,KAAKD,KAAKW,GAAKK,EACff,KAAKC,OAAOS,GAAKV,KAAKC,OAAOa,GAC7Bd,KAAKE,KAAKQ,GAAKM,EACfN,EAAII,CACR,CAGAd,KAAKD,KAAKW,GAAKC,EACfX,KAAKC,OAAOS,GAAKE,EACjBZ,KAAKE,KAAKQ,GAAKG,CACnB,EAACR,EAEDY,WAAA,WACI,IAAMC,EAAIlB,KAAKG,OACf,GAAU,IAANe,EAAS,OAAO,KAEpB,IAAMC,EAAWnB,KAAKC,OAAO,GACvBmB,EAAOF,EAAI,EAWjB,OAVAlB,KAAKG,OAASiB,EAEVA,EAAO,IAEPpB,KAAKD,KAAK,GAAKC,KAAKD,KAAKqB,GACzBpB,KAAKC,OAAO,GAAKD,KAAKC,OAAOmB,GAC7BpB,KAAKE,KAAK,GAAKF,KAAKE,KAAKkB,GACzBpB,KAAKqB,WAAW,IAGbF,CACX,EAACd,EAEDiB,WAAA,WACI,OAAuB,SAAXnB,OAAeoB,OAAOC,kBAAoBxB,KAAKD,KAAK,EACpE,EAACM,EAEDoB,MAAA,WAEIzB,KAAKG,OAAS,EACdH,KAAKI,cAAgB,CACzB,EAACC,EAEDqB,KAAA,WACI,OAAO1B,KAAKG,MAChB,EAACE,EAEOgB,WAAA,SAAWX,GAUf,IATA,IAAMQ,EAAIlB,KAAKG,OACTwB,EAAI3B,KAAKD,KACT6B,EAAI5B,KAAKC,OACT4B,EAAM7B,KAAKE,KAEX4B,EAAQH,EAAEjB,GACVqB,EAAQH,EAAElB,GACVsB,EAAQH,EAAInB,KAEL,CACT,IAAMuB,EAAgB,GAAVvB,GAAK,GACjB,GAAIuB,GAAMf,EAAG,MAGb,IAAIgB,EAAWD,EACXE,EAAKR,EAAEM,GACPG,EAAKP,EAAII,GACTI,EAAKT,EAAEK,GAELK,EAAKL,EAAK,EAChB,GAAIK,EAAKpB,EAAG,CACR,IAAMqB,EAAKZ,EAAEW,GACPE,EAAKX,EAAIS,IACXC,EAAKJ,GAAOI,IAAOJ,GAAMK,EAAKJ,KAC9BF,EAAWI,EACXH,EAAKI,EACLH,EAAKI,EACLH,EAAKT,EAAEU,GAEf,CAEA,IAAMG,EAAKR,EAAK,EAChB,GAAIQ,EAAKvB,EAAG,CACR,IAAMwB,EAAKf,EAAEc,GACPE,EAAKd,EAAIY,IACXC,EAAKP,GAAOO,IAAOP,GAAMQ,EAAKP,KAC9BF,EAAWO,EACXN,EAAKO,EACLN,EAAKO,EACLN,EAAKT,EAAEa,GAEf,CAEA,IAAMG,EAAKX,EAAK,EAChB,GAAIW,EAAK1B,EAAG,CACR,IAAM2B,EAAKlB,EAAEiB,GACPE,EAAKjB,EAAIe,IACXC,EAAKV,GAAOU,IAAOV,GAAMW,EAAKV,KAC9BF,EAAWU,EACXT,EAAKU,EACLT,EAAKU,EACLT,EAAKT,EAAEgB,GAEf,CAEA,KAAIT,EAAKL,GAAUK,IAAOL,GAASM,EAAKJ,GAMpC,MALAL,EAAEjB,GAAKyB,EACPP,EAAElB,GAAK2B,EACPR,EAAInB,GAAK0B,EACT1B,EAAIwB,CAIZ,CAEAP,EAAEjB,GAAKoB,EACPF,EAAElB,GAAKqB,EACPF,EAAInB,GAAKsB,CACb,EAAClC,CAAA,CA1ImB,mCCDR,WAoCZ,SAAAiD,EAAYC,GAGX,IAAAC,EAAAC,EAtCOC,KAAAA,QAAgD,KAAInD,KACpDoD,yBACAC,EAAAA,KAAAA,qBAGAC,EAAAA,KAAAA,mBAAuD,IAAIC,IAAKvD,KAChEwD,YAA0B,GAAExD,KAE5ByD,cAAkE,GAGlEC,KAAAA,WAAgC,UAChCC,WAAgC,KAChCC,KAAAA,aAAoC,KAAI5D,KACxC6D,aAAe,EAAC7D,KAEhB8D,kBAAoB,EACpBC,KAAAA,cAAgB,OAChBC,sBAA6C,KAAIhE,KACxCiE,aAAe,EACxBC,KAAAA,gBAAiB,EAGjBC,KAAAA,cAAqC,KAAInE,KACzCoE,gBAAqC,KAAIpE,KACzCqE,eAAoC,KACpCC,KAAAA,iBAAwC,UACxCC,sBAA4C,KAAIvE,KAChDwE,oBAAsB,EACtBC,KAAAA,gBAAkB,EAACzE,KAInB0E,YAAoD,KAMxD1E,KAAKoD,oBAAkDH,OAA/BA,EAAU,MAAPD,OAAO,EAAPA,EAASI,qBAAmBH,EAAIhE,EAC3De,KAAKqD,gBAA+BH,OAAhBA,EAAU,MAAPF,OAAO,EAAPA,EAAS2B,MAAIzB,EAAIpD,CAC5C,CAAC,IAAAO,EAAA0C,EAAAzC,UAsmBA,OAtmBAD,EAMMuE,gBAAA,SAAgBzB,GACnBnD,KAAKmD,QAAUA,EAGfnD,KAAKsD,mBAAqB,IAAIC,IAC9BvD,KAAKwD,YAAc,GACnBxD,KAAKyD,cAAgB,GAErBzD,KAAK0D,WAAa,KAClB1D,KAAK2D,WAAa,KAClB3D,KAAK4D,aAAe,KACpB5D,KAAK6D,aAAe,EACpB7D,KAAK8D,kBAAoB,EACzB9D,KAAK+D,cAAgB,EACrB/D,KAAKgE,sBAAwB,KAC7BhE,KAAKkE,gBAAiB,EActB,IAXA,IAAMW,EAAqB7E,KAAKsD,mBAC1BwB,EAAc9E,KAAKwD,YACnBuB,EAAkB/E,KAAKoD,oBAGvB4B,EAAmB,GACnBC,EAAqB,GACrBC,EAAmB,GACnBC,EAAyB,GAEzBC,EAAWjC,EAAQiC,SAChBC,EAAI,EAAGC,EAAgBF,EAASjF,OAAQkF,EAAIC,EAAeD,IAEhE,IADA,IAAME,EAAaH,EAASC,GAAGG,SAAShC,YAC/B9C,EAAI,EAAG+E,EAAgBF,EAAWpF,OAAS,EAAGO,EAAI+E,EAAe/E,IAAK,CAAAgF,IAAAA,EAAAC,EACrEC,EAAOL,EAAW7E,GAClBmF,EAAKN,EAAW7E,EAAI,GAEpBoF,EAAS9F,KAAK+F,gBAAgBH,EAAMf,EAAoBC,GACxDkB,EAAShG,KAAK+F,gBAAgBF,EAAIhB,EAAoBC,GAE5DE,EAAOc,IAAyBJ,OAAfA,EAACV,EAAOc,IAAOJ,EAAI,GAAK,EACzCV,EAAOgB,IAAyBL,OAAfA,EAACX,EAAOgB,IAAOL,EAAI,GAAK,EAEzCV,EAASgB,KAAKH,GACdZ,EAAOe,KAAKD,GACZb,EAAac,KAAKlB,EAAgBa,EAAMC,GAC5C,CAIJ,IAAMK,EAAYlG,KAAKwD,YAAYrD,OACnCH,KAAK6D,aAAeqC,EAEpB,IADA,IAAMC,EAAU,IAAIC,WAAWF,EAAY,GAClCxF,EAAI,EAAGA,EAAIwF,EAAWxF,IAAK,CAAA2F,IAAAA,EAC1BC,EAAe,OAAZD,EAAGrB,EAAOtE,IAAE2F,EAAI,EACzBF,EAAQzF,EAAI,GAAKyF,EAAQzF,GAAK4F,CAClC,CAOA,IANA,IAAMC,EAAaJ,EAAQD,GACrBM,EAAU,IAAIJ,WAAWG,GACzBE,EAAY,IAAIC,aAAaH,GAG7BI,EAASR,EAAQS,QACdlG,EAAI,EAAGmG,EAAa5B,EAAS9E,OAAQO,EAAImG,EAAYnG,IAAK,CAC/D,IAAMoF,EAASb,EAASvE,GAClBsF,EAASd,EAAOxE,GAChBoG,EAAkB3B,EAAazE,GAEjCqG,EAAMJ,EAAOb,KACjBU,EAAQO,GAAOf,EACfS,EAAUM,GAAOD,EAEjBN,EADAO,EAAMJ,EAAOX,MACEF,EACfW,EAAUM,GAAOD,CACrB,CAGA9G,KAAK0D,WAAayC,EAClBnG,KAAK2D,WAAa6C,EAClBxG,KAAK4D,aAAe6C,EAGpBzG,KAAKyD,cAAgB,IAAIuD,MAAMd,EACnC,EAAC7F,EAKM4G,iBAAA,SAAiB9D,GAAsC+D,IAAAA,EAC1DlH,KAAA,GAAqB,OAAjBA,KAAKmD,QACL,MAAU,IAAAgE,MAAM,kEAIpBnH,KAAKmD,QAAU,CACXiE,KAAM,oBACNhC,SAAQ,GAAAiC,OAAMrH,KAAKmD,QAAQiC,SAAajC,EAAQiC,WAUpD,IAPA,IAAMP,EAAqB7E,KAAKsD,mBAC1BwB,EAAc9E,KAAKwD,YACnBuB,EAAkB/E,KAAKoD,oBACvBkE,EAAMtH,KAAKyD,cAIR/C,EAAI,EAAGA,EAAI4G,EAAInH,OAAQO,SACb6G,IAAXD,EAAI5G,KAAkB4G,EAAI5G,GAAK,IAIvCV,KAAKwH,eAAerE,EAAS,SAACzD,EAAG+H,GAC7B,IAAM3B,EAASoB,EAAKnB,gBAAgBrG,EAAGmF,EAAoBC,EAAa,SAACjD,GAAUyF,EAAIzF,GAAO,EAAI,GAC5FmE,EAASkB,EAAKnB,gBAAgB0B,EAAG5C,EAAoBC,EAAa,SAACjD,GAAUyF,EAAIzF,GAAO,EAAI,GAE5FiF,EAAkB/B,EAAgBrF,EAAG+H,GAE3CH,EAAIxB,GAAQG,KAAK,CAAEyB,KAAM1B,EAAQ2B,SAAUb,IAC3CQ,EAAItB,GAAQC,KAAK,CAAEyB,KAAM5B,EAAQ6B,SAAUb,GAC/C,GAEA9G,KAAK4H,yBACT,EAACvH,EAOOuH,wBAAA,WACJ,IAAM1B,EAAYlG,KAAKwD,YAAYrD,OAC7BmH,EAAMtH,KAAKyD,cAGXuB,EAAS,IAAIoB,WAAWF,GAE9B,GAAIlG,KAAK0D,YAAc1D,KAAK2D,YAAc3D,KAAK4D,aAG3C,IAFA,IAAMF,EAAa1D,KAAK0D,WAClBmE,EAAU9I,KAAK+I,IAAI9H,KAAK6D,aAAcqC,GACnCxF,EAAI,EAAGA,EAAImH,EAASnH,IACzBsE,EAAOtE,IAAOgD,EAAWhD,EAAI,GAAKgD,EAAWhD,GAIrD,IAAK,IAAIA,EAAI,EAAGA,EAAIwF,EAAWxF,IAAK,CAChC,IAAMqH,EAAYT,EAAI5G,GAClBqH,GAAaA,EAAU5H,SAAQ6E,EAAOtE,IAAMqH,EAAU5H,OAC9D,CAGA,IADA,IAAMgG,EAAU,IAAIC,WAAWF,EAAY,GAClCxF,EAAI,EAAGA,EAAIwF,EAAWxF,IAC3ByF,EAAQzF,EAAI,GAAKyF,EAAQzF,GAAKsE,EAAOtE,GAEzC,IAAM6F,EAAaJ,EAAQD,GACrBM,EAAU,IAAIJ,WAAWG,GACzBE,EAAY,IAAIC,aAAaH,GAC7BI,EAASR,EAAQS,QAGvB,GAAI5G,KAAK0D,YAAc1D,KAAK2D,YAAc3D,KAAK4D,aAK3C,IAJA,IAAMF,EAAa1D,KAAK0D,WAClBC,EAAa3D,KAAK2D,WAClBC,EAAe5D,KAAK4D,aACpBiE,EAAU9I,KAAK+I,IAAI9H,KAAK6D,aAAcqC,GACnChF,EAAI,EAAGA,EAAI2G,EAAS3G,IAAK,CAI9B,IAHA,IACM8G,EAAStE,EAAWxC,EAAI,GAC1B6F,EAAMJ,EAAOzF,GACRR,EAHQgD,EAAWxC,GAGLR,EAAIsH,EAAQtH,IAC/B8F,EAAQO,GAAOpD,EAAWjD,GAC1B+F,EAAUM,GAAOnD,EAAalD,GAC9BqG,IAEJJ,EAAOzF,GAAK6F,CAChB,CAIJ,IAAK,IAAI7F,EAAI,EAAGA,EAAIgF,EAAWhF,IAAK,CAChC,IAAM6G,EAAYT,EAAIpG,GACtB,GAAK6G,GAAkC,IAArBA,EAAU5H,OAA5B,CAEA,IADA,IAAI4G,EAAMJ,EAAOzF,GACRR,EAAI,EAAGuH,EAAMF,EAAU5H,OAAQO,EAAIuH,EAAKvH,IAAK,CAClD,IAAMwH,EAAKH,EAAUrH,GACrB8F,EAAQO,GAAOmB,EAAGR,KAClBjB,EAAUM,GAAOmB,EAAGP,SACpBZ,GACJ,CACAJ,EAAOzF,GAAK6F,CAPZ,CAQJ,CAGA/G,KAAK0D,WAAayC,EAClBnG,KAAK2D,WAAa6C,EAClBxG,KAAK4D,aAAe6C,EACpBzG,KAAK6D,aAAeqC,EACpBlG,KAAKkE,gBAAiB,EACtBlE,KAAK8D,kBAAoB,EACzB9D,KAAK+D,cAAgB,EACrB/D,KAAKgE,sBAAwB,KAG7BhE,KAAKyD,cAAgB,IAAIuD,MAAMd,EACnC,EAAC7F,EAWM8H,SAAA,SACHC,EACAC,SAEA,GAAqB,OAAjBrI,KAAKmD,QACL,MAAM,IAAIgE,MAAM,kEAIpB,IAAMmB,EAAatI,KAAKuI,iBAAiBH,EAAM5C,SAAShC,aAClDgF,EAAWxI,KAAKuI,iBAAiBF,EAAI7C,SAAShC,aAGpD,GAAI8E,IAAeE,EACf,YAIJ,IAAMhF,EAAcxD,KAAKwD,YACnBiF,EAAYzI,KAAKyD,cACjBC,EAAa1D,KAAK0D,WAClBC,EAAa3D,KAAK2D,WAClBC,EAAe5D,KAAK4D,aACpBC,EAAe7D,KAAK6D,aACpB6E,IAAWhF,EACXiF,EAAmBpH,OAAOC,kBAC1BuD,EAAkB/E,KAAKoD,oBACvBwF,EAAiBP,EAAI7C,SAAShC,YAEpCxD,KAAK6I,8BACL,IAAM7E,EAAwBhE,KAAKgE,sBAC7BF,EAAoB9D,KAAK8D,kBACzBC,EAAgB/D,KAAK+D,cAGrBmC,EAAY1C,EAAYrD,OAC9BH,KAAK8I,cAAc5C,GAGnB,IAAM6C,EAAK/I,KAAKmE,cACV6E,EAAQhJ,KAAKoE,gBACb6E,EAAOjJ,KAAKqE,eACZ6E,EAAYlJ,KAAKsE,iBACjB6E,EAAiBnJ,KAAKuE,sBAE5BwE,EAAGK,KAAKT,EAAkB,EAAGzC,GAC7B8C,EAAMI,MAAM,EAAG,EAAGlD,GAClB+C,EAAKG,KAAK,EAAG,EAAGlD,GAGhB,IAAImD,EAAcrJ,KAAKwE,oBAAsB,IAAO,EACjC,IAAf6E,IACAF,EAAeC,KAAK,EAAG,EAAGlD,GAC1BmD,EAAa,GAEjBrJ,KAAKwE,oBAAsB6E,EAE3B,IAAMC,EAAe,SAAC5B,GAClB,GAAIyB,EAAezB,KAAU2B,EAGzB,GAFAF,EAAezB,GAAQ2B,EAEnBrF,GAAyBD,EAAgB,GAAK2D,EAAO5D,GAAqB0E,EAAW1E,EAAmB,CAExG,IADA,IAAIyF,EAAa,EACRC,EAAI,EAAGC,EAAS,EAAGD,EAAIzF,EAAeyF,IAAKC,GAAU3F,EAAmB,CAC7E,IAAM4F,EAAiB1F,EAAsByF,EAAS/B,GAChDiC,EAAgB3F,EAAsByF,EAASjB,GAErD,GAAKjH,OAAOqI,SAASF,IAAoBnI,OAAOqI,SAASD,GAAzD,CAIA,IAAME,EAAqBF,GAAiBD,EACtCC,EAAgBD,EAChBA,EAAiBC,EAEnBE,EAAqBN,IACrBA,EAAaM,EAPjB,CASJ,CACAX,EAAUxB,GAAQ6B,CACtB,MACIL,EAAUxB,GAAQ3C,EAAgBvB,EAAYkE,GAAOkB,GAG7D,OAAOM,EAAUxB,EACrB,EAGMoC,SAAUC,EAAG/J,KAAK0E,aAAWqF,EAAK/J,KAAK0E,YAAc,IAAQ1E,KAACqD,gBAC9D2G,EAAWF,EACXG,IAAaD,EAASvI,MAEtByI,EAASD,EAAWH,EAAa,IAAI9J,KAAKqD,gBAShD,IAPI4G,GACAD,EAASvI,QAGbsH,EAAGT,GAAc,EACjB4B,EAAO3J,OAAO+I,EAAahB,GAAaA,GAEjC4B,EAAOxI,OAAS,GAAG,CACtB,IAAMyI,EAAUD,EAAOjJ,aACvB,GAAgB,OAAZkJ,EACA,MAEJ,GAAsB,IAAlBlB,EAAKkB,GAAT,CAGA,GAAIA,IAAY3B,EACZ,MAGJS,EAAKkB,GAAW,EAChB,IAAMC,EAAkBrB,EAAGoB,GAG3B,GADkBzB,GAAUyB,EAAUtG,EAsBtC,IAAK,IAAInD,EAAIgD,EAAYyG,GAAUnC,EAAStE,EAAYyG,EAAU,GAAIzJ,EAAIsH,EAAQtH,IAAK,CACnF,IAAM2J,EAAS1G,EAAYjD,GACrB4J,EAAaF,EAAkBxG,EAAclD,GAC/C4J,GAAcvB,EAAGsB,KAIrBtB,EAAGsB,GAAUC,EACbtB,EAAMqB,GAAUF,EAChBD,EAAO3J,OAAO+J,EAAahB,EAAae,GAASA,GACrD,KA/BA,CACI,IAAMtC,EAAYU,EAAU0B,GAC5B,IAAKpC,GAAkC,IAArBA,EAAU5H,OACxB,SAGJ,IAAK,IAAIO,EAAI,EAAGQ,EAAI6G,EAAU5H,OAAQO,EAAIQ,EAAGR,IAAK,CAC9C,IAAMwH,EAAKH,EAAUrH,GACf2J,EAASnC,EAAGR,KACZ4C,EAAaF,EAAkBlC,EAAGP,SACpC2C,GAAcvB,EAAGsB,KAIrBtB,EAAGsB,GAAUC,EACbtB,EAAMqB,GAAUF,EAChBD,EAAO3J,OAAO+J,EAAahB,EAAae,GAASA,GACrD,CAEJ,CA5BA,CAyCJ,CAEA,GAAItB,EAAGP,KAAcG,EACjB,OACJ,KAMA,IAHA,IAAM4B,EAAmB,GAErBC,EAAMhC,EACHgC,IAAQlC,GAAckC,GAAO,GAChCD,EAAKtE,KAAKzC,EAAYgH,IACtBA,EAAMxB,EAAMwB,GAKhB,OAHAD,EAAKtE,KAAKzC,EAAY8E,IACtBiC,EAAKE,UAEE,CACHrD,KAAM,UACN5B,SAAU,CAAE4B,KAAM,aAAc5D,YAAa+G,GAC7CG,WAAY,CAAA,EAEpB,EAACrK,EAGOsK,2BAAA,WACJ,IAAMxE,EAAUnG,KAAK0D,WACf8C,EAAUxG,KAAK2D,WACf8C,EAAYzG,KAAK4D,aACjBsC,EAAYlG,KAAK6D,aAEvB,IAAKsC,IAAYK,IAAYC,GAA2B,IAAdP,EAItC,OAHAlG,KAAK8D,kBAAoB,EACzB9D,KAAK+D,cAAgB,OACrB/D,KAAKgE,sBAAwB,MASjC,IALA,IAAM4G,EAAsB7L,KAAK+I,IAAI9H,KAAKiE,aAAciC,GAClD2E,EAAW,IAAIC,WAAW5E,GAC1B6E,EAA+B,GAEjCC,EAAS,EACJC,EAAgB,EAAGA,EAAgBL,EAAqBK,IAAiB,CAC9EJ,EAASG,GAAU,EAEnB,IAAME,EAAoBlL,KAAKmL,6BAA6BH,EAAQ9E,EAAWC,EAASK,EAASC,GACjGsE,EAAa9E,KAAKiF,GAIlB,IAFA,IAAIE,GAAoB,EACpBC,GAAiB,EACZ3D,EAAO,EAAGA,EAAOxB,EAAWwB,IACjC,GAAuB,IAAnBmD,EAASnD,GAAb,CAIA,IAAM4D,EAAiBJ,EAAkBxD,GACpCnG,OAAOqI,SAAS0B,IAIjBA,EAAiBF,IACjBA,EAAmBE,EACnBD,EAAgB3D,EATpB,CAaJ,GAAI2D,EAAgB,EAChB,MAEJL,EAASK,CACb,CAKA,IAHA,IAAMtH,EAAgBgH,EAAa5K,OAE7BoL,EAAO,IAAI7E,aAAa3C,EAAgBmC,GACrCxF,EAAI,EAAGA,EAAIqD,EAAerD,IAC/B6K,EAAKC,IAAIT,EAAarK,GAAIA,EAAIwF,GAGlClG,KAAK8D,kBAAoBoC,EACzBlG,KAAK+D,cAAgBA,EACrB/D,KAAKgE,sBAAwBuH,EAC7BvL,KAAKkE,gBAAiB,CAC1B,EAAC7D,EAGOwI,4BAAA,WACC7I,KAAKkE,gBAGVlE,KAAK2K,4BACT,EAACtK,EAGO8K,6BAAA,SACJH,EACA9E,EACAC,EACAK,EACAC,GAEA,IAAMkC,EAAmBpH,OAAOC,kBAC1BiK,EAAe,IAAI/E,aAAaR,GAChCwF,EAAU,IAAIZ,WAAW5E,GAC/BuF,EAAarC,KAAKT,GAClB8C,EAAaT,GAAU,EAEvB,IAAMW,EAAU,IAAI3L,KAAKqD,gBAGzB,IAFAsI,EAAQpL,OAAO,EAAGyK,GAEXW,EAAQjK,OAAS,GAAG,CACvB,IAAMyI,EAAUwB,EAAQ1K,aACxB,GAAgB,OAAZkJ,EACA,MAEJ,GAAyB,IAArBuB,EAAQvB,GAAZ,CAIAuB,EAAQvB,GAAW,EAGnB,IAFA,IAAMC,EAAkBqB,EAAatB,GAE5BzJ,EAAIyF,EAAQgE,GAAUyB,EAAYzF,EAAQgE,EAAU,GAAIzJ,EAAIkL,EAAWlL,IAAK,CACjF,IAAMmL,EAAWrF,EAAQ9F,GACnBoL,EAAoB1B,EAAkB3D,EAAU/F,GAClDoL,GAAqBL,EAAaI,KAItCJ,EAAaI,GAAYC,EACzBH,EAAQpL,OAAOuL,EAAmBD,GACtC,CAdA,CAeJ,CAEA,OAAOJ,CACX,EAACpL,EAKOkI,iBAAA,SAAiBwD,GACrB,IAAMC,EAAMD,EAAM,GACZE,EAAMF,EAAM,GAEdG,EAASlM,KAAKsD,mBAAmB6I,IAAIH,QAC1BzE,IAAX2E,IACAA,EAAS,IAAI3I,IACbvD,KAAKsD,mBAAmBkI,IAAIQ,EAAKE,IAGrC,IAAIE,EAAQF,EAAOC,IAAIF,GACvB,QAAc1E,IAAV6E,IAEAA,EAAQpM,KAAKwD,YAAYrD,OACzBH,KAAKwD,YAAYyC,KAAK8F,GACtBG,EAAOV,IAAIS,EAAKG,GAGhBpM,KAAKyD,cAAc2I,GAAS,GAGxBpM,KAAK0D,YAAY,CAGjB,IAAM2I,EAAWrM,KAAK6D,aAGtB,GAAIuI,IAAUC,EAAU,CACpB,IAAMC,EAAa,IAAIlG,WAAWiG,EAAW,GAC7CC,EAAWd,IAAIxL,KAAK0D,WAAY,GAGhC4I,EAAWD,EAAW,GAAKC,EAAWD,GACtCrM,KAAK0D,WAAa4I,EAClBtM,KAAK6D,aAAewI,EAAW,CACnC,CACJ,CAGJ,OAAOD,CACX,EAAC/L,EAGOyI,cAAA,SAAcpH,GAQlB,KAP2B1B,KAAKyE,iBAAmB/C,GAC5C1B,KAAKmE,eACLnE,KAAKoE,iBACLpE,KAAKqE,gBACLrE,KAAKsE,kBACLtE,KAAKuE,uBAEZ,CAGA,IAAMgI,EAAkB,EAAP7K,EACjB1B,KAAKmE,cAAgB,IAAIuC,aAAa6F,GACtCvM,KAAKoE,gBAAkB,IAAIgC,WAAWmG,GACtCvM,KAAKqE,eAAiB,IAAIyG,WAAWyB,GACrCvM,KAAKsE,iBAAmB,IAAIoC,aAAa6F,GACzCvM,KAAKuE,sBAAwB,IAAIiI,YAAYD,GAC7CvM,KAAKyE,gBAAkB8H,CAPvB,CAQJ,EAAClM,EAKOmH,eAAA,SACJrE,EACAsJ,GAGA,IADA,IAAMrH,EAAWjC,EAAQiC,SAChBC,EAAI,EAAGqH,EAAOtH,EAASjF,OAAQkF,EAAIqH,EAAMrH,IAE9C,IADA,IAAME,EAAaH,EAASC,GAAGG,SAAShC,YAC/B9C,EAAI,EAAGuH,EAAM1C,EAAWpF,OAAS,EAAGO,EAAIuH,EAAKvH,IAElD+L,EAAGlH,EAAW7E,GAAgB6E,EAAW7E,EAAI,GAGzD,EAACL,EAIO0F,gBAAA,SACJgG,EACAlH,EACAC,EACA6H,GAEA,IAAMX,EAAMD,EAAM,GACZE,EAAMF,EAAM,GAEdG,EAASrH,EAAmBsH,IAAIH,QACrBzE,IAAX2E,IACAA,EAAS,IAAI3I,IACbsB,EAAmB2G,IAAIQ,EAAKE,IAGhC,IAAIrK,EAAMqK,EAAOC,IAAIF,GAQrB,YAPY1E,IAAR1F,IACAA,EAAMiD,EAAY3E,OAClB2E,EAAYmB,KAAK8F,GACjBG,EAAOV,IAAIS,EAAKpK,GACZ8K,GAAYA,EAAW9K,IAGxBA,CACX,EAACkB,CAAA,CAhpBW,4BCoBV,SAA2BkJ,GAC7B,IACMW,EAAK,EAAI,cACTC,EAAKD,GAAM,EAAIA,GACfE,EAAM/N,KAAKC,GAAK,IAEhB+N,EAAShO,KAAKY,IAAIsM,EAAMa,GACxBE,EAAK,GAAK,EAAIH,GAAM,EAAIE,EAASA,IACjCE,EAAIlO,KAAKc,KAAKmN,GAEdE,EATK,SASDJ,EACJK,EAAKD,EAAID,EAAIF,EACbK,EAAKF,EAAID,EAAID,GAAM,EAAIH,GAE7B,OAAgB,SAASnN,EAAa+H,GAGlC,IAFA,IAAI4F,EAAW3N,EAAE,GAAK+H,EAAE,GAEjB4F,GAAY,KAAKA,GAAY,IACpC,KAAOA,EAAW,KAAKA,GAAY,IAEnC,IAAMC,EAAKD,EAAWF,EAChBI,GAAM7N,EAAE,GAAK+H,EAAE,IAAM2F,EAE3B,OAAOrO,KAAKc,KAAKyN,EAAKA,EAAKC,EAAKA,EACpC,CACJ"}