@rushstack/lookup-by-path - npm Package Compare versions

Comparing version 0.9.10 to 0.10.0

CHANGELOG.json

@@ -5,2 +5,19 @@ {
     {
+      "version": "0.10.0",
+      "tag": "@rushstack/lookup-by-path_v0.10.0",
+      "date": "Thu, 09 Apr 2026 00:15:07 GMT",
+      "comments": {
+        "minor": [
+          {
+            "comment": "Add `toJson`/`fromJson` methods to `LookupByPath` for serialization/deserialization"
+          }
+        ],
+        "dependency": [
+          {
+            "comment": "Updating dependency \"@rushstack/heft\" to `1.2.11`"
+          }
+        ]
+      }
+    },
+    {
       "version": "0.9.10",
@@ -7,0 +24,0 @@ "tag": "@rushstack/lookup-by-path_v0.9.10",

CHANGELOG.md

 # Change Log - @rushstack/lookup-by-path
 
-This log was last generated on Sat, 04 Apr 2026 00:14:00 GMT and should not be manually modified.
+This log was last generated on Thu, 09 Apr 2026 00:15:07 GMT and should not be manually modified.
 
+## 0.10.0
+Thu, 09 Apr 2026 00:15:07 GMT
+
+### Minor changes
+
+- Add `toJson`/`fromJson` methods to `LookupByPath` for serialization/deserialization
+
 ## 0.9.10
@@ -6,0 +13,0 @@ Sat, 04 Apr 2026 00:14:00 GMT

dist/lookup-by-path.d.ts

@@ -51,2 +51,29 @@ /**
 /**
+ * JSON-serializable representation of a {@link LookupByPath} instance.
+ *
+ * @remarks
+ * The `values` array stores each unique value exactly once (by reference identity).
+ * Nodes in the tree reference values by their index in this array, which ensures that
+ * reference equality is preserved across serialization and deserialization.
+ *
+ * @beta
+ */
+export declare interface ILookupByPathJson<TSerialized> {
+    /**
+     * The path delimiter used by the serialized trie.
+     */
+    delimiter: string;
+    /**
+     * Array of serialized values. Nodes in the tree reference values by their index in this array.
+     * Using an array with index-based references preserves reference equality: if multiple nodes
+     * share the same value (by reference), they will reference the same index.
+     */
+    values: TSerialized[];
+    /**
+     * The serialized tree structure.
+     */
+    tree: ISerializedPathTrieNode;
+}
+
+/**
  * Object containing both the matched item and the start index of the remainder of the query.
@@ -186,2 +213,13 @@ *
     getNodeAtPrefix(query: string, delimiter?: string): IReadonlyPathTrieNode<TItem> | undefined;
+    /**
+     * Serializes this `LookupByPath` instance to a JSON-compatible representation.
+     *
+     * @param serializeValue - A function that converts a value of type `TItem` to a JSON-serializable form.
+     * @returns A JSON-serializable representation of this trie.
+     *
+     * @remarks
+     * Values that are reference-equal will be serialized once and referenced by index, ensuring
+     * that reference equality is preserved when deserialized via {@link LookupByPath.fromJson}.
+     */
+    toJson<TSerialized>(serializeValue: (value: TItem) => TSerialized): ILookupByPathJson<TSerialized>;
 }
@@ -209,2 +247,19 @@
 /**
+ * JSON-serializable representation of a node in a {@link LookupByPath} trie.
+ *
+ * @beta
+ */
+export declare interface ISerializedPathTrieNode {
+    /**
+     * Index into the `values` array of the containing {@link ILookupByPathJson}.
+     * If `undefined`, this node has no associated value.
+     */
+    valueIndex?: number;
+    /**
+     * Child nodes keyed by path segment.
+     */
+    children?: Record<string, ISerializedPathTrieNode>;
+}
+
+/**
  * This class is used to associate path-like-strings, such as those returned by `git` commands,
@@ -340,2 +395,20 @@ * with entities that correspond with ancestor folders, such as Rush Projects or npm packages.
     /**
+     * {@inheritdoc IReadonlyLookupByPath.toJson}
+     */
+    toJson<TSerialized>(serializeValue: (value: TItem) => TSerialized): ILookupByPathJson<TSerialized>;
+    /**
+     * Deserializes a `LookupByPath` instance from a JSON representation previously
+     * created by {@link LookupByPath.toJson}.
+     *
+     * @param json - The JSON representation to deserialize.
+     * @param deserializeValue - A function that converts a serialized value back to its original type.
+     * @returns A new `LookupByPath` instance.
+     *
+     * @remarks
+     * Reference equality is preserved: if multiple nodes in the serialized trie pointed at the same
+     * value (i.e., the same index in the `values` array), the deserialized nodes will share the same
+     * object reference.
+     */
+    static fromJson<TItem extends {}, TSerialized>(json: ILookupByPathJson<TSerialized>, deserializeValue: (serialized: TSerialized) => TItem): LookupByPath<TItem>;
+    /**
      * Iterates through progressively longer prefixes of a given string and returns as soon
@@ -342,0 +415,0 @@ * as the number of candidate items that match the prefix are 1 or 0.

dist/tsdoc-metadata.json

@@ -8,5 +8,5 @@ // This file is read by tools that parse documentation comments conforming to the TSDoc standard.
       "packageName": "@microsoft/api-extractor",
-      "packageVersion": "7.58.0"
+      "packageVersion": "7.58.1"
     }
   ]
 }

lib-commonjs/index.js.map

@@ -1,1 +0,1 @@
-{"version":3,"file":"index.js","sourceRoot":"","sources":["../src/index.ts"],"names":[],"mappings":";AAAA,4FAA4F;AAC5F,2DAA2D;;;AAS3D,+CAA8C;AAArC,4GAAA,YAAY,OAAA;AAErB,qFAAoF;AAA3E,kJAAA,+BAA+B,OAAA","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * Strongly typed trie data structure for path and URL-like strings.\n *\n * @packageDocumentation\n */\n\nexport type { IPrefixMatch, IReadonlyLookupByPath, IReadonlyPathTrieNode } from './LookupByPath';\nexport { LookupByPath } from './LookupByPath';\nexport type { IGetFirstDifferenceInCommonNodesOptions } from './getFirstDifferenceInCommonNodes';\nexport { getFirstDifferenceInCommonNodes } from './getFirstDifferenceInCommonNodes';\n"]}
+{"version":3,"file":"index.js","sourceRoot":"","sources":["../src/index.ts"],"names":[],"mappings":";AAAA,4FAA4F;AAC5F,2DAA2D;;;AAe3D,+CAA8C;AAArC,4GAAA,YAAY,OAAA;AAErB,qFAAoF;AAA3E,kJAAA,+BAA+B,OAAA","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * Strongly typed trie data structure for path and URL-like strings.\n *\n * @packageDocumentation\n */\n\nexport type {\n  ILookupByPathJson,\n  IPrefixMatch,\n  IReadonlyLookupByPath,\n  IReadonlyPathTrieNode,\n  ISerializedPathTrieNode\n} from './LookupByPath';\nexport { LookupByPath } from './LookupByPath';\nexport type { IGetFirstDifferenceInCommonNodesOptions } from './getFirstDifferenceInCommonNodes';\nexport { getFirstDifferenceInCommonNodes } from './getFirstDifferenceInCommonNodes';\n"]}

lib-commonjs/LookupByPath.js

