{"version":3,"file":"terra-route-graph.cjs","sources":["../src/methods/connected.ts","../src/methods/unique.ts","../src/methods/duplicates.ts","../src/methods/leaf.ts","../src/methods/bounding-box.ts","../src/distance/haversine.ts","../src/methods/spatial-index/kdbush.ts","../src/methods/spatial-index/tinyqueue.ts","../src/methods/spatial-index/geokdbush.ts","../src/test-utils/utils.ts","../src/terra-route-graph.ts","../src/methods/nodes.ts","../src/methods/unify.ts"],"sourcesContent":["import { Feature, FeatureCollection, LineString, Position } from 'geojson'\n\n/**\n * Counts the number of connected components in a graph represented by LineString features in a GeoJSON FeatureCollection.\n * Each LineString is treated as an edge in the graph, and connected components are determined by shared coordinates.\n * @param featureCollection - A GeoJSON FeatureCollection containing LineString features\n * @returns The number of connected components in the graph represented by the LineStrings\n */\nexport function graphGetConnectedComponentCount(\n    featureCollection: FeatureCollection<LineString>\n): number {\n    const features = featureCollection.features\n    const numberOfFeatures = features.length\n\n    // Map coordinates to feature indices\n    const coordinateToFeatureIndices = new Map<string, number[]>()\n\n    for (let index = 0; index < numberOfFeatures; index++) {\n        const coordinates = features[index].geometry.coordinates\n\n        for (const coordinate of coordinates) {\n            const key = coordinateKey(coordinate)\n\n            if (!coordinateToFeatureIndices.has(key)) {\n                coordinateToFeatureIndices.set(key, [])\n            }\n\n            coordinateToFeatureIndices.get(key)!.push(index)\n        }\n    }\n\n    // Build adjacency list for the graph\n    const adjacencyList: number[][] = Array.from({ length: numberOfFeatures }, () => [])\n\n    for (const indices of coordinateToFeatureIndices.values()) {\n        for (let i = 0; i < indices.length; i++) {\n            for (let j = i + 1; j < indices.length; j++) {\n                const a = indices[i]\n                const b = indices[j]\n                adjacencyList[a].push(b)\n                adjacencyList[b].push(a)\n            }\n        }\n    }\n\n    const visited = new Array<boolean>(numberOfFeatures).fill(false)\n    let connectedComponents = 0\n\n    for (let index = 0; index < numberOfFeatures; index++) {\n        if (!visited[index]) {\n            dfs(index, adjacencyList, visited)\n            connectedComponents++\n        }\n    }\n\n    return connectedComponents\n}\n\n/**\n * Depth-first search to mark all reachable nodes from the given index.\n * @param index - The current node index to start DFS from.\n * @param adjacencyList - The adjacency list representing the graph.\n * @param visited - An array to keep track of visited nodes.\n */\nfunction dfs(index: number, adjacencyList: number[][], visited: boolean[]): void {\n    visited[index] = true\n\n    for (const neighbor of adjacencyList[index]) {\n        if (!visited[neighbor]) {\n            dfs(neighbor, adjacencyList, visited)\n        }\n    }\n}\n\nfunction coordinateKey(position: Position): string {\n    return `${position[0]},${position[1]}`\n}\n\nexport function graphGetConnectedComponents(\n    featureCollection: FeatureCollection<LineString>\n): FeatureCollection<LineString>[] {\n    const features = featureCollection.features\n    const graph: Map<number, Set<number>> = new Map()\n    const coordinateMap: Map<string, Set<number>> = new Map()\n\n    function coordinateKey(coordinate: Position): string {\n        return `${coordinate[0]},${coordinate[1]}`\n    }\n\n    // Build coordinate map: coordinate string -> Set of feature indices\n    for (let index = 0; index < features.length; index++) {\n        const coordinates = features[index].geometry.coordinates\n\n        for (const coordinate of coordinates) {\n            const key = coordinateKey(coordinate)\n\n            if (!coordinateMap.has(key)) {\n                coordinateMap.set(key, new Set())\n            }\n\n            coordinateMap.get(key)!.add(index)\n        }\n    }\n\n    // Build adjacency list for graph\n    for (let index = 0; index < features.length; index++) {\n        graph.set(index, new Set())\n\n        const coordinates = features[index].geometry.coordinates\n        for (const coordinate of coordinates) {\n            const key = coordinateKey(coordinate)\n            const neighbors = coordinateMap.get(key)\n\n            if (neighbors) {\n                for (const neighborIndex of neighbors) {\n                    if (neighborIndex !== index) {\n                        graph.get(index)!.add(neighborIndex)\n                    }\n                }\n            }\n        }\n    }\n\n    // DFS to find connected components\n    const visited = new Set<number>()\n    const components: FeatureCollection<LineString>[] = []\n\n    function dfs(startIndex: number, currentComponent: Feature<LineString>[]): void {\n        const stack: number[] = [startIndex]\n\n        while (stack.length > 0) {\n            const currentIndex = stack.pop()!\n\n            if (visited.has(currentIndex)) {\n                continue\n            }\n\n            visited.add(currentIndex)\n            currentComponent.push(features[currentIndex])\n\n            const neighbors = graph.get(currentIndex)\n            if (neighbors) {\n                for (const neighbor of neighbors) {\n                    if (!visited.has(neighbor)) {\n                        stack.push(neighbor)\n                    }\n                }\n            }\n        }\n    }\n\n    for (let index = 0; index < features.length; index++) {\n        if (!visited.has(index)) {\n            const component: Feature<LineString>[] = []\n            dfs(index, component)\n            components.push({\n                type: 'FeatureCollection',\n                features: component\n            })\n        }\n    }\n\n\n    // Sort components by the number of features in ascending order\n    components.sort((a, b) => a.features.length - b.features.length)\n\n    return components\n}\n","import {\n    Feature,\n    FeatureCollection,\n    LineString,\n    Position\n} from 'geojson';\n\n/**\n * Normalize a segment so that [A, B] is equal to [B, A]\n */\nfunction normalizeSegment(start: Position, end: Position): [Position, Position] {\n    const [aLat, aLng] = start;\n    const [bLat, bLng] = end;\n\n    if (\n        aLat < bLat ||\n        (aLat === bLat && aLng <= bLng)\n    ) {\n        return [start, end];\n    }\n\n    return [end, start];\n}\n\n/**\n * Convert a pair of Positions to a string key for deduplication\n */\nfunction segmentKey(start: Position, end: Position): string {\n    const [normalizedStart, normalizedEnd] = normalizeSegment(start, end);\n    return JSON.stringify([normalizedStart, normalizedEnd]);\n}\n\n/**\n * Breaks LineStrings in a FeatureCollection into unique single line segments\n */\nexport function graphGetUniqueSegments(\n    input: FeatureCollection<LineString>\n): FeatureCollection<LineString> {\n    const uniqueSegments = new Map<string, Feature<LineString>>();\n\n    for (const feature of input.features) {\n        const coordinates = feature.geometry.coordinates;\n\n        for (let index = 0; index < coordinates.length - 1; index++) {\n            const start = coordinates[index];\n            const end = coordinates[index + 1];\n\n            const key = segmentKey(start, end);\n\n            if (!uniqueSegments.has(key)) {\n                const segment: Feature<LineString> = {\n                    type: 'Feature',\n                    geometry: {\n                        type: 'LineString',\n                        coordinates: [start, end]\n                    },\n                    properties: {}\n                };\n\n                uniqueSegments.set(key, segment);\n            }\n        }\n    }\n\n    return {\n        type: 'FeatureCollection',\n        features: Array.from(uniqueSegments.values())\n    };\n}\n","import { FeatureCollection, LineString, Feature, Position } from 'geojson'\n\n/**\n * Are the two coordinate sequences exactly equal (in same order)?\n */\nfunction areCoordinatesEqual(a: Position[], b: Position[]): boolean {\n    if (a.length !== b.length) {\n        return false\n    }\n\n    for (let i = 0; i < a.length; i++) {\n        if (a[i][0] !== b[i][0] || a[i][1] !== b[i][1]) {\n            return false\n        }\n    }\n\n    return true\n}\n\n/**\n * Is `sub` a contiguous subsequence of `full`, either forward or reversed?\n */\nfunction isSubsequence(sub: Position[], full: Position[]): boolean {\n    const subLength = sub.length\n    const fullLength = full.length\n\n    if (subLength > fullLength) {\n        return false\n    }\n\n    // check forward\n    for (let start = 0; start <= fullLength - subLength; start++) {\n        let matches = true\n\n        for (let offset = 0; offset < subLength; offset++) {\n            if (\n                full[start + offset][0] !== sub[offset][0] ||\n                full[start + offset][1] !== sub[offset][1]\n            ) {\n                matches = false\n                break\n            }\n        }\n\n        if (matches) {\n            return true\n        }\n    }\n\n    // check reversed\n    const reversedSub = [...sub].reverse()\n\n    for (let start = 0; start <= fullLength - subLength; start++) {\n        let matches = true\n\n        for (let offset = 0; offset < subLength; offset++) {\n            if (\n                full[start + offset][0] !== reversedSub[offset][0] ||\n                full[start + offset][1] !== reversedSub[offset][1]\n            ) {\n                matches = false\n                break\n            }\n        }\n\n        if (matches) {\n            return true\n        }\n    }\n\n    return false\n}\n\n/**\n * Remove any LineString that is either\n *  - an exact duplicate of an earlier one, or\n *  - a contiguous subsequence (in either direction) of any other.\n */\nexport function removeDuplicateAndSubsectionLines(\n    collection: FeatureCollection<LineString>\n): FeatureCollection<LineString> {\n    const features = collection.features\n    const toRemove = new Set<number>()\n\n    for (let i = 0; i < features.length; i++) {\n        const coordsI = features[i].geometry.coordinates\n\n        for (let j = 0; j < features.length; j++) {\n            if (i === j) {\n                continue\n            }\n\n            const coordsJ = features[j].geometry.coordinates\n\n            // if coordsI are a subsequence of coordsJ, OR exactly equal,\n            // then mark coordsI for removal—but only if\n            //   • coordsI is strictly shorter than coordsJ, or\n            //   • they’re the same length and this is the later duplicate (i > j)\n            if (\n                isSubsequence(coordsI, coordsJ) &&\n                (\n                    coordsI.length < coordsJ.length ||\n                    (coordsI.length === coordsJ.length && i > j)\n                )\n            ) {\n                toRemove.add(i)\n                break\n            }\n        }\n    }\n\n    const filtered = features.filter((_, index) => !toRemove.has(index))\n    return {\n        type: 'FeatureCollection',\n        features: filtered\n    }\n}\n","import { FeatureCollection, LineString, Feature } from 'geojson';\nimport { graphGetUniqueSegments } from './unique';\n\n/**\n * Separates a graph's edges into leaf and non-leaf edges.\n * A leaf edge has a start or end node with degree 1.\n *\n * @param edgesFc - FeatureCollection containing LineString features representing edges of a graph\n * @returns Object containing two FeatureCollections: leafEdges and nonLeafEdges\n */\nexport function getLeafEdges(\n    edgesFc: FeatureCollection<LineString>\n): {\n    leafEdges: FeatureCollection<LineString>;\n    nonLeafEdges: FeatureCollection<LineString>;\n} {\n    const edges = graphGetUniqueSegments(edgesFc);\n\n    const endpointCountMap: Map<string, number> = new Map();\n\n    function coordKey(position: number[]): string {\n        return position.join(\",\");\n    }\n\n    // Count the degree (number of edge endpoints) for each coordinate\n    for (let i = 0; i < edges.features.length; i++) {\n        const feature = edges.features[i];\n        const coordinates = feature.geometry.coordinates;\n\n        if (coordinates.length < 2) {\n            continue;\n        }\n\n        const startKey = coordKey(coordinates[0]);\n        const endKey = coordKey(coordinates[coordinates.length - 1]);\n\n        endpointCountMap.set(\n            startKey,\n            (endpointCountMap.get(startKey) || 0) + 1\n        );\n        endpointCountMap.set(\n            endKey,\n            (endpointCountMap.get(endKey) || 0) + 1\n        );\n    }\n\n    const leafEdgeMap: Map<string, Feature<LineString>> = new Map();\n    const nonLeafEdgeMap: Map<string, Feature<LineString>> = new Map();\n\n    for (let i = 0; i < edges.features.length; i++) {\n        const feature = edges.features[i];\n        const coordinates = feature.geometry.coordinates;\n\n        if (coordinates.length < 2) {\n            continue;\n        }\n\n        const startKey = coordKey(coordinates[0]);\n        const endKey = coordKey(coordinates[coordinates.length - 1]);\n\n        const startCount = endpointCountMap.get(startKey) || 0;\n        const endCount = endpointCountMap.get(endKey) || 0;\n\n        const edgeKey = coordinates.map(coordKey).join(\";\");\n\n        if (startCount === 1 || endCount === 1) {\n            if (!leafEdgeMap.has(edgeKey)) {\n                leafEdgeMap.set(edgeKey, feature);\n            }\n        } else {\n            if (!nonLeafEdgeMap.has(edgeKey)) {\n                nonLeafEdgeMap.set(edgeKey, feature);\n            }\n        }\n    }\n\n    return {\n        leafEdges: {\n            type: \"FeatureCollection\",\n            features: Array.from(leafEdgeMap.values())\n        },\n        nonLeafEdges: {\n            type: \"FeatureCollection\",\n            features: Array.from(nonLeafEdgeMap.values())\n        }\n    };\n}\n\n","import { Feature, FeatureCollection, LineString, Position } from 'geojson'\n\n/**\n * Type representing a bounding box as [minLng, minLat, maxLng, maxLat]\n */\nexport type BoundingBox = [number, number, number, number]\n\n/**\n * Filters a FeatureCollection of LineString features to only include LineStrings \n * that are completely within the specified bounding box.\n * @param featureCollection - A GeoJSON FeatureCollection containing LineString features\n * @param boundingBox - A bounding box array in the format [minLng, minLat, maxLng, maxLat]\n * @returns A new FeatureCollection<LineString> containing only the LineStrings completely within the bounding box\n */\nexport function getNetworkInBoundingBox(\n    featureCollection: FeatureCollection<LineString>,\n    boundingBox: BoundingBox\n): FeatureCollection<LineString> {\n    const [minLng, minLat, maxLng, maxLat] = boundingBox\n\n    // Validate bounding box\n    if (minLng >= maxLng || minLat >= maxLat) {\n        throw new Error('Invalid bounding box: min values must be less than max values')\n    }\n\n    const filteredFeatures: Feature<LineString>[] = []\n\n    for (const feature of featureCollection.features) {\n        if (isLineStringCompletelyWithinBounds(feature, minLng, minLat, maxLng, maxLat)) {\n            filteredFeatures.push(feature)\n        }\n    }\n\n    return {\n        type: 'FeatureCollection',\n        features: filteredFeatures\n    }\n}\n\n/**\n * Checks if a LineString feature is completely within the specified bounds.\n * @param lineStringFeature - A GeoJSON Feature<LineString>\n * @param minLng - Minimum longitude\n * @param minLat - Minimum latitude\n * @param maxLng - Maximum longitude\n * @param maxLat - Maximum latitude\n * @returns true if all coordinates of the LineString are within the bounds, false otherwise\n */\nfunction isLineStringCompletelyWithinBounds(\n    lineStringFeature: Feature<LineString>,\n    minLng: number,\n    minLat: number,\n    maxLng: number,\n    maxLat: number\n): boolean {\n    const coordinates = lineStringFeature.geometry.coordinates\n\n    for (const coordinate of coordinates) {\n        if (!isCoordinateWithinBounds(coordinate, minLng, minLat, maxLng, maxLat)) {\n            return false\n        }\n    }\n\n    return true\n}\n\n/**\n * Checks if a coordinate is within the specified bounds.\n * @param coordinate - A coordinate position [lng, lat]\n * @param minLng - Minimum longitude\n * @param minLat - Minimum latitude\n * @param maxLng - Maximum longitude\n * @param maxLat - Maximum latitude\n * @returns true if the coordinate is within the bounds, false otherwise\n */\nfunction isCoordinateWithinBounds(\n    coordinate: Position,\n    minLng: number,\n    minLat: number,\n    maxLng: number,\n    maxLat: number\n): boolean {\n    const [lng, lat] = coordinate\n    return lng >= minLng && lng <= maxLng && lat >= minLat && lat <= maxLat\n}\n","import { Position } from \"geojson\";\n\n/** Distance measured in kilometers */\nexport const haversineDistance = (pointOne: Position, pointTwo: Position): number => {\n    const toRadians = (latOrLng: number) => (latOrLng * Math.PI) / 180;\n\n    const phiOne = toRadians(pointOne[1]);\n    const lambdaOne = toRadians(pointOne[0]);\n    const phiTwo = toRadians(pointTwo[1]);\n    const lambdaTwo = toRadians(pointTwo[0]);\n    const deltaPhi = phiTwo - phiOne;\n    const deltalambda = lambdaTwo - lambdaOne;\n\n    const a =\n        Math.sin(deltaPhi / 2) * Math.sin(deltaPhi / 2) +\n        Math.cos(phiOne) *\n        Math.cos(phiTwo) *\n        Math.sin(deltalambda / 2) *\n        Math.sin(deltalambda / 2);\n    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));\n\n    const radius = 6371e3;\n    const distance = radius * c;\n\n\n    // Convert distance from meters to kilometers\n    return distance / 1000;\n}\n","// Adapted from https://github.com/mourner/kdbush\n\n// ISC License\n\n// Copyright (c) 2018, Vladimir Agafonkin\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\nconst ARRAY_TYPES = [\n    Int8Array, Uint8Array, Uint8ClampedArray, Int16Array, Uint16Array,\n    Int32Array, Uint32Array, Float32Array, Float64Array\n];\n\nconst VERSION = 1;\nconst HEADER_SIZE = 8;\n\nexport class KDBush {\n    public data: ArrayBuffer;\n    public ids: Uint16Array | Uint32Array;\n    public coords: InstanceType<TypedArrayConstructor>;\n    private _pos: number;\n    private _finished: boolean;\n    public numItems: number;\n    public nodeSize: number;\n    private ArrayType: TypedArrayConstructor;\n    private IndexArrayType: typeof Uint16Array | typeof Uint32Array;\n\n    constructor(\n        numItems: number,\n        nodeSize: number = 64,\n        ArrayType: TypedArrayConstructor = Float64Array,\n        data?: ArrayBuffer\n    ) {\n        if (isNaN(numItems) || numItems < 0) {\n            throw new Error(`Unexpected numItems value: ${numItems}.`);\n        }\n\n        this.numItems = numItems;\n        this.nodeSize = Math.min(Math.max(nodeSize, 2), 65535);\n        this.ArrayType = ArrayType;\n        this.IndexArrayType = numItems < 65536 ? Uint16Array : Uint32Array;\n\n        const arrayTypeIndex = ARRAY_TYPES.indexOf(this.ArrayType);\n        const coordsByteSize = numItems * 2 * this.ArrayType.BYTES_PER_ELEMENT;\n        const idsByteSize = numItems * this.IndexArrayType.BYTES_PER_ELEMENT;\n        const padCoords = (8 - idsByteSize % 8) % 8;\n\n        if (arrayTypeIndex < 0) {\n            throw new Error(`Unexpected typed array class: ${ArrayType}.`);\n        }\n\n        if (data) {\n            this.data = data;\n            this.ids = new (this.IndexArrayType as any)(this.data, HEADER_SIZE, numItems);\n            this.coords = new (this.ArrayType as any)(this.data, HEADER_SIZE + idsByteSize + padCoords, numItems * 2);\n            this._pos = numItems * 2;\n            this._finished = true;\n        } else {\n            this.data = new ArrayBuffer(HEADER_SIZE + coordsByteSize + idsByteSize + padCoords);\n            this.ids = new (this.IndexArrayType as any)(this.data, HEADER_SIZE, numItems);\n            this.coords = new (this.ArrayType as any)(this.data, HEADER_SIZE + idsByteSize + padCoords, numItems * 2);\n            this._pos = 0;\n            this._finished = false;\n\n            new Uint8Array(this.data, 0, 2).set([0xdb, (VERSION << 4) + arrayTypeIndex]);\n            new Uint16Array(this.data, 2, 1)[0] = this.nodeSize;\n            new Uint32Array(this.data, 4, 1)[0] = this.numItems;\n        }\n    }\n\n    add(x: number, y: number): number {\n        const index = this._pos >> 1;\n        this.ids[index] = index;\n        this.coords[this._pos++] = x;\n        this.coords[this._pos++] = y;\n        return index;\n    }\n\n    finish(): this {\n        const numAdded = this._pos >> 1;\n        if (numAdded !== this.numItems) {\n            throw new Error(`Added ${numAdded} items when expected ${this.numItems}.`);\n        }\n        sort(this.ids, this.coords, this.nodeSize, 0, this.numItems - 1, 0);\n        this._finished = true;\n        return this;\n    }\n}\n\ntype TypedArrayConstructor =\n    Int8ArrayConstructor | Uint8ArrayConstructor | Uint8ClampedArrayConstructor |\n    Int16ArrayConstructor | Uint16ArrayConstructor |\n    Int32ArrayConstructor | Uint32ArrayConstructor |\n    Float32ArrayConstructor | Float64ArrayConstructor;\n\nfunction sort(\n    ids: Uint16Array | Uint32Array,\n    coords: InstanceType<TypedArrayConstructor>,\n    nodeSize: number,\n    left: number,\n    right: number,\n    axis: number\n): void {\n    if (right - left <= nodeSize) return;\n    const m = (left + right) >> 1;\n    select(ids, coords, m, left, right, axis);\n    sort(ids, coords, nodeSize, left, m - 1, 1 - axis);\n    sort(ids, coords, nodeSize, m + 1, right, 1 - axis);\n}\n\nfunction select(\n    ids: Uint16Array | Uint32Array,\n    coords: InstanceType<TypedArrayConstructor>,\n    k: number,\n    left: number,\n    right: number,\n    axis: number\n): void {\n    while (right > left) {\n        if (right - left > 600) {\n            const n = right - left + 1;\n            const m = k - left + 1;\n            const z = Math.log(n);\n            const s = 0.5 * Math.exp(2 * z / 3);\n            const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);\n            const newLeft = Math.max(left, Math.floor(k - m * s / n + sd));\n            const newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));\n            select(ids, coords, k, newLeft, newRight, axis);\n        }\n\n        const t = coords[2 * k + axis];\n        let i = left;\n        let j = right;\n\n        swapItem(ids, coords, left, k);\n        if (coords[2 * right + axis] > t) {\n            swapItem(ids, coords, left, right);\n        }\n\n        while (i < j) {\n            swapItem(ids, coords, i, j);\n            i++;\n            j--;\n            while (coords[2 * i + axis] < t) i++;\n            while (coords[2 * j + axis] > t) j--;\n        }\n\n        if (coords[2 * left + axis] === t) {\n            swapItem(ids, coords, left, j);\n        } else {\n            j++;\n            swapItem(ids, coords, j, right);\n        }\n\n        if (j <= k) left = j + 1;\n        if (k <= j) right = j - 1;\n    }\n}\n\nfunction swapItem(\n    ids: Uint16Array | Uint32Array,\n    coords: InstanceType<TypedArrayConstructor>,\n    i: number,\n    j: number\n): void {\n    swap(ids, i, j);\n    swap(coords, 2 * i, 2 * j);\n    swap(coords, 2 * i + 1, 2 * j + 1);\n}\n\nfunction swap<T extends Uint16Array | Uint32Array | Float32Array | Float64Array | Int8Array | Int16Array | Int32Array | Uint8Array | Uint8ClampedArray>(\n    arr: T,\n    i: number,\n    j: number\n): void {\n    const tmp = arr[i];\n    arr[i] = arr[j];\n    arr[j] = tmp;\n}\n","// Adapted from https://github.com/mourner/kdbush\n\n// ISC License\n\n// Copyright (c) 2017, Vladimir Agafonkin\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\nexport default class TinyQueue<T> {\n\n    private data: T[];\n    public length: number;\n    private compare: (a: T, b: T) => number;\n\n    constructor(\n        data: T[] = [],\n        compare: (a: T, b: T) => number = (a, b) =>\n            a < b ? -1 : a > b ? 1 : 0\n    ) {\n        this.data = data;\n        this.length = this.data.length;\n        this.compare = compare;\n\n        if (this.length > 0) {\n            for (let i = (this.length >> 1) - 1; i >= 0; i--) {\n                this._down(i);\n            }\n        }\n    }\n\n    push(item: T): void {\n        this.data.push(item);\n        this._up(this.length++);\n    }\n\n    pop(): T | undefined {\n        if (this.length === 0) {\n            return undefined;\n        }\n\n        const top = this.data[0];\n        const bottom = this.data.pop() as T;\n\n        this.length--;\n\n        if (this.length > 0) {\n            this.data[0] = bottom;\n            this._down(0);\n        }\n\n        return top;\n    }\n\n    peek(): T | undefined {\n        return this.data[0];\n    }\n\n    private _up(pos: number): void {\n        const { data, compare } = this;\n        const item = data[pos];\n\n        while (pos > 0) {\n            const parent = (pos - 1) >> 1;\n            const current = data[parent];\n            if (compare(item, current) >= 0) {\n                break;\n            }\n            data[pos] = current;\n            pos = parent;\n        }\n\n        data[pos] = item;\n    }\n\n    private _down(pos: number): void {\n        const { data, compare } = this;\n        const halfLength = this.length >> 1;\n        const item = data[pos];\n\n        while (pos < halfLength) {\n            let bestChild = (pos << 1) + 1;\n            const right = bestChild + 1;\n\n            if (right < this.length && compare(data[right], data[bestChild]) < 0) {\n                bestChild = right;\n            }\n\n            if (compare(data[bestChild], item) >= 0) {\n                break;\n            }\n\n            data[pos] = data[bestChild];\n            pos = bestChild;\n        }\n\n        data[pos] = item;\n    }\n}\n","// Adapted from https://github.com/mourner/geokdbush\n\n// ISC License\n\n// Copyright (c) 2017, Vladimir Agafonkin\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\nimport { KDBush } from './kdbush';\nimport TinyQueue from './tinyqueue';\n\nconst earthRadius = 6371;\nconst rad = Math.PI / 180;\n\n\n// Distance is in kilometers\nexport function around(index: KDBush, lng: number, lat: number, maxResults = Infinity, maxDistanceKm = Infinity) {\n    let maxHaverSinDist = 1;\n    const result = [];\n\n    if (maxResults === undefined) {\n        maxResults = Infinity;\n    }\n\n    if (maxDistanceKm !== undefined) {\n        maxHaverSinDist = haverSin(maxDistanceKm / earthRadius);\n    }\n\n    // a distance-sorted priority queue that will contain both points and kd-tree nodes\n    const q = new TinyQueue([], compareDist);\n\n    // an object that represents the top kd-tree node (the whole Earth)\n    let node = {\n        left: 0, // left index in the kd-tree array\n        right: index.ids.length - 1, // right index\n        axis: 0, // 0 for longitude axis and 1 for latitude axis\n        dist: 0, // will hold the lower bound of children's distances to the query point\n        minLng: -180, // bounding box of the node\n        minLat: -90,\n        maxLng: 180,\n        maxLat: 90\n    };\n\n    const cosLat = Math.cos(lat * rad);\n\n    while (node) {\n        const right = node.right;\n        const left = node.left;\n\n        if (right - left <= index.nodeSize) { // leaf node\n\n            // add all points of the leaf node to the queue\n            for (let i = left; i <= right; i++) {\n                const id = index.ids[i];\n\n                const dist = haverSinDist(lng, lat, index.coords[2 * i], index.coords[2 * i + 1], cosLat);\n                q.push({ id, dist });\n            }\n\n        } else { // not a leaf node (has child nodes)\n\n            const m = (left + right) >> 1; // middle index\n            const midLng = index.coords[2 * m];\n            const midLat = index.coords[2 * m + 1];\n\n            // add middle point to the queue\n            const id = index.ids[m];\n            const dist = haverSinDist(lng, lat, midLng, midLat, cosLat);\n            q.push({ id, dist });\n\n\n            const nextAxis = (node.axis + 1) % 2;\n\n            // first half of the node\n            const leftNode = {\n                left,\n                right: m - 1,\n                axis: nextAxis,\n                minLng: node.minLng,\n                minLat: node.minLat,\n                maxLng: node.axis === 0 ? midLng : node.maxLng,\n                maxLat: node.axis === 1 ? midLat : node.maxLat,\n                dist: 0\n            };\n            // second half of the node\n            const rightNode = {\n                left: m + 1,\n                right,\n                axis: nextAxis,\n                minLng: node.axis === 0 ? midLng : node.minLng,\n                minLat: node.axis === 1 ? midLat : node.minLat,\n                maxLng: node.maxLng,\n                maxLat: node.maxLat,\n                dist: 0\n            };\n\n            leftNode.dist = boxDist(lng, lat, cosLat, leftNode);\n            rightNode.dist = boxDist(lng, lat, cosLat, rightNode);\n\n            // add child nodes to the queue\n            q.push(leftNode);\n            q.push(rightNode);\n        }\n\n        // fetch closest points from the queue; they're guaranteed to be closer\n        // than all remaining points (both individual and those in kd-tree nodes),\n        // since each node's distance is a lower bound of distances to its children\n        while (q.length && q.peek().id != null) {\n            const candidate = q.pop()!;\n            if (candidate.dist > maxHaverSinDist) return result;\n            result.push(candidate.id);\n            if (result.length === maxResults) return result;\n        }\n\n        // the next closest kd-tree node\n        node = q.pop();\n    }\n\n    return result;\n}\n\n// lower bound for distance from a location to points inside a bounding box\nfunction boxDist(lng: number, lat: number, cosLat: number, node: any) {\n    const minLng = node.minLng;\n    const maxLng = node.maxLng;\n    const minLat = node.minLat;\n    const maxLat = node.maxLat;\n\n    // query point is between minimum and maximum longitudes\n    if (lng >= minLng && lng <= maxLng) {\n        if (lat < minLat) return haverSin((lat - minLat) * rad);\n        if (lat > maxLat) return haverSin((lat - maxLat) * rad);\n        return 0;\n    }\n\n    // query point is west or east of the bounding box;\n    // calculate the extremum for great circle distance from query point to the closest longitude;\n    const haverSinDLng = Math.min(haverSin((lng - minLng) * rad), haverSin((lng - maxLng) * rad));\n    const extremumLat = vertexLat(lat, haverSinDLng);\n\n    // if extremum is inside the box, return the distance to it\n    if (extremumLat > minLat && extremumLat < maxLat) {\n        return haverSinDistPartial(haverSinDLng, cosLat, lat, extremumLat);\n    }\n    // otherwise return the distan e to one of the bbox corners (whichever is closest)\n    return Math.min(\n        haverSinDistPartial(haverSinDLng, cosLat, lat, minLat),\n        haverSinDistPartial(haverSinDLng, cosLat, lat, maxLat)\n    );\n}\n\nfunction compareDist(a: any, b: any) {\n    return a.dist - b.dist;\n}\n\nfunction haverSin(theta: number) {\n    const s = Math.sin(theta / 2);\n    return s * s;\n}\n\nfunction haverSinDistPartial(haverSinDLng: number, cosLat1: number, lat1: number, lat2: number) {\n    return cosLat1 * Math.cos(lat2 * rad) * haverSinDLng + haverSin((lat1 - lat2) * rad);\n}\n\nfunction haverSinDist(lng1: number, lat1: number, lng2: number, lat2: number, cosLat1: number) {\n    const haverSinDLng = haverSin((lng1 - lng2) * rad);\n    return haverSinDistPartial(haverSinDLng, cosLat1, lat1, lat2);\n}\n\nexport function distance(lng1: number, lat1: number, lng2: number, lat2: number) {\n    const h = haverSinDist(lng1, lat1, lng2, lat2, Math.cos(lat1 * rad));\n    return 2 * earthRadius * Math.asin(Math.sqrt(h));\n}\n\nfunction vertexLat(lat: number, haverSinDLng: number) {\n    const cosDLng = 1 - 2 * haverSinDLng;\n    if (cosDLng <= 0) return lat > 0 ? 90 : -90;\n    return Math.atan(Math.tan(lat * rad) / cosDLng) / rad;\n}","import { Position, Feature, Point, LineString, FeatureCollection } from \"geojson\";\nimport { haversineDistance } from \"../distance/haversine\";\n\n/**\n * Calculates the total length of a LineString route in meters.\n *\n * @param line - A GeoJSON Feature<LineString> representing the route\n * @returns The total length of the route in meters\n */\nexport function routeLength(\n    line: Feature<LineString>,\n) {\n    const lineCoords = line.geometry.coordinates;\n\n    // Calculate the total route distance\n    let routeDistance = 0;\n    for (let i = 0; i < lineCoords.length - 1; i++) {\n        routeDistance += haversineDistance(lineCoords[i], lineCoords[i + 1]);\n    }\n    return routeDistance\n}\n\n/**\n * Extracts unique coordinates from a FeatureCollection of LineStrings.\n *\n * @param collection - A GeoJSON FeatureCollection of LineStrings\n * @returns An array of unique Position coordinates\n */\nexport function getUniqueCoordinatesFromLineStrings(\n    collection: FeatureCollection<LineString>\n): Position[] {\n    const seen = new Set<string>();\n    const unique: Position[] = [];\n\n    for (const feature of collection.features) {\n        if (feature.geometry.type !== \"LineString\") {\n            continue;\n        }\n\n        for (const coord of feature.geometry.coordinates) {\n            const key = `${coord[0]},${coord[1]}`;\n\n            if (!seen.has(key)) {\n                seen.add(key);\n                unique.push(coord);\n            }\n        }\n    }\n\n    return unique;\n}\n\n/**\n * Validates a GeoJSON Feature<LineString> route.\n *\n * @param route - The GeoJSON feature to validate\n * @returns A boolean indicating if it is a valid LineString route\n */\nexport function getReasonIfLineStringInvalid(\n    route: Feature<LineString> | null | undefined\n): string | undefined {\n    // 1. Must exist\n    if (!route) {\n        return 'No feature';\n    }\n\n    // 2. Must be a Feature\n    if (route.type !== \"Feature\") {\n        return 'Not a Feature';\n    }\n\n    // 3. Must have a geometry of type LineString\n    if (!route.geometry || route.geometry.type !== \"LineString\") {\n        return 'Not a LineString';\n    }\n\n    // 4. Coordinates must be an array with length >= 2\n    const coords = route.geometry.coordinates;\n    if (!Array.isArray(coords) || coords.length < 2) {\n        return `Not enough coordinates: ${coords.length} (${coords})`;\n    }\n\n    const seen = new Set<string>();\n\n    // 5. Validate each coordinate is a valid Position\n    //    (At minimum, [number, number] or [number, number, number])\n    for (const position of coords) {\n        if (!Array.isArray(position)) {\n            return 'Not a Position; not an array';\n        }\n\n        // Check numeric values, ignoring optional altitude\n        if (\n            position.length < 2 ||\n            typeof position[0] !== \"number\" ||\n            typeof position[1] !== \"number\"\n        ) {\n            return 'Not a Position; elements are not a numbers';\n        }\n\n        // 6. Check for duplicates\n        const key = `${position[0]},${position[1]}`;\n        if (seen.has(key)) {\n            return `Duplicate coordinate: ${key}`;\n        }\n        seen.add(key);\n    }\n}\n\n/**\n * Checks if the start and end coordinates of a LineString match the given start and end points.\n * \n * @param line - The LineString feature to check\n * @param start - The start point feature\n * @param end - The end point feature\n * @return True if the start and end coordinates match, false otherwise\n * */\nexport function startAndEndAreCorrect(line: Feature<LineString>, start: Feature<Point>, end: Feature<Point>): boolean {\n    const lineCoords = line.geometry.coordinates;\n    const startCoords = start.geometry.coordinates;\n    const endCoords = end.geometry.coordinates;\n\n    // Check if the first coordinate of the LineString matches the start point\n    const startMatches = lineCoords[0][0] === startCoords[0] && lineCoords[0][1] === startCoords[1];\n\n    // Check if the last coordinate of the LineString matches the end point\n    const endMatches = lineCoords[lineCoords.length - 1][0] === endCoords[0] && lineCoords[lineCoords.length - 1][1] === endCoords[1];\n\n    return startMatches && endMatches;\n}\n\n/**\n * Checks if the route represented by a LineString is longer than the direct path. \n * In theory, a route should always longer than the direct path if it has more than two points.\n * @param line - The LineString feature representing the route\n * @param start - The start point feature\n * @param end - The end point feature\n * @returns - True if the route is longer than the direct path, false otherwise\n */\nexport function routeIsLongerThanDirectPath(line: Feature<LineString>, start: Feature<Point>, end: Feature<Point>): boolean {\n    const lineCoords = line.geometry.coordinates;\n    const startCoords = start.geometry.coordinates;\n    const endCoords = end.geometry.coordinates;\n\n    if (lineCoords.length <= 2) {\n        return true;\n    }\n\n    // Calculate the direct distance between the start and end points\n    const directDistance = haversineDistance(startCoords, endCoords);\n\n    // Calculate the route distance\n    let routeDistance = 0;\n    for (let i = 0; i < lineCoords.length - 1; i++) {\n        routeDistance += haversineDistance(lineCoords[i], lineCoords[i + 1]);\n    }\n\n    // If the route distance is 0, it means the start and end points are the same\n    if (routeDistance === 0) {\n        return true;\n    }\n\n    if (routeDistance < directDistance) {\n\n        // Check if the route distance is very close to the direct distance\n        const absoluteDifference = Math.abs(routeDistance - directDistance);\n        if (absoluteDifference < 0.000000000001) {\n            return true;\n        }\n\n        return false;\n    }\n\n    return true\n}\n\n/**\n * Modifies a FeatureCollection of LineStrings to break connections\n * between lines that share coordinates, by adjusting one of the shared\n * coordinates within a given tolerance.\n * \n * @param collection - The input FeatureCollection of LineStrings\n * @param tolerance - The amount by which to offset shared coordinates (in degrees)\n * @returns A new FeatureCollection with modified coordinates\n */\nexport function disconnectLineStrings(\n    collection: FeatureCollection<LineString>,\n    tolerance: number\n): FeatureCollection<LineString> {\n    const seenCoordinates = new Map<string, number>()\n\n    function getCoordinateKey(coordinate: Position): string {\n        return `${coordinate[0]},${coordinate[1]}`\n    }\n\n    function offsetCoordinate(coordinate: Position, count: number): Position {\n        const offset = count * tolerance\n        return [coordinate[0] + offset, coordinate[1] + offset]\n    }\n\n    const updatedFeatures = collection.features.map((feature) => {\n        const updatedCoordinates: Position[] = feature.geometry.coordinates.map((coordinate) => {\n            const key = getCoordinateKey(coordinate)\n\n            if (seenCoordinates.has(key)) {\n                const count = seenCoordinates.get(key)!\n                seenCoordinates.set(key, count + 1)\n                return offsetCoordinate(coordinate, count + 1)\n            }\n\n            seenCoordinates.set(key, 0)\n            return coordinate\n        })\n\n        return {\n            ...feature,\n            geometry: {\n                ...feature.geometry,\n                coordinates: updatedCoordinates\n            }\n        }\n    })\n\n    return {\n        ...collection,\n        features: updatedFeatures\n    }\n}\n","import { Feature, FeatureCollection, LineString, Point } from \"geojson\";\nimport { graphGetConnectedComponentCount, graphGetConnectedComponents } from \"./methods/connected\";\nimport { graphGetNodeAndEdgeCount, graphGetNodesAsPoints } from \"./methods/nodes\";\nimport { graphGetUniqueSegments } from \"./methods/unique\";\nimport { removeDuplicateAndSubsectionLines } from \"./methods/duplicates\";\nimport { getLeafEdges } from \"./methods/leaf\";\nimport { getNetworkInBoundingBox, BoundingBox } from \"./methods/bounding-box\";\nimport { unifyCloseCoordinates } from \"./methods/unify\";\nimport { routeLength } from \"./test-utils/utils\";\n\n/**\n * Represents a graph constructed from a GeoJSON FeatureCollection of LineString features.\n * This class provides methods to analyze the graph, including connected components, node and edge counts,\n * and shortest paths. Coordinates in the LineStrings are considered connected if they share identical coordinates.\n */\nexport class TerraRouteGraph {\n    constructor(network: FeatureCollection<LineString>) {\n        this.network = network;\n    }\n\n    private network: FeatureCollection<LineString>;\n\n    /**\n     * Gets the length of a specific route.\n     * @param line A GeoJSON Feature of type LineString\n     * @returns The length of the route in meters\n     */\n    getRouteLength(line: Feature<LineString>) {\n        return routeLength(line);\n    }\n\n    /**\n     * Sets the network for the graph.\n     * This method replaces the current network with a new one.\n     * @param network A GeoJSON FeatureCollection of LineString features representing the network.\n     */\n    setNetwork(network: FeatureCollection<LineString>) {\n        this.network = network;\n    }\n\n    /**\n     * Gets the current network of the graph.\n     * @returns A GeoJSON FeatureCollection of LineString features representing the network.\n     */\n    getNetwork(): FeatureCollection<LineString> {\n        return this.network;\n    }\n\n    /**\n     * Gets a filtered network containing only LineStrings that are completely within the specified bounding box.\n     * @param boundingBox A bounding box array in the format [minLng, minLat, maxLng, maxLat]\n     * @returns A GeoJSON FeatureCollection of LineString features representing the network filtered by the bounding box.\n     */\n    getNetworkInBoundingBox(boundingBox: BoundingBox): FeatureCollection<LineString> {\n        return getNetworkInBoundingBox(this.network, boundingBox);\n    }\n\n    /**\n     * Gets the network without duplicate or subsection lines. \n     * This method processes the network to remove any duplicate lines or lines that are subsections of other lines.\n     * @returns A FeatureCollection<LineString> representing the network without duplicate or subsection lines.\n     */\n    getNetworkWithoutDuplicatesOrSubsections() {\n        return removeDuplicateAndSubsectionLines(this.network);\n    }\n\n    /**\n     * Gets the connected components of the graph.\n     * @returns An array of FeatureCollection<LineString> representing the connected components.\n     */\n    getConnectedComponents(): FeatureCollection<LineString>[] {\n        return graphGetConnectedComponents(this.network)\n    }\n\n    /**\n     * Gets the count of connected components in the graph.\n     * @returns The number of connected components in the graph.\n     */\n    getConnectedComponentCount(): number {\n        return graphGetConnectedComponentCount(this.network);\n    }\n\n    /**\n     * Gets the count of unique nodes and edges in the graph.\n     * @returns An object containing the counts of nodes and edges.\n     */\n    getNodeAndEdgeCount(): { nodeCount: number, edgeCount: number } {\n        return graphGetNodeAndEdgeCount(this.network);\n    }\n\n    /**\n     * Gets the unique nodes of the graph as a FeatureCollection of Point features.\n     * @returns A FeatureCollection<Point> containing the nodes of the graph.\n     */\n    getNodes(): FeatureCollection<Point> {\n        const nodes = graphGetNodesAsPoints(this.network);\n        return {\n            type: \"FeatureCollection\",\n            features: nodes\n        };\n    }\n\n    /**\n     * Gets the count of unique nodes in the graph.\n     * @returns The number of unique nodes in the graph.\n     */\n    getNodeCount(): number {\n        const { nodeCount } = this.getNodeAndEdgeCount();\n        return nodeCount;\n    }\n\n    /**\n     * Gets the unique edges of the graph as a FeatureCollection of LineString features. Each edge is represented as a LineString.\n     * This method ensures that each edge is unique, meaning that edges are not duplicated in the collection. Each linestring only \n     * two coordinates, representing the start and end points of the edge.\n     * @returns A FeatureCollection<LineString> containing the unique edges of the graph.\n     */\n    getEdges(): FeatureCollection<LineString> {\n        return graphGetUniqueSegments(this.network);\n    }\n\n    /**\n     * Gets the length of the longest edge in the graph based on the length of the LineString.\n     * If no edges exist, it returns -1.\n     * @returns The length of the longest edge in meters, or 0 if no edges exist.\n     */\n    getLongestEdgeLength(): number {\n        const longestEdge = this.getLongestEdge();\n        if (!longestEdge) {\n            return -1;\n        }\n        return routeLength(longestEdge);\n    }\n\n    /**\n     * Gets the average length of all edges in the graph based on the length of the LineString.\n     * If no edges exist, it returns -1.\n     * @returns The average length of all edges in meters, or -1 if no edges exist.\n     */\n    getAverageEdgeLength(): number {\n        const edges = this.getEdges().features;\n        if (edges.length === 0) {\n            return -1;\n        }\n        const totalLength = edges.reduce((sum, edge) => sum + routeLength(edge), 0);\n        return totalLength / edges.length;\n    }\n\n    /**\n     * Gets the degree of each node in the graph.\n     * @returns A Map where the key is a coordinate string \"lng,lat\" and the value is the degree.\n     */\n    getNodeDegrees(): Record<string, number> {\n        const degrees: Record<string, number> = {};\n        const edges = this.getEdges().features;\n\n        for (const edge of edges) {\n            const [start, end] = edge.geometry.coordinates;\n            const startKey = `${start[0]},${start[1]}`;\n            const endKey = `${end[0]},${end[1]}`;\n\n            degrees[startKey] = (degrees[startKey] || 0) + 1;\n            degrees[endKey] = (degrees[endKey] || 0) + 1;\n        }\n\n        return degrees;\n    }\n\n    /**\n     * Gets summary statistics for node degrees (min, max, average).\n     */\n    getNodeDegreeStats(): { min: number, max: number, avg: number } {\n        const degrees = Object.values(this.getNodeDegrees());\n        if (degrees.length === 0) return { min: 0, max: 0, avg: 0 };\n\n        const min = Math.min(...degrees);\n        const max = Math.max(...degrees);\n        const avg = degrees.reduce((a, b) => a + b, 0) / degrees.length;\n        return { min, max, avg };\n    }\n\n    /**\n     * Gets the length of the shortest edge in the graph based on the length of the LineString.\n     * If no edges exist, it returns -1.\n     * @returns The length of the shortest edge in meters, or 0 if no edges exist.\n     */\n    getShortestEdgeLength(): number {\n        const shortestEdge = this.getShortestEdge();\n        if (!shortestEdge) {\n            return -1;\n        }\n        return routeLength(shortestEdge);\n    }\n\n    /**\n     * Gets the longest edge in the graph based on the length of the LineString.\n     * @returns The longest edge as a Feature<LineString> or null if no edges exist.\n     */\n    getLongestEdge(): Feature<LineString> | null {\n        const edges = this.getEdges().features;\n        if (edges.length === 0) {\n            return null;\n        }\n        const longestEdges = edges.sort((a, b) => routeLength(a) - routeLength(b));\n        return longestEdges[longestEdges.length - 1];\n    }\n\n    /**\n     * Gets the shortest edge in the graph based on the length of the LineString.\n     * @returns The shortest edge as a Feature<LineString> or null if no edges exist.\n     */\n    getShortestEdge(): Feature<LineString> | null {\n        const edges = this.getEdges().features;\n        if (edges.length === 0) {\n            return null;\n        }\n        const shortestEdges = edges.sort((a, b) => routeLength(a) - routeLength(b));\n        return shortestEdges[0];\n    }\n\n    /**\n     * Gets the count of unique edges in the graph.\n     * @returns The number of unique edges in the graph.\n     */\n    getEdgeCount(): number {\n        const { edgeCount } = this.getNodeAndEdgeCount();\n        return edgeCount;\n    }\n\n    /**\n     * Gets the leaf edges of the graph. A leaf edge is defined as an edge whose start or end node has a degree of 1.\n     * Here an edge is defined as a LineString with two coordinates, representing the start and end points.\n     * @returns A FeatureCollection<LineString> containing only the leaf edges of the graph.\n     */\n    getLeafEdges(): FeatureCollection<LineString> {\n        return getLeafEdges(this.network).leafEdges;\n    }\n\n    /**\n     * Returns the pruned network, which is the network without the leaf edges.\n     * i.e. This method removes all leaf edges from the network, leaving only the non-leaf edges\n     * @return A FeatureCollection<LineString> representing the pruned network without leaf edges.\n     */\n    getPrunedEdges(depth?: number): FeatureCollection<LineString> {\n        if (depth && depth > 0) {\n\n            let currentEdges = this.network;\n\n            for (let i = 0; i < depth; i++) {\n                const leafEdges = getLeafEdges(currentEdges);\n                currentEdges = leafEdges.nonLeafEdges;\n            }\n\n            return currentEdges;\n\n        }\n        return getLeafEdges(this.network).nonLeafEdges;\n    }\n\n    /**\n     * Returns the network where all nodes that are with n meters of each other are unified. \n     * The function will avoid unifying coordinates in the same linestring.\n     * @param toleranceMeters the tolerance for unifying nodes in meters. \n     */\n    getUnifiedNetwork(toleranceMeters: number) {\n        return unifyCloseCoordinates(this.network, toleranceMeters);\n    }\n}","import { Feature, FeatureCollection, LineString, Point, Position } from 'geojson'\n\n/**\n * Counts the unique nodes and edges in a GeoJSON FeatureCollection of LineString features.\n * @param featureCollection - A GeoJSON FeatureCollection containing LineString features\n * @returns An object containing the count of unique nodes and edges\n */\nexport function graphGetNodeAndEdgeCount(\n    featureCollection: FeatureCollection<LineString>\n): { nodeCount: number; edgeCount: number } {\n    const nodeSet = new Set<string>()\n    const edgeSet = new Set<string>()\n\n    for (const feature of featureCollection.features) {\n        const coordinates = feature.geometry.coordinates\n\n        for (const coordinate of coordinates) {\n            nodeSet.add(JSON.stringify(coordinate))\n        }\n\n        for (let i = 0; i < coordinates.length - 1; i++) {\n            const coordinateOne = coordinates[i]\n            const coordinateTwo = coordinates[i + 1]\n\n            const edge = normalizeEdge(coordinateOne, coordinateTwo)\n            edgeSet.add(edge)\n        }\n    }\n\n    return {\n        nodeCount: nodeSet.size,\n        edgeCount: edgeSet.size,\n    }\n}\n\nfunction normalizeEdge(coordinateOne: Position, coordinateTwo: Position): string {\n    const stringOne = JSON.stringify(coordinateOne)\n    const stringTwo = JSON.stringify(coordinateTwo)\n\n    if (stringOne < stringTwo) {\n        return `${stringOne}|${stringTwo}`\n    }\n\n    return `${stringTwo}|${stringOne}`\n}\n\n\n/**\n * Converts a FeatureCollection of LineString features into a FeatureCollection of Point features,\n * where each unique coordinate in the LineStrings becomes a Point.\n * @param lines - A GeoJSON FeatureCollection containing LineString features\n * @returns A FeatureCollection of Point features representing unique nodes\n */\nexport function graphGetNodesAsPoints(lines: FeatureCollection<LineString>): Feature<Point>[] {\n    const seen = new Set<string>();\n    const points: Feature<Point>[] = [];\n\n    for (const feature of lines.features) {\n        for (const coord of feature.geometry.coordinates) {\n            const key = coord.join(',');\n\n            if (!seen.has(key)) {\n                seen.add(key);\n                points.push({\n                    type: 'Feature',\n                    geometry: {\n                        type: 'Point',\n                        coordinates: coord\n                    },\n                    properties: {}\n                });\n            }\n        }\n    }\n\n    return points;\n}\n","import { FeatureCollection, LineString, Position } from 'geojson';\nimport { haversineDistance } from '../distance/haversine';\nimport { KDBush } from './spatial-index/kdbush';\nimport { around } from './spatial-index/geokdbush';\n\nexport function unifyCloseCoordinates(\n    featureCollection: FeatureCollection<LineString>,\n    radiusMeters: number\n): FeatureCollection<LineString> {\n    if (featureCollection.features.length < 2) {\n        return featureCollection; // No features to process\n    }\n\n    const globalSeen: Position[] = [];\n    const globalSeenSet = new Set<string>(); // Fast O(1) lookup for globalSeen\n    const mapping: Map<string, Position> = new Map();\n\n    // Build a one-time spatial index with all coordinates for efficient querying\n    const allCoords: Position[] = [];\n    const coordToGlobalIndex = new Map<string, number>();\n\n    // Collect all unique coordinates first\n    for (const feature of featureCollection.features) {\n        for (const coord of feature.geometry.coordinates) {\n            const key = `${coord[0]},${coord[1]}`; // Faster than join\n            if (!coordToGlobalIndex.has(key)) {\n                coordToGlobalIndex.set(key, allCoords.length);\n                allCoords.push(coord);\n            }\n        }\n    }\n\n    // Build spatial index once for all coordinates\n    let spatialIndex: KDBush = new KDBush(allCoords.length);\n    for (const coord of allCoords) {\n        spatialIndex.add(coord[0], coord[1]); // lng, lat\n    }\n    spatialIndex.finish();\n\n    function findOrRegisterCoordinate(\n        coordinate: Position,\n        exclude: Position[],\n        futureConflictCheck: Set<string>\n    ): Position {\n        let closest: Position | null = null;\n        let closestDistance = Infinity;\n\n        // if (globalSeen.length > 5) {\n        // Use spatial index for efficient querying\n        const radiusKm = radiusMeters / 1000; // Convert meters to kilometers\n        const candidateIndices = around(spatialIndex, coordinate[0], coordinate[1], Infinity, radiusKm);\n\n        for (const candidateIndex of candidateIndices) {\n            const candidateCoord = allCoords[candidateIndex];\n            const candidateKey = `${candidateCoord[0]},${candidateCoord[1]}`;\n\n            // Only consider coordinates that are in globalSeen (O(1) lookup)\n            if (!globalSeenSet.has(candidateKey)) {\n                continue;\n            }\n\n            if (exclude.includes(candidateCoord)) {\n                continue;\n            }\n\n            if (futureConflictCheck.has(candidateKey)) {\n                continue;\n            }\n\n            const distance = haversineDistance(candidateCoord, coordinate) * 1000; // Convert to meters\n\n            if (distance <= radiusMeters && distance < closestDistance) {\n                closest = candidateCoord;\n                closestDistance = distance;\n            }\n        }\n\n\n        if (closest !== null) {\n            return closest;\n        }\n\n        globalSeen.push(coordinate);\n        globalSeenSet.add(`${coordinate[0]},${coordinate[1]}`);\n        return coordinate;\n    }\n\n    const updatedFeatures = featureCollection.features.map((feature) => {\n        const localSeen: Position[] = [];\n        const updatedCoordinates: Position[] = [];\n        const usedKeys = new Set<string>();\n\n        for (const coordinate of feature.geometry.coordinates) {\n            const key = `${coordinate[0]},${coordinate[1]}`;\n\n            if (!mapping.has(key)) {\n                const unified = findOrRegisterCoordinate(coordinate, localSeen, usedKeys);\n                const unifiedKey = `${unified[0]},${unified[1]}`;\n\n                // Avoid inserting a coordinate if it's going to cause duplication later in this feature\n                if (usedKeys.has(unifiedKey)) {\n                    mapping.set(key, coordinate);\n                } else {\n                    mapping.set(key, unified);\n                }\n            }\n\n            const unifiedCoordinate = mapping.get(key)!;\n            const unifiedKey = `${unifiedCoordinate[0]},${unifiedCoordinate[1]}`;\n\n            if (!usedKeys.has(unifiedKey)) {\n                updatedCoordinates.push(unifiedCoordinate);\n                usedKeys.add(unifiedKey);\n            }\n\n            localSeen.push(coordinate);\n        }\n\n        return {\n            ...feature,\n            geometry: {\n                ...feature.geometry,\n                coordinates: updatedCoordinates\n            }\n        };\n    });\n\n    return {\n        ...featureCollection,\n        features: updatedFeatures\n    };\n}\n"],"names":["dfs","index","adjacencyList","visited","_step3","_iterator3","_createForOfIteratorHelperLoose","done","neighbor","value","segmentKey","start","end","_normalizeSegment","aLat","bLat","normalizeSegment","JSON","stringify","graphGetUniqueSegments","input","_step","uniqueSegments","Map","_iterator","features","coordinates","geometry","length","key","has","set","type","properties","Array","from","values","isSubsequence","sub","full","subLength","fullLength","matches","offset","reversedSub","concat","reverse","getLeafEdges","edgesFc","edges","endpointCountMap","coordKey","position","join","i","startKey","endKey","get","leafEdgeMap","nonLeafEdgeMap","feature","startCount","endCount","edgeKey","map","leafEdges","nonLeafEdges","isLineStringCompletelyWithinBounds","lineStringFeature","minLng","minLat","maxLng","maxLat","_step2","_iterator2","isCoordinateWithinBounds","coordinate","lng","lat","haversineDistance","pointOne","pointTwo","toRadians","latOrLng","Math","PI","phiOne","lambdaOne","phiTwo","deltaPhi","deltalambda","a","sin","cos","atan2","sqrt","ARRAY_TYPES","Int8Array","Uint8Array","Uint8ClampedArray","Int16Array","Uint16Array","Int32Array","Uint32Array","Float32Array","Float64Array","KDBush","numItems","nodeSize","ArrayType","data","ids","this","coords","_pos","_finished","IndexArrayType","isNaN","Error","min","max","arrayTypeIndex","indexOf","coordsByteSize","BYTES_PER_ELEMENT","idsByteSize","padCoords","ArrayBuffer","_proto","prototype","add","x","y","finish","numAdded","sort","left","right","axis","m","select","k","n","z","log","s","exp","sd","floor","t","j","swapItem","swap","arr","tmp","TinyQueue","compare","b","_down","push","item","_up","pop","top","bottom","peek","pos","parent","current","halfLength","bestChild","rad","boxDist","cosLat","node","haverSin","haverSinDLng","extremumLat","cosDLng","atan","tan","vertexLat","haverSinDistPartial","compareDist","dist","theta","cosLat1","lat1","lat2","haverSinDist","lng1","lng2","routeLength","line","lineCoords","routeDistance","TerraRouteGraph","network","getRouteLength","setNetwork","getNetwork","getNetworkInBoundingBox","boundingBox","featureCollection","filteredFeatures","getNetworkWithoutDuplicatesOrSubsections","collection","toRemove","Set","coordsI","coordsJ","filter","_","removeDuplicateAndSubsectionLines","getConnectedComponents","graph","coordinateMap","coordinateKey","_step4","_iterator4","_step5","_iterator5","neighbors","_iterator6","_step6","neighborIndex","components","startIndex","currentComponent","stack","currentIndex","_step7","_iterator7","component","graphGetConnectedComponents","getConnectedComponentCount","numberOfFeatures","coordinateToFeatureIndices","indices","fill","connectedComponents","graphGetConnectedComponentCount","getNodeAndEdgeCount","nodeSet","edgeSet","edge","coordinateTwo","stringOne","stringTwo","nodeCount","size","edgeCount","graphGetNodeAndEdgeCount","getNodes","lines","seen","points","coord","graphGetNodesAsPoints","getNodeCount","getEdges","getLongestEdgeLength","longestEdge","getLongestEdge","getAverageEdgeLength","reduce","sum","getNodeDegrees","degrees","_edge$geometry$coordi","getNodeDegreeStats","Object","avg","apply","getShortestEdgeLength","shortestEdge","getShortestEdge","longestEdges","getEdgeCount","getPrunedEdges","depth","currentEdges","getUnifiedNetwork","toleranceMeters","radiusMeters","globalSeenSet","mapping","allCoords","coordToGlobalIndex","spatialIndex","_i","_allCoords","findOrRegisterCoordinate","exclude","futureConflictCheck","closest","closestDistance","Infinity","maxResults","maxDistanceKm","maxHaverSinDist","result","undefined","q","id","midLng","midLat","nextAxis","leftNode","rightNode","candidate","around","candidateCoord","candidateKey","includes","distance","updatedFeatures","localSeen","updatedCoordinates","usedKeys","unified","unifiedCoordinate","unifiedKey","_extends","unifyCloseCoordinates"],"mappings":"4/BAgEA,SAASA,EAAIC,EAAeC,EAA2BC,GACnDA,EAAQF,IAAS,EAEjB,QAA2CG,EAA3CC,EAAAC,EAAuBJ,EAAcD,MAAMG,EAAAC,KAAAE,MAAE,CAAlC,IAAAC,EAAQJ,EAAAK,MACVN,EAAQK,IACTR,EAAIQ,EAAUN,EAAeC,EAErC,CACJ,CC7CA,SAASO,EAAWC,EAAiBC,GACjC,IAAAC,EAlBJ,SAA0BF,EAAiBC,GACvC,IAAOE,EAAcH,EAAK,GACnBI,EAAcH,EAAG,GAExB,OACIE,EAAOC,GACND,IAASC,GALOJ,EAAK,IACLC,EAAG,GAMb,CAACD,EAAOC,GAGZ,CAACA,EAAKD,EACjB,CAM6CK,CAAiBL,EAAOC,GACjE,OAAOK,KAAKC,UAAU,CADAL,EAAA,GAAeA,EACrC,IACJ,CAKgB,SAAAM,EACZC,GAIA,IAFA,IAEoCC,EAF9BC,EAAiB,IAAIC,IAE3BC,EAAAlB,EAAsBc,EAAMK,YAAQJ,EAAAG,KAAAjB,MAGhC,IAHkC,IAC5BmB,EADQL,EAAAZ,MACckB,SAASD,YAE5BzB,EAAQ,EAAGA,EAAQyB,EAAYE,OAAS,EAAG3B,IAAS,CACzD,IAAMU,EAAQe,EAAYzB,GACpBW,EAAMc,EAAYzB,EAAQ,GAE1B4B,EAAMnB,EAAWC,EAAOC,GAEzBU,EAAeQ,IAAID,IAUpBP,EAAeS,IAAIF,EATkB,CACjCG,KAAM,UACNL,SAAU,CACNK,KAAM,aACNN,YAAa,CAACf,EAAOC,IAEzBqB,WAAY,IAKxB,CAGJ,MAAO,CACHD,KAAM,oBACNP,SAAUS,MAAMC,KAAKb,EAAec,UAE5C,CC9CA,SAASC,EAAcC,EAAiBC,GACpC,IAAMC,EAAYF,EAAIV,OAChBa,EAAaF,EAAKX,OAExB,GAAIY,EAAYC,EACZ,OACJ,EAGA,IAAK,IAAI9B,EAAQ,EAAGA,GAAS8B,EAAaD,EAAW7B,IAAS,CAG1D,IAFA,IAAI+B,GAAU,EAELC,EAAS,EAAGA,EAASH,EAAWG,IACrC,GACIJ,EAAK5B,EAAQgC,GAAQ,KAAOL,EAAIK,GAAQ,IACxCJ,EAAK5B,EAAQgC,GAAQ,KAAOL,EAAIK,GAAQ,GAC1C,CACED,GAAU,EACV,KACJ,CAGJ,GAAIA,EACA,OACJ,CACJ,CAKA,IAFA,IAAME,EAAc,GAAAC,OAAIP,GAAKQ,UAEpBnC,EAAQ,EAAGA,GAAS8B,EAAaD,EAAW7B,IAAS,CAG1D,IAFA,IAAI+B,GAAU,EAELC,EAAS,EAAGA,EAASH,EAAWG,IACrC,GACIJ,EAAK5B,EAAQgC,GAAQ,KAAOC,EAAYD,GAAQ,IAChDJ,EAAK5B,EAAQgC,GAAQ,KAAOC,EAAYD,GAAQ,GAClD,CACED,GAAU,EACV,KACJ,CAGJ,GAAIA,EACA,OAAO,CAEf,CAEA,OAAO,CACX,CC7DgB,SAAAK,EACZC,GAKA,IAAMC,EAAQ9B,EAAuB6B,GAE/BE,EAAwC,IAAI3B,IAElD,SAAS4B,EAASC,GACd,OAAOA,EAASC,KAAK,IACzB,CAGA,IAAK,IAAIC,EAAI,EAAGA,EAAIL,EAAMxB,SAASG,OAAQ0B,IAAK,CAC5C,IACM5B,EADUuB,EAAMxB,SAAS6B,GACH3B,SAASD,YAErC,KAAIA,EAAYE,OAAS,GAAzB,CAIA,IAAM2B,EAAWJ,EAASzB,EAAY,IAChC8B,EAASL,EAASzB,EAAYA,EAAYE,OAAS,IAEzDsB,EAAiBnB,IACbwB,GACCL,EAAiBO,IAAIF,IAAa,GAAK,GAE5CL,EAAiBnB,IACbyB,GACCN,EAAiBO,IAAID,IAAW,GAAK,EAX1C,CAaJ,CAKA,IAHA,IAAME,EAAgD,IAAInC,IACpDoC,EAAmD,IAAIpC,IAEpD+B,EAAI,EAAGA,EAAIL,EAAMxB,SAASG,OAAQ0B,IAAK,CAC5C,IAAMM,EAAUX,EAAMxB,SAAS6B,GACzB5B,EAAckC,EAAQjC,SAASD,YAErC,KAAIA,EAAYE,OAAS,GAAzB,CAIA,IAAM2B,EAAWJ,EAASzB,EAAY,IAChC8B,EAASL,EAASzB,EAAYA,EAAYE,OAAS,IAEnDiC,EAAaX,EAAiBO,IAAIF,IAAa,EAC/CO,EAAWZ,EAAiBO,IAAID,IAAW,EAE3CO,EAAUrC,EAAYsC,IAAIb,GAAUE,KAAK,KAE5B,IAAfQ,GAAiC,IAAbC,EACfJ,EAAY5B,IAAIiC,IACjBL,EAAY3B,IAAIgC,EAASH,GAGxBD,EAAe7B,IAAIiC,IACpBJ,EAAe5B,IAAIgC,EAASH,EAhBpC,CAmBJ,CAEA,MAAO,CACHK,UAAW,CACPjC,KAAM,oBACNP,SAAUS,MAAMC,KAAKuB,EAAYtB,WAErC8B,aAAc,CACVlC,KAAM,oBACNP,SAAUS,MAAMC,KAAKwB,EAAevB,WAGhD,CCtCA,SAAS+B,EACLC,EACAC,EACAC,EACAC,EACAC,GAIA,IAFA,IAEoCC,EAApCC,EAAApE,EAFoB8D,EAAkBzC,SAASD,eAEX+C,EAAAC,KAAAnE,MAChC,IAAKoE,EADYF,EAAAhE,MACyB4D,EAAQC,EAAQC,EAAQC,GAC9D,OACJ,EAGJ,OACJ,CAAA,CAWA,SAASG,EACLC,EACAP,EACAC,EACAC,EACAC,GAEA,IAAOK,EAAYD,EAAU,GAAjBE,EAAOF,EACnB,GAAA,OAAOC,GAAOR,GAAUQ,GAAON,GAAUO,GAAOR,GAAUQ,GAAON,CACrE,CCjFO,IAAMO,EAAoB,SAACC,EAAoBC,GAClD,IAAMC,EAAY,SAACC,GAAgB,OAAMA,EAAWC,KAAKC,GAAM,GAAG,EAE5DC,EAASJ,EAAUF,EAAS,IAC5BO,EAAYL,EAAUF,EAAS,IAC/BQ,EAASN,EAAUD,EAAS,IAE5BQ,EAAWD,EAASF,EACpBI,EAFYR,EAAUD,EAAS,IAELM,EAE1BI,EACFP,KAAKQ,IAAIH,EAAW,GAAKL,KAAKQ,IAAIH,EAAW,GAC7CL,KAAKS,IAAIP,GACTF,KAAKS,IAAIL,GACTJ,KAAKQ,IAAIF,EAAc,GACvBN,KAAKQ,IAAIF,EAAc,GAQ3B,OAPU,EAAIN,KAAKU,MAAMV,KAAKW,KAAKJ,GAAIP,KAAKW,KAAK,EAAIJ,IAEtC,OAKG,GACtB,ECTMK,EAAc,CAChBC,UAAWC,WAAYC,kBAAmBC,WAAYC,YACtDC,WAAYC,YAAaC,aAAcC,cAM9BC,eAWT,WAAA,SAAAA,EACIC,EACAC,EACAC,EACAC,GAEA,QAJAF,IAAAA,IAAAA,EAAmB,SACnBC,IAAAA,IAAAA,EAAmCJ,cAbhCK,KAAAA,iBACAC,SAAG,EAAAC,KACHC,YAAM,EAAAD,KACLE,UAAI,EAAAF,KACJG,eAAS,EAAAH,KACVL,cAAQ,EAAAK,KACRJ,cAAQ,EAAAI,KACPH,eAAS,EAAAG,KACTI,oBAAc,EAQdC,MAAMV,IAAaA,EAAW,EAC9B,MAAM,IAAIW,MAAoCX,8BAAAA,OAGlDK,KAAKL,SAAWA,EAChBK,KAAKJ,SAAWxB,KAAKmC,IAAInC,KAAKoC,IAAIZ,EAAU,GAAI,OAChDI,KAAKH,UAAYA,EACjBG,KAAKI,eAAiBT,EAAW,MAAQN,YAAcE,YAEvD,IAAMkB,EAAiBzB,EAAY0B,QAAQV,KAAKH,WAC1Cc,EAA4B,EAAXhB,EAAeK,KAAKH,UAAUe,kBAC/CC,EAAclB,EAAWK,KAAKI,eAAeQ,kBAC7CE,GAAa,EAAID,EAAc,GAAK,EAE1C,GAAIJ,EAAiB,EACjB,MAAM,IAAIH,MAAuCT,iCAAAA,EAAY,KAG7DC,GACAE,KAAKF,KAAOA,EACZE,KAAKD,IAAM,IAAKC,KAAKI,eAAuBJ,KAAKF,KAvCzC,EAuC4DH,GACpEK,KAAKC,OAAS,IAASD,KAACH,UAAkBG,KAAKF,KAxCvC,EAwC2De,EAAcC,EAAsB,EAAXnB,GAC5FK,KAAKE,KAAkB,EAAXP,EACZK,KAAKG,WAAY,IAEjBH,KAAKF,KAAO,IAAIiB,YA5CR,EA4CkCJ,EAAiBE,EAAcC,GACzEd,KAAKD,IAAM,IAAKC,KAAKI,eAAuBJ,KAAKF,KA7CzC,EA6C4DH,GACpEK,KAAKC,OAAS,IAASD,KAACH,UAAkBG,KAAKF,KA9CvC,EA8C2De,EAAcC,EAAsB,EAAXnB,GAC5FK,KAAKE,KAAO,EACZF,KAAKG,WAAY,EAEjB,IAAIjB,WAAWc,KAAKF,KAAM,EAAG,GAAG/E,IAAI,CAAC,IAAM,GAAiB0F,IAC5D,IAAIpB,YAAYW,KAAKF,KAAM,EAAG,GAAG,GAAKE,KAAKJ,SAC3C,IAAIL,YAAYS,KAAKF,KAAM,EAAG,GAAG,GAAKE,KAAKL,SAEnD,CAAC,IAAAqB,EAAAtB,EAAAuB,UAkBAvB,OAlBAsB,EAEDE,IAAA,SAAIC,EAAWC,GACX,IAAMnI,EAAQ+G,KAAKE,MAAQ,EAI3B,OAHAF,KAAKD,IAAI9G,GAASA,EAClB+G,KAAKC,OAAOD,KAAKE,QAAUiB,EAC3BnB,KAAKC,OAAOD,KAAKE,QAAUkB,EACpBnI,CACX,EAAC+H,EAEDK,OAAA,WACI,IAAMC,EAAWtB,KAAKE,MAAQ,EAC9B,GAAIoB,IAAatB,KAAKL,SAClB,MAAM,IAAIW,MAAegB,SAAAA,EAAgC,wBAAAtB,KAAKL,SAAW,KAI7E,OAFA4B,EAAKvB,KAAKD,IAAKC,KAAKC,OAAQD,KAAKJ,SAAU,EAAGI,KAAKL,SAAW,EAAG,GACjEK,KAAKG,WAAY,EAErBH,IAAA,EAACN,CAAA,CA3DD,GAoEJ,SAAS6B,EACLxB,EACAE,EACAL,EACA4B,EACAC,EACAC,GAEA,KAAID,EAAQD,GAAQ5B,GAApB,CACA,IAAM+B,EAAKH,EAAOC,GAAU,EAC5BG,EAAO7B,EAAKE,EAAQ0B,EAAGH,EAAMC,EAAOC,GACpCH,EAAKxB,EAAKE,EAAQL,EAAU4B,EAAMG,EAAI,EAAG,EAAID,GAC7CH,EAAKxB,EAAKE,EAAQL,EAAU+B,EAAI,EAAGF,EAAO,EAAIC,EAH9C,CAIJ,CAEA,SAASE,EACL7B,EACAE,EACA4B,EACAL,EACAC,EACAC,GAEA,KAAOD,EAAQD,GAAM,CACjB,GAAIC,EAAQD,EAAO,IAAK,CACpB,IAAMM,EAAIL,EAAQD,EAAO,EACnBG,EAAIE,EAAIL,EAAO,EACfO,EAAI3D,KAAK4D,IAAIF,GACbG,EAAI,GAAM7D,KAAK8D,IAAI,EAAIH,EAAI,GAC3BI,EAAK,GAAM/D,KAAKW,KAAKgD,EAAIE,GAAKH,EAAIG,GAAKH,IAAMH,EAAIG,EAAI,EAAI,GAAK,EAAI,GAGxEF,EAAO7B,EAAKE,EAAQ4B,EAFJzD,KAAKoC,IAAIgB,EAAMpD,KAAKgE,MAAMP,EAAIF,EAAIM,EAAIH,EAAIK,IACzC/D,KAAKmC,IAAIkB,EAAOrD,KAAKgE,MAAMP,GAAKC,EAAIH,GAAKM,EAAIH,EAAIK,IACxBT,EAC9C,CAEA,IAAMW,EAAIpC,EAAO,EAAI4B,EAAIH,GACrBpF,EAAIkF,EACJc,EAAIb,EAOR,IALAc,EAASxC,EAAKE,EAAQuB,EAAMK,GACxB5B,EAAO,EAAIwB,EAAQC,GAAQW,GAC3BE,EAASxC,EAAKE,EAAQuB,EAAMC,GAGzBnF,EAAIgG,GAAG,CAIV,IAHAC,EAASxC,EAAKE,EAAQ3D,EAAGgG,GACzBhG,IACAgG,IACOrC,EAAO,EAAI3D,EAAIoF,GAAQW,GAAG/F,IACjC,KAAO2D,EAAO,EAAIqC,EAAIZ,GAAQW,GAAGC,GACrC,CAEIrC,EAAO,EAAIuB,EAAOE,KAAUW,EAC5BE,EAASxC,EAAKE,EAAQuB,EAAMc,GAG5BC,EAASxC,EAAKE,IADdqC,EACyBb,GAGzBa,GAAKT,IAAGL,EAAOc,EAAI,GACnBT,GAAKS,IAAGb,EAAQa,EAAI,EAC5B,CACJ,CAEA,SAASC,EACLxC,EACAE,EACA3D,EACAgG,GAEAE,EAAKzC,EAAKzD,EAAGgG,GACbE,EAAKvC,EAAQ,EAAI3D,EAAG,EAAIgG,GACxBE,EAAKvC,EAAQ,EAAI3D,EAAI,EAAG,EAAIgG,EAAI,EACpC,CAEA,SAASE,EACLC,EACAnG,EACAgG,GAEA,IAAMI,EAAMD,EAAInG,GAChBmG,EAAInG,GAAKmG,EAAIH,GACbG,EAAIH,GAAKI,CACb,KC1KqBC,eAMjB,WAAA,SAAAA,EACI7C,EACA8C,GAOA,QARA9C,IAAAA,IAAAA,EAAY,SACZ,IAAA8C,IAAAA,EAAkC,SAACjE,EAAGkE,GAAC,OACnClE,EAAIkE,GAAK,EAAIlE,EAAIkE,EAAI,EAAI,CAAC,QAP1B/C,UAAI,EAAAE,KACLpF,YAAM,EAAAoF,KACL4C,aAAO,EAOX5C,KAAKF,KAAOA,EACZE,KAAKpF,OAASoF,KAAKF,KAAKlF,OACxBoF,KAAK4C,QAAUA,EAEX5C,KAAKpF,OAAS,EACd,IAAK,IAAI0B,GAAK0D,KAAKpF,QAAU,GAAK,EAAG0B,GAAK,EAAGA,IACzC0D,KAAK8C,MAAMxG,EAGvB,CAAC,IAAA0E,EAAA2B,EAAA1B,UAoEA,OApEAD,EAED+B,KAAA,SAAKC,GACDhD,KAAKF,KAAKiD,KAAKC,GACfhD,KAAKiD,IAAIjD,KAAKpF,SAClB,EAACoG,EAEDkC,IAAA,WACI,GAAoB,IAAhBlD,KAAKpF,OAAT,CAIA,IAAMuI,EAAMnD,KAAKF,KAAK,GAChBsD,EAASpD,KAAKF,KAAKoD,MASzB,OAPAlD,KAAKpF,SAEDoF,KAAKpF,OAAS,IACdoF,KAAKF,KAAK,GAAKsD,EACfpD,KAAK8C,MAAM,IAGRK,CAZP,CAaJ,EAACnC,EAEDqC,KAAA,WACI,YAAYvD,KAAK,EACrB,EAACkB,EAEOiC,IAAA,SAAIK,GAIR,IAHA,IAAQxD,EAAkBE,KAAlBF,KAAM8C,EAAY5C,KAAZ4C,QACRI,EAAOlD,EAAKwD,GAEXA,EAAM,GAAG,CACZ,IAAMC,EAAUD,EAAM,GAAM,EACtBE,EAAU1D,EAAKyD,GACrB,GAAIX,EAAQI,EAAMQ,IAAY,EAC1B,MAEJ1D,EAAKwD,GAAOE,EACZF,EAAMC,CACV,CAEAzD,EAAKwD,GAAON,CAChB,EAAChC,EAEO8B,MAAA,SAAMQ,GAKV,IAJA,IAAQxD,EAAkBE,KAAlBF,KAAM8C,EAAY5C,KAAZ4C,QACRa,EAAazD,KAAKpF,QAAU,EAC5BoI,EAAOlD,EAAKwD,GAEXA,EAAMG,GAAY,CACrB,IAAIC,EAAyB,GAAZJ,GAAO,GAClB7B,EAAQiC,EAAY,EAM1B,GAJIjC,EAAQzB,KAAKpF,QAAUgI,EAAQ9C,EAAK2B,GAAQ3B,EAAK4D,IAAc,IAC/DA,EAAYjC,GAGZmB,EAAQ9C,EAAK4D,GAAYV,IAAS,EAClC,MAGJlD,EAAKwD,GAAOxD,EAAK4D,GACjBJ,EAAMI,CACV,CAEA5D,EAAKwD,GAAON,CAChB,EAACL,CAAA,CAlFD,GCFEgB,EAAMvF,KAAKC,GAAK,IA8GtB,SAASuF,EAAQ/F,EAAaC,EAAa+F,EAAgBC,GACvD,IAAMzG,EAASyG,EAAKzG,OACdE,EAASuG,EAAKvG,OACdD,EAASwG,EAAKxG,OACdE,EAASsG,EAAKtG,OAGpB,GAAIK,GAAOR,GAAUQ,GAAON,EACxB,OAAIO,EAAMR,EAAeyG,GAAUjG,EAAMR,GAAUqG,GAC/C7F,EAAMN,EAAeuG,GAAUjG,EAAMN,GAAUmG,GAC5C,EAKX,IAAMK,EAAe5F,KAAKmC,IAAIwD,GAAUlG,EAAMR,GAAUsG,GAAMI,GAAUlG,EAAMN,GAAUoG,IAClFM,EAoCV,SAAmBnG,EAAakG,GAC5B,IAAME,EAAU,EAAI,EAAIF,EACxB,OAAIE,GAAW,EAAUpG,EAAM,EAAI,IAAM,GAClCM,KAAK+F,KAAK/F,KAAKgG,IAAItG,EAAM6F,GAAOO,GAAWP,CACtD,CAxCwBU,CAAUvG,EAAKkG,GAGnC,OAAIC,EAAc3G,GAAU2G,EAAczG,EAC/B8G,EAAoBN,EAAcH,EAAQ/F,EAAKmG,GAGnD7F,KAAKmC,IACR+D,EAAoBN,EAAcH,EAAQ/F,EAAKR,GAC/CgH,EAAoBN,EAAcH,EAAQ/F,EAAKN,GAEvD,CAEA,SAAS+G,EAAY5F,EAAQkE,GACzB,OAAOlE,EAAE6F,KAAO3B,EAAE2B,IACtB,CAEA,SAAST,EAASU,GACd,IAAMxC,EAAI7D,KAAKQ,IAAI6F,EAAQ,GAC3B,OAAOxC,EAAIA,CACf,CAEA,SAASqC,EAAoBN,EAAsBU,EAAiBC,EAAcC,GAC9E,OAAOF,EAAUtG,KAAKS,IAAI+F,EAAOjB,GAAOK,EAAeD,GAAUY,EAAOC,GAAQjB,EACpF,CAEA,SAASkB,EAAaC,EAAcH,EAAcI,EAAcH,EAAcF,GAE1E,OAAOJ,EADcP,GAAUe,EAAOC,GAAQpB,GACLe,EAASC,EAAMC,EAC5D,CCxKgB,SAAAI,EACZC,GAMA,IAJA,IAAMC,EAAaD,EAAKtK,SAASD,YAG7ByK,EAAgB,EACX7I,EAAI,EAAGA,EAAI4I,EAAWtK,OAAS,EAAG0B,IACvC6I,GAAiBpH,EAAkBmH,EAAW5I,GAAI4I,EAAW5I,EAAI,IAErE,OAAO6I,CACX,CCLa,IAAAC,eACT,WAAA,SAAAA,EAAYC,GAAsCrF,KAI1CqF,aAHJ,EAAArF,KAAKqF,QAAUA,CACnB,CAAC,IAAArE,EAAAoE,EAAAnE,UAwPA,OAxPAD,EASDsE,eAAA,SAAeL,GACX,OAAOD,EAAYC,EACvB,EAACjE,EAODuE,WAAA,SAAWF,GACPrF,KAAKqF,QAAUA,CACnB,EAACrE,EAMDwE,WAAA,WACI,OAAOxF,KAAKqF,OAChB,EAACrE,EAODyE,wBAAA,SAAwBC,GACpB,ONxCQ,SACZC,EACAD,GAEA,IAAOrI,EAAkCqI,EAAW,GAArCpI,EAA0BoI,EAAW,GAA7BnI,EAAkBmI,EAAVlI,GAAAA,EAAUkI,KAGzC,GAAIrI,GAAUE,GAAUD,GAAUE,EAC9B,MAAU,IAAA8C,MAAM,iEAKpB,IAFA,IAEgDjG,EAF1CuL,EAA0C,GAEhDpL,EAAAlB,EAAsBqM,EAAkBlL,YAAQJ,EAAAG,KAAAjB,MAAE,KAAvCqD,EAAOvC,EAAAZ,MACV0D,EAAmCP,EAASS,EAAQC,EAAQC,EAAQC,IACpEoI,EAAiB7C,KAAKnG,EAE9B,CAEA,MAAO,CACH5B,KAAM,oBACNP,SAAUmL,EAElB,CMiBeH,CAAwBzF,KAAKqF,QAASK,EACjD,EAAC1E,EAOD6E,yCAAA,WACI,gBRgBJC,GAKA,IAHA,IAAMrL,EAAWqL,EAAWrL,SACtBsL,EAAW,IAAIC,IAEZ1J,EAAI,EAAGA,EAAI7B,EAASG,OAAQ0B,IAGjC,IAFA,IAAM2J,EAAUxL,EAAS6B,GAAG3B,SAASD,YAE5B4H,EAAI,EAAGA,EAAI7H,EAASG,OAAQ0H,IACjC,GAAIhG,IAAMgG,EAAV,CAIA,IAAM4D,EAAUzL,EAAS6H,GAAG3H,SAASD,YAMrC,GACIW,EAAc4K,EAASC,KAEnBD,EAAQrL,OAASsL,EAAQtL,QACxBqL,EAAQrL,SAAWsL,EAAQtL,QAAU0B,EAAIgG,GAEhD,CACEyD,EAAS7E,IAAI5E,GACb,KACJ,CAjBA,CAsBR,MAAO,CACHtB,KAAM,oBACNP,SAHaA,EAAS0L,OAAO,SAACC,EAAGnN,GAAU,OAAC8M,EAASjL,IAAI7B,EAAM,GAKvE,CQrDeoN,CAAkCrG,KAAKqF,QAClD,EAACrE,EAMDsF,uBAAA,WACI,OVOQ,SACZX,GAEA,IAAMlL,EAAWkL,EAAkBlL,SAC7B8L,EAAkC,IAAIhM,IACtCiM,EAA0C,IAAIjM,IAEpD,SAASkM,EAAc7I,GACnB,OAAUA,EAAW,GAAMA,IAAAA,EAAW,EAC1C,CAGA,IAAK,IAAI3E,EAAQ,EAAGA,EAAQwB,EAASG,OAAQ3B,IAGzC,IAFA,IAEoCyN,EAApCC,EAAArN,EAFoBmB,EAASxB,GAAO0B,SAASD,eAETgM,EAAAC,KAAApN,MAAE,CAA3B,IACDsB,EAAM4L,EADKC,EAAAjN,OAGZ+M,EAAc1L,IAAID,IACnB2L,EAAczL,IAAIF,EAAK,IAAImL,KAG/BQ,EAAc/J,IAAI5B,GAAMqG,IAAIjI,EAChC,CAIJ,IAAK,IAAIA,EAAQ,EAAGA,EAAQwB,EAASG,OAAQ3B,IAAS,CAClDsN,EAAMxL,IAAI9B,EAAO,IAAI+M,KAGrB,IADA,IACoCY,EAApCC,EAAAvN,EADoBmB,EAASxB,GAAO0B,SAASD,eACTkM,EAAAC,KAAAtN,MAAE,CAAA,IAC5BsB,EAAM4L,EADKG,EAAAnN,OAEXqN,EAAYN,EAAc/J,IAAI5B,GAEpC,GAAIiM,EACA,IAAAC,IAAqCC,EAArCD,EAAAzN,EAA4BwN,KAASE,EAAAD,KAAAxN,MAAE,CAAA,IAA5B0N,EAAaD,EAAAvN,MAChBwN,IAAkBhO,GAClBsN,EAAM9J,IAAIxD,GAAQiI,IAAI+F,EAE9B,CAER,CACJ,CAGA,IAAM9N,EAAU,IAAI6M,IACdkB,EAA8C,GAEpD,SAASlO,EAAImO,EAAoBC,GAG7B,IAFA,IAAMC,EAAkB,CAACF,GAElBE,EAAMzM,OAAS,GAAG,CACrB,IAAM0M,EAAeD,EAAMnE,MAE3B,IAAI/J,EAAQ2B,IAAIwM,GAAhB,CAIAnO,EAAQ+H,IAAIoG,GACZF,EAAiBrE,KAAKtI,EAAS6M,IAE/B,IAAMR,EAAYP,EAAM9J,IAAI6K,GAC5B,GAAIR,EACA,IAAA,IAAgCS,EAAhCC,EAAAlO,EAAuBwN,KAASS,EAAAC,KAAAjO,MAAE,KAAvBC,EAAQ+N,EAAA9N,MACVN,EAAQ2B,IAAItB,IACb6N,EAAMtE,KAAKvJ,EAEnB,CAXJ,CAaJ,CACJ,CAEA,IAAK,IAAIP,EAAQ,EAAGA,EAAQwB,EAASG,OAAQ3B,IACzC,IAAKE,EAAQ2B,IAAI7B,GAAQ,CACrB,IAAMwO,EAAmC,GACzCzO,EAAIC,EAAOwO,GACXP,EAAWnE,KAAK,CACZ/H,KAAM,oBACNP,SAAUgN,GAElB,CAOJ,OAFAP,EAAW3F,KAAK,SAAC5C,EAAGkE,GAAC,OAAKlE,EAAElE,SAASG,OAASiI,EAAEpI,SAASG,MAAM,GAExDsM,CACX,CUhGeQ,CAA4B1H,KAAKqF,QAC5C,EAACrE,EAMD2G,2BAAA,WACI,OVvEF,SACFhC,GAQA,IANA,IA+DmBvJ,EA/Db3B,EAAWkL,EAAkBlL,SAC7BmN,EAAmBnN,EAASG,OAG5BiN,EAA6B,IAAItN,IAE9BtB,EAAQ,EAAGA,EAAQ2O,EAAkB3O,IAG1C,IAFA,IAEoCoB,EAApCG,EAAAlB,EAFoBmB,EAASxB,GAAO0B,SAASD,eAETL,EAAAG,KAAAjB,MAAE,KAC5BsB,GAqDKuB,EAtDM/B,EAAAZ,OAuDN,GAAM2C,IAAAA,EAAS,GApDrByL,EAA2B/M,IAAID,IAChCgN,EAA2B9M,IAAIF,EAAK,IAGxCgN,EAA2BpL,IAAI5B,GAAMkI,KAAK9J,EAC9C,CAMJ,IAFA,IAEyDwE,EAFnDvE,EAA4BgC,MAAMC,KAAK,CAAEP,OAAQgN,GAAoB,WAAM,MAAA,EAAE,GAEnFlK,EAAApE,EAAsBuO,EAA2BzM,YAAQqC,EAAAC,KAAAnE,MACrD,IADO,IAAAuO,EAAOrK,EAAAhE,MACL6C,EAAI,EAAGA,EAAIwL,EAAQlN,OAAQ0B,IAChC,IAAK,IAAIgG,EAAIhG,EAAI,EAAGgG,EAAIwF,EAAQlN,OAAQ0H,IAAK,CACzC,IAAM3D,EAAImJ,EAAQxL,GACZuG,EAAIiF,EAAQxF,GAClBpJ,EAAcyF,GAAGoE,KAAKF,GACtB3J,EAAc2J,GAAGE,KAAKpE,EAC1B,CAOR,IAHA,IAAMxF,EAAU,IAAI+B,MAAe0M,GAAkBG,MAAK,GACtDC,EAAsB,EAEjB/O,EAAQ,EAAGA,EAAQ2O,EAAkB3O,IACrCE,EAAQF,KACTD,EAAIC,EAAOC,EAAeC,GAC1B6O,KAIR,OAAOA,CACX,CUuBeC,CAAgCjI,KAAKqF,QAChD,EAACrE,EAMDkH,oBAAA,WACI,gBC/EJvC,GAKA,IAHA,IAGgDtL,EAH1C8N,EAAU,IAAInC,IACdoC,EAAU,IAAIpC,IAEpBxL,EAAAlB,EAAsBqM,EAAkBlL,YAAQJ,EAAAG,KAAAjB,MAAE,CAG9C,IAHO,IAG6BkE,EAF9B/C,EADQL,EAAAZ,MACckB,SAASD,YAErCgD,EAAApE,EAAyBoB,KAAW+C,EAAAC,KAAAnE,MAChC4O,EAAQjH,IAAIjH,KAAKC,UADAuD,EAAAhE,QAIrB,IAAK,IAAI6C,EAAI,EAAGA,EAAI5B,EAAYE,OAAS,EAAG0B,IAAK,CAC7C,IAGM+L,GAW8BC,EAbd5N,EAAY4B,EAAI,IAcxCiM,EAAYtO,KAAKC,UAfOQ,EAAY4B,MAgBpCkM,EAAYvO,KAAKC,UAAUoO,IAGnBC,EAAS,IAAIC,EAGjBA,MAAaD,GAlBfH,EAAQlH,IAAImH,EAChB,CACJ,CAQJ,IAAgDC,EACtCC,EACAC,EARN,MAAO,CACHC,UAAWN,EAAQO,KACnBC,UAAWP,EAAQM,KAE3B,CDsDeE,CAAyB5I,KAAKqF,QACzC,EAACrE,EAMD6H,SAAA,WAEI,MAAO,CACH7N,KAAM,oBACNP,SC7CI,SAAsBqO,GAIlC,IAHA,IAGoC1P,EAH9B2P,EAAO,IAAI/C,IACXgD,EAA2B,GAEjC3P,EAAAC,EAAsBwP,EAAMrO,YAAQrB,EAAAC,KAAAE,MAChC,IADO,IACyCmN,EAAhDC,EAAArN,EADcF,EAAAK,MACckB,SAASD,eAAWgM,EAAAC,KAAApN,MAAE,KAAvC0P,EAAKvC,EAAAjN,MACNoB,EAAMoO,EAAM5M,KAAK,KAElB0M,EAAKjO,IAAID,KACVkO,EAAK7H,IAAIrG,GACTmO,EAAOjG,KAAK,CACR/H,KAAM,UACNL,SAAU,CACNK,KAAM,QACNN,YAAauO,GAEjBhO,WAAY,KAGxB,CAGJ,OAAO+N,CACX,CDmBsBE,CAAsBlJ,KAAKqF,SAK7C,EAACrE,EAMDmI,aAAA,WAEI,OADsBnJ,KAAKkI,sBAAnBO,SAEZ,EAACzH,EAQDoI,SAAA,WACI,OAAOjP,EAAuB6F,KAAKqF,QACvC,EAACrE,EAODqI,qBAAA,WACI,IAAMC,EAActJ,KAAKuJ,iBACzB,OAAKD,EAGEtE,EAAYsE,IAFP,CAGhB,EAACtI,EAODwI,qBAAA,WACI,IAAMvN,EAAQ+D,KAAKoJ,WAAW3O,SAC9B,OAAqB,IAAjBwB,EAAMrB,QACE,EAEQqB,EAAMwN,OAAO,SAACC,EAAKrB,GAAI,OAAKqB,EAAM1E,EAAYqD,EAAK,EAAE,GACpDpM,EAAMrB,MAC/B,EAACoG,EAMD2I,eAAA,WAII,IAHA,IAGwBtP,EAHlBuP,EAAkC,CAAA,EAGxCpP,EAAAlB,EAFc0G,KAAKoJ,WAAW3O,YAENJ,EAAAG,KAAAjB,MAAE,CAAA,IACtBsQ,EADWxP,EAAAZ,MACekB,SAASD,YAA5Bf,EAAKkQ,EAAEjQ,GAAAA,EAAGiQ,EACjB,GAAMtN,EAAc5C,EAAM,GAAE,IAAIA,EAAM,GAChC6C,EAAY5C,EAAI,GAAMA,IAAAA,EAAI,GAEhCgQ,EAAQrN,IAAaqN,EAAQrN,IAAa,GAAK,EAC/CqN,EAAQpN,IAAWoN,EAAQpN,IAAW,GAAK,CAC/C,CAEA,OAAOoN,CACX,EAAC5I,EAKD8I,mBAAA,WACI,IAAMF,EAAUG,OAAO3O,OAAO4E,KAAK2J,kBACnC,OAAuB,IAAnBC,EAAQhP,OAAqB,CAAE2F,IAAK,EAAGC,IAAK,EAAGwJ,IAAK,GAKjD,CAAEzJ,IAHGnC,KAAKmC,IAAG0J,MAAR7L,KAAYwL,GAGVpJ,IAFFpC,KAAKoC,IAAGyJ,MAAR7L,KAAYwL,GAELI,IADPJ,EAAQH,OAAO,SAAC9K,EAAGkE,GAAC,OAAKlE,EAAIkE,CAAC,EAAE,GAAK+G,EAAQhP,OAE7D,EAACoG,EAODkJ,sBAAA,WACI,IAAMC,EAAenK,KAAKoK,kBAC1B,OAAKD,EAGEnF,EAAYmF,IAFP,CAGhB,EAACnJ,EAMDuI,eAAA,WACI,IAAMtN,EAAQ+D,KAAKoJ,WAAW3O,SAC9B,GAAqB,IAAjBwB,EAAMrB,OACN,OAAO,KAEX,IAAMyP,EAAepO,EAAMsF,KAAK,SAAC5C,EAAGkE,GAAM,OAAAmC,EAAYrG,GAAKqG,EAAYnC,EAAE,GACzE,OAAOwH,EAAaA,EAAazP,OAAS,EAC9C,EAACoG,EAMDoJ,gBAAA,WACI,IAAMnO,EAAQ+D,KAAKoJ,WAAW3O,SAC9B,OAAqB,IAAjBwB,EAAMrB,OACC,KAEWqB,EAAMsF,KAAK,SAAC5C,EAAGkE,GAAM,OAAAmC,EAAYrG,GAAKqG,EAAYnC,EAAE,GACrD,EACzB,EAAC7B,EAMDsJ,aAAA,WAEI,OADsBtK,KAAKkI,sBAAnBS,SAEZ,EAAC3H,EAODjF,aAAA,WACI,OAAOA,EAAaiE,KAAKqF,SAASpI,SACtC,EAAC+D,EAODuJ,eAAA,SAAeC,GACX,GAAIA,GAASA,EAAQ,EAAG,CAIpB,IAFA,IAAIC,EAAezK,KAAKqF,QAEf/I,EAAI,EAAGA,EAAIkO,EAAOlO,IAEvBmO,EADkB1O,EAAa0O,GACNvN,aAG7B,OAAOuN,CAEX,CACA,OAAO1O,EAAaiE,KAAKqF,SAASnI,YACtC,EAAC8D,EAOD0J,kBAAA,SAAkBC,GACd,gBEnQJhF,EACAiF,GAEA,GAAIjF,EAAkBlL,SAASG,OAAS,EACpC,OAAO+K,EAYX,IARA,IAQgDtL,EAR1CwQ,EAAgB,IAAI7E,IACpB8E,EAAiC,IAAIvQ,IAGrCwQ,EAAwB,GACxBC,EAAqB,IAAIzQ,IAG/BC,EAAAlB,EAAsBqM,EAAkBlL,YAAQJ,EAAAG,KAAAjB,MAC5C,IAD8C,IACEmN,EAAhDC,EAAArN,EADce,EAAAZ,MACckB,SAASD,eAAWgM,EAAAC,KAAApN,MAAE,KAAvC0P,EAAKvC,EAAAjN,MACNoB,EAASoO,EAAM,GAAMA,IAAAA,EAAM,GAC5B+B,EAAmBlQ,IAAID,KACxBmQ,EAAmBjQ,IAAIF,EAAKkQ,EAAUnQ,QACtCmQ,EAAUhI,KAAKkG,GAEvB,CAKJ,IADA,IAAIgC,EAAuB,IAAIvL,EAAOqL,EAAUnQ,QAChDsQ,IAAAC,EAAoBJ,EAASG,EAAAC,EAAAvQ,OAAAsQ,IAAE,CAA1B,IAAMjC,EAAKkC,EAAAD,GACZD,EAAa/J,IAAI+H,EAAM,GAAIA,EAAM,GACrC,CAGA,SAASmC,EACLxN,EACAyN,EACAC,GAUA,IARA,IAQ6C7N,EARzC8N,EAA2B,KAC3BC,EAAkBC,SAOtB/N,EAAApE,EJ1BQ,SAAOL,EAAe4E,EAAaC,EAAa4N,EAAuBC,QAAb,IAAVD,IAAAA,EAAaD,eAAuB,IAAbE,IAAAA,EAAgBF,UACnG,IAAIG,EAAkB,EAChBC,EAAS,QAEIC,IAAfJ,IACAA,EAAaD,eAGKK,IAAlBH,IACAC,EAAkB7H,EAAS4H,EAdf,OAkChB,IAhBA,IAAMI,EAAI,IAAIpJ,EAAU,GAAI4B,GAGxBT,EAAO,CACPtC,KAAM,EACNC,MAAOxI,EAAM8G,IAAInF,OAAS,EAC1B8G,KAAM,EACN8C,KAAM,EACNnH,QAAS,IACTC,QAAS,GACTC,OAAQ,IACRC,OAAQ,IAGNqG,EAASzF,KAAKS,IAAIf,EAAM6F,GAEvBG,GAAM,CACT,IAAMrC,EAAQqC,EAAKrC,MACbD,EAAOsC,EAAKtC,KAElB,GAAIC,EAAQD,GAAQvI,EAAM2G,SAGtB,IAAK,IAAItD,EAAIkF,EAAMlF,GAAKmF,EAAOnF,IAAK,CAChC,IAAM0P,EAAK/S,EAAM8G,IAAIzD,GAEfkI,EAAOK,EAAahH,EAAKC,EAAK7E,EAAMgH,OAAO,EAAI3D,GAAIrD,EAAMgH,OAAO,EAAI3D,EAAI,GAAIuH,GAClFkI,EAAEhJ,KAAK,CAAEiJ,GAAAA,EAAIxH,KAAAA,GACjB,KAEG,CAEH,IAAM7C,EAAKH,EAAOC,GAAU,EACtBwK,EAAShT,EAAMgH,OAAO,EAAI0B,GAC1BuK,EAASjT,EAAMgH,OAAO,EAAI0B,EAAI,GAG9BqK,EAAK/S,EAAM8G,IAAI4B,GACf6C,EAAOK,EAAahH,EAAKC,EAAKmO,EAAQC,EAAQrI,GACpDkI,EAAEhJ,KAAK,CAAEiJ,GAAAA,EAAIxH,KAAAA,IAGb,IAAM2H,GAAYrI,EAAKpC,KAAO,GAAK,EAG7B0K,EAAW,CACb5K,KAAAA,EACAC,MAAOE,EAAI,EACXD,KAAMyK,EACN9O,OAAQyG,EAAKzG,OACbC,OAAQwG,EAAKxG,OACbC,OAAsB,IAAduG,EAAKpC,KAAauK,EAASnI,EAAKvG,OACxCC,OAAsB,IAAdsG,EAAKpC,KAAawK,EAASpI,EAAKtG,OACxCgH,KAAM,GAGJ6H,EAAY,CACd7K,KAAMG,EAAI,EACVF,MAAAA,EACAC,KAAMyK,EACN9O,OAAsB,IAAdyG,EAAKpC,KAAauK,EAASnI,EAAKzG,OACxCC,OAAsB,IAAdwG,EAAKpC,KAAawK,EAASpI,EAAKxG,OACxCC,OAAQuG,EAAKvG,OACbC,OAAQsG,EAAKtG,OACbgH,KAAM,GAGV4H,EAAS5H,KAAOZ,EAAQ/F,EAAKC,EAAK+F,EAAQuI,GAC1CC,EAAU7H,KAAOZ,EAAQ/F,EAAKC,EAAK+F,EAAQwI,GAG3CN,EAAEhJ,KAAKqJ,GACPL,EAAEhJ,KAAKsJ,EACX,CAKA,KAAON,EAAEnR,QAAyB,MAAfmR,EAAE1I,OAAO2I,IAAY,CACpC,IAAMM,EAAYP,EAAE7I,MACpB,GAAIoJ,EAAU9H,KAAOoH,EAAiB,OAAOC,EAE7C,GADAA,EAAO9I,KAAKuJ,EAAUN,IAClBH,EAAOjR,SAAW8Q,EAAY,OAAOG,CAC7C,CAGA/H,EAAOiI,EAAE7I,KACb,CAEA,OAAO2I,CACX,CI/EiCU,CAAOtB,EAAcrN,EAAW,GAAIA,EAAW,GAAI6N,SAD3Db,EAAe,QAGanN,EAAAC,KAAAnE,MAAE,CAAA,IACrCiT,EAAiBzB,EADFtN,EAAAhE,OAEfgT,EAAkBD,EAAe,OAAMA,EAAe,GAG5D,GAAK3B,EAAc/P,IAAI2R,KAInBpB,EAAQqB,SAASF,KAIjBlB,EAAoBxQ,IAAI2R,GAA5B,CAIA,IAAME,EAA2D,IAAhD5O,EAAkByO,EAAgB5O,GAE/C+O,GAAY/B,GAAgB+B,EAAWnB,IACvCD,EAAUiB,EACVhB,EAAkBmB,EANtB,CAQJ,CAGA,OAAgB,OAAZpB,EACOA,GAIXV,EAAc3J,IAAOtD,EAAW,GAAE,IAAIA,EAAW,IAC1CA,EACX,CAhDAqN,EAAa5J,SAkDb,IAAMuL,EAAkBjH,EAAkBlL,SAASuC,IAAI,SAACJ,GAKpD,IAJA,IAIqDxD,EAJ/CyT,EAAwB,GACxBC,EAAiC,GACjCC,EAAW,IAAI/G,IAErB3M,EAAAC,EAAyBsD,EAAQjC,SAASD,eAAWtB,EAAAC,KAAAE,MAAE,CAAA,IAA5CqE,EAAUxE,EAAAK,MACXoB,EAAS+C,EAAW,GAAE,IAAIA,EAAW,GAE3C,IAAKkN,EAAQhQ,IAAID,GAAM,CACnB,IAAMmS,EAAU5B,EAAyBxN,EAAYiP,EAAWE,GAI5DA,EAASjS,IAHSkS,EAAQ,OAAMA,EAAQ,IAIxClC,EAAQ/P,IAAIF,EAAK+C,GAEjBkN,EAAQ/P,IAAIF,EAAKmS,EAEzB,CAEA,IAAMC,EAAoBnC,EAAQrO,IAAI5B,GAChCqS,EAAgBD,EAAkB,GAAMA,IAAAA,EAAkB,GAE3DF,EAASjS,IAAIoS,KACdJ,EAAmB/J,KAAKkK,GACxBF,EAAS7L,IAAIgM,IAGjBL,EAAU9J,KAAKnF,EACnB,CAEA,OAAAuP,EACOvQ,CAAAA,EAAAA,GACHjC,SAAQwS,EACDvQ,CAAAA,EAAAA,EAAQjC,UACXD,YAAaoS,KAGzB,GAEA,OAAAK,EACOxH,CAAAA,EAAAA,GACHlL,SAAUmS,GAElB,CFsIeQ,CAAsBpN,KAAKqF,QAASsF,EAC/C,EAACvF,CAAA,CA1PD"}