@@ -295,2 +295,73 @@ "use strict";
     /**
+     * {@inheritdoc IReadonlyLookupByPath.toJson}
+     */
+    toJson(serializeValue) {
+        const valueToIndex = new Map();
+        const values = [];
+        const getOrAddValueIndex = (value) => {
+            let index = valueToIndex.get(value);
+            if (index === undefined) {
+                index = values.length;
+                valueToIndex.set(value, index);
+                values.push(serializeValue(value));
+            }
+            return index;
+        };
+        const serializeNode = (node) => {
+            const result = {};
+            if (node.value !== undefined) {
+                result.valueIndex = getOrAddValueIndex(node.value);
+            }
+            if (node.children && node.children.size > 0) {
+                const children = Object.create(null);
+                for (const [segment, child] of node.children) {
+                    children[segment] = serializeNode(child);
+                }
+                result.children = children;
+            }
+            return result;
+        };
+        return {
+            delimiter: this.delimiter,
+            values,
+            tree: serializeNode(this._root)
+        };
+    }
+    /**
+     * Deserializes a `LookupByPath` instance from a JSON representation previously
+     * created by {@link LookupByPath.toJson}.
+     *
+     * @param json - The JSON representation to deserialize.
+     * @param deserializeValue - A function that converts a serialized value back to its original type.
+     * @returns A new `LookupByPath` instance.
+     *
+     * @remarks
+     * Reference equality is preserved: if multiple nodes in the serialized trie pointed at the same
+     * value (i.e., the same index in the `values` array), the deserialized nodes will share the same
+     * object reference.
+     */
+    static fromJson(json, deserializeValue) {
+        const deserializedValues = json.values.map(deserializeValue);
+        const result = new LookupByPath(undefined, json.delimiter);
+        const deserializeNode = (jsonNode, targetNode) => {
+            if (jsonNode.valueIndex !== undefined) {
+                targetNode.value = deserializedValues[jsonNode.valueIndex];
+                result._size++;
+            }
+            if (jsonNode.children) {
+                targetNode.children = new Map();
+                for (const [segment, childJson] of Object.entries(jsonNode.children)) {
+                    const childNode = {
+                        value: undefined,
+                        children: undefined
+                    };
+                    targetNode.children.set(segment, childNode);
+                    deserializeNode(childJson, childNode);
+                }
+            }
+        };
+        deserializeNode(json.tree, result._root);
+        return result;
+    }
+    /**
      * Iterates through progressively longer prefixes of a given string and returns as soon
@@ -297,0 +368,0 @@ * as the number of candidate items that match the prefix are 1 or 0.

lib-commonjs/LookupByPath.js.map

@@ -1,1 +0,1 @@
-{"version":3,"file":"LookupByPath.js","sourceRoot":"","sources":["../src/LookupByPath.ts"],"names":[],"mappings":";AAAA,4FAA4F;AAC5F,2DAA2D;;;AAsM3D;;;;;;;;;;;;;;;;;;;GAmBG;AACH,MAAa,YAAY;IAgBvB;;;;OAIG;IACH,YAAmB,OAAmC,EAAE,SAAkB;QACxE,IAAI,CAAC,KAAK,GAAG;YACX,KAAK,EAAE,SAAS;YAChB,QAAQ,EAAE,SAAS;SACpB,CAAC;QAEF,IAAI,CAAC,SAAS,GAAG,SAAS,aAAT,SAAS,cAAT,SAAS,GAAI,GAAG,CAAC;QAClC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QAEf,IAAI,OAAO,EAAE,CAAC;YACZ,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,OAAO,EAAE,CAAC;gBACnC,IAAI,CAAC,OAAO,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;YAC3B,CAAC;QACH,CAAC;IACH,CAAC;IAED;;;;;;;;OAQG;IACI,MAAM,CAAC,CAAC,mBAAmB,CAAC,cAAsB,EAAE,YAAoB,GAAG;QAChF,KAAK,MAAM,WAAW,IAAI,IAAI,CAAC,gBAAgB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,CAAC;YAC3E,MAAM,WAAW,CAAC,MAAM,CAAC;QAC3B,CAAC;IACH,CAAC;IAEO,MAAM,CAAC,CAAC,gBAAgB,CAAC,KAAa,EAAE,YAAoB,GAAG;QACrE,IAAI,CAAC,KAAK,EAAE,CAAC;YACX,OAAO;QACT,CAAC;QAED,IAAI,aAAa,GAAW,CAAC,CAAC;QAC9B,IAAI,SAAS,GAAW,KAAK,CAAC,OAAO,CAAC,SAAS,CAAC,CAAC;QAEjD,mBAAmB;QACnB,OAAO,SAAS,IAAI,CAAC,EAAE,CAAC;YACtB,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,SAAS,CAAC;gBAC7C,KAAK,EAAE,SAAS;aACjB,CAAC;YACF,aAAa,GAAG,SAAS,GAAG,CAAC,CAAC;YAC9B,SAAS,GAAG,KAAK,CAAC,OAAO,CAAC,SAAS,EAAE,aAAa,CAAC,CAAC;QACtD,CAAC;QAED,eAAe;QACf,IAAI,aAAa,GAAG,KAAK,CAAC,MAAM,EAAE,CAAC;YACjC,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,KAAK,CAAC,MAAM,CAAC;gBAChD,KAAK,EAAE,KAAK,CAAC,MAAM;aACpB,CAAC;QACJ,CAAC;IACH,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;;;OAIG;IACI,KAAK;QACV,IAAI,CAAC,KAAK,CAAC,KAAK,GAAG,SAAS,CAAC;QAC7B,IAAI,CAAC,KAAK,CAAC,QAAQ,GAAG,SAAS,CAAC;QAChC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QACf,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACI,OAAO,CAAC,cAAsB,EAAE,KAAY,EAAE,YAAoB,IAAI,CAAC,SAAS;QACrF,OAAO,IAAI,CAAC,mBAAmB,CAAC,YAAY,CAAC,mBAAmB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,KAAK,CAAC,CAAC;IACtG,CAAC;IAED;;;;;;;OAOG;IACI,UAAU,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACjE,MAAM,IAAI,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QACxF,IAAI,CAAA,IAAI,aAAJ,IAAI,uBAAJ,IAAI,CAAE,KAAK,MAAK,SAAS,EAAE,CAAC;YAC9B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;YACvB,IAAI,CAAC,KAAK,EAAE,CAAC;YACb,OAAO,IAAI,CAAC;QACd,CAAC;QAED,OAAO,KAAK,CAAC;IACf,CAAC;IAED;;;;;OAKG;IACI,aAAa,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACpE,MAAM,SAAS,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QAC7F,IAAI,CAAC,SAAS,EAAE,CAAC;YACf,OAAO,KAAK,CAAC;QACf,CAAC;QAED,MAAM,KAAK,GAA2B,CAAC,SAAS,CAAC,CAAC;QAClD,IAAI,OAAO,GAAW,CAAC,CAAC;QACxB,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,IAAI,GAAyB,KAAK,CAAC,GAAG,EAAG,CAAC;YAChD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;gBACvB,OAAO,EAAE,CAAC;YACZ,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,KAAK,IAAI,IAAI,CAAC,QAAQ,CAAC,MAAM,EAAE,EAAE,CAAC;oBAC3C,KAAK,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;gBACpB,CAAC;gBACD,IAAI,CAAC,QAAQ,CAAC,KAAK,EAAE,CAAC;YACxB,CAAC;QACH,CAAC;QAED,IAAI,CAAC,KAAK,IAAI,OAAO,CAAC;QACtB,OAAO,OAAO,GAAG,CAAC,CAAC;IACrB,CAAC;IAED;;;;;OAKG;IACI,mBAAmB,CAAC,YAA8B,EAAE,KAAY;QACrE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,OAAO,IAAI,YAAY,EAAE,CAAC;YACnC,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,IAAI,CAAC,QAAQ,GAAG,IAAI,GAAG,EAAE,CAAC;YAC5B,CAAC;YACD,IAAI,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;YACzE,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,IAAI,CAAC,QAAQ,CAAC,GAAG,CACf,OAAO,EACP,CAAC,KAAK,GAAG;oBACP,KAAK,EAAE,SAAS;oBAChB,QAAQ,EAAE,SAAS;iBACpB,CAAC,CACH,CAAC;YACJ,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;YAC7B,IAAI,CAAC,KAAK,EAAE,CAAC;QACf,CAAC;QACD,IAAI,CAAC,KAAK,GAAG,KAAK,CAAC;QAEnB,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,aAAa,CAAC,SAAiB,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxE,OAAO,IAAI,CAAC,yBAAyB,CAAC,YAAY,CAAC,mBAAmB,CAAC,SAAS,EAAE,SAAS,CAAC,CAAC,CAAC;IAChG,CAAC;IAED;;OAEG;IACI,sBAAsB,CAC3B,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,uBAAuB,CAAC,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC,CAAC;IACvF,CAAC;IAED;;OAEG;IACI,yBAAyB,CAAC,iBAAmC;;QAClE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAsB,IAAI,CAAC,KAAK,CAAC;QACzC,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,OAAO,IAAI,iBAAiB,EAAE,CAAC;gBACxC,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;gBAC3E,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,GAAG,MAAA,IAAI,CAAC,KAAK,mCAAI,IAAI,CAAC;gBAC1B,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC;IACrC,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC,CAAC,CAAC,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,SAAS,CAAC;IAC/D,CAAC;IAED;;OAEG;IACI,YAAY,CACjB,UAA8B,EAC9B,YAAoB,IAAI,CAAC,SAAS;QAElC,MAAM,kBAAkB,GAAmC,IAAI,GAAG,EAAE,CAAC;QAErE,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,UAAU,EAAE,CAAC;YACtC,MAAM,KAAK,GAAsB,IAAI,CAAC,aAAa,CAAC,IAAI,EAAE,SAAS,CAAC,CAAC;YACrE,IAAI,KAAK,KAAK,SAAS,EAAE,CAAC;gBACxB,SAAS;YACX,CAAC;YACD,IAAI,WAAW,GAAmC,kBAAkB,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;YAChF,IAAI,CAAC,WAAW,EAAE,CAAC;gBACjB,WAAW,GAAG,IAAI,GAAG,EAAE,CAAC;gBACxB,kBAAkB,CAAC,GAAG,CAAC,KAAK,EAAE,WAAW,CAAC,CAAC;YAC7C,CAAC;YACD,WAAW,CAAC,GAAG,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;QAC9B,CAAC;QAED,OAAO,kBAAkB,CAAC;IAC5B,CAAC;IAED;;OAEG;IACI,CAAC,OAAO,CAAC,KAAc,EAAE,YAAoB,IAAI,CAAC,SAAS;QAChE,IAAI,IAAsC,CAAC;QAC3C,IAAI,KAAK,EAAE,CAAC;YACV,IAAI,GAAG,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;YAChD,IAAI,CAAC,IAAI,EAAE,CAAC;gBACV,OAAO;YACT,CAAC;QACH,CAAC;aAAM,CAAC;YACN,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC;QACpB,CAAC;QAED,MAAM,KAAK,GAAqC,CAAC,CAAC,KAAK,aAAL,KAAK,cAAL,KAAK,GAAI,EAAE,EAAE,IAAI,CAAC,CAAC,CAAC;QACtE,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,GAAG,KAAK,CAAC,GAAG,EAAG,CAAC;YACpC,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,KAAK,CAAC,CAAC;YAC7B,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,CAAC,OAAO,EAAE,KAAK,CAAC,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;oBAC7C,KAAK,CAAC,IAAI,CAAC,CAAC,MAAM,CAAC,CAAC,CAAC,GAAG,MAAM,GAAG,SAAS,GAAG,OAAO,EAAE,CAAC,CAAC,CAAC,OAAO,EAAE,KAAK,CAAC,CAAC,CAAC;gBAC5E,CAAC;YACH,CAAC;QACH,CAAC;IACH,CAAC;IAED;;OAEG;IACI,CAAC,MAAM,CAAC,QAAQ,CAAC,CACtB,KAAc,EACd,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,OAAO,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IACxC,CAAC;IAED;;OAEG;IACI,eAAe,CACpB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IAClD,CAAC;IAED;;;;;;;OAOG;IACK,uBAAuB,CAAC,QAAgC;QAC9D,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAoC,IAAI,CAAC,KAAK;YACpD,CAAC,CAAC;gBACE,KAAK,EAAE,IAAI,CAAC,KAAK;gBACjB,KAAK,EAAE,CAAC;gBACR,SAAS,EAAE,SAAS;aACrB;YACH,CAAC,CAAC,SAAS,CAAC;QACd,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,EAAE,KAAK,EAAE,IAAI,QAAQ,EAAE,CAAC;gBAC/C,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC;gBACxE,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;oBAC7B,IAAI,GAAG;wBACL,KAAK,EAAE,IAAI,CAAC,KAAK;wBACjB,KAAK;wBACL,SAAS,EAAE,IAAI;qBAChB,CAAC;gBACJ,CAAC;gBACD,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACK,iBAAiB,CACvB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,EAAE,CAAC;YACzE,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,MAAM,CAAC,CAAC;YAC1E,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,OAAO,IAAI,CAAC;IACd,CAAC;CACF;AAxYD,oCAwYC","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * A node in the path trie used in LookupByPath\n */\ninterface IPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  children: Map<string, IPathTrieNode<TItem>> | undefined;\n}\n\n/**\n * Readonly view of a node in the path trie used in LookupByPath\n *\n * @remarks\n * This interface is used to facilitate parallel traversals for comparing two `LookupByPath` instances.\n *\n * @beta\n */\nexport interface IReadonlyPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  readonly value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  readonly children: ReadonlyMap<string, IReadonlyPathTrieNode<TItem>> | undefined;\n}\n\ninterface IPrefixEntry {\n  /**\n   * The prefix that was matched\n   */\n  prefix: string;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n}\n\n/**\n * Object containing both the matched item and the start index of the remainder of the query.\n *\n * @beta\n */\nexport interface IPrefixMatch<TItem extends {}> {\n  /**\n   * The item that matched the prefix\n   */\n  value: TItem;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n\n  /**\n   * The last match found (with a shorter prefix), if any\n   */\n  lastMatch?: IPrefixMatch<TItem>;\n}\n\n/**\n * The readonly component of `LookupByPath`, to simplify unit testing.\n *\n * @beta\n */\nexport interface IReadonlyLookupByPath<TItem extends {}> extends Iterable<[string, TItem]> {\n  /**\n   * Searches for the item associated with `childPath`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPath('foo/baz'); // returns 1\n   * trie.findChildPath('foo/bar/baz'); // returns 2\n   * ```\n   */\n  findChildPath(childPath: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Searches for the item for which the recorded prefix is the longest matching prefix of `query`.\n   * Obtains both the item and the length of the matched prefix, so that the remainder of the path can be\n   * extracted.\n   *\n   * @returns the found item and the length of the matched prefix, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findLongestPrefixMatch('foo/baz'); // returns { item: 1, index: 3 }\n   * trie.findLongestPrefixMatch('foo/bar/baz'); // returns { item: 2, index: 7 }\n   * ```\n   */\n  findLongestPrefixMatch(query: string, delimiter?: string): IPrefixMatch<TItem> | undefined;\n\n  /**\n   * Searches for the item associated with `childPathSegments`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPathFromSegments(['foo', 'baz']); // returns 1\n   * trie.findChildPathFromSegments(['foo','bar', 'baz']); // returns 2\n   * ```\n   */\n  findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined;\n\n  /**\n   * Determines if an entry exists exactly at the specified path.\n   *\n   * @returns `true` if an entry exists at the specified path, `false` otherwise\n   */\n  has(query: string, delimiter?: string): boolean;\n\n  /**\n   * Retrieves the entry that exists exactly at the specified path, if any.\n   *\n   * @returns The entry that exists exactly at the specified path, or `undefined` if no entry exists.\n   */\n  get(query: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Gets the number of entries in this trie.\n   *\n   * @returns The number of entries in this trie.\n   */\n  get size(): number;\n\n  /**\n   * @returns The root node of the trie, corresponding to the path ''\n   */\n  get tree(): IReadonlyPathTrieNode<TItem>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * [...trie.entries(undefined, ',')); // returns [['foo', 1], ['foo,bar', 2]]\n   * ```\n   */\n  entries(query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   */\n  [Symbol.iterator](query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Groups the provided map of info by the nearest entry in the trie that contains the path. If the path\n   * is not found in the trie, the info is ignored.\n   *\n   * @returns The grouped info, grouped by the nearest entry in the trie that contains the path\n   *\n   * @param infoByPath - The info to be grouped, keyed by path\n   */\n  groupByChild<TInfo>(infoByPath: Map<string, TInfo>, delimiter?: string): Map<TItem, Map<string, TInfo>>;\n\n  /**\n   * Retrieves the trie node at the specified prefix, if it exists.\n   *\n   * @param query - The prefix to check for\n   * @param delimiter - The path delimiter\n   * @returns The trie node at the specified prefix, or `undefined` if no node was found\n   */\n  getNodeAtPrefix(query: string, delimiter?: string): IReadonlyPathTrieNode<TItem> | undefined;\n}\n\n/**\n * This class is used to associate path-like-strings, such as those returned by `git` commands,\n * with entities that correspond with ancestor folders, such as Rush Projects or npm packages.\n *\n * It is optimized for efficiently locating the nearest ancestor path with an associated value.\n *\n * It is implemented as a Trie (https://en.wikipedia.org/wiki/Trie) data structure, with each edge\n * being a path segment.\n *\n * @example\n * ```ts\n * const trie = new LookupByPath([['foo', 1], ['bar', 2], ['foo/bar', 3]]);\n * trie.findChildPath('foo'); // returns 1\n * trie.findChildPath('foo/baz'); // returns 1\n * trie.findChildPath('baz'); // returns undefined\n * trie.findChildPath('foo/bar/baz'); returns 3\n * trie.findChildPath('bar/foo/bar'); returns 2\n * ```\n * @beta\n */\nexport class LookupByPath<TItem extends {}> implements IReadonlyLookupByPath<TItem> {\n  /**\n   * The delimiter used to split paths\n   */\n  public readonly delimiter: string;\n\n  /**\n   * The root node of the trie, corresponding to the path ''\n   */\n  private readonly _root: IPathTrieNode<TItem>;\n\n  /**\n   * The number of entries in this trie.\n   */\n  private _size: number;\n\n  /**\n   * Constructs a new `LookupByPath`\n   *\n   * @param entries - Initial path-value pairs to populate the trie.\n   */\n  public constructor(entries?: Iterable<[string, TItem]>, delimiter?: string) {\n    this._root = {\n      value: undefined,\n      children: undefined\n    };\n\n    this.delimiter = delimiter ?? '/';\n    this._size = 0;\n\n    if (entries) {\n      for (const [path, item] of entries) {\n        this.setItem(path, item);\n      }\n    }\n  }\n\n  /**\n   * Iterates over the segments of a serialized path.\n   *\n   * @example\n   *\n   * `LookupByPath.iteratePathSegments('foo/bar/baz')` yields 'foo', 'bar', 'baz'\n   *\n   * `LookupByPath.iteratePathSegments('foo\\\\bar\\\\baz', '\\\\')` yields 'foo', 'bar', 'baz'\n   */\n  public static *iteratePathSegments(serializedPath: string, delimiter: string = '/'): Iterable<string> {\n    for (const prefixMatch of this._iteratePrefixes(serializedPath, delimiter)) {\n      yield prefixMatch.prefix;\n    }\n  }\n\n  private static *_iteratePrefixes(input: string, delimiter: string = '/'): Iterable<IPrefixEntry> {\n    if (!input) {\n      return;\n    }\n\n    let previousIndex: number = 0;\n    let nextIndex: number = input.indexOf(delimiter);\n\n    // Leading segments\n    while (nextIndex >= 0) {\n      yield {\n        prefix: input.slice(previousIndex, nextIndex),\n        index: nextIndex\n      };\n      previousIndex = nextIndex + 1;\n      nextIndex = input.indexOf(delimiter, previousIndex);\n    }\n\n    // Last segment\n    if (previousIndex < input.length) {\n      yield {\n        prefix: input.slice(previousIndex, input.length),\n        index: input.length\n      };\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.size}\n   */\n  public get size(): number {\n    return this._size;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.tree}\n   */\n  public get tree(): IReadonlyPathTrieNode<TItem> {\n    return this._root;\n  }\n\n  /**\n   * Deletes all entries from this `LookupByPath` instance.\n   *\n   * @returns this, for chained calls\n   */\n  public clear(): this {\n    this._root.value = undefined;\n    this._root.children = undefined;\n    this._size = 0;\n    return this;\n  }\n\n  /**\n   * Associates the value with the specified serialized path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItem(serializedPath: string, value: TItem, delimiter: string = this.delimiter): this {\n    return this.setItemFromSegments(LookupByPath.iteratePathSegments(serializedPath, delimiter), value);\n  }\n\n  /**\n   * Deletes an item if it exists.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if the item was found and deleted, `false` otherwise\n   * @remarks\n   * If the node has children with values, they will be retained.\n   */\n  public deleteItem(query: string, delimeter: string = this.delimiter): boolean {\n    const node: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (node?.value !== undefined) {\n      node.value = undefined;\n      this._size--;\n      return true;\n    }\n\n    return false;\n  }\n\n  /**\n   * Deletes an item and all its children.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if any nodes were deleted, `false` otherwise\n   */\n  public deleteSubtree(query: string, delimeter: string = this.delimiter): boolean {\n    const queryNode: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (!queryNode) {\n      return false;\n    }\n\n    const queue: IPathTrieNode<TItem>[] = [queryNode];\n    let removed: number = 0;\n    while (queue.length > 0) {\n      const node: IPathTrieNode<TItem> = queue.pop()!;\n      if (node.value !== undefined) {\n        node.value = undefined;\n        removed++;\n      }\n      if (node.children) {\n        for (const child of node.children.values()) {\n          queue.push(child);\n        }\n        node.children.clear();\n      }\n    }\n\n    this._size -= removed;\n    return removed > 0;\n  }\n\n  /**\n   * Associates the value with the specified path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItemFromSegments(pathSegments: Iterable<string>, value: TItem): this {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const segment of pathSegments) {\n      if (!node.children) {\n        node.children = new Map();\n      }\n      let child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n      if (!child) {\n        node.children.set(\n          segment,\n          (child = {\n            value: undefined,\n            children: undefined\n          })\n        );\n      }\n      node = child;\n    }\n    if (node.value === undefined) {\n      this._size++;\n    }\n    node.value = value;\n\n    return this;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPath(childPath: string, delimiter: string = this.delimiter): TItem | undefined {\n    return this.findChildPathFromSegments(LookupByPath.iteratePathSegments(childPath, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findLongestPrefixMatch(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPrefixMatch<TItem> | undefined {\n    return this._findLongestPrefixMatch(LookupByPath._iteratePrefixes(query, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: TItem | undefined = node.value;\n    // Trivial cases\n    if (node.children) {\n      for (const segment of childPathSegments) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n        if (!child) {\n          break;\n        }\n        node = child;\n        best = node.value ?? best;\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public has(key: string, delimiter: string = this.delimiter): boolean {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public get(key: string, delimiter: string = this.delimiter): TItem | undefined {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length ? match.value : undefined;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public groupByChild<TInfo>(\n    infoByPath: Map<string, TInfo>,\n    delimiter: string = this.delimiter\n  ): Map<TItem, Map<string, TInfo>> {\n    const groupedInfoByChild: Map<TItem, Map<string, TInfo>> = new Map();\n\n    for (const [path, info] of infoByPath) {\n      const child: TItem | undefined = this.findChildPath(path, delimiter);\n      if (child === undefined) {\n        continue;\n      }\n      let groupedInfo: Map<string, TInfo> | undefined = groupedInfoByChild.get(child);\n      if (!groupedInfo) {\n        groupedInfo = new Map();\n        groupedInfoByChild.set(child, groupedInfo);\n      }\n      groupedInfo.set(path, info);\n    }\n\n    return groupedInfoByChild;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public *entries(query?: string, delimiter: string = this.delimiter): IterableIterator<[string, TItem]> {\n    let root: IPathTrieNode<TItem> | undefined;\n    if (query) {\n      root = this._findNodeAtPrefix(query, delimiter);\n      if (!root) {\n        return;\n      }\n    } else {\n      root = this._root;\n    }\n\n    const stack: [string, IPathTrieNode<TItem>][] = [[query ?? '', root]];\n    while (stack.length > 0) {\n      const [prefix, node] = stack.pop()!;\n      if (node.value !== undefined) {\n        yield [prefix, node.value];\n      }\n      if (node.children) {\n        for (const [segment, child] of node.children) {\n          stack.push([prefix ? `${prefix}${delimiter}${segment}` : segment, child]);\n        }\n      }\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public [Symbol.iterator](\n    query?: string,\n    delimiter: string = this.delimiter\n  ): IterableIterator<[string, TItem]> {\n    return this.entries(query, delimiter);\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public getNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IReadonlyPathTrieNode<TItem> | undefined {\n    return this._findNodeAtPrefix(query, delimiter);\n  }\n\n  /**\n   * Iterates through progressively longer prefixes of a given string and returns as soon\n   * as the number of candidate items that match the prefix are 1 or 0.\n   *\n   * If a match is present, returns the matched itme and the length of the matched prefix.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   */\n  private _findLongestPrefixMatch(prefixes: Iterable<IPrefixEntry>): IPrefixMatch<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: IPrefixMatch<TItem> | undefined = node.value\n      ? {\n          value: node.value,\n          index: 0,\n          lastMatch: undefined\n        }\n      : undefined;\n    // Trivial cases\n    if (node.children) {\n      for (const { prefix: hash, index } of prefixes) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(hash);\n        if (!child) {\n          break;\n        }\n        node = child;\n        if (node.value !== undefined) {\n          best = {\n            value: node.value,\n            index,\n            lastMatch: best\n          };\n        }\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * Finds the node at the specified path, or `undefined` if no node was found.\n   *\n   * @param query - The path to the node to search for\n   * @returns The trie node at the specified path, or `undefined` if no node was found\n   */\n  private _findNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPathTrieNode<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const { prefix } of LookupByPath._iteratePrefixes(query, delimiter)) {\n      if (!node.children) {\n        return undefined;\n      }\n      const child: IPathTrieNode<TItem> | undefined = node.children.get(prefix);\n      if (!child) {\n        return undefined;\n      }\n      node = child;\n    }\n    return node;\n  }\n}\n"]}
+{"version":3,"file":"LookupByPath.js","sourceRoot":"","sources":["../src/LookupByPath.ts"],"names":[],"mappings":";AAAA,4FAA4F;AAC5F,2DAA2D;;;AAiQ3D;;;;;;;;;;;;;;;;;;;GAmBG;AACH,MAAa,YAAY;IAgBvB;;;;OAIG;IACH,YAAmB,OAAmC,EAAE,SAAkB;QACxE,IAAI,CAAC,KAAK,GAAG;YACX,KAAK,EAAE,SAAS;YAChB,QAAQ,EAAE,SAAS;SACpB,CAAC;QAEF,IAAI,CAAC,SAAS,GAAG,SAAS,aAAT,SAAS,cAAT,SAAS,GAAI,GAAG,CAAC;QAClC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QAEf,IAAI,OAAO,EAAE,CAAC;YACZ,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,OAAO,EAAE,CAAC;gBACnC,IAAI,CAAC,OAAO,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;YAC3B,CAAC;QACH,CAAC;IACH,CAAC;IAED;;;;;;;;OAQG;IACI,MAAM,CAAC,CAAC,mBAAmB,CAAC,cAAsB,EAAE,YAAoB,GAAG;QAChF,KAAK,MAAM,WAAW,IAAI,IAAI,CAAC,gBAAgB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,CAAC;YAC3E,MAAM,WAAW,CAAC,MAAM,CAAC;QAC3B,CAAC;IACH,CAAC;IAEO,MAAM,CAAC,CAAC,gBAAgB,CAAC,KAAa,EAAE,YAAoB,GAAG;QACrE,IAAI,CAAC,KAAK,EAAE,CAAC;YACX,OAAO;QACT,CAAC;QAED,IAAI,aAAa,GAAW,CAAC,CAAC;QAC9B,IAAI,SAAS,GAAW,KAAK,CAAC,OAAO,CAAC,SAAS,CAAC,CAAC;QAEjD,mBAAmB;QACnB,OAAO,SAAS,IAAI,CAAC,EAAE,CAAC;YACtB,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,SAAS,CAAC;gBAC7C,KAAK,EAAE,SAAS;aACjB,CAAC;YACF,aAAa,GAAG,SAAS,GAAG,CAAC,CAAC;YAC9B,SAAS,GAAG,KAAK,CAAC,OAAO,CAAC,SAAS,EAAE,aAAa,CAAC,CAAC;QACtD,CAAC;QAED,eAAe;QACf,IAAI,aAAa,GAAG,KAAK,CAAC,MAAM,EAAE,CAAC;YACjC,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,KAAK,CAAC,MAAM,CAAC;gBAChD,KAAK,EAAE,KAAK,CAAC,MAAM;aACpB,CAAC;QACJ,CAAC;IACH,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;;;OAIG;IACI,KAAK;QACV,IAAI,CAAC,KAAK,CAAC,KAAK,GAAG,SAAS,CAAC;QAC7B,IAAI,CAAC,KAAK,CAAC,QAAQ,GAAG,SAAS,CAAC;QAChC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QACf,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACI,OAAO,CAAC,cAAsB,EAAE,KAAY,EAAE,YAAoB,IAAI,CAAC,SAAS;QACrF,OAAO,IAAI,CAAC,mBAAmB,CAAC,YAAY,CAAC,mBAAmB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,KAAK,CAAC,CAAC;IACtG,CAAC;IAED;;;;;;;OAOG;IACI,UAAU,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACjE,MAAM,IAAI,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QACxF,IAAI,CAAA,IAAI,aAAJ,IAAI,uBAAJ,IAAI,CAAE,KAAK,MAAK,SAAS,EAAE,CAAC;YAC9B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;YACvB,IAAI,CAAC,KAAK,EAAE,CAAC;YACb,OAAO,IAAI,CAAC;QACd,CAAC;QAED,OAAO,KAAK,CAAC;IACf,CAAC;IAED;;;;;OAKG;IACI,aAAa,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACpE,MAAM,SAAS,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QAC7F,IAAI,CAAC,SAAS,EAAE,CAAC;YACf,OAAO,KAAK,CAAC;QACf,CAAC;QAED,MAAM,KAAK,GAA2B,CAAC,SAAS,CAAC,CAAC;QAClD,IAAI,OAAO,GAAW,CAAC,CAAC;QACxB,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,IAAI,GAAyB,KAAK,CAAC,GAAG,EAAG,CAAC;YAChD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;gBACvB,OAAO,EAAE,CAAC;YACZ,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,KAAK,IAAI,IAAI,CAAC,QAAQ,CAAC,MAAM,EAAE,EAAE,CAAC;oBAC3C,KAAK,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;gBACpB,CAAC;gBACD,IAAI,CAAC,QAAQ,CAAC,KAAK,EAAE,CAAC;YACxB,CAAC;QACH,CAAC;QAED,IAAI,CAAC,KAAK,IAAI,OAAO,CAAC;QACtB,OAAO,OAAO,GAAG,CAAC,CAAC;IACrB,CAAC;IAED;;;;;OAKG;IACI,mBAAmB,CAAC,YAA8B,EAAE,KAAY;QACrE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,OAAO,IAAI,YAAY,EAAE,CAAC;YACnC,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,IAAI,CAAC,QAAQ,GAAG,IAAI,GAAG,EAAE,CAAC;YAC5B,CAAC;YACD,IAAI,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;YACzE,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,IAAI,CAAC,QAAQ,CAAC,GAAG,CACf,OAAO,EACP,CAAC,KAAK,GAAG;oBACP,KAAK,EAAE,SAAS;oBAChB,QAAQ,EAAE,SAAS;iBACpB,CAAC,CACH,CAAC;YACJ,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;YAC7B,IAAI,CAAC,KAAK,EAAE,CAAC;QACf,CAAC;QACD,IAAI,CAAC,KAAK,GAAG,KAAK,CAAC;QAEnB,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,aAAa,CAAC,SAAiB,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxE,OAAO,IAAI,CAAC,yBAAyB,CAAC,YAAY,CAAC,mBAAmB,CAAC,SAAS,EAAE,SAAS,CAAC,CAAC,CAAC;IAChG,CAAC;IAED;;OAEG;IACI,sBAAsB,CAC3B,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,uBAAuB,CAAC,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC,CAAC;IACvF,CAAC;IAED;;OAEG;IACI,yBAAyB,CAAC,iBAAmC;;QAClE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAsB,IAAI,CAAC,KAAK,CAAC;QACzC,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,OAAO,IAAI,iBAAiB,EAAE,CAAC;gBACxC,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;gBAC3E,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,GAAG,MAAA,IAAI,CAAC,KAAK,mCAAI,IAAI,CAAC;gBAC1B,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC;IACrC,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC,CAAC,CAAC,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,SAAS,CAAC;IAC/D,CAAC;IAED;;OAEG;IACI,YAAY,CACjB,UAA8B,EAC9B,YAAoB,IAAI,CAAC,SAAS;QAElC,MAAM,kBAAkB,GAAmC,IAAI,GAAG,EAAE,CAAC;QAErE,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,UAAU,EAAE,CAAC;YACtC,MAAM,KAAK,GAAsB,IAAI,CAAC,aAAa,CAAC,IAAI,EAAE,SAAS,CAAC,CAAC;YACrE,IAAI,KAAK,KAAK,SAAS,EAAE,CAAC;gBACxB,SAAS;YACX,CAAC;YACD,IAAI,WAAW,GAAmC,kBAAkB,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;YAChF,IAAI,CAAC,WAAW,EAAE,CAAC;gBACjB,WAAW,GAAG,IAAI,GAAG,EAAE,CAAC;gBACxB,kBAAkB,CAAC,GAAG,CAAC,KAAK,EAAE,WAAW,CAAC,CAAC;YAC7C,CAAC;YACD,WAAW,CAAC,GAAG,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;QAC9B,CAAC;QAED,OAAO,kBAAkB,CAAC;IAC5B,CAAC;IAED;;OAEG;IACI,CAAC,OAAO,CAAC,KAAc,EAAE,YAAoB,IAAI,CAAC,SAAS;QAChE,IAAI,IAAsC,CAAC;QAC3C,IAAI,KAAK,EAAE,CAAC;YACV,IAAI,GAAG,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;YAChD,IAAI,CAAC,IAAI,EAAE,CAAC;gBACV,OAAO;YACT,CAAC;QACH,CAAC;aAAM,CAAC;YACN,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC;QACpB,CAAC;QAED,MAAM,KAAK,GAAqC,CAAC,CAAC,KAAK,aAAL,KAAK,cAAL,KAAK,GAAI,EAAE,EAAE,IAAI,CAAC,CAAC,CAAC;QACtE,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,GAAG,KAAK,CAAC,GAAG,EAAG,CAAC;YACpC,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,KAAK,CAAC,CAAC;YAC7B,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,CAAC,OAAO,EAAE,KAAK,CAAC,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;oBAC7C,KAAK,CAAC,IAAI,CAAC,CAAC,MAAM,CAAC,CAAC,CAAC,GAAG,MAAM,GAAG,SAAS,GAAG,OAAO,EAAE,CAAC,CAAC,CAAC,OAAO,EAAE,KAAK,CAAC,CAAC,CAAC;gBAC5E,CAAC;YACH,CAAC;QACH,CAAC;IACH,CAAC;IAED;;OAEG;IACI,CAAC,MAAM,CAAC,QAAQ,CAAC,CACtB,KAAc,EACd,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,OAAO,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IACxC,CAAC;IAED;;OAEG;IACI,eAAe,CACpB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IAClD,CAAC;IAED;;OAEG;IACI,MAAM,CACX,cAA6C;QAE7C,MAAM,YAAY,GAAuB,IAAI,GAAG,EAAE,CAAC;QACnD,MAAM,MAAM,GAAkB,EAAE,CAAC;QAEjC,MAAM,kBAAkB,GAA6B,CAAC,KAAY,EAAE,EAAE;YACpE,IAAI,KAAK,GAAuB,YAAY,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;YACxD,IAAI,KAAK,KAAK,SAAS,EAAE,CAAC;gBACxB,KAAK,GAAG,MAAM,CAAC,MAAM,CAAC;gBACtB,YAAY,CAAC,GAAG,CAAC,KAAK,EAAE,KAAK,CAAC,CAAC;gBAC/B,MAAM,CAAC,IAAI,CAAC,cAAc,CAAC,KAAK,CAAC,CAAC,CAAC;YACrC,CAAC;YACD,OAAO,KAAK,CAAC;QACf,CAAC,CAAC;QAEF,MAAM,aAAa,GAA4D,CAC7E,IAA0B,EAC1B,EAAE;YACF,MAAM,MAAM,GAA4B,EAAE,CAAC;YAE3C,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,MAAM,CAAC,UAAU,GAAG,kBAAkB,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;YACrD,CAAC;YAED,IAAI,IAAI,CAAC,QAAQ,IAAI,IAAI,CAAC,QAAQ,CAAC,IAAI,GAAG,CAAC,EAAE,CAAC;gBAC5C,MAAM,QAAQ,GAA4C,MAAM,CAAC,MAAM,CAAC,IAAI,CAAC,CAAC;gBAC9E,KAAK,MAAM,CAAC,OAAO,EAAE,KAAK,CAAC,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;oBAC7C,QAAQ,CAAC,OAAO,CAAC,GAAG,aAAa,CAAC,KAAK,CAAC,CAAC;gBAC3C,CAAC;gBACD,MAAM,CAAC,QAAQ,GAAG,QAAQ,CAAC;YAC7B,CAAC;YAED,OAAO,MAAM,CAAC;QAChB,CAAC,CAAC;QAEF,OAAO;YACL,SAAS,EAAE,IAAI,CAAC,SAAS;YACzB,MAAM;YACN,IAAI,EAAE,aAAa,CAAC,IAAI,CAAC,KAAK,CAAC;SAChC,CAAC;IACJ,CAAC;IAED;;;;;;;;;;;;OAYG;IACI,MAAM,CAAC,QAAQ,CACpB,IAAoC,EACpC,gBAAoD;QAEpD,MAAM,kBAAkB,GAAY,IAAI,CAAC,MAAM,CAAC,GAAG,CAAC,gBAAgB,CAAC,CAAC;QAEtE,MAAM,MAAM,GAAwB,IAAI,YAAY,CAAQ,SAAS,EAAE,IAAI,CAAC,SAAS,CAAC,CAAC;QAEvF,MAAM,eAAe,GAGT,CAAC,QAAiC,EAAE,UAAgC,EAAE,EAAE;YAClF,IAAI,QAAQ,CAAC,UAAU,KAAK,SAAS,EAAE,CAAC;gBACtC,UAAU,CAAC,KAAK,GAAG,kBAAkB,CAAC,QAAQ,CAAC,UAAU,CAAC,CAAC;gBAC3D,MAAM,CAAC,KAAK,EAAE,CAAC;YACjB,CAAC;YAED,IAAI,QAAQ,CAAC,QAAQ,EAAE,CAAC;gBACtB,UAAU,CAAC,QAAQ,GAAG,IAAI,GAAG,EAAE,CAAC;gBAChC,KAAK,MAAM,CAAC,OAAO,EAAE,SAAS,CAAC,IAAI,MAAM,CAAC,OAAO,CAAC,QAAQ,CAAC,QAAQ,CAAC,EAAE,CAAC;oBACrE,MAAM,SAAS,GAAyB;wBACtC,KAAK,EAAE,SAAS;wBAChB,QAAQ,EAAE,SAAS;qBACpB,CAAC;oBACF,UAAU,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,EAAE,SAAS,CAAC,CAAC;oBAC5C,eAAe,CAAC,SAAS,EAAE,SAAS,CAAC,CAAC;gBACxC,CAAC;YACH,CAAC;QACH,CAAC,CAAC;QAEF,eAAe,CAAC,IAAI,CAAC,IAAI,EAAE,MAAM,CAAC,KAAK,CAAC,CAAC;QAEzC,OAAO,MAAM,CAAC;IAChB,CAAC;IAED;;;;;;;OAOG;IACK,uBAAuB,CAAC,QAAgC;QAC9D,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAoC,IAAI,CAAC,KAAK;YACpD,CAAC,CAAC;gBACE,KAAK,EAAE,IAAI,CAAC,KAAK;gBACjB,KAAK,EAAE,CAAC;gBACR,SAAS,EAAE,SAAS;aACrB;YACH,CAAC,CAAC,SAAS,CAAC;QACd,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,EAAE,KAAK,EAAE,IAAI,QAAQ,EAAE,CAAC;gBAC/C,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC;gBACxE,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;oBAC7B,IAAI,GAAG;wBACL,KAAK,EAAE,IAAI,CAAC,KAAK;wBACjB,KAAK;wBACL,SAAS,EAAE,IAAI;qBAChB,CAAC;gBACJ,CAAC;gBACD,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACK,iBAAiB,CACvB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,EAAE,CAAC;YACzE,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,MAAM,CAAC,CAAC;YAC1E,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,OAAO,IAAI,CAAC;IACd,CAAC;CACF;AAteD,oCAseC","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * A node in the path trie used in LookupByPath\n */\ninterface IPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  children: Map<string, IPathTrieNode<TItem>> | undefined;\n}\n\n/**\n * Readonly view of a node in the path trie used in LookupByPath\n *\n * @remarks\n * This interface is used to facilitate parallel traversals for comparing two `LookupByPath` instances.\n *\n * @beta\n */\nexport interface IReadonlyPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  readonly value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  readonly children: ReadonlyMap<string, IReadonlyPathTrieNode<TItem>> | undefined;\n}\n\n/**\n * JSON-serializable representation of a node in a {@link LookupByPath} trie.\n *\n * @beta\n */\nexport interface ISerializedPathTrieNode {\n  /**\n   * Index into the `values` array of the containing {@link ILookupByPathJson}.\n   * If `undefined`, this node has no associated value.\n   */\n  valueIndex?: number;\n\n  /**\n   * Child nodes keyed by path segment.\n   */\n  children?: Record<string, ISerializedPathTrieNode>;\n}\n\n/**\n * JSON-serializable representation of a {@link LookupByPath} instance.\n *\n * @remarks\n * The `values` array stores each unique value exactly once (by reference identity).\n * Nodes in the tree reference values by their index in this array, which ensures that\n * reference equality is preserved across serialization and deserialization.\n *\n * @beta\n */\nexport interface ILookupByPathJson<TSerialized> {\n  /**\n   * The path delimiter used by the serialized trie.\n   */\n  delimiter: string;\n\n  /**\n   * Array of serialized values. Nodes in the tree reference values by their index in this array.\n   * Using an array with index-based references preserves reference equality: if multiple nodes\n   * share the same value (by reference), they will reference the same index.\n   */\n  values: TSerialized[];\n\n  /**\n   * The serialized tree structure.\n   */\n  tree: ISerializedPathTrieNode;\n}\n\ninterface IPrefixEntry {\n  /**\n   * The prefix that was matched\n   */\n  prefix: string;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n}\n\n/**\n * Object containing both the matched item and the start index of the remainder of the query.\n *\n * @beta\n */\nexport interface IPrefixMatch<TItem extends {}> {\n  /**\n   * The item that matched the prefix\n   */\n  value: TItem;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n\n  /**\n   * The last match found (with a shorter prefix), if any\n   */\n  lastMatch?: IPrefixMatch<TItem>;\n}\n\n/**\n * The readonly component of `LookupByPath`, to simplify unit testing.\n *\n * @beta\n */\nexport interface IReadonlyLookupByPath<TItem extends {}> extends Iterable<[string, TItem]> {\n  /**\n   * Searches for the item associated with `childPath`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPath('foo/baz'); // returns 1\n   * trie.findChildPath('foo/bar/baz'); // returns 2\n   * ```\n   */\n  findChildPath(childPath: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Searches for the item for which the recorded prefix is the longest matching prefix of `query`.\n   * Obtains both the item and the length of the matched prefix, so that the remainder of the path can be\n   * extracted.\n   *\n   * @returns the found item and the length of the matched prefix, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findLongestPrefixMatch('foo/baz'); // returns { item: 1, index: 3 }\n   * trie.findLongestPrefixMatch('foo/bar/baz'); // returns { item: 2, index: 7 }\n   * ```\n   */\n  findLongestPrefixMatch(query: string, delimiter?: string): IPrefixMatch<TItem> | undefined;\n\n  /**\n   * Searches for the item associated with `childPathSegments`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPathFromSegments(['foo', 'baz']); // returns 1\n   * trie.findChildPathFromSegments(['foo','bar', 'baz']); // returns 2\n   * ```\n   */\n  findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined;\n\n  /**\n   * Determines if an entry exists exactly at the specified path.\n   *\n   * @returns `true` if an entry exists at the specified path, `false` otherwise\n   */\n  has(query: string, delimiter?: string): boolean;\n\n  /**\n   * Retrieves the entry that exists exactly at the specified path, if any.\n   *\n   * @returns The entry that exists exactly at the specified path, or `undefined` if no entry exists.\n   */\n  get(query: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Gets the number of entries in this trie.\n   *\n   * @returns The number of entries in this trie.\n   */\n  get size(): number;\n\n  /**\n   * @returns The root node of the trie, corresponding to the path ''\n   */\n  get tree(): IReadonlyPathTrieNode<TItem>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * [...trie.entries(undefined, ',')); // returns [['foo', 1], ['foo,bar', 2]]\n   * ```\n   */\n  entries(query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   */\n  [Symbol.iterator](query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Groups the provided map of info by the nearest entry in the trie that contains the path. If the path\n   * is not found in the trie, the info is ignored.\n   *\n   * @returns The grouped info, grouped by the nearest entry in the trie that contains the path\n   *\n   * @param infoByPath - The info to be grouped, keyed by path\n   */\n  groupByChild<TInfo>(infoByPath: Map<string, TInfo>, delimiter?: string): Map<TItem, Map<string, TInfo>>;\n\n  /**\n   * Retrieves the trie node at the specified prefix, if it exists.\n   *\n   * @param query - The prefix to check for\n   * @param delimiter - The path delimiter\n   * @returns The trie node at the specified prefix, or `undefined` if no node was found\n   */\n  getNodeAtPrefix(query: string, delimiter?: string): IReadonlyPathTrieNode<TItem> | undefined;\n\n  /**\n   * Serializes this `LookupByPath` instance to a JSON-compatible representation.\n   *\n   * @param serializeValue - A function that converts a value of type `TItem` to a JSON-serializable form.\n   * @returns A JSON-serializable representation of this trie.\n   *\n   * @remarks\n   * Values that are reference-equal will be serialized once and referenced by index, ensuring\n   * that reference equality is preserved when deserialized via {@link LookupByPath.fromJson}.\n   */\n  toJson<TSerialized>(serializeValue: (value: TItem) => TSerialized): ILookupByPathJson<TSerialized>;\n}\n\n/**\n * This class is used to associate path-like-strings, such as those returned by `git` commands,\n * with entities that correspond with ancestor folders, such as Rush Projects or npm packages.\n *\n * It is optimized for efficiently locating the nearest ancestor path with an associated value.\n *\n * It is implemented as a Trie (https://en.wikipedia.org/wiki/Trie) data structure, with each edge\n * being a path segment.\n *\n * @example\n * ```ts\n * const trie = new LookupByPath([['foo', 1], ['bar', 2], ['foo/bar', 3]]);\n * trie.findChildPath('foo'); // returns 1\n * trie.findChildPath('foo/baz'); // returns 1\n * trie.findChildPath('baz'); // returns undefined\n * trie.findChildPath('foo/bar/baz'); returns 3\n * trie.findChildPath('bar/foo/bar'); returns 2\n * ```\n * @beta\n */\nexport class LookupByPath<TItem extends {}> implements IReadonlyLookupByPath<TItem> {\n  /**\n   * The delimiter used to split paths\n   */\n  public readonly delimiter: string;\n\n  /**\n   * The root node of the trie, corresponding to the path ''\n   */\n  private readonly _root: IPathTrieNode<TItem>;\n\n  /**\n   * The number of entries in this trie.\n   */\n  private _size: number;\n\n  /**\n   * Constructs a new `LookupByPath`\n   *\n   * @param entries - Initial path-value pairs to populate the trie.\n   */\n  public constructor(entries?: Iterable<[string, TItem]>, delimiter?: string) {\n    this._root = {\n      value: undefined,\n      children: undefined\n    };\n\n    this.delimiter = delimiter ?? '/';\n    this._size = 0;\n\n    if (entries) {\n      for (const [path, item] of entries) {\n        this.setItem(path, item);\n      }\n    }\n  }\n\n  /**\n   * Iterates over the segments of a serialized path.\n   *\n   * @example\n   *\n   * `LookupByPath.iteratePathSegments('foo/bar/baz')` yields 'foo', 'bar', 'baz'\n   *\n   * `LookupByPath.iteratePathSegments('foo\\\\bar\\\\baz', '\\\\')` yields 'foo', 'bar', 'baz'\n   */\n  public static *iteratePathSegments(serializedPath: string, delimiter: string = '/'): Iterable<string> {\n    for (const prefixMatch of this._iteratePrefixes(serializedPath, delimiter)) {\n      yield prefixMatch.prefix;\n    }\n  }\n\n  private static *_iteratePrefixes(input: string, delimiter: string = '/'): Iterable<IPrefixEntry> {\n    if (!input) {\n      return;\n    }\n\n    let previousIndex: number = 0;\n    let nextIndex: number = input.indexOf(delimiter);\n\n    // Leading segments\n    while (nextIndex >= 0) {\n      yield {\n        prefix: input.slice(previousIndex, nextIndex),\n        index: nextIndex\n      };\n      previousIndex = nextIndex + 1;\n      nextIndex = input.indexOf(delimiter, previousIndex);\n    }\n\n    // Last segment\n    if (previousIndex < input.length) {\n      yield {\n        prefix: input.slice(previousIndex, input.length),\n        index: input.length\n      };\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.size}\n   */\n  public get size(): number {\n    return this._size;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.tree}\n   */\n  public get tree(): IReadonlyPathTrieNode<TItem> {\n    return this._root;\n  }\n\n  /**\n   * Deletes all entries from this `LookupByPath` instance.\n   *\n   * @returns this, for chained calls\n   */\n  public clear(): this {\n    this._root.value = undefined;\n    this._root.children = undefined;\n    this._size = 0;\n    return this;\n  }\n\n  /**\n   * Associates the value with the specified serialized path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItem(serializedPath: string, value: TItem, delimiter: string = this.delimiter): this {\n    return this.setItemFromSegments(LookupByPath.iteratePathSegments(serializedPath, delimiter), value);\n  }\n\n  /**\n   * Deletes an item if it exists.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if the item was found and deleted, `false` otherwise\n   * @remarks\n   * If the node has children with values, they will be retained.\n   */\n  public deleteItem(query: string, delimeter: string = this.delimiter): boolean {\n    const node: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (node?.value !== undefined) {\n      node.value = undefined;\n      this._size--;\n      return true;\n    }\n\n    return false;\n  }\n\n  /**\n   * Deletes an item and all its children.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if any nodes were deleted, `false` otherwise\n   */\n  public deleteSubtree(query: string, delimeter: string = this.delimiter): boolean {\n    const queryNode: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (!queryNode) {\n      return false;\n    }\n\n    const queue: IPathTrieNode<TItem>[] = [queryNode];\n    let removed: number = 0;\n    while (queue.length > 0) {\n      const node: IPathTrieNode<TItem> = queue.pop()!;\n      if (node.value !== undefined) {\n        node.value = undefined;\n        removed++;\n      }\n      if (node.children) {\n        for (const child of node.children.values()) {\n          queue.push(child);\n        }\n        node.children.clear();\n      }\n    }\n\n    this._size -= removed;\n    return removed > 0;\n  }\n\n  /**\n   * Associates the value with the specified path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItemFromSegments(pathSegments: Iterable<string>, value: TItem): this {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const segment of pathSegments) {\n      if (!node.children) {\n        node.children = new Map();\n      }\n      let child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n      if (!child) {\n        node.children.set(\n          segment,\n          (child = {\n            value: undefined,\n            children: undefined\n          })\n        );\n      }\n      node = child;\n    }\n    if (node.value === undefined) {\n      this._size++;\n    }\n    node.value = value;\n\n    return this;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPath(childPath: string, delimiter: string = this.delimiter): TItem | undefined {\n    return this.findChildPathFromSegments(LookupByPath.iteratePathSegments(childPath, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findLongestPrefixMatch(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPrefixMatch<TItem> | undefined {\n    return this._findLongestPrefixMatch(LookupByPath._iteratePrefixes(query, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: TItem | undefined = node.value;\n    // Trivial cases\n    if (node.children) {\n      for (const segment of childPathSegments) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n        if (!child) {\n          break;\n        }\n        node = child;\n        best = node.value ?? best;\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public has(key: string, delimiter: string = this.delimiter): boolean {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public get(key: string, delimiter: string = this.delimiter): TItem | undefined {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length ? match.value : undefined;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public groupByChild<TInfo>(\n    infoByPath: Map<string, TInfo>,\n    delimiter: string = this.delimiter\n  ): Map<TItem, Map<string, TInfo>> {\n    const groupedInfoByChild: Map<TItem, Map<string, TInfo>> = new Map();\n\n    for (const [path, info] of infoByPath) {\n      const child: TItem | undefined = this.findChildPath(path, delimiter);\n      if (child === undefined) {\n        continue;\n      }\n      let groupedInfo: Map<string, TInfo> | undefined = groupedInfoByChild.get(child);\n      if (!groupedInfo) {\n        groupedInfo = new Map();\n        groupedInfoByChild.set(child, groupedInfo);\n      }\n      groupedInfo.set(path, info);\n    }\n\n    return groupedInfoByChild;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public *entries(query?: string, delimiter: string = this.delimiter): IterableIterator<[string, TItem]> {\n    let root: IPathTrieNode<TItem> | undefined;\n    if (query) {\n      root = this._findNodeAtPrefix(query, delimiter);\n      if (!root) {\n        return;\n      }\n    } else {\n      root = this._root;\n    }\n\n    const stack: [string, IPathTrieNode<TItem>][] = [[query ?? '', root]];\n    while (stack.length > 0) {\n      const [prefix, node] = stack.pop()!;\n      if (node.value !== undefined) {\n        yield [prefix, node.value];\n      }\n      if (node.children) {\n        for (const [segment, child] of node.children) {\n          stack.push([prefix ? `${prefix}${delimiter}${segment}` : segment, child]);\n        }\n      }\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public [Symbol.iterator](\n    query?: string,\n    delimiter: string = this.delimiter\n  ): IterableIterator<[string, TItem]> {\n    return this.entries(query, delimiter);\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public getNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IReadonlyPathTrieNode<TItem> | undefined {\n    return this._findNodeAtPrefix(query, delimiter);\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.toJson}\n   */\n  public toJson<TSerialized>(\n    serializeValue: (value: TItem) => TSerialized\n  ): ILookupByPathJson<TSerialized> {\n    const valueToIndex: Map<TItem, number> = new Map();\n    const values: TSerialized[] = [];\n\n    const getOrAddValueIndex: (value: TItem) => number = (value: TItem) => {\n      let index: number | undefined = valueToIndex.get(value);\n      if (index === undefined) {\n        index = values.length;\n        valueToIndex.set(value, index);\n        values.push(serializeValue(value));\n      }\n      return index;\n    };\n\n    const serializeNode: (node: IPathTrieNode<TItem>) => ISerializedPathTrieNode = (\n      node: IPathTrieNode<TItem>\n    ) => {\n      const result: ISerializedPathTrieNode = {};\n\n      if (node.value !== undefined) {\n        result.valueIndex = getOrAddValueIndex(node.value);\n      }\n\n      if (node.children && node.children.size > 0) {\n        const children: Record<string, ISerializedPathTrieNode> = Object.create(null);\n        for (const [segment, child] of node.children) {\n          children[segment] = serializeNode(child);\n        }\n        result.children = children;\n      }\n\n      return result;\n    };\n\n    return {\n      delimiter: this.delimiter,\n      values,\n      tree: serializeNode(this._root)\n    };\n  }\n\n  /**\n   * Deserializes a `LookupByPath` instance from a JSON representation previously\n   * created by {@link LookupByPath.toJson}.\n   *\n   * @param json - The JSON representation to deserialize.\n   * @param deserializeValue - A function that converts a serialized value back to its original type.\n   * @returns A new `LookupByPath` instance.\n   *\n   * @remarks\n   * Reference equality is preserved: if multiple nodes in the serialized trie pointed at the same\n   * value (i.e., the same index in the `values` array), the deserialized nodes will share the same\n   * object reference.\n   */\n  public static fromJson<TItem extends {}, TSerialized>(\n    json: ILookupByPathJson<TSerialized>,\n    deserializeValue: (serialized: TSerialized) => TItem\n  ): LookupByPath<TItem> {\n    const deserializedValues: TItem[] = json.values.map(deserializeValue);\n\n    const result: LookupByPath<TItem> = new LookupByPath<TItem>(undefined, json.delimiter);\n\n    const deserializeNode: (\n      jsonNode: ISerializedPathTrieNode,\n      targetNode: IPathTrieNode<TItem>\n    ) => void = (jsonNode: ISerializedPathTrieNode, targetNode: IPathTrieNode<TItem>) => {\n      if (jsonNode.valueIndex !== undefined) {\n        targetNode.value = deserializedValues[jsonNode.valueIndex];\n        result._size++;\n      }\n\n      if (jsonNode.children) {\n        targetNode.children = new Map();\n        for (const [segment, childJson] of Object.entries(jsonNode.children)) {\n          const childNode: IPathTrieNode<TItem> = {\n            value: undefined,\n            children: undefined\n          };\n          targetNode.children.set(segment, childNode);\n          deserializeNode(childJson, childNode);\n        }\n      }\n    };\n\n    deserializeNode(json.tree, result._root);\n\n    return result;\n  }\n\n  /**\n   * Iterates through progressively longer prefixes of a given string and returns as soon\n   * as the number of candidate items that match the prefix are 1 or 0.\n   *\n   * If a match is present, returns the matched itme and the length of the matched prefix.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   */\n  private _findLongestPrefixMatch(prefixes: Iterable<IPrefixEntry>): IPrefixMatch<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: IPrefixMatch<TItem> | undefined = node.value\n      ? {\n          value: node.value,\n          index: 0,\n          lastMatch: undefined\n        }\n      : undefined;\n    // Trivial cases\n    if (node.children) {\n      for (const { prefix: hash, index } of prefixes) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(hash);\n        if (!child) {\n          break;\n        }\n        node = child;\n        if (node.value !== undefined) {\n          best = {\n            value: node.value,\n            index,\n            lastMatch: best\n          };\n        }\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * Finds the node at the specified path, or `undefined` if no node was found.\n   *\n   * @param query - The path to the node to search for\n   * @returns The trie node at the specified path, or `undefined` if no node was found\n   */\n  private _findNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPathTrieNode<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const { prefix } of LookupByPath._iteratePrefixes(query, delimiter)) {\n      if (!node.children) {\n        return undefined;\n      }\n      const child: IPathTrieNode<TItem> | undefined = node.children.get(prefix);\n      if (!child) {\n        return undefined;\n      }\n      node = child;\n    }\n    return node;\n  }\n}\n"]}

lib-dts/index.d.ts

@@ -6,3 +6,3 @@ /**
  */
-export type { IPrefixMatch, IReadonlyLookupByPath, IReadonlyPathTrieNode } from './LookupByPath';
+export type { ILookupByPathJson, IPrefixMatch, IReadonlyLookupByPath, IReadonlyPathTrieNode, ISerializedPathTrieNode } from './LookupByPath';
 export { LookupByPath } from './LookupByPath';
@@ -9,0 +9,0 @@ export type { IGetFirstDifferenceInCommonNodesOptions } from './getFirstDifferenceInCommonNodes';

lib-dts/index.d.ts.map

@@ -1,1 +0,1 @@
-{"version":3,"file":"index.d.ts","sourceRoot":"","sources":["../src/index.ts"],"names":[],"mappings":"AAGA;;;;GAIG;AAEH,YAAY,EAAE,YAAY,EAAE,qBAAqB,EAAE,qBAAqB,EAAE,MAAM,gBAAgB,CAAC;AACjG,OAAO,EAAE,YAAY,EAAE,MAAM,gBAAgB,CAAC;AAC9C,YAAY,EAAE,uCAAuC,EAAE,MAAM,mCAAmC,CAAC;AACjG,OAAO,EAAE,+BAA+B,EAAE,MAAM,mCAAmC,CAAC"}
+{"version":3,"file":"index.d.ts","sourceRoot":"","sources":["../src/index.ts"],"names":[],"mappings":"AAGA;;;;GAIG;AAEH,YAAY,EACV,iBAAiB,EACjB,YAAY,EACZ,qBAAqB,EACrB,qBAAqB,EACrB,uBAAuB,EACxB,MAAM,gBAAgB,CAAC;AACxB,OAAO,EAAE,YAAY,EAAE,MAAM,gBAAgB,CAAC;AAC9C,YAAY,EAAE,uCAAuC,EAAE,MAAM,mCAAmC,CAAC;AACjG,OAAO,EAAE,+BAA+B,EAAE,MAAM,mCAAmC,CAAC"}

lib-dts/LookupByPath.d.ts

@@ -20,2 +20,44 @@ /**
 /**
+ * JSON-serializable representation of a node in a {@link LookupByPath} trie.
+ *
+ * @beta
+ */
+export interface ISerializedPathTrieNode {
+    /**
+     * Index into the `values` array of the containing {@link ILookupByPathJson}.
+     * If `undefined`, this node has no associated value.
+     */
+    valueIndex?: number;
+    /**
+     * Child nodes keyed by path segment.
+     */
+    children?: Record<string, ISerializedPathTrieNode>;
+}
+/**
+ * JSON-serializable representation of a {@link LookupByPath} instance.
+ *
+ * @remarks
+ * The `values` array stores each unique value exactly once (by reference identity).
+ * Nodes in the tree reference values by their index in this array, which ensures that
+ * reference equality is preserved across serialization and deserialization.
+ *
+ * @beta
+ */
+export interface ILookupByPathJson<TSerialized> {
+    /**
+     * The path delimiter used by the serialized trie.
+     */
+    delimiter: string;
+    /**
+     * Array of serialized values. Nodes in the tree reference values by their index in this array.
+     * Using an array with index-based references preserves reference equality: if multiple nodes
+     * share the same value (by reference), they will reference the same index.
+     */
+    values: TSerialized[];
+    /**
+     * The serialized tree structure.
+     */
+    tree: ISerializedPathTrieNode;
+}
+/**
  * Object containing both the matched item and the start index of the remainder of the query.
@@ -154,2 +196,13 @@ *
     getNodeAtPrefix(query: string, delimiter?: string): IReadonlyPathTrieNode<TItem> | undefined;
+    /**
+     * Serializes this `LookupByPath` instance to a JSON-compatible representation.
+     *
+     * @param serializeValue - A function that converts a value of type `TItem` to a JSON-serializable form.
+     * @returns A JSON-serializable representation of this trie.
+     *
+     * @remarks
+     * Values that are reference-equal will be serialized once and referenced by index, ensuring
+     * that reference equality is preserved when deserialized via {@link LookupByPath.fromJson}.
+     */
+    toJson<TSerialized>(serializeValue: (value: TItem) => TSerialized): ILookupByPathJson<TSerialized>;
 }
@@ -287,2 +340,20 @@ /**
     /**
+     * {@inheritdoc IReadonlyLookupByPath.toJson}
+     */
+    toJson<TSerialized>(serializeValue: (value: TItem) => TSerialized): ILookupByPathJson<TSerialized>;
+    /**
+     * Deserializes a `LookupByPath` instance from a JSON representation previously
+     * created by {@link LookupByPath.toJson}.
+     *
+     * @param json - The JSON representation to deserialize.
+     * @param deserializeValue - A function that converts a serialized value back to its original type.
+     * @returns A new `LookupByPath` instance.
+     *
+     * @remarks
+     * Reference equality is preserved: if multiple nodes in the serialized trie pointed at the same
+     * value (i.e., the same index in the `values` array), the deserialized nodes will share the same
+     * object reference.
+     */
+    static fromJson<TItem extends {}, TSerialized>(json: ILookupByPathJson<TSerialized>, deserializeValue: (serialized: TSerialized) => TItem): LookupByPath<TItem>;
+    /**
      * Iterates through progressively longer prefixes of a given string and returns as soon
@@ -289,0 +360,0 @@ * as the number of candidate items that match the prefix are 1 or 0.

lib-dts/LookupByPath.d.ts.map

@@ -1,1 +0,1 @@
-{"version":3,"file":"LookupByPath.d.ts","sourceRoot":"","sources":["../src/LookupByPath.ts"],"names":[],"mappings":"AAkBA;;;;;;;GAOG;AACH,MAAM,WAAW,qBAAqB,CAAC,KAAK,SAAS,EAAE;IACrD;;OAEG;IACH,QAAQ,CAAC,KAAK,EAAE,KAAK,GAAG,SAAS,CAAC;IAElC;;OAEG;IACH,QAAQ,CAAC,QAAQ,EAAE,WAAW,CAAC,MAAM,EAAE,qBAAqB,CAAC,KAAK,CAAC,CAAC,GAAG,SAAS,CAAC;CAClF;AAcD;;;;GAIG;AACH,MAAM,WAAW,YAAY,CAAC,KAAK,SAAS,EAAE;IAC5C;;OAEG;IACH,KAAK,EAAE,KAAK,CAAC;IAEb;;OAEG;IACH,KAAK,EAAE,MAAM,CAAC;IAEd;;OAEG;IACH,SAAS,CAAC,EAAE,YAAY,CAAC,KAAK,CAAC,CAAC;CACjC;AAED;;;;GAIG;AACH,MAAM,WAAW,qBAAqB,CAAC,KAAK,SAAS,EAAE,CAAE,SAAQ,QAAQ,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IACxF;;;;;;;;;;;;OAYG;IACH,aAAa,CAAC,SAAS,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,KAAK,GAAG,SAAS,CAAC;IAExE;;;;;;;;;;;;;OAaG;IACH,sBAAsB,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,YAAY,CAAC,KAAK,CAAC,GAAG,SAAS,CAAC;IAE3F;;;;;;;;;;;;OAYG;IACH,yBAAyB,CAAC,iBAAiB,EAAE,QAAQ,CAAC,MAAM,CAAC,GAAG,KAAK,GAAG,SAAS,CAAC;IAElF;;;;OAIG;IACH,GAAG,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,OAAO,CAAC;IAEhD;;;;OAIG;IACH,GAAG,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,KAAK,GAAG,SAAS,CAAC;IAE1D;;;;OAIG;IACH,IAAI,IAAI,IAAI,MAAM,CAAC;IAEnB;;OAEG;IACH,IAAI,IAAI,IAAI,qBAAqB,CAAC,KAAK,CAAC,CAAC;IAEzC;;;;;;;;;;;;;;OAcG;IACH,OAAO,CAAC,KAAK,CAAC,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,CAAC;IAE/E;;;;;;;;;OASG;IACH,CAAC,MAAM,CAAC,QAAQ,CAAC,CAAC,KAAK,CAAC,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,CAAC;IAEzF;;;;;;;OAOG;IACH,YAAY,CAAC,KAAK,EAAE,UAAU,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,GAAG,CAAC,KAAK,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,CAAC;IAExG;;;;;;OAMG;IACH,eAAe,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,qBAAqB,CAAC,KAAK,CAAC,GAAG,SAAS,CAAC;CAC9F;AAED;;;;;;;;;;;;;;;;;;;GAmBG;AACH,qBAAa,YAAY,CAAC,KAAK,SAAS,EAAE,CAAE,YAAW,qBAAqB,CAAC,KAAK,CAAC;IACjF;;OAEG;IACH,SAAgB,SAAS,EAAE,MAAM,CAAC;IAElC;;OAEG;IACH,OAAO,CAAC,QAAQ,CAAC,KAAK,CAAuB;IAE7C;;OAEG;IACH,OAAO,CAAC,KAAK,CAAS;IAEtB;;;;OAIG;gBACgB,OAAO,CAAC,EAAE,QAAQ,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,EAAE,SAAS,CAAC,EAAE,MAAM;IAgB1E;;;;;;;;OAQG;WACY,mBAAmB,CAAC,cAAc,EAAE,MAAM,EAAE,SAAS,GAAE,MAAY,GAAG,QAAQ,CAAC,MAAM,CAAC;IAMrG,OAAO,CAAC,MAAM,CAAE,gBAAgB;IA2BhC;;OAEG;IACH,IAAW,IAAI,IAAI,MAAM,CAExB;IAED;;OAEG;IACH,IAAW,IAAI,IAAI,qBAAqB,CAAC,KAAK,CAAC,CAE9C;IAED;;;;OAIG;IACI,KAAK,IAAI,IAAI;IAOpB;;;;;OAKG;IACI,OAAO,CAAC,cAAc,EAAE,MAAM,EAAE,KAAK,EAAE,KAAK,EAAE,SAAS,GAAE,MAAuB,GAAG,IAAI;IAI9F;;;;;;;OAOG;IACI,UAAU,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,OAAO;IAW7E;;;;;OAKG;IACI,aAAa,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,OAAO;IA0BhF;;;;;OAKG;IACI,mBAAmB,CAAC,YAAY,EAAE,QAAQ,CAAC,MAAM,CAAC,EAAE,KAAK,EAAE,KAAK,GAAG,IAAI;IA0B9E;;OAEG;IACI,aAAa,CAAC,SAAS,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,KAAK,GAAG,SAAS;IAI9F;;OAEG;IACI,sBAAsB,CAC3B,KAAK,EAAE,MAAM,EACb,SAAS,GAAE,MAAuB,GACjC,YAAY,CAAC,KAAK,CAAC,GAAG,SAAS;IAIlC;;OAEG;IACI,yBAAyB,CAAC,iBAAiB,EAAE,QAAQ,CAAC,MAAM,CAAC,GAAG,KAAK,GAAG,SAAS;IAqBxF;;OAEG;IACI,GAAG,CAAC,GAAG,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,OAAO;IAKpE;;OAEG;IACI,GAAG,CAAC,GAAG,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,KAAK,GAAG,SAAS;IAK9E;;OAEG;IACI,YAAY,CAAC,KAAK,EACvB,UAAU,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,EAC9B,SAAS,GAAE,MAAuB,GACjC,GAAG,CAAC,KAAK,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IAmBjC;;OAEG;IACK,OAAO,CAAC,KAAK,CAAC,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IAyBtG;;OAEG;IACI,CAAC,MAAM,CAAC,QAAQ,CAAC,CACtB,KAAK,CAAC,EAAE,MAAM,EACd,SAAS,GAAE,MAAuB,GACjC,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IAIpC;;OAEG;IACI,eAAe,CACpB,KAAK,EAAE,MAAM,EACb,SAAS,GAAE,MAAuB,GACjC,qBAAqB,CAAC,KAAK,CAAC,GAAG,SAAS;IAI3C;;;;;;;OAOG;IACH,OAAO,CAAC,uBAAuB;IAiC/B;;;;;OAKG;IACH,OAAO,CAAC,iBAAiB;CAiB1B"}
+{"version":3,"file":"LookupByPath.d.ts","sourceRoot":"","sources":["../src/LookupByPath.ts"],"names":[],"mappings":"AAkBA;;;;;;;GAOG;AACH,MAAM,WAAW,qBAAqB,CAAC,KAAK,SAAS,EAAE;IACrD;;OAEG;IACH,QAAQ,CAAC,KAAK,EAAE,KAAK,GAAG,SAAS,CAAC;IAElC;;OAEG;IACH,QAAQ,CAAC,QAAQ,EAAE,WAAW,CAAC,MAAM,EAAE,qBAAqB,CAAC,KAAK,CAAC,CAAC,GAAG,SAAS,CAAC;CAClF;AAED;;;;GAIG;AACH,MAAM,WAAW,uBAAuB;IACtC;;;OAGG;IACH,UAAU,CAAC,EAAE,MAAM,CAAC;IAEpB;;OAEG;IACH,QAAQ,CAAC,EAAE,MAAM,CAAC,MAAM,EAAE,uBAAuB,CAAC,CAAC;CACpD;AAED;;;;;;;;;GASG;AACH,MAAM,WAAW,iBAAiB,CAAC,WAAW;IAC5C;;OAEG;IACH,SAAS,EAAE,MAAM,CAAC;IAElB;;;;OAIG;IACH,MAAM,EAAE,WAAW,EAAE,CAAC;IAEtB;;OAEG;IACH,IAAI,EAAE,uBAAuB,CAAC;CAC/B;AAcD;;;;GAIG;AACH,MAAM,WAAW,YAAY,CAAC,KAAK,SAAS,EAAE;IAC5C;;OAEG;IACH,KAAK,EAAE,KAAK,CAAC;IAEb;;OAEG;IACH,KAAK,EAAE,MAAM,CAAC;IAEd;;OAEG;IACH,SAAS,CAAC,EAAE,YAAY,CAAC,KAAK,CAAC,CAAC;CACjC;AAED;;;;GAIG;AACH,MAAM,WAAW,qBAAqB,CAAC,KAAK,SAAS,EAAE,CAAE,SAAQ,QAAQ,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IACxF;;;;;;;;;;;;OAYG;IACH,aAAa,CAAC,SAAS,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,KAAK,GAAG,SAAS,CAAC;IAExE;;;;;;;;;;;;;OAaG;IACH,sBAAsB,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,YAAY,CAAC,KAAK,CAAC,GAAG,SAAS,CAAC;IAE3F;;;;;;;;;;;;OAYG;IACH,yBAAyB,CAAC,iBAAiB,EAAE,QAAQ,CAAC,MAAM,CAAC,GAAG,KAAK,GAAG,SAAS,CAAC;IAElF;;;;OAIG;IACH,GAAG,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,OAAO,CAAC;IAEhD;;;;OAIG;IACH,GAAG,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,KAAK,GAAG,SAAS,CAAC;IAE1D;;;;OAIG;IACH,IAAI,IAAI,IAAI,MAAM,CAAC;IAEnB;;OAEG;IACH,IAAI,IAAI,IAAI,qBAAqB,CAAC,KAAK,CAAC,CAAC;IAEzC;;;;;;;;;;;;;;OAcG;IACH,OAAO,CAAC,KAAK,CAAC,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,CAAC;IAE/E;;;;;;;;;OASG;IACH,CAAC,MAAM,CAAC,QAAQ,CAAC,CAAC,KAAK,CAAC,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,CAAC;IAEzF;;;;;;;OAOG;IACH,YAAY,CAAC,KAAK,EAAE,UAAU,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,GAAG,CAAC,KAAK,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,CAAC;IAExG;;;;;;OAMG;IACH,eAAe,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,CAAC,EAAE,MAAM,GAAG,qBAAqB,CAAC,KAAK,CAAC,GAAG,SAAS,CAAC;IAE7F;;;;;;;;;OASG;IACH,MAAM,CAAC,WAAW,EAAE,cAAc,EAAE,CAAC,KAAK,EAAE,KAAK,KAAK,WAAW,GAAG,iBAAiB,CAAC,WAAW,CAAC,CAAC;CACpG;AAED;;;;;;;;;;;;;;;;;;;GAmBG;AACH,qBAAa,YAAY,CAAC,KAAK,SAAS,EAAE,CAAE,YAAW,qBAAqB,CAAC,KAAK,CAAC;IACjF;;OAEG;IACH,SAAgB,SAAS,EAAE,MAAM,CAAC;IAElC;;OAEG;IACH,OAAO,CAAC,QAAQ,CAAC,KAAK,CAAuB;IAE7C;;OAEG;IACH,OAAO,CAAC,KAAK,CAAS;IAEtB;;;;OAIG;gBACgB,OAAO,CAAC,EAAE,QAAQ,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC,EAAE,SAAS,CAAC,EAAE,MAAM;IAgB1E;;;;;;;;OAQG;WACY,mBAAmB,CAAC,cAAc,EAAE,MAAM,EAAE,SAAS,GAAE,MAAY,GAAG,QAAQ,CAAC,MAAM,CAAC;IAMrG,OAAO,CAAC,MAAM,CAAE,gBAAgB;IA2BhC;;OAEG;IACH,IAAW,IAAI,IAAI,MAAM,CAExB;IAED;;OAEG;IACH,IAAW,IAAI,IAAI,qBAAqB,CAAC,KAAK,CAAC,CAE9C;IAED;;;;OAIG;IACI,KAAK,IAAI,IAAI;IAOpB;;;;;OAKG;IACI,OAAO,CAAC,cAAc,EAAE,MAAM,EAAE,KAAK,EAAE,KAAK,EAAE,SAAS,GAAE,MAAuB,GAAG,IAAI;IAI9F;;;;;;;OAOG;IACI,UAAU,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,OAAO;IAW7E;;;;;OAKG;IACI,aAAa,CAAC,KAAK,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,OAAO;IA0BhF;;;;;OAKG;IACI,mBAAmB,CAAC,YAAY,EAAE,QAAQ,CAAC,MAAM,CAAC,EAAE,KAAK,EAAE,KAAK,GAAG,IAAI;IA0B9E;;OAEG;IACI,aAAa,CAAC,SAAS,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,KAAK,GAAG,SAAS;IAI9F;;OAEG;IACI,sBAAsB,CAC3B,KAAK,EAAE,MAAM,EACb,SAAS,GAAE,MAAuB,GACjC,YAAY,CAAC,KAAK,CAAC,GAAG,SAAS;IAIlC;;OAEG;IACI,yBAAyB,CAAC,iBAAiB,EAAE,QAAQ,CAAC,MAAM,CAAC,GAAG,KAAK,GAAG,SAAS;IAqBxF;;OAEG;IACI,GAAG,CAAC,GAAG,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,OAAO;IAKpE;;OAEG;IACI,GAAG,CAAC,GAAG,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,KAAK,GAAG,SAAS;IAK9E;;OAEG;IACI,YAAY,CAAC,KAAK,EACvB,UAAU,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,EAC9B,SAAS,GAAE,MAAuB,GACjC,GAAG,CAAC,KAAK,EAAE,GAAG,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IAmBjC;;OAEG;IACK,OAAO,CAAC,KAAK,CAAC,EAAE,MAAM,EAAE,SAAS,GAAE,MAAuB,GAAG,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IAyBtG;;OAEG;IACI,CAAC,MAAM,CAAC,QAAQ,CAAC,CACtB,KAAK,CAAC,EAAE,MAAM,EACd,SAAS,GAAE,MAAuB,GACjC,gBAAgB,CAAC,CAAC,MAAM,EAAE,KAAK,CAAC,CAAC;IAIpC;;OAEG;IACI,eAAe,CACpB,KAAK,EAAE,MAAM,EACb,SAAS,GAAE,MAAuB,GACjC,qBAAqB,CAAC,KAAK,CAAC,GAAG,SAAS;IAI3C;;OAEG;IACI,MAAM,CAAC,WAAW,EACvB,cAAc,EAAE,CAAC,KAAK,EAAE,KAAK,KAAK,WAAW,GAC5C,iBAAiB,CAAC,WAAW,CAAC;IAyCjC;;;;;;;;;;;;OAYG;WACW,QAAQ,CAAC,KAAK,SAAS,EAAE,EAAE,WAAW,EAClD,IAAI,EAAE,iBAAiB,CAAC,WAAW,CAAC,EACpC,gBAAgB,EAAE,CAAC,UAAU,EAAE,WAAW,KAAK,KAAK,GACnD,YAAY,CAAC,KAAK,CAAC;IAgCtB;;;;;;;OAOG;IACH,OAAO,CAAC,uBAAuB;IAiC/B;;;;;OAKG;IACH,OAAO,CAAC,iBAAiB;CAiB1B"}

lib-esm/index.js.map

@@ -1,1 +0,1 @@
-{"version":3,"file":"index.js","sourceRoot":"","sources":["../src/index.ts"],"names":[],"mappings":"AAAA,4FAA4F;AAC5F,2DAA2D;AAS3D,OAAO,EAAE,YAAY,EAAE,MAAM,gBAAgB,CAAC;AAE9C,OAAO,EAAE,+BAA+B,EAAE,MAAM,mCAAmC,CAAC","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * Strongly typed trie data structure for path and URL-like strings.\n *\n * @packageDocumentation\n */\n\nexport type { IPrefixMatch, IReadonlyLookupByPath, IReadonlyPathTrieNode } from './LookupByPath';\nexport { LookupByPath } from './LookupByPath';\nexport type { IGetFirstDifferenceInCommonNodesOptions } from './getFirstDifferenceInCommonNodes';\nexport { getFirstDifferenceInCommonNodes } from './getFirstDifferenceInCommonNodes';\n"]}
+{"version":3,"file":"index.js","sourceRoot":"","sources":["../src/index.ts"],"names":[],"mappings":"AAAA,4FAA4F;AAC5F,2DAA2D;AAe3D,OAAO,EAAE,YAAY,EAAE,MAAM,gBAAgB,CAAC;AAE9C,OAAO,EAAE,+BAA+B,EAAE,MAAM,mCAAmC,CAAC","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * Strongly typed trie data structure for path and URL-like strings.\n *\n * @packageDocumentation\n */\n\nexport type {\n  ILookupByPathJson,\n  IPrefixMatch,\n  IReadonlyLookupByPath,\n  IReadonlyPathTrieNode,\n  ISerializedPathTrieNode\n} from './LookupByPath';\nexport { LookupByPath } from './LookupByPath';\nexport type { IGetFirstDifferenceInCommonNodesOptions } from './getFirstDifferenceInCommonNodes';\nexport { getFirstDifferenceInCommonNodes } from './getFirstDifferenceInCommonNodes';\n"]}

lib-esm/LookupByPath.js

@@ -292,2 +292,73 @@ // Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.
     /**
+     * {@inheritdoc IReadonlyLookupByPath.toJson}
+     */
+    toJson(serializeValue) {
+        const valueToIndex = new Map();
+        const values = [];
+        const getOrAddValueIndex = (value) => {
+            let index = valueToIndex.get(value);
+            if (index === undefined) {
+                index = values.length;
+                valueToIndex.set(value, index);
+                values.push(serializeValue(value));
+            }
+            return index;
+        };
+        const serializeNode = (node) => {
+            const result = {};
+            if (node.value !== undefined) {
+                result.valueIndex = getOrAddValueIndex(node.value);
+            }
+            if (node.children && node.children.size > 0) {
+                const children = Object.create(null);
+                for (const [segment, child] of node.children) {
+                    children[segment] = serializeNode(child);
+                }
+                result.children = children;
+            }
+            return result;
+        };
+        return {
+            delimiter: this.delimiter,
+            values,
+            tree: serializeNode(this._root)
+        };
+    }
+    /**
+     * Deserializes a `LookupByPath` instance from a JSON representation previously
+     * created by {@link LookupByPath.toJson}.
+     *
+     * @param json - The JSON representation to deserialize.
+     * @param deserializeValue - A function that converts a serialized value back to its original type.
+     * @returns A new `LookupByPath` instance.
+     *
+     * @remarks
+     * Reference equality is preserved: if multiple nodes in the serialized trie pointed at the same
+     * value (i.e., the same index in the `values` array), the deserialized nodes will share the same
+     * object reference.
+     */
+    static fromJson(json, deserializeValue) {
+        const deserializedValues = json.values.map(deserializeValue);
+        const result = new LookupByPath(undefined, json.delimiter);
+        const deserializeNode = (jsonNode, targetNode) => {
+            if (jsonNode.valueIndex !== undefined) {
+                targetNode.value = deserializedValues[jsonNode.valueIndex];
+                result._size++;
+            }
+            if (jsonNode.children) {
+                targetNode.children = new Map();
+                for (const [segment, childJson] of Object.entries(jsonNode.children)) {
+                    const childNode = {
+                        value: undefined,
+                        children: undefined
+                    };
+                    targetNode.children.set(segment, childNode);
+                    deserializeNode(childJson, childNode);
+                }
+            }
+        };
+        deserializeNode(json.tree, result._root);
+        return result;
+    }
+    /**
      * Iterates through progressively longer prefixes of a given string and returns as soon
@@ -294,0 +365,0 @@ * as the number of candidate items that match the prefix are 1 or 0.

lib-esm/LookupByPath.js.map

@@ -1,1 +0,1 @@
-{"version":3,"file":"LookupByPath.js","sourceRoot":"","sources":["../src/LookupByPath.ts"],"names":[],"mappings":"AAAA,4FAA4F;AAC5F,2DAA2D;AAsM3D;;;;;;;;;;;;;;;;;;;GAmBG;AACH,MAAM,OAAO,YAAY;IAgBvB;;;;OAIG;IACH,YAAmB,OAAmC,EAAE,SAAkB;QACxE,IAAI,CAAC,KAAK,GAAG;YACX,KAAK,EAAE,SAAS;YAChB,QAAQ,EAAE,SAAS;SACpB,CAAC;QAEF,IAAI,CAAC,SAAS,GAAG,SAAS,aAAT,SAAS,cAAT,SAAS,GAAI,GAAG,CAAC;QAClC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QAEf,IAAI,OAAO,EAAE,CAAC;YACZ,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,OAAO,EAAE,CAAC;gBACnC,IAAI,CAAC,OAAO,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;YAC3B,CAAC;QACH,CAAC;IACH,CAAC;IAED;;;;;;;;OAQG;IACI,MAAM,CAAC,CAAC,mBAAmB,CAAC,cAAsB,EAAE,YAAoB,GAAG;QAChF,KAAK,MAAM,WAAW,IAAI,IAAI,CAAC,gBAAgB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,CAAC;YAC3E,MAAM,WAAW,CAAC,MAAM,CAAC;QAC3B,CAAC;IACH,CAAC;IAEO,MAAM,CAAC,CAAC,gBAAgB,CAAC,KAAa,EAAE,YAAoB,GAAG;QACrE,IAAI,CAAC,KAAK,EAAE,CAAC;YACX,OAAO;QACT,CAAC;QAED,IAAI,aAAa,GAAW,CAAC,CAAC;QAC9B,IAAI,SAAS,GAAW,KAAK,CAAC,OAAO,CAAC,SAAS,CAAC,CAAC;QAEjD,mBAAmB;QACnB,OAAO,SAAS,IAAI,CAAC,EAAE,CAAC;YACtB,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,SAAS,CAAC;gBAC7C,KAAK,EAAE,SAAS;aACjB,CAAC;YACF,aAAa,GAAG,SAAS,GAAG,CAAC,CAAC;YAC9B,SAAS,GAAG,KAAK,CAAC,OAAO,CAAC,SAAS,EAAE,aAAa,CAAC,CAAC;QACtD,CAAC;QAED,eAAe;QACf,IAAI,aAAa,GAAG,KAAK,CAAC,MAAM,EAAE,CAAC;YACjC,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,KAAK,CAAC,MAAM,CAAC;gBAChD,KAAK,EAAE,KAAK,CAAC,MAAM;aACpB,CAAC;QACJ,CAAC;IACH,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;;;OAIG;IACI,KAAK;QACV,IAAI,CAAC,KAAK,CAAC,KAAK,GAAG,SAAS,CAAC;QAC7B,IAAI,CAAC,KAAK,CAAC,QAAQ,GAAG,SAAS,CAAC;QAChC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QACf,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACI,OAAO,CAAC,cAAsB,EAAE,KAAY,EAAE,YAAoB,IAAI,CAAC,SAAS;QACrF,OAAO,IAAI,CAAC,mBAAmB,CAAC,YAAY,CAAC,mBAAmB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,KAAK,CAAC,CAAC;IACtG,CAAC;IAED;;;;;;;OAOG;IACI,UAAU,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACjE,MAAM,IAAI,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QACxF,IAAI,CAAA,IAAI,aAAJ,IAAI,uBAAJ,IAAI,CAAE,KAAK,MAAK,SAAS,EAAE,CAAC;YAC9B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;YACvB,IAAI,CAAC,KAAK,EAAE,CAAC;YACb,OAAO,IAAI,CAAC;QACd,CAAC;QAED,OAAO,KAAK,CAAC;IACf,CAAC;IAED;;;;;OAKG;IACI,aAAa,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACpE,MAAM,SAAS,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QAC7F,IAAI,CAAC,SAAS,EAAE,CAAC;YACf,OAAO,KAAK,CAAC;QACf,CAAC;QAED,MAAM,KAAK,GAA2B,CAAC,SAAS,CAAC,CAAC;QAClD,IAAI,OAAO,GAAW,CAAC,CAAC;QACxB,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,IAAI,GAAyB,KAAK,CAAC,GAAG,EAAG,CAAC;YAChD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;gBACvB,OAAO,EAAE,CAAC;YACZ,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,KAAK,IAAI,IAAI,CAAC,QAAQ,CAAC,MAAM,EAAE,EAAE,CAAC;oBAC3C,KAAK,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;gBACpB,CAAC;gBACD,IAAI,CAAC,QAAQ,CAAC,KAAK,EAAE,CAAC;YACxB,CAAC;QACH,CAAC;QAED,IAAI,CAAC,KAAK,IAAI,OAAO,CAAC;QACtB,OAAO,OAAO,GAAG,CAAC,CAAC;IACrB,CAAC;IAED;;;;;OAKG;IACI,mBAAmB,CAAC,YAA8B,EAAE,KAAY;QACrE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,OAAO,IAAI,YAAY,EAAE,CAAC;YACnC,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,IAAI,CAAC,QAAQ,GAAG,IAAI,GAAG,EAAE,CAAC;YAC5B,CAAC;YACD,IAAI,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;YACzE,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,IAAI,CAAC,QAAQ,CAAC,GAAG,CACf,OAAO,EACP,CAAC,KAAK,GAAG;oBACP,KAAK,EAAE,SAAS;oBAChB,QAAQ,EAAE,SAAS;iBACpB,CAAC,CACH,CAAC;YACJ,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;YAC7B,IAAI,CAAC,KAAK,EAAE,CAAC;QACf,CAAC;QACD,IAAI,CAAC,KAAK,GAAG,KAAK,CAAC;QAEnB,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,aAAa,CAAC,SAAiB,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxE,OAAO,IAAI,CAAC,yBAAyB,CAAC,YAAY,CAAC,mBAAmB,CAAC,SAAS,EAAE,SAAS,CAAC,CAAC,CAAC;IAChG,CAAC;IAED;;OAEG;IACI,sBAAsB,CAC3B,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,uBAAuB,CAAC,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC,CAAC;IACvF,CAAC;IAED;;OAEG;IACI,yBAAyB,CAAC,iBAAmC;;QAClE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAsB,IAAI,CAAC,KAAK,CAAC;QACzC,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,OAAO,IAAI,iBAAiB,EAAE,CAAC;gBACxC,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;gBAC3E,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,GAAG,MAAA,IAAI,CAAC,KAAK,mCAAI,IAAI,CAAC;gBAC1B,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC;IACrC,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC,CAAC,CAAC,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,SAAS,CAAC;IAC/D,CAAC;IAED;;OAEG;IACI,YAAY,CACjB,UAA8B,EAC9B,YAAoB,IAAI,CAAC,SAAS;QAElC,MAAM,kBAAkB,GAAmC,IAAI,GAAG,EAAE,CAAC;QAErE,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,UAAU,EAAE,CAAC;YACtC,MAAM,KAAK,GAAsB,IAAI,CAAC,aAAa,CAAC,IAAI,EAAE,SAAS,CAAC,CAAC;YACrE,IAAI,KAAK,KAAK,SAAS,EAAE,CAAC;gBACxB,SAAS;YACX,CAAC;YACD,IAAI,WAAW,GAAmC,kBAAkB,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;YAChF,IAAI,CAAC,WAAW,EAAE,CAAC;gBACjB,WAAW,GAAG,IAAI,GAAG,EAAE,CAAC;gBACxB,kBAAkB,CAAC,GAAG,CAAC,KAAK,EAAE,WAAW,CAAC,CAAC;YAC7C,CAAC;YACD,WAAW,CAAC,GAAG,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;QAC9B,CAAC;QAED,OAAO,kBAAkB,CAAC;IAC5B,CAAC;IAED;;OAEG;IACI,CAAC,OAAO,CAAC,KAAc,EAAE,YAAoB,IAAI,CAAC,SAAS;QAChE,IAAI,IAAsC,CAAC;QAC3C,IAAI,KAAK,EAAE,CAAC;YACV,IAAI,GAAG,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;YAChD,IAAI,CAAC,IAAI,EAAE,CAAC;gBACV,OAAO;YACT,CAAC;QACH,CAAC;aAAM,CAAC;YACN,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC;QACpB,CAAC;QAED,MAAM,KAAK,GAAqC,CAAC,CAAC,KAAK,aAAL,KAAK,cAAL,KAAK,GAAI,EAAE,EAAE,IAAI,CAAC,CAAC,CAAC;QACtE,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,GAAG,KAAK,CAAC,GAAG,EAAG,CAAC;YACpC,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,KAAK,CAAC,CAAC;YAC7B,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,CAAC,OAAO,EAAE,KAAK,CAAC,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;oBAC7C,KAAK,CAAC,IAAI,CAAC,CAAC,MAAM,CAAC,CAAC,CAAC,GAAG,MAAM,GAAG,SAAS,GAAG,OAAO,EAAE,CAAC,CAAC,CAAC,OAAO,EAAE,KAAK,CAAC,CAAC,CAAC;gBAC5E,CAAC;YACH,CAAC;QACH,CAAC;IACH,CAAC;IAED;;OAEG;IACI,CAAC,MAAM,CAAC,QAAQ,CAAC,CACtB,KAAc,EACd,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,OAAO,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IACxC,CAAC;IAED;;OAEG;IACI,eAAe,CACpB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IAClD,CAAC;IAED;;;;;;;OAOG;IACK,uBAAuB,CAAC,QAAgC;QAC9D,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAoC,IAAI,CAAC,KAAK;YACpD,CAAC,CAAC;gBACE,KAAK,EAAE,IAAI,CAAC,KAAK;gBACjB,KAAK,EAAE,CAAC;gBACR,SAAS,EAAE,SAAS;aACrB;YACH,CAAC,CAAC,SAAS,CAAC;QACd,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,EAAE,KAAK,EAAE,IAAI,QAAQ,EAAE,CAAC;gBAC/C,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC;gBACxE,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;oBAC7B,IAAI,GAAG;wBACL,KAAK,EAAE,IAAI,CAAC,KAAK;wBACjB,KAAK;wBACL,SAAS,EAAE,IAAI;qBAChB,CAAC;gBACJ,CAAC;gBACD,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACK,iBAAiB,CACvB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,EAAE,CAAC;YACzE,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,MAAM,CAAC,CAAC;YAC1E,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,OAAO,IAAI,CAAC;IACd,CAAC;CACF","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * A node in the path trie used in LookupByPath\n */\ninterface IPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  children: Map<string, IPathTrieNode<TItem>> | undefined;\n}\n\n/**\n * Readonly view of a node in the path trie used in LookupByPath\n *\n * @remarks\n * This interface is used to facilitate parallel traversals for comparing two `LookupByPath` instances.\n *\n * @beta\n */\nexport interface IReadonlyPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  readonly value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  readonly children: ReadonlyMap<string, IReadonlyPathTrieNode<TItem>> | undefined;\n}\n\ninterface IPrefixEntry {\n  /**\n   * The prefix that was matched\n   */\n  prefix: string;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n}\n\n/**\n * Object containing both the matched item and the start index of the remainder of the query.\n *\n * @beta\n */\nexport interface IPrefixMatch<TItem extends {}> {\n  /**\n   * The item that matched the prefix\n   */\n  value: TItem;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n\n  /**\n   * The last match found (with a shorter prefix), if any\n   */\n  lastMatch?: IPrefixMatch<TItem>;\n}\n\n/**\n * The readonly component of `LookupByPath`, to simplify unit testing.\n *\n * @beta\n */\nexport interface IReadonlyLookupByPath<TItem extends {}> extends Iterable<[string, TItem]> {\n  /**\n   * Searches for the item associated with `childPath`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPath('foo/baz'); // returns 1\n   * trie.findChildPath('foo/bar/baz'); // returns 2\n   * ```\n   */\n  findChildPath(childPath: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Searches for the item for which the recorded prefix is the longest matching prefix of `query`.\n   * Obtains both the item and the length of the matched prefix, so that the remainder of the path can be\n   * extracted.\n   *\n   * @returns the found item and the length of the matched prefix, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findLongestPrefixMatch('foo/baz'); // returns { item: 1, index: 3 }\n   * trie.findLongestPrefixMatch('foo/bar/baz'); // returns { item: 2, index: 7 }\n   * ```\n   */\n  findLongestPrefixMatch(query: string, delimiter?: string): IPrefixMatch<TItem> | undefined;\n\n  /**\n   * Searches for the item associated with `childPathSegments`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPathFromSegments(['foo', 'baz']); // returns 1\n   * trie.findChildPathFromSegments(['foo','bar', 'baz']); // returns 2\n   * ```\n   */\n  findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined;\n\n  /**\n   * Determines if an entry exists exactly at the specified path.\n   *\n   * @returns `true` if an entry exists at the specified path, `false` otherwise\n   */\n  has(query: string, delimiter?: string): boolean;\n\n  /**\n   * Retrieves the entry that exists exactly at the specified path, if any.\n   *\n   * @returns The entry that exists exactly at the specified path, or `undefined` if no entry exists.\n   */\n  get(query: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Gets the number of entries in this trie.\n   *\n   * @returns The number of entries in this trie.\n   */\n  get size(): number;\n\n  /**\n   * @returns The root node of the trie, corresponding to the path ''\n   */\n  get tree(): IReadonlyPathTrieNode<TItem>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * [...trie.entries(undefined, ',')); // returns [['foo', 1], ['foo,bar', 2]]\n   * ```\n   */\n  entries(query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   */\n  [Symbol.iterator](query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Groups the provided map of info by the nearest entry in the trie that contains the path. If the path\n   * is not found in the trie, the info is ignored.\n   *\n   * @returns The grouped info, grouped by the nearest entry in the trie that contains the path\n   *\n   * @param infoByPath - The info to be grouped, keyed by path\n   */\n  groupByChild<TInfo>(infoByPath: Map<string, TInfo>, delimiter?: string): Map<TItem, Map<string, TInfo>>;\n\n  /**\n   * Retrieves the trie node at the specified prefix, if it exists.\n   *\n   * @param query - The prefix to check for\n   * @param delimiter - The path delimiter\n   * @returns The trie node at the specified prefix, or `undefined` if no node was found\n   */\n  getNodeAtPrefix(query: string, delimiter?: string): IReadonlyPathTrieNode<TItem> | undefined;\n}\n\n/**\n * This class is used to associate path-like-strings, such as those returned by `git` commands,\n * with entities that correspond with ancestor folders, such as Rush Projects or npm packages.\n *\n * It is optimized for efficiently locating the nearest ancestor path with an associated value.\n *\n * It is implemented as a Trie (https://en.wikipedia.org/wiki/Trie) data structure, with each edge\n * being a path segment.\n *\n * @example\n * ```ts\n * const trie = new LookupByPath([['foo', 1], ['bar', 2], ['foo/bar', 3]]);\n * trie.findChildPath('foo'); // returns 1\n * trie.findChildPath('foo/baz'); // returns 1\n * trie.findChildPath('baz'); // returns undefined\n * trie.findChildPath('foo/bar/baz'); returns 3\n * trie.findChildPath('bar/foo/bar'); returns 2\n * ```\n * @beta\n */\nexport class LookupByPath<TItem extends {}> implements IReadonlyLookupByPath<TItem> {\n  /**\n   * The delimiter used to split paths\n   */\n  public readonly delimiter: string;\n\n  /**\n   * The root node of the trie, corresponding to the path ''\n   */\n  private readonly _root: IPathTrieNode<TItem>;\n\n  /**\n   * The number of entries in this trie.\n   */\n  private _size: number;\n\n  /**\n   * Constructs a new `LookupByPath`\n   *\n   * @param entries - Initial path-value pairs to populate the trie.\n   */\n  public constructor(entries?: Iterable<[string, TItem]>, delimiter?: string) {\n    this._root = {\n      value: undefined,\n      children: undefined\n    };\n\n    this.delimiter = delimiter ?? '/';\n    this._size = 0;\n\n    if (entries) {\n      for (const [path, item] of entries) {\n        this.setItem(path, item);\n      }\n    }\n  }\n\n  /**\n   * Iterates over the segments of a serialized path.\n   *\n   * @example\n   *\n   * `LookupByPath.iteratePathSegments('foo/bar/baz')` yields 'foo', 'bar', 'baz'\n   *\n   * `LookupByPath.iteratePathSegments('foo\\\\bar\\\\baz', '\\\\')` yields 'foo', 'bar', 'baz'\n   */\n  public static *iteratePathSegments(serializedPath: string, delimiter: string = '/'): Iterable<string> {\n    for (const prefixMatch of this._iteratePrefixes(serializedPath, delimiter)) {\n      yield prefixMatch.prefix;\n    }\n  }\n\n  private static *_iteratePrefixes(input: string, delimiter: string = '/'): Iterable<IPrefixEntry> {\n    if (!input) {\n      return;\n    }\n\n    let previousIndex: number = 0;\n    let nextIndex: number = input.indexOf(delimiter);\n\n    // Leading segments\n    while (nextIndex >= 0) {\n      yield {\n        prefix: input.slice(previousIndex, nextIndex),\n        index: nextIndex\n      };\n      previousIndex = nextIndex + 1;\n      nextIndex = input.indexOf(delimiter, previousIndex);\n    }\n\n    // Last segment\n    if (previousIndex < input.length) {\n      yield {\n        prefix: input.slice(previousIndex, input.length),\n        index: input.length\n      };\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.size}\n   */\n  public get size(): number {\n    return this._size;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.tree}\n   */\n  public get tree(): IReadonlyPathTrieNode<TItem> {\n    return this._root;\n  }\n\n  /**\n   * Deletes all entries from this `LookupByPath` instance.\n   *\n   * @returns this, for chained calls\n   */\n  public clear(): this {\n    this._root.value = undefined;\n    this._root.children = undefined;\n    this._size = 0;\n    return this;\n  }\n\n  /**\n   * Associates the value with the specified serialized path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItem(serializedPath: string, value: TItem, delimiter: string = this.delimiter): this {\n    return this.setItemFromSegments(LookupByPath.iteratePathSegments(serializedPath, delimiter), value);\n  }\n\n  /**\n   * Deletes an item if it exists.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if the item was found and deleted, `false` otherwise\n   * @remarks\n   * If the node has children with values, they will be retained.\n   */\n  public deleteItem(query: string, delimeter: string = this.delimiter): boolean {\n    const node: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (node?.value !== undefined) {\n      node.value = undefined;\n      this._size--;\n      return true;\n    }\n\n    return false;\n  }\n\n  /**\n   * Deletes an item and all its children.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if any nodes were deleted, `false` otherwise\n   */\n  public deleteSubtree(query: string, delimeter: string = this.delimiter): boolean {\n    const queryNode: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (!queryNode) {\n      return false;\n    }\n\n    const queue: IPathTrieNode<TItem>[] = [queryNode];\n    let removed: number = 0;\n    while (queue.length > 0) {\n      const node: IPathTrieNode<TItem> = queue.pop()!;\n      if (node.value !== undefined) {\n        node.value = undefined;\n        removed++;\n      }\n      if (node.children) {\n        for (const child of node.children.values()) {\n          queue.push(child);\n        }\n        node.children.clear();\n      }\n    }\n\n    this._size -= removed;\n    return removed > 0;\n  }\n\n  /**\n   * Associates the value with the specified path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItemFromSegments(pathSegments: Iterable<string>, value: TItem): this {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const segment of pathSegments) {\n      if (!node.children) {\n        node.children = new Map();\n      }\n      let child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n      if (!child) {\n        node.children.set(\n          segment,\n          (child = {\n            value: undefined,\n            children: undefined\n          })\n        );\n      }\n      node = child;\n    }\n    if (node.value === undefined) {\n      this._size++;\n    }\n    node.value = value;\n\n    return this;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPath(childPath: string, delimiter: string = this.delimiter): TItem | undefined {\n    return this.findChildPathFromSegments(LookupByPath.iteratePathSegments(childPath, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findLongestPrefixMatch(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPrefixMatch<TItem> | undefined {\n    return this._findLongestPrefixMatch(LookupByPath._iteratePrefixes(query, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: TItem | undefined = node.value;\n    // Trivial cases\n    if (node.children) {\n      for (const segment of childPathSegments) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n        if (!child) {\n          break;\n        }\n        node = child;\n        best = node.value ?? best;\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public has(key: string, delimiter: string = this.delimiter): boolean {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public get(key: string, delimiter: string = this.delimiter): TItem | undefined {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length ? match.value : undefined;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public groupByChild<TInfo>(\n    infoByPath: Map<string, TInfo>,\n    delimiter: string = this.delimiter\n  ): Map<TItem, Map<string, TInfo>> {\n    const groupedInfoByChild: Map<TItem, Map<string, TInfo>> = new Map();\n\n    for (const [path, info] of infoByPath) {\n      const child: TItem | undefined = this.findChildPath(path, delimiter);\n      if (child === undefined) {\n        continue;\n      }\n      let groupedInfo: Map<string, TInfo> | undefined = groupedInfoByChild.get(child);\n      if (!groupedInfo) {\n        groupedInfo = new Map();\n        groupedInfoByChild.set(child, groupedInfo);\n      }\n      groupedInfo.set(path, info);\n    }\n\n    return groupedInfoByChild;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public *entries(query?: string, delimiter: string = this.delimiter): IterableIterator<[string, TItem]> {\n    let root: IPathTrieNode<TItem> | undefined;\n    if (query) {\n      root = this._findNodeAtPrefix(query, delimiter);\n      if (!root) {\n        return;\n      }\n    } else {\n      root = this._root;\n    }\n\n    const stack: [string, IPathTrieNode<TItem>][] = [[query ?? '', root]];\n    while (stack.length > 0) {\n      const [prefix, node] = stack.pop()!;\n      if (node.value !== undefined) {\n        yield [prefix, node.value];\n      }\n      if (node.children) {\n        for (const [segment, child] of node.children) {\n          stack.push([prefix ? `${prefix}${delimiter}${segment}` : segment, child]);\n        }\n      }\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public [Symbol.iterator](\n    query?: string,\n    delimiter: string = this.delimiter\n  ): IterableIterator<[string, TItem]> {\n    return this.entries(query, delimiter);\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public getNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IReadonlyPathTrieNode<TItem> | undefined {\n    return this._findNodeAtPrefix(query, delimiter);\n  }\n\n  /**\n   * Iterates through progressively longer prefixes of a given string and returns as soon\n   * as the number of candidate items that match the prefix are 1 or 0.\n   *\n   * If a match is present, returns the matched itme and the length of the matched prefix.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   */\n  private _findLongestPrefixMatch(prefixes: Iterable<IPrefixEntry>): IPrefixMatch<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: IPrefixMatch<TItem> | undefined = node.value\n      ? {\n          value: node.value,\n          index: 0,\n          lastMatch: undefined\n        }\n      : undefined;\n    // Trivial cases\n    if (node.children) {\n      for (const { prefix: hash, index } of prefixes) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(hash);\n        if (!child) {\n          break;\n        }\n        node = child;\n        if (node.value !== undefined) {\n          best = {\n            value: node.value,\n            index,\n            lastMatch: best\n          };\n        }\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * Finds the node at the specified path, or `undefined` if no node was found.\n   *\n   * @param query - The path to the node to search for\n   * @returns The trie node at the specified path, or `undefined` if no node was found\n   */\n  private _findNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPathTrieNode<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const { prefix } of LookupByPath._iteratePrefixes(query, delimiter)) {\n      if (!node.children) {\n        return undefined;\n      }\n      const child: IPathTrieNode<TItem> | undefined = node.children.get(prefix);\n      if (!child) {\n        return undefined;\n      }\n      node = child;\n    }\n    return node;\n  }\n}\n"]}
+{"version":3,"file":"LookupByPath.js","sourceRoot":"","sources":["../src/LookupByPath.ts"],"names":[],"mappings":"AAAA,4FAA4F;AAC5F,2DAA2D;AAiQ3D;;;;;;;;;;;;;;;;;;;GAmBG;AACH,MAAM,OAAO,YAAY;IAgBvB;;;;OAIG;IACH,YAAmB,OAAmC,EAAE,SAAkB;QACxE,IAAI,CAAC,KAAK,GAAG;YACX,KAAK,EAAE,SAAS;YAChB,QAAQ,EAAE,SAAS;SACpB,CAAC;QAEF,IAAI,CAAC,SAAS,GAAG,SAAS,aAAT,SAAS,cAAT,SAAS,GAAI,GAAG,CAAC;QAClC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QAEf,IAAI,OAAO,EAAE,CAAC;YACZ,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,OAAO,EAAE,CAAC;gBACnC,IAAI,CAAC,OAAO,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;YAC3B,CAAC;QACH,CAAC;IACH,CAAC;IAED;;;;;;;;OAQG;IACI,MAAM,CAAC,CAAC,mBAAmB,CAAC,cAAsB,EAAE,YAAoB,GAAG;QAChF,KAAK,MAAM,WAAW,IAAI,IAAI,CAAC,gBAAgB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,CAAC;YAC3E,MAAM,WAAW,CAAC,MAAM,CAAC;QAC3B,CAAC;IACH,CAAC;IAEO,MAAM,CAAC,CAAC,gBAAgB,CAAC,KAAa,EAAE,YAAoB,GAAG;QACrE,IAAI,CAAC,KAAK,EAAE,CAAC;YACX,OAAO;QACT,CAAC;QAED,IAAI,aAAa,GAAW,CAAC,CAAC;QAC9B,IAAI,SAAS,GAAW,KAAK,CAAC,OAAO,CAAC,SAAS,CAAC,CAAC;QAEjD,mBAAmB;QACnB,OAAO,SAAS,IAAI,CAAC,EAAE,CAAC;YACtB,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,SAAS,CAAC;gBAC7C,KAAK,EAAE,SAAS;aACjB,CAAC;YACF,aAAa,GAAG,SAAS,GAAG,CAAC,CAAC;YAC9B,SAAS,GAAG,KAAK,CAAC,OAAO,CAAC,SAAS,EAAE,aAAa,CAAC,CAAC;QACtD,CAAC;QAED,eAAe;QACf,IAAI,aAAa,GAAG,KAAK,CAAC,MAAM,EAAE,CAAC;YACjC,MAAM;gBACJ,MAAM,EAAE,KAAK,CAAC,KAAK,CAAC,aAAa,EAAE,KAAK,CAAC,MAAM,CAAC;gBAChD,KAAK,EAAE,KAAK,CAAC,MAAM;aACpB,CAAC;QACJ,CAAC;IACH,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;OAEG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,KAAK,CAAC;IACpB,CAAC;IAED;;;;OAIG;IACI,KAAK;QACV,IAAI,CAAC,KAAK,CAAC,KAAK,GAAG,SAAS,CAAC;QAC7B,IAAI,CAAC,KAAK,CAAC,QAAQ,GAAG,SAAS,CAAC;QAChC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC;QACf,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACI,OAAO,CAAC,cAAsB,EAAE,KAAY,EAAE,YAAoB,IAAI,CAAC,SAAS;QACrF,OAAO,IAAI,CAAC,mBAAmB,CAAC,YAAY,CAAC,mBAAmB,CAAC,cAAc,EAAE,SAAS,CAAC,EAAE,KAAK,CAAC,CAAC;IACtG,CAAC;IAED;;;;;;;OAOG;IACI,UAAU,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACjE,MAAM,IAAI,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QACxF,IAAI,CAAA,IAAI,aAAJ,IAAI,uBAAJ,IAAI,CAAE,KAAK,MAAK,SAAS,EAAE,CAAC;YAC9B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;YACvB,IAAI,CAAC,KAAK,EAAE,CAAC;YACb,OAAO,IAAI,CAAC;QACd,CAAC;QAED,OAAO,KAAK,CAAC;IACf,CAAC;IAED;;;;;OAKG;IACI,aAAa,CAAC,KAAa,EAAE,YAAoB,IAAI,CAAC,SAAS;QACpE,MAAM,SAAS,GAAqC,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;QAC7F,IAAI,CAAC,SAAS,EAAE,CAAC;YACf,OAAO,KAAK,CAAC;QACf,CAAC;QAED,MAAM,KAAK,GAA2B,CAAC,SAAS,CAAC,CAAC;QAClD,IAAI,OAAO,GAAW,CAAC,CAAC;QACxB,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,IAAI,GAAyB,KAAK,CAAC,GAAG,EAAG,CAAC;YAChD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,IAAI,CAAC,KAAK,GAAG,SAAS,CAAC;gBACvB,OAAO,EAAE,CAAC;YACZ,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,KAAK,IAAI,IAAI,CAAC,QAAQ,CAAC,MAAM,EAAE,EAAE,CAAC;oBAC3C,KAAK,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;gBACpB,CAAC;gBACD,IAAI,CAAC,QAAQ,CAAC,KAAK,EAAE,CAAC;YACxB,CAAC;QACH,CAAC;QAED,IAAI,CAAC,KAAK,IAAI,OAAO,CAAC;QACtB,OAAO,OAAO,GAAG,CAAC,CAAC;IACrB,CAAC;IAED;;;;;OAKG;IACI,mBAAmB,CAAC,YAA8B,EAAE,KAAY;QACrE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,OAAO,IAAI,YAAY,EAAE,CAAC;YACnC,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,IAAI,CAAC,QAAQ,GAAG,IAAI,GAAG,EAAE,CAAC;YAC5B,CAAC;YACD,IAAI,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;YACzE,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,IAAI,CAAC,QAAQ,CAAC,GAAG,CACf,OAAO,EACP,CAAC,KAAK,GAAG;oBACP,KAAK,EAAE,SAAS;oBAChB,QAAQ,EAAE,SAAS;iBACpB,CAAC,CACH,CAAC;YACJ,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;YAC7B,IAAI,CAAC,KAAK,EAAE,CAAC;QACf,CAAC;QACD,IAAI,CAAC,KAAK,GAAG,KAAK,CAAC;QAEnB,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,aAAa,CAAC,SAAiB,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxE,OAAO,IAAI,CAAC,yBAAyB,CAAC,YAAY,CAAC,mBAAmB,CAAC,SAAS,EAAE,SAAS,CAAC,CAAC,CAAC;IAChG,CAAC;IAED;;OAEG;IACI,sBAAsB,CAC3B,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,uBAAuB,CAAC,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC,CAAC;IACvF,CAAC;IAED;;OAEG;IACI,yBAAyB,CAAC,iBAAmC;;QAClE,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAsB,IAAI,CAAC,KAAK,CAAC;QACzC,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,OAAO,IAAI,iBAAiB,EAAE,CAAC;gBACxC,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,CAAC,CAAC;gBAC3E,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,GAAG,MAAA,IAAI,CAAC,KAAK,mCAAI,IAAI,CAAC;gBAC1B,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC;IACrC,CAAC;IAED;;OAEG;IACI,GAAG,CAAC,GAAW,EAAE,YAAoB,IAAI,CAAC,SAAS;QACxD,MAAM,KAAK,GAAoC,IAAI,CAAC,sBAAsB,CAAC,GAAG,EAAE,SAAS,CAAC,CAAC;QAC3F,OAAO,CAAA,KAAK,aAAL,KAAK,uBAAL,KAAK,CAAE,KAAK,MAAK,GAAG,CAAC,MAAM,CAAC,CAAC,CAAC,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,SAAS,CAAC;IAC/D,CAAC;IAED;;OAEG;IACI,YAAY,CACjB,UAA8B,EAC9B,YAAoB,IAAI,CAAC,SAAS;QAElC,MAAM,kBAAkB,GAAmC,IAAI,GAAG,EAAE,CAAC;QAErE,KAAK,MAAM,CAAC,IAAI,EAAE,IAAI,CAAC,IAAI,UAAU,EAAE,CAAC;YACtC,MAAM,KAAK,GAAsB,IAAI,CAAC,aAAa,CAAC,IAAI,EAAE,SAAS,CAAC,CAAC;YACrE,IAAI,KAAK,KAAK,SAAS,EAAE,CAAC;gBACxB,SAAS;YACX,CAAC;YACD,IAAI,WAAW,GAAmC,kBAAkB,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;YAChF,IAAI,CAAC,WAAW,EAAE,CAAC;gBACjB,WAAW,GAAG,IAAI,GAAG,EAAE,CAAC;gBACxB,kBAAkB,CAAC,GAAG,CAAC,KAAK,EAAE,WAAW,CAAC,CAAC;YAC7C,CAAC;YACD,WAAW,CAAC,GAAG,CAAC,IAAI,EAAE,IAAI,CAAC,CAAC;QAC9B,CAAC;QAED,OAAO,kBAAkB,CAAC;IAC5B,CAAC;IAED;;OAEG;IACI,CAAC,OAAO,CAAC,KAAc,EAAE,YAAoB,IAAI,CAAC,SAAS;QAChE,IAAI,IAAsC,CAAC;QAC3C,IAAI,KAAK,EAAE,CAAC;YACV,IAAI,GAAG,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;YAChD,IAAI,CAAC,IAAI,EAAE,CAAC;gBACV,OAAO;YACT,CAAC;QACH,CAAC;aAAM,CAAC;YACN,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC;QACpB,CAAC;QAED,MAAM,KAAK,GAAqC,CAAC,CAAC,KAAK,aAAL,KAAK,cAAL,KAAK,GAAI,EAAE,EAAE,IAAI,CAAC,CAAC,CAAC;QACtE,OAAO,KAAK,CAAC,MAAM,GAAG,CAAC,EAAE,CAAC;YACxB,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,GAAG,KAAK,CAAC,GAAG,EAAG,CAAC;YACpC,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,MAAM,CAAC,MAAM,EAAE,IAAI,CAAC,KAAK,CAAC,CAAC;YAC7B,CAAC;YACD,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;gBAClB,KAAK,MAAM,CAAC,OAAO,EAAE,KAAK,CAAC,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;oBAC7C,KAAK,CAAC,IAAI,CAAC,CAAC,MAAM,CAAC,CAAC,CAAC,GAAG,MAAM,GAAG,SAAS,GAAG,OAAO,EAAE,CAAC,CAAC,CAAC,OAAO,EAAE,KAAK,CAAC,CAAC,CAAC;gBAC5E,CAAC;YACH,CAAC;QACH,CAAC;IACH,CAAC;IAED;;OAEG;IACI,CAAC,MAAM,CAAC,QAAQ,CAAC,CACtB,KAAc,EACd,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,OAAO,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IACxC,CAAC;IAED;;OAEG;IACI,eAAe,CACpB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,OAAO,IAAI,CAAC,iBAAiB,CAAC,KAAK,EAAE,SAAS,CAAC,CAAC;IAClD,CAAC;IAED;;OAEG;IACI,MAAM,CACX,cAA6C;QAE7C,MAAM,YAAY,GAAuB,IAAI,GAAG,EAAE,CAAC;QACnD,MAAM,MAAM,GAAkB,EAAE,CAAC;QAEjC,MAAM,kBAAkB,GAA6B,CAAC,KAAY,EAAE,EAAE;YACpE,IAAI,KAAK,GAAuB,YAAY,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;YACxD,IAAI,KAAK,KAAK,SAAS,EAAE,CAAC;gBACxB,KAAK,GAAG,MAAM,CAAC,MAAM,CAAC;gBACtB,YAAY,CAAC,GAAG,CAAC,KAAK,EAAE,KAAK,CAAC,CAAC;gBAC/B,MAAM,CAAC,IAAI,CAAC,cAAc,CAAC,KAAK,CAAC,CAAC,CAAC;YACrC,CAAC;YACD,OAAO,KAAK,CAAC;QACf,CAAC,CAAC;QAEF,MAAM,aAAa,GAA4D,CAC7E,IAA0B,EAC1B,EAAE;YACF,MAAM,MAAM,GAA4B,EAAE,CAAC;YAE3C,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;gBAC7B,MAAM,CAAC,UAAU,GAAG,kBAAkB,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;YACrD,CAAC;YAED,IAAI,IAAI,CAAC,QAAQ,IAAI,IAAI,CAAC,QAAQ,CAAC,IAAI,GAAG,CAAC,EAAE,CAAC;gBAC5C,MAAM,QAAQ,GAA4C,MAAM,CAAC,MAAM,CAAC,IAAI,CAAC,CAAC;gBAC9E,KAAK,MAAM,CAAC,OAAO,EAAE,KAAK,CAAC,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;oBAC7C,QAAQ,CAAC,OAAO,CAAC,GAAG,aAAa,CAAC,KAAK,CAAC,CAAC;gBAC3C,CAAC;gBACD,MAAM,CAAC,QAAQ,GAAG,QAAQ,CAAC;YAC7B,CAAC;YAED,OAAO,MAAM,CAAC;QAChB,CAAC,CAAC;QAEF,OAAO;YACL,SAAS,EAAE,IAAI,CAAC,SAAS;YACzB,MAAM;YACN,IAAI,EAAE,aAAa,CAAC,IAAI,CAAC,KAAK,CAAC;SAChC,CAAC;IACJ,CAAC;IAED;;;;;;;;;;;;OAYG;IACI,MAAM,CAAC,QAAQ,CACpB,IAAoC,EACpC,gBAAoD;QAEpD,MAAM,kBAAkB,GAAY,IAAI,CAAC,MAAM,CAAC,GAAG,CAAC,gBAAgB,CAAC,CAAC;QAEtE,MAAM,MAAM,GAAwB,IAAI,YAAY,CAAQ,SAAS,EAAE,IAAI,CAAC,SAAS,CAAC,CAAC;QAEvF,MAAM,eAAe,GAGT,CAAC,QAAiC,EAAE,UAAgC,EAAE,EAAE;YAClF,IAAI,QAAQ,CAAC,UAAU,KAAK,SAAS,EAAE,CAAC;gBACtC,UAAU,CAAC,KAAK,GAAG,kBAAkB,CAAC,QAAQ,CAAC,UAAU,CAAC,CAAC;gBAC3D,MAAM,CAAC,KAAK,EAAE,CAAC;YACjB,CAAC;YAED,IAAI,QAAQ,CAAC,QAAQ,EAAE,CAAC;gBACtB,UAAU,CAAC,QAAQ,GAAG,IAAI,GAAG,EAAE,CAAC;gBAChC,KAAK,MAAM,CAAC,OAAO,EAAE,SAAS,CAAC,IAAI,MAAM,CAAC,OAAO,CAAC,QAAQ,CAAC,QAAQ,CAAC,EAAE,CAAC;oBACrE,MAAM,SAAS,GAAyB;wBACtC,KAAK,EAAE,SAAS;wBAChB,QAAQ,EAAE,SAAS;qBACpB,CAAC;oBACF,UAAU,CAAC,QAAQ,CAAC,GAAG,CAAC,OAAO,EAAE,SAAS,CAAC,CAAC;oBAC5C,eAAe,CAAC,SAAS,EAAE,SAAS,CAAC,CAAC;gBACxC,CAAC;YACH,CAAC;QACH,CAAC,CAAC;QAEF,eAAe,CAAC,IAAI,CAAC,IAAI,EAAE,MAAM,CAAC,KAAK,CAAC,CAAC;QAEzC,OAAO,MAAM,CAAC;IAChB,CAAC;IAED;;;;;;;OAOG;IACK,uBAAuB,CAAC,QAAgC;QAC9D,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,IAAI,IAAI,GAAoC,IAAI,CAAC,KAAK;YACpD,CAAC,CAAC;gBACE,KAAK,EAAE,IAAI,CAAC,KAAK;gBACjB,KAAK,EAAE,CAAC;gBACR,SAAS,EAAE,SAAS;aACrB;YACH,CAAC,CAAC,SAAS,CAAC;QACd,gBAAgB;QAChB,IAAI,IAAI,CAAC,QAAQ,EAAE,CAAC;YAClB,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,EAAE,KAAK,EAAE,IAAI,QAAQ,EAAE,CAAC;gBAC/C,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC;gBACxE,IAAI,CAAC,KAAK,EAAE,CAAC;oBACX,MAAM;gBACR,CAAC;gBACD,IAAI,GAAG,KAAK,CAAC;gBACb,IAAI,IAAI,CAAC,KAAK,KAAK,SAAS,EAAE,CAAC;oBAC7B,IAAI,GAAG;wBACL,KAAK,EAAE,IAAI,CAAC,KAAK;wBACjB,KAAK;wBACL,SAAS,EAAE,IAAI;qBAChB,CAAC;gBACJ,CAAC;gBACD,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;oBACnB,MAAM;gBACR,CAAC;YACH,CAAC;QACH,CAAC;QAED,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;OAKG;IACK,iBAAiB,CACvB,KAAa,EACb,YAAoB,IAAI,CAAC,SAAS;QAElC,IAAI,IAAI,GAAyB,IAAI,CAAC,KAAK,CAAC;QAC5C,KAAK,MAAM,EAAE,MAAM,EAAE,IAAI,YAAY,CAAC,gBAAgB,CAAC,KAAK,EAAE,SAAS,CAAC,EAAE,CAAC;YACzE,IAAI,CAAC,IAAI,CAAC,QAAQ,EAAE,CAAC;gBACnB,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,MAAM,KAAK,GAAqC,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,MAAM,CAAC,CAAC;YAC1E,IAAI,CAAC,KAAK,EAAE,CAAC;gBACX,OAAO,SAAS,CAAC;YACnB,CAAC;YACD,IAAI,GAAG,KAAK,CAAC;QACf,CAAC;QACD,OAAO,IAAI,CAAC;IACd,CAAC;CACF","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * A node in the path trie used in LookupByPath\n */\ninterface IPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  children: Map<string, IPathTrieNode<TItem>> | undefined;\n}\n\n/**\n * Readonly view of a node in the path trie used in LookupByPath\n *\n * @remarks\n * This interface is used to facilitate parallel traversals for comparing two `LookupByPath` instances.\n *\n * @beta\n */\nexport interface IReadonlyPathTrieNode<TItem extends {}> {\n  /**\n   * The value that exactly matches the current relative path\n   */\n  readonly value: TItem | undefined;\n\n  /**\n   * Child nodes by subfolder\n   */\n  readonly children: ReadonlyMap<string, IReadonlyPathTrieNode<TItem>> | undefined;\n}\n\n/**\n * JSON-serializable representation of a node in a {@link LookupByPath} trie.\n *\n * @beta\n */\nexport interface ISerializedPathTrieNode {\n  /**\n   * Index into the `values` array of the containing {@link ILookupByPathJson}.\n   * If `undefined`, this node has no associated value.\n   */\n  valueIndex?: number;\n\n  /**\n   * Child nodes keyed by path segment.\n   */\n  children?: Record<string, ISerializedPathTrieNode>;\n}\n\n/**\n * JSON-serializable representation of a {@link LookupByPath} instance.\n *\n * @remarks\n * The `values` array stores each unique value exactly once (by reference identity).\n * Nodes in the tree reference values by their index in this array, which ensures that\n * reference equality is preserved across serialization and deserialization.\n *\n * @beta\n */\nexport interface ILookupByPathJson<TSerialized> {\n  /**\n   * The path delimiter used by the serialized trie.\n   */\n  delimiter: string;\n\n  /**\n   * Array of serialized values. Nodes in the tree reference values by their index in this array.\n   * Using an array with index-based references preserves reference equality: if multiple nodes\n   * share the same value (by reference), they will reference the same index.\n   */\n  values: TSerialized[];\n\n  /**\n   * The serialized tree structure.\n   */\n  tree: ISerializedPathTrieNode;\n}\n\ninterface IPrefixEntry {\n  /**\n   * The prefix that was matched\n   */\n  prefix: string;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n}\n\n/**\n * Object containing both the matched item and the start index of the remainder of the query.\n *\n * @beta\n */\nexport interface IPrefixMatch<TItem extends {}> {\n  /**\n   * The item that matched the prefix\n   */\n  value: TItem;\n\n  /**\n   * The index of the first character after the matched prefix\n   */\n  index: number;\n\n  /**\n   * The last match found (with a shorter prefix), if any\n   */\n  lastMatch?: IPrefixMatch<TItem>;\n}\n\n/**\n * The readonly component of `LookupByPath`, to simplify unit testing.\n *\n * @beta\n */\nexport interface IReadonlyLookupByPath<TItem extends {}> extends Iterable<[string, TItem]> {\n  /**\n   * Searches for the item associated with `childPath`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPath('foo/baz'); // returns 1\n   * trie.findChildPath('foo/bar/baz'); // returns 2\n   * ```\n   */\n  findChildPath(childPath: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Searches for the item for which the recorded prefix is the longest matching prefix of `query`.\n   * Obtains both the item and the length of the matched prefix, so that the remainder of the path can be\n   * extracted.\n   *\n   * @returns the found item and the length of the matched prefix, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findLongestPrefixMatch('foo/baz'); // returns { item: 1, index: 3 }\n   * trie.findLongestPrefixMatch('foo/bar/baz'); // returns { item: 2, index: 7 }\n   * ```\n   */\n  findLongestPrefixMatch(query: string, delimiter?: string): IPrefixMatch<TItem> | undefined;\n\n  /**\n   * Searches for the item associated with `childPathSegments`, or the nearest ancestor of that path that\n   * has an associated item.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   *\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * trie.findChildPathFromSegments(['foo', 'baz']); // returns 1\n   * trie.findChildPathFromSegments(['foo','bar', 'baz']); // returns 2\n   * ```\n   */\n  findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined;\n\n  /**\n   * Determines if an entry exists exactly at the specified path.\n   *\n   * @returns `true` if an entry exists at the specified path, `false` otherwise\n   */\n  has(query: string, delimiter?: string): boolean;\n\n  /**\n   * Retrieves the entry that exists exactly at the specified path, if any.\n   *\n   * @returns The entry that exists exactly at the specified path, or `undefined` if no entry exists.\n   */\n  get(query: string, delimiter?: string): TItem | undefined;\n\n  /**\n   * Gets the number of entries in this trie.\n   *\n   * @returns The number of entries in this trie.\n   */\n  get size(): number;\n\n  /**\n   * @returns The root node of the trie, corresponding to the path ''\n   */\n  get tree(): IReadonlyPathTrieNode<TItem>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   * @example\n   * ```ts\n   * const trie = new LookupByPath([['foo', 1], ['foo/bar', 2]]);\n   * [...trie.entries(undefined, ',')); // returns [['foo', 1], ['foo,bar', 2]]\n   * ```\n   */\n  entries(query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Iterates over the entries in this trie.\n   *\n   * @param query - An optional query. If specified only entries that start with the query will be returned.\n   *\n   * @returns An iterator over the entries under the specified query (or the root if no query is specified).\n   * @remarks\n   * Keys in the returned iterator use the provided delimiter to join segments.\n   * Iteration order is not specified.\n   */\n  [Symbol.iterator](query?: string, delimiter?: string): IterableIterator<[string, TItem]>;\n\n  /**\n   * Groups the provided map of info by the nearest entry in the trie that contains the path. If the path\n   * is not found in the trie, the info is ignored.\n   *\n   * @returns The grouped info, grouped by the nearest entry in the trie that contains the path\n   *\n   * @param infoByPath - The info to be grouped, keyed by path\n   */\n  groupByChild<TInfo>(infoByPath: Map<string, TInfo>, delimiter?: string): Map<TItem, Map<string, TInfo>>;\n\n  /**\n   * Retrieves the trie node at the specified prefix, if it exists.\n   *\n   * @param query - The prefix to check for\n   * @param delimiter - The path delimiter\n   * @returns The trie node at the specified prefix, or `undefined` if no node was found\n   */\n  getNodeAtPrefix(query: string, delimiter?: string): IReadonlyPathTrieNode<TItem> | undefined;\n\n  /**\n   * Serializes this `LookupByPath` instance to a JSON-compatible representation.\n   *\n   * @param serializeValue - A function that converts a value of type `TItem` to a JSON-serializable form.\n   * @returns A JSON-serializable representation of this trie.\n   *\n   * @remarks\n   * Values that are reference-equal will be serialized once and referenced by index, ensuring\n   * that reference equality is preserved when deserialized via {@link LookupByPath.fromJson}.\n   */\n  toJson<TSerialized>(serializeValue: (value: TItem) => TSerialized): ILookupByPathJson<TSerialized>;\n}\n\n/**\n * This class is used to associate path-like-strings, such as those returned by `git` commands,\n * with entities that correspond with ancestor folders, such as Rush Projects or npm packages.\n *\n * It is optimized for efficiently locating the nearest ancestor path with an associated value.\n *\n * It is implemented as a Trie (https://en.wikipedia.org/wiki/Trie) data structure, with each edge\n * being a path segment.\n *\n * @example\n * ```ts\n * const trie = new LookupByPath([['foo', 1], ['bar', 2], ['foo/bar', 3]]);\n * trie.findChildPath('foo'); // returns 1\n * trie.findChildPath('foo/baz'); // returns 1\n * trie.findChildPath('baz'); // returns undefined\n * trie.findChildPath('foo/bar/baz'); returns 3\n * trie.findChildPath('bar/foo/bar'); returns 2\n * ```\n * @beta\n */\nexport class LookupByPath<TItem extends {}> implements IReadonlyLookupByPath<TItem> {\n  /**\n   * The delimiter used to split paths\n   */\n  public readonly delimiter: string;\n\n  /**\n   * The root node of the trie, corresponding to the path ''\n   */\n  private readonly _root: IPathTrieNode<TItem>;\n\n  /**\n   * The number of entries in this trie.\n   */\n  private _size: number;\n\n  /**\n   * Constructs a new `LookupByPath`\n   *\n   * @param entries - Initial path-value pairs to populate the trie.\n   */\n  public constructor(entries?: Iterable<[string, TItem]>, delimiter?: string) {\n    this._root = {\n      value: undefined,\n      children: undefined\n    };\n\n    this.delimiter = delimiter ?? '/';\n    this._size = 0;\n\n    if (entries) {\n      for (const [path, item] of entries) {\n        this.setItem(path, item);\n      }\n    }\n  }\n\n  /**\n   * Iterates over the segments of a serialized path.\n   *\n   * @example\n   *\n   * `LookupByPath.iteratePathSegments('foo/bar/baz')` yields 'foo', 'bar', 'baz'\n   *\n   * `LookupByPath.iteratePathSegments('foo\\\\bar\\\\baz', '\\\\')` yields 'foo', 'bar', 'baz'\n   */\n  public static *iteratePathSegments(serializedPath: string, delimiter: string = '/'): Iterable<string> {\n    for (const prefixMatch of this._iteratePrefixes(serializedPath, delimiter)) {\n      yield prefixMatch.prefix;\n    }\n  }\n\n  private static *_iteratePrefixes(input: string, delimiter: string = '/'): Iterable<IPrefixEntry> {\n    if (!input) {\n      return;\n    }\n\n    let previousIndex: number = 0;\n    let nextIndex: number = input.indexOf(delimiter);\n\n    // Leading segments\n    while (nextIndex >= 0) {\n      yield {\n        prefix: input.slice(previousIndex, nextIndex),\n        index: nextIndex\n      };\n      previousIndex = nextIndex + 1;\n      nextIndex = input.indexOf(delimiter, previousIndex);\n    }\n\n    // Last segment\n    if (previousIndex < input.length) {\n      yield {\n        prefix: input.slice(previousIndex, input.length),\n        index: input.length\n      };\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.size}\n   */\n  public get size(): number {\n    return this._size;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.tree}\n   */\n  public get tree(): IReadonlyPathTrieNode<TItem> {\n    return this._root;\n  }\n\n  /**\n   * Deletes all entries from this `LookupByPath` instance.\n   *\n   * @returns this, for chained calls\n   */\n  public clear(): this {\n    this._root.value = undefined;\n    this._root.children = undefined;\n    this._size = 0;\n    return this;\n  }\n\n  /**\n   * Associates the value with the specified serialized path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItem(serializedPath: string, value: TItem, delimiter: string = this.delimiter): this {\n    return this.setItemFromSegments(LookupByPath.iteratePathSegments(serializedPath, delimiter), value);\n  }\n\n  /**\n   * Deletes an item if it exists.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if the item was found and deleted, `false` otherwise\n   * @remarks\n   * If the node has children with values, they will be retained.\n   */\n  public deleteItem(query: string, delimeter: string = this.delimiter): boolean {\n    const node: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (node?.value !== undefined) {\n      node.value = undefined;\n      this._size--;\n      return true;\n    }\n\n    return false;\n  }\n\n  /**\n   * Deletes an item and all its children.\n   * @param query - The path to the item to delete\n   * @param delimeter - Optional override delimeter for parsing the query\n   * @returns `true` if any nodes were deleted, `false` otherwise\n   */\n  public deleteSubtree(query: string, delimeter: string = this.delimiter): boolean {\n    const queryNode: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);\n    if (!queryNode) {\n      return false;\n    }\n\n    const queue: IPathTrieNode<TItem>[] = [queryNode];\n    let removed: number = 0;\n    while (queue.length > 0) {\n      const node: IPathTrieNode<TItem> = queue.pop()!;\n      if (node.value !== undefined) {\n        node.value = undefined;\n        removed++;\n      }\n      if (node.children) {\n        for (const child of node.children.values()) {\n          queue.push(child);\n        }\n        node.children.clear();\n      }\n    }\n\n    this._size -= removed;\n    return removed > 0;\n  }\n\n  /**\n   * Associates the value with the specified path.\n   * If a value is already associated, will overwrite.\n   *\n   * @returns this, for chained calls\n   */\n  public setItemFromSegments(pathSegments: Iterable<string>, value: TItem): this {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const segment of pathSegments) {\n      if (!node.children) {\n        node.children = new Map();\n      }\n      let child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n      if (!child) {\n        node.children.set(\n          segment,\n          (child = {\n            value: undefined,\n            children: undefined\n          })\n        );\n      }\n      node = child;\n    }\n    if (node.value === undefined) {\n      this._size++;\n    }\n    node.value = value;\n\n    return this;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPath(childPath: string, delimiter: string = this.delimiter): TItem | undefined {\n    return this.findChildPathFromSegments(LookupByPath.iteratePathSegments(childPath, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findLongestPrefixMatch(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPrefixMatch<TItem> | undefined {\n    return this._findLongestPrefixMatch(LookupByPath._iteratePrefixes(query, delimiter));\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public findChildPathFromSegments(childPathSegments: Iterable<string>): TItem | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: TItem | undefined = node.value;\n    // Trivial cases\n    if (node.children) {\n      for (const segment of childPathSegments) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(segment);\n        if (!child) {\n          break;\n        }\n        node = child;\n        best = node.value ?? best;\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public has(key: string, delimiter: string = this.delimiter): boolean {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public get(key: string, delimiter: string = this.delimiter): TItem | undefined {\n    const match: IPrefixMatch<TItem> | undefined = this.findLongestPrefixMatch(key, delimiter);\n    return match?.index === key.length ? match.value : undefined;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public groupByChild<TInfo>(\n    infoByPath: Map<string, TInfo>,\n    delimiter: string = this.delimiter\n  ): Map<TItem, Map<string, TInfo>> {\n    const groupedInfoByChild: Map<TItem, Map<string, TInfo>> = new Map();\n\n    for (const [path, info] of infoByPath) {\n      const child: TItem | undefined = this.findChildPath(path, delimiter);\n      if (child === undefined) {\n        continue;\n      }\n      let groupedInfo: Map<string, TInfo> | undefined = groupedInfoByChild.get(child);\n      if (!groupedInfo) {\n        groupedInfo = new Map();\n        groupedInfoByChild.set(child, groupedInfo);\n      }\n      groupedInfo.set(path, info);\n    }\n\n    return groupedInfoByChild;\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public *entries(query?: string, delimiter: string = this.delimiter): IterableIterator<[string, TItem]> {\n    let root: IPathTrieNode<TItem> | undefined;\n    if (query) {\n      root = this._findNodeAtPrefix(query, delimiter);\n      if (!root) {\n        return;\n      }\n    } else {\n      root = this._root;\n    }\n\n    const stack: [string, IPathTrieNode<TItem>][] = [[query ?? '', root]];\n    while (stack.length > 0) {\n      const [prefix, node] = stack.pop()!;\n      if (node.value !== undefined) {\n        yield [prefix, node.value];\n      }\n      if (node.children) {\n        for (const [segment, child] of node.children) {\n          stack.push([prefix ? `${prefix}${delimiter}${segment}` : segment, child]);\n        }\n      }\n    }\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public [Symbol.iterator](\n    query?: string,\n    delimiter: string = this.delimiter\n  ): IterableIterator<[string, TItem]> {\n    return this.entries(query, delimiter);\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath}\n   */\n  public getNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IReadonlyPathTrieNode<TItem> | undefined {\n    return this._findNodeAtPrefix(query, delimiter);\n  }\n\n  /**\n   * {@inheritdoc IReadonlyLookupByPath.toJson}\n   */\n  public toJson<TSerialized>(\n    serializeValue: (value: TItem) => TSerialized\n  ): ILookupByPathJson<TSerialized> {\n    const valueToIndex: Map<TItem, number> = new Map();\n    const values: TSerialized[] = [];\n\n    const getOrAddValueIndex: (value: TItem) => number = (value: TItem) => {\n      let index: number | undefined = valueToIndex.get(value);\n      if (index === undefined) {\n        index = values.length;\n        valueToIndex.set(value, index);\n        values.push(serializeValue(value));\n      }\n      return index;\n    };\n\n    const serializeNode: (node: IPathTrieNode<TItem>) => ISerializedPathTrieNode = (\n      node: IPathTrieNode<TItem>\n    ) => {\n      const result: ISerializedPathTrieNode = {};\n\n      if (node.value !== undefined) {\n        result.valueIndex = getOrAddValueIndex(node.value);\n      }\n\n      if (node.children && node.children.size > 0) {\n        const children: Record<string, ISerializedPathTrieNode> = Object.create(null);\n        for (const [segment, child] of node.children) {\n          children[segment] = serializeNode(child);\n        }\n        result.children = children;\n      }\n\n      return result;\n    };\n\n    return {\n      delimiter: this.delimiter,\n      values,\n      tree: serializeNode(this._root)\n    };\n  }\n\n  /**\n   * Deserializes a `LookupByPath` instance from a JSON representation previously\n   * created by {@link LookupByPath.toJson}.\n   *\n   * @param json - The JSON representation to deserialize.\n   * @param deserializeValue - A function that converts a serialized value back to its original type.\n   * @returns A new `LookupByPath` instance.\n   *\n   * @remarks\n   * Reference equality is preserved: if multiple nodes in the serialized trie pointed at the same\n   * value (i.e., the same index in the `values` array), the deserialized nodes will share the same\n   * object reference.\n   */\n  public static fromJson<TItem extends {}, TSerialized>(\n    json: ILookupByPathJson<TSerialized>,\n    deserializeValue: (serialized: TSerialized) => TItem\n  ): LookupByPath<TItem> {\n    const deserializedValues: TItem[] = json.values.map(deserializeValue);\n\n    const result: LookupByPath<TItem> = new LookupByPath<TItem>(undefined, json.delimiter);\n\n    const deserializeNode: (\n      jsonNode: ISerializedPathTrieNode,\n      targetNode: IPathTrieNode<TItem>\n    ) => void = (jsonNode: ISerializedPathTrieNode, targetNode: IPathTrieNode<TItem>) => {\n      if (jsonNode.valueIndex !== undefined) {\n        targetNode.value = deserializedValues[jsonNode.valueIndex];\n        result._size++;\n      }\n\n      if (jsonNode.children) {\n        targetNode.children = new Map();\n        for (const [segment, childJson] of Object.entries(jsonNode.children)) {\n          const childNode: IPathTrieNode<TItem> = {\n            value: undefined,\n            children: undefined\n          };\n          targetNode.children.set(segment, childNode);\n          deserializeNode(childJson, childNode);\n        }\n      }\n    };\n\n    deserializeNode(json.tree, result._root);\n\n    return result;\n  }\n\n  /**\n   * Iterates through progressively longer prefixes of a given string and returns as soon\n   * as the number of candidate items that match the prefix are 1 or 0.\n   *\n   * If a match is present, returns the matched itme and the length of the matched prefix.\n   *\n   * @returns the found item, or `undefined` if no item was found\n   */\n  private _findLongestPrefixMatch(prefixes: Iterable<IPrefixEntry>): IPrefixMatch<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    let best: IPrefixMatch<TItem> | undefined = node.value\n      ? {\n          value: node.value,\n          index: 0,\n          lastMatch: undefined\n        }\n      : undefined;\n    // Trivial cases\n    if (node.children) {\n      for (const { prefix: hash, index } of prefixes) {\n        const child: IPathTrieNode<TItem> | undefined = node.children.get(hash);\n        if (!child) {\n          break;\n        }\n        node = child;\n        if (node.value !== undefined) {\n          best = {\n            value: node.value,\n            index,\n            lastMatch: best\n          };\n        }\n        if (!node.children) {\n          break;\n        }\n      }\n    }\n\n    return best;\n  }\n\n  /**\n   * Finds the node at the specified path, or `undefined` if no node was found.\n   *\n   * @param query - The path to the node to search for\n   * @returns The trie node at the specified path, or `undefined` if no node was found\n   */\n  private _findNodeAtPrefix(\n    query: string,\n    delimiter: string = this.delimiter\n  ): IPathTrieNode<TItem> | undefined {\n    let node: IPathTrieNode<TItem> = this._root;\n    for (const { prefix } of LookupByPath._iteratePrefixes(query, delimiter)) {\n      if (!node.children) {\n        return undefined;\n      }\n      const child: IPathTrieNode<TItem> | undefined = node.children.get(prefix);\n      if (!child) {\n        return undefined;\n      }\n      node = child;\n    }\n    return node;\n  }\n}\n"]}

package.json

 {
   "name": "@rushstack/lookup-by-path",
-  "version": "0.9.10",
+  "version": "0.10.0",
   "description": "Strongly typed trie data structure for path and URL-like strings.",
@@ -45,4 +45,4 @@ "main": "./lib-commonjs/index.js",
     "eslint": "~9.37.0",
-    "@rushstack/heft": "1.2.10",
-    "local-node-rig": "1.0.0"
+    "local-node-rig": "1.0.0",
+    "@rushstack/heft": "1.2.11"
   },
@@ -49,0 +49,0 @@ "peerDependencies": {

No alert changes

Improved metrics

Total package byte prevSize

188434

16.94%

Lines of code

2869

11.72%

No dependency changes