Socket
Socket
Sign inDemoInstall

minisearch

Package Overview
Dependencies
Maintainers
1
Versions
81
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

minisearch - npm Package Compare versions

Comparing version 6.3.0 to 7.0.0

dist/cjs/index.d.cts
dist/cjs/SearchableMap.d.cts
dist/es/index.d.ts
dist/es/SearchableMap.d.ts

77

CHANGELOG.md

@@ -5,8 +5,27 @@ # Changelog

# v6.3.0
## v7.0.0
This is a major release, but the only real breaking change is that it targets
ES6 (ES2015) and later. This means that it will not work in legacy browsers,
most notably Internet Explorer 11 and earlier (by now well below 1% global
usage according to https://caniuse.com).
- [breaking change] Target ES6 (ES2015) and later, dropping support for
Internet Explorer 11 and earlier.
- [breaking change] Better TypeScript type of `combineWith` search option
values, catching invalid operators at compile time. Note that this is a
breaking change only if one was using unlikely weird casing for the
`combineWith` option. For example, `AND`, `and`, `And` are all still valid,
but `aNd` won't compile anymore.
- More informative error when specifying an invalid value for `combineWith`
in JavaScript (in TypeScript this would be a compile time error)
- Use the Unicode flag to simplify the tokenizer regular expression
- Add `loadJSONAsync` method, to load a serialized index asynchronously
## v6.3.0 - 2023-11-22
- Add `queryTerms` array to the search results. This is useful to determine
which query terms were matched by each search result.
# v6.2.0
## v6.2.0 - 2023-10-26

@@ -17,3 +36,3 @@ - Add the possibility to search for the special value `MiniSearch.wildcard` to

# v6.1.0
## v6.1.0 - 2023-05-15

@@ -26,3 +45,3 @@ - Add `getStoredFields` method to retrieve the stored fields for a document

# v6.0.1
## v6.0.1 - 2023-02-01

@@ -37,3 +56,3 @@ - [fix] The `boost` search option now does not interfere with the `fields`

# v6.0.0
## v6.0.0 - 2022-12-01

@@ -77,3 +96,3 @@ This is a major release. The most notable change is the addition of `discard`,

# v5.1.0
## v5.1.0

@@ -84,3 +103,3 @@ - The `processTerm` option can now also expand a single term into several

# v5.0.0
## v5.0.0

@@ -112,3 +131,3 @@ This is a major release. The main change is an improved scoring algorithm based

# v4.0.3
## v4.0.3

@@ -118,7 +137,7 @@ - [fix] Fix regression causing stored fields not being saved in some

# v4.0.2
## v4.0.2
- [fix] Fix match data on mixed prefix and fuzzy search
# v4.0.1
## v4.0.1

@@ -133,3 +152,3 @@ - [fix] Fix an issue with scoring, causing a result matching both fuzzy and

# v4.0.0
## v4.0.0

@@ -176,3 +195,3 @@ - [breaking change] The serialization format was changed, to abstract away the

# v3.3.0
## v3.3.0

@@ -182,3 +201,3 @@ - Add `maxFuzzy` search option, to limit the maximum edit distance for fuzzy

# v3.2.0
## v3.2.0

@@ -188,3 +207,3 @@ - Add AND_NOT combinator to subtract results of a subquery from another (for

# v3.1.0
## v3.1.0

@@ -194,3 +213,3 @@ - Add possibility for advanced combination of subqueries as query expression

# v3.0.4
## v3.0.4

@@ -200,7 +219,7 @@ - [fix] Keep radix tree property (no node with a single child) after removal

# v3.0.3
## v3.0.3
- [fix] Adjust data about field lengths upon document removal
# v3.0.2
## v3.0.2

@@ -210,3 +229,3 @@ - [fix] `addAllAsync` now allows events to be processed between chunks, avoid

# v3.0.1
## v3.0.1

@@ -217,3 +236,3 @@ - [fix] Fix type signature of `removeAll` to allow calling it with no

# v3.0.0
## v3.0.0

@@ -234,11 +253,11 @@ This major version ports the source code to TypeScript. That made it possible

# v2.6.2
## v2.6.2
- [fix] Improve TypeScript types: default generic document type is `any`, not `object`
# v2.6.1
## v2.6.1
- No change from 2.6.0
# v2.6.0
## v2.6.0

@@ -248,3 +267,3 @@ - Better TypeScript typings using generics, letting the user (optionally)

# v2.5.1
## v2.5.1

@@ -254,3 +273,3 @@ - [fix] Fix document removal when using a custom `extractField` function

# v2.5.0
## v2.5.0

@@ -260,3 +279,3 @@ - Make `idField` extraction customizeable and consistent with other fields,

# v2.4.1
## v2.4.1

@@ -269,3 +288,3 @@ - [fix] Fix issue with the term `constructor` (reported by

# v2.4.0
## v2.4.0

@@ -276,3 +295,3 @@ - Convert field value to string before tokenization and indexing. This makes

# v2.3.1
## v2.3.1

@@ -282,7 +301,7 @@ - Version `v2.3.1` mistakenly did not contain the commit adding `removeAll`,

# v2.3.0
## v2.3.0
- Add `removeAll` method, to remove many documents, or all documents, at once.
# v2.2.2
## v2.2.2

@@ -289,0 +308,0 @@ - Avoid destructuring variables named with an underscore prefix. This plays

530

dist/es/SearchableMap.js

@@ -1,93 +0,42 @@

/******************************************************************************
Copyright (c) Microsoft Corporation.
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
***************************************************************************** */
/* global Reflect, Promise, SuppressedError, Symbol */
function __values(o) {
var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0;
if (m) return m.call(o);
if (o && typeof o.length === "number") return {
next: function () {
if (o && i >= o.length) o = void 0;
return { value: o && o[i++], done: !o };
}
};
throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
}
function __read(o, n) {
var m = typeof Symbol === "function" && o[Symbol.iterator];
if (!m) return o;
var i = m.call(o), r, ar = [], e;
try {
while ((n === void 0 || n-- > 0) && !(r = i.next()).done) ar.push(r.value);
}
catch (error) { e = { error: error }; }
finally {
try {
if (r && !r.done && (m = i["return"])) m.call(i);
}
finally { if (e) throw e.error; }
}
return ar;
}
typeof SuppressedError === "function" ? SuppressedError : function (error, suppressed, message) {
var e = new Error(message);
return e.name = "SuppressedError", e.error = error, e.suppressed = suppressed, e;
};
/** @ignore */
var ENTRIES = 'ENTRIES';
const ENTRIES = 'ENTRIES';
/** @ignore */
var KEYS = 'KEYS';
const KEYS = 'KEYS';
/** @ignore */
var VALUES = 'VALUES';
const VALUES = 'VALUES';
/** @ignore */
var LEAF = '';
const LEAF = '';
/**
* @private
*/
var TreeIterator = /** @class */ (function () {
function TreeIterator(set, type) {
var node = set._tree;
var keys = Array.from(node.keys());
class TreeIterator {
constructor(set, type) {
const node = set._tree;
const keys = Array.from(node.keys());
this.set = set;
this._type = type;
this._path = keys.length > 0 ? [{ node: node, keys: keys }] : [];
this._path = keys.length > 0 ? [{ node, keys }] : [];
}
TreeIterator.prototype.next = function () {
var value = this.dive();
next() {
const value = this.dive();
this.backtrack();
return value;
};
TreeIterator.prototype.dive = function () {
}
dive() {
if (this._path.length === 0) {
return { done: true, value: undefined };
}
var _a = last$1(this._path), node = _a.node, keys = _a.keys;
const { node, keys } = last$1(this._path);
if (last$1(keys) === LEAF) {
return { done: false, value: this.result() };
}
var child = node.get(last$1(keys));
const child = node.get(last$1(keys));
this._path.push({ node: child, keys: Array.from(child.keys()) });
return this.dive();
};
TreeIterator.prototype.backtrack = function () {
}
backtrack() {
if (this._path.length === 0) {
return;
}
var keys = last$1(this._path).keys;
const keys = last$1(this._path).keys;
keys.pop();

@@ -99,16 +48,13 @@ if (keys.length > 0) {

this.backtrack();
};
TreeIterator.prototype.key = function () {
}
key() {
return this.set._prefix + this._path
.map(function (_a) {
var keys = _a.keys;
return last$1(keys);
})
.filter(function (key) { return key !== LEAF; })
.map(({ keys }) => last$1(keys))
.filter(key => key !== LEAF)
.join('');
};
TreeIterator.prototype.value = function () {
}
value() {
return last$1(this._path).node.get(LEAF);
};
TreeIterator.prototype.result = function () {
}
result() {
switch (this._type) {

@@ -119,28 +65,28 @@ case VALUES: return this.value();

}
};
TreeIterator.prototype[Symbol.iterator] = function () {
}
[Symbol.iterator]() {
return this;
};
return TreeIterator;
}());
var last$1 = function (array) {
}
}
const last$1 = (array) => {
return array[array.length - 1];
};
/* eslint-disable no-labels */
/**
* @ignore
*/
var fuzzySearch = function (node, query, maxDistance) {
var results = new Map();
const fuzzySearch = (node, query, maxDistance) => {
const results = new Map();
if (query === undefined)
return results;
// Number of columns in the Levenshtein matrix.
var n = query.length + 1;
const n = query.length + 1;
// Matching terms can never be longer than N + maxDistance.
var m = n + maxDistance;
const m = n + maxDistance;
// Fill first matrix row and column with numbers: 0 1 2 3 ...
var matrix = new Uint8Array(m * n).fill(maxDistance + 1);
for (var j = 0; j < n; ++j)
const matrix = new Uint8Array(m * n).fill(maxDistance + 1);
for (let j = 0; j < n; ++j)
matrix[j] = j;
for (var i = 1; i < m; ++i)
for (let i = 1; i < m; ++i)
matrix[i * n] = i;

@@ -163,62 +109,52 @@ recurse(node, query, maxDistance, results, matrix, 1, n, '');

// ^ term in radix tree, rows are added and removed as needed
var recurse = function (node, query, maxDistance, results, matrix, m, n, prefix) {
var e_1, _a;
var offset = m * n;
try {
key: for (var _b = __values(node.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var key = _c.value;
if (key === LEAF) {
// We've reached a leaf node. Check if the edit distance acceptable and
// store the result if it is.
var distance = matrix[offset - 1];
if (distance <= maxDistance) {
results.set(prefix, [node.get(key), distance]);
}
const recurse = (node, query, maxDistance, results, matrix, m, n, prefix) => {
const offset = m * n;
key: for (const key of node.keys()) {
if (key === LEAF) {
// We've reached a leaf node. Check if the edit distance acceptable and
// store the result if it is.
const distance = matrix[offset - 1];
if (distance <= maxDistance) {
results.set(prefix, [node.get(key), distance]);
}
else {
// Iterate over all characters in the key. Update the Levenshtein matrix
// and check if the minimum distance in the last row is still within the
// maximum edit distance. If it is, we can recurse over all child nodes.
var i = m;
for (var pos = 0; pos < key.length; ++pos, ++i) {
var char = key[pos];
var thisRowOffset = n * i;
var prevRowOffset = thisRowOffset - n;
// Set the first column based on the previous row, and initialize the
// minimum distance in the current row.
var minDistance = matrix[thisRowOffset];
var jmin = Math.max(0, i - maxDistance - 1);
var jmax = Math.min(n - 1, i + maxDistance);
// Iterate over remaining columns (characters in the query).
for (var j = jmin; j < jmax; ++j) {
var different = char !== query[j];
// It might make sense to only read the matrix positions used for
// deletion/insertion if the characters are different. But we want to
// avoid conditional reads for performance reasons.
var rpl = matrix[prevRowOffset + j] + +different;
var del = matrix[prevRowOffset + j + 1] + 1;
var ins = matrix[thisRowOffset + j] + 1;
var dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins);
if (dist < minDistance)
minDistance = dist;
}
// Because distance will never decrease, we can stop. There will be no
// matching child nodes.
if (minDistance > maxDistance) {
continue key;
}
}
else {
// Iterate over all characters in the key. Update the Levenshtein matrix
// and check if the minimum distance in the last row is still within the
// maximum edit distance. If it is, we can recurse over all child nodes.
let i = m;
for (let pos = 0; pos < key.length; ++pos, ++i) {
const char = key[pos];
const thisRowOffset = n * i;
const prevRowOffset = thisRowOffset - n;
// Set the first column based on the previous row, and initialize the
// minimum distance in the current row.
let minDistance = matrix[thisRowOffset];
const jmin = Math.max(0, i - maxDistance - 1);
const jmax = Math.min(n - 1, i + maxDistance);
// Iterate over remaining columns (characters in the query).
for (let j = jmin; j < jmax; ++j) {
const different = char !== query[j];
// It might make sense to only read the matrix positions used for
// deletion/insertion if the characters are different. But we want to
// avoid conditional reads for performance reasons.
const rpl = matrix[prevRowOffset + j] + +different;
const del = matrix[prevRowOffset + j + 1] + 1;
const ins = matrix[thisRowOffset + j] + 1;
const dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins);
if (dist < minDistance)
minDistance = dist;
}
recurse(node.get(key), query, maxDistance, results, matrix, i, n, prefix + key);
// Because distance will never decrease, we can stop. There will be no
// matching child nodes.
if (minDistance > maxDistance) {
continue key;
}
}
recurse(node.get(key), query, maxDistance, results, matrix, i, n, prefix + key);
}
}
catch (e_1_1) { e_1 = { error: e_1_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_1) throw e_1.error; }
}
};
/* eslint-disable no-labels */
/**

@@ -238,3 +174,3 @@ * A class implementing the same interface as a standard JavaScript

*/
var SearchableMap = /** @class */ (function () {
class SearchableMap {
/**

@@ -249,5 +185,3 @@ * The constructor is normally called without arguments, creating an empty

*/
function SearchableMap(tree, prefix) {
if (tree === void 0) { tree = new Map(); }
if (prefix === void 0) { prefix = ''; }
constructor(tree = new Map(), prefix = '') {
this._size = undefined;

@@ -286,37 +220,26 @@ this._tree = tree;

*/
SearchableMap.prototype.atPrefix = function (prefix) {
var e_1, _a;
atPrefix(prefix) {
if (!prefix.startsWith(this._prefix)) {
throw new Error('Mismatched prefix');
}
var _b = __read(trackDown(this._tree, prefix.slice(this._prefix.length)), 2), node = _b[0], path = _b[1];
const [node, path] = trackDown(this._tree, prefix.slice(this._prefix.length));
if (node === undefined) {
var _c = __read(last(path), 2), parentNode = _c[0], key = _c[1];
try {
for (var _d = __values(parentNode.keys()), _e = _d.next(); !_e.done; _e = _d.next()) {
var k = _e.value;
if (k !== LEAF && k.startsWith(key)) {
var node_1 = new Map();
node_1.set(k.slice(key.length), parentNode.get(k));
return new SearchableMap(node_1, prefix);
}
const [parentNode, key] = last(path);
for (const k of parentNode.keys()) {
if (k !== LEAF && k.startsWith(key)) {
const node = new Map();
node.set(k.slice(key.length), parentNode.get(k));
return new SearchableMap(node, prefix);
}
}
catch (e_1_1) { e_1 = { error: e_1_1 }; }
finally {
try {
if (_e && !_e.done && (_a = _d.return)) _a.call(_d);
}
finally { if (e_1) throw e_1.error; }
}
}
return new SearchableMap(node, prefix);
};
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/clear
*/
SearchableMap.prototype.clear = function () {
clear() {
this._size = undefined;
this._tree.clear();
};
}
/**

@@ -326,6 +249,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/delete

*/
SearchableMap.prototype.delete = function (key) {
delete(key) {
this._size = undefined;
return remove(this._tree, key);
};
}
/**

@@ -335,5 +258,5 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/entries

*/
SearchableMap.prototype.entries = function () {
entries() {
return new TreeIterator(this, ENTRIES);
};
}
/**

@@ -343,18 +266,7 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/forEach

*/
SearchableMap.prototype.forEach = function (fn) {
var e_2, _a;
try {
for (var _b = __values(this), _c = _b.next(); !_c.done; _c = _b.next()) {
var _d = __read(_c.value, 2), key = _d[0], value = _d[1];
fn(key, value, this);
}
forEach(fn) {
for (const [key, value] of this) {
fn(key, value, this);
}
catch (e_2_1) { e_2 = { error: e_2_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_2) throw e_2.error; }
}
};
}
/**

@@ -388,5 +300,5 @@ * Returns a Map of all the entries that have a key within the given edit

*/
SearchableMap.prototype.fuzzyGet = function (key, maxEditDistance) {
fuzzyGet(key, maxEditDistance) {
return fuzzySearch(this._tree, key, maxEditDistance);
};
}
/**

@@ -398,6 +310,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/get

*/
SearchableMap.prototype.get = function (key) {
var node = lookup(this._tree, key);
get(key) {
const node = lookup(this._tree, key);
return node !== undefined ? node.get(LEAF) : undefined;
};
}
/**

@@ -408,6 +320,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/has

*/
SearchableMap.prototype.has = function (key) {
var node = lookup(this._tree, key);
has(key) {
const node = lookup(this._tree, key);
return node !== undefined && node.has(LEAF);
};
}
/**

@@ -417,5 +329,5 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/keys

*/
SearchableMap.prototype.keys = function () {
keys() {
return new TreeIterator(this, KEYS);
};
}
/**

@@ -427,3 +339,3 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/set

*/
SearchableMap.prototype.set = function (key, value) {
set(key, value) {
if (typeof key !== 'string') {

@@ -433,24 +345,20 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
const node = createPath(this._tree, key);
node.set(LEAF, value);
return this;
};
Object.defineProperty(SearchableMap.prototype, "size", {
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
*/
get: function () {
if (this._size) {
return this._size;
}
/** @ignore */
this._size = 0;
var iter = this.entries();
while (!iter.next().done)
this._size += 1;
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
*/
get size() {
if (this._size) {
return this._size;
},
enumerable: false,
configurable: true
});
}
/** @ignore */
this._size = 0;
const iter = this.entries();
while (!iter.next().done)
this._size += 1;
return this._size;
}
/**

@@ -476,3 +384,3 @@ * Updates the value at the given key using the provided function. The function

*/
SearchableMap.prototype.update = function (key, fn) {
update(key, fn) {
if (typeof key !== 'string') {

@@ -482,6 +390,6 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
const node = createPath(this._tree, key);
node.set(LEAF, fn(node.get(LEAF)));
return this;
};
}
/**

@@ -503,3 +411,3 @@ * Fetches the value of the given key. If the value does not exist, calls the

*/
SearchableMap.prototype.fetch = function (key, initial) {
fetch(key, initial) {
if (typeof key !== 'string') {

@@ -509,4 +417,4 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
var value = node.get(LEAF);
const node = createPath(this._tree, key);
let value = node.get(LEAF);
if (value === undefined) {

@@ -516,3 +424,3 @@ node.set(LEAF, value = initial());

return value;
};
}
/**

@@ -522,11 +430,11 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/values

*/
SearchableMap.prototype.values = function () {
values() {
return new TreeIterator(this, VALUES);
};
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@iterator
*/
SearchableMap.prototype[Symbol.iterator] = function () {
[Symbol.iterator]() {
return this.entries();
};
}
/**

@@ -538,20 +446,9 @@ * Creates a {@link SearchableMap} from an `Iterable` of entries

*/
SearchableMap.from = function (entries) {
var e_3, _a;
var tree = new SearchableMap();
try {
for (var entries_1 = __values(entries), entries_1_1 = entries_1.next(); !entries_1_1.done; entries_1_1 = entries_1.next()) {
var _b = __read(entries_1_1.value, 2), key = _b[0], value = _b[1];
tree.set(key, value);
}
static from(entries) {
const tree = new SearchableMap();
for (const [key, value] of entries) {
tree.set(key, value);
}
catch (e_3_1) { e_3 = { error: e_3_1 }; }
finally {
try {
if (entries_1_1 && !entries_1_1.done && (_a = entries_1.return)) _a.call(entries_1);
}
finally { if (e_3) throw e_3.error; }
}
return tree;
};
}
/**

@@ -563,52 +460,28 @@ * Creates a {@link SearchableMap} from the iterable properties of a JavaScript object

*/
SearchableMap.fromObject = function (object) {
static fromObject(object) {
return SearchableMap.from(Object.entries(object));
};
return SearchableMap;
}());
var trackDown = function (tree, key, path) {
var e_4, _a;
if (path === void 0) { path = []; }
}
}
const trackDown = (tree, key, path = []) => {
if (key.length === 0 || tree == null) {
return [tree, path];
}
try {
for (var _b = __values(tree.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
if (k !== LEAF && key.startsWith(k)) {
path.push([tree, k]); // performance: update in place
return trackDown(tree.get(k), key.slice(k.length), path);
}
for (const k of tree.keys()) {
if (k !== LEAF && key.startsWith(k)) {
path.push([tree, k]); // performance: update in place
return trackDown(tree.get(k), key.slice(k.length), path);
}
}
catch (e_4_1) { e_4 = { error: e_4_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_4) throw e_4.error; }
}
path.push([tree, key]); // performance: update in place
return trackDown(undefined, '', path);
};
var lookup = function (tree, key) {
var e_5, _a;
const lookup = (tree, key) => {
if (key.length === 0 || tree == null) {
return tree;
}
try {
for (var _b = __values(tree.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
if (k !== LEAF && key.startsWith(k)) {
return lookup(tree.get(k), key.slice(k.length));
}
for (const k of tree.keys()) {
if (k !== LEAF && key.startsWith(k)) {
return lookup(tree.get(k), key.slice(k.length));
}
}
catch (e_5_1) { e_5 = { error: e_5_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_5) throw e_5.error; }
}
};

@@ -618,44 +491,33 @@ // Create a path in the radix tree for the given key, and returns the deepest

// string operations and recursion for performance.
var createPath = function (node, key) {
var e_6, _a;
var keyLength = key.length;
outer: for (var pos = 0; node && pos < keyLength;) {
try {
for (var _b = (e_6 = void 0, __values(node.keys())), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
// Check whether this key is a candidate: the first characters must match.
if (k !== LEAF && key[pos] === k[0]) {
var len = Math.min(keyLength - pos, k.length);
// Advance offset to the point where key and k no longer match.
var offset = 1;
while (offset < len && key[pos + offset] === k[offset])
++offset;
var child_1 = node.get(k);
if (offset === k.length) {
// The existing key is shorter than the key we need to create.
node = child_1;
}
else {
// Partial match: we need to insert an intermediate node to contain
// both the existing subtree and the new node.
var intermediate = new Map();
intermediate.set(k.slice(offset), child_1);
node.set(key.slice(pos, pos + offset), intermediate);
node.delete(k);
node = intermediate;
}
pos += offset;
continue outer;
const createPath = (node, key) => {
const keyLength = key.length;
outer: for (let pos = 0; node && pos < keyLength;) {
for (const k of node.keys()) {
// Check whether this key is a candidate: the first characters must match.
if (k !== LEAF && key[pos] === k[0]) {
const len = Math.min(keyLength - pos, k.length);
// Advance offset to the point where key and k no longer match.
let offset = 1;
while (offset < len && key[pos + offset] === k[offset])
++offset;
const child = node.get(k);
if (offset === k.length) {
// The existing key is shorter than the key we need to create.
node = child;
}
else {
// Partial match: we need to insert an intermediate node to contain
// both the existing subtree and the new node.
const intermediate = new Map();
intermediate.set(k.slice(offset), child);
node.set(key.slice(pos, pos + offset), intermediate);
node.delete(k);
node = intermediate;
}
pos += offset;
continue outer;
}
}
catch (e_6_1) { e_6 = { error: e_6_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_6) throw e_6.error; }
}
// Create a final child node to contain the final suffix of the key.
var child = new Map();
const child = new Map();
node.set(key.slice(pos), child);

@@ -666,4 +528,4 @@ return child;

};
var remove = function (tree, key) {
var _a = __read(trackDown(tree, key), 2), node = _a[0], path = _a[1];
const remove = (tree, key) => {
const [node, path] = trackDown(tree, key);
if (node === undefined) {

@@ -677,11 +539,11 @@ return;

else if (node.size === 1) {
var _b = __read(node.entries().next().value, 2), key_1 = _b[0], value = _b[1];
merge(path, key_1, value);
const [key, value] = node.entries().next().value;
merge(path, key, value);
}
};
var cleanup = function (path) {
const cleanup = (path) => {
if (path.length === 0) {
return;
}
var _a = __read(last(path), 2), node = _a[0], key = _a[1];
const [node, key] = last(path);
node.delete(key);

@@ -692,17 +554,17 @@ if (node.size === 0) {

else if (node.size === 1) {
var _b = __read(node.entries().next().value, 2), key_2 = _b[0], value = _b[1];
if (key_2 !== LEAF) {
merge(path.slice(0, -1), key_2, value);
const [key, value] = node.entries().next().value;
if (key !== LEAF) {
merge(path.slice(0, -1), key, value);
}
}
};
var merge = function (path, key, value) {
const merge = (path, key, value) => {
if (path.length === 0) {
return;
}
var _a = __read(last(path), 2), node = _a[0], nodeKey = _a[1];
const [node, nodeKey] = last(path);
node.set(nodeKey + key, value);
node.delete(nodeKey);
};
var last = function (array) {
const last = (array) => {
return array[array.length - 1];

@@ -709,0 +571,0 @@ };

530

dist/es5m/SearchableMap.js

@@ -1,93 +0,42 @@

/******************************************************************************
Copyright (c) Microsoft Corporation.
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
***************************************************************************** */
/* global Reflect, Promise, SuppressedError, Symbol */
function __values(o) {
var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0;
if (m) return m.call(o);
if (o && typeof o.length === "number") return {
next: function () {
if (o && i >= o.length) o = void 0;
return { value: o && o[i++], done: !o };
}
};
throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
}
function __read(o, n) {
var m = typeof Symbol === "function" && o[Symbol.iterator];
if (!m) return o;
var i = m.call(o), r, ar = [], e;
try {
while ((n === void 0 || n-- > 0) && !(r = i.next()).done) ar.push(r.value);
}
catch (error) { e = { error: error }; }
finally {
try {
if (r && !r.done && (m = i["return"])) m.call(i);
}
finally { if (e) throw e.error; }
}
return ar;
}
typeof SuppressedError === "function" ? SuppressedError : function (error, suppressed, message) {
var e = new Error(message);
return e.name = "SuppressedError", e.error = error, e.suppressed = suppressed, e;
};
/** @ignore */
var ENTRIES = 'ENTRIES';
const ENTRIES = 'ENTRIES';
/** @ignore */
var KEYS = 'KEYS';
const KEYS = 'KEYS';
/** @ignore */
var VALUES = 'VALUES';
const VALUES = 'VALUES';
/** @ignore */
var LEAF = '';
const LEAF = '';
/**
* @private
*/
var TreeIterator = /** @class */ (function () {
function TreeIterator(set, type) {
var node = set._tree;
var keys = Array.from(node.keys());
class TreeIterator {
constructor(set, type) {
const node = set._tree;
const keys = Array.from(node.keys());
this.set = set;
this._type = type;
this._path = keys.length > 0 ? [{ node: node, keys: keys }] : [];
this._path = keys.length > 0 ? [{ node, keys }] : [];
}
TreeIterator.prototype.next = function () {
var value = this.dive();
next() {
const value = this.dive();
this.backtrack();
return value;
};
TreeIterator.prototype.dive = function () {
}
dive() {
if (this._path.length === 0) {
return { done: true, value: undefined };
}
var _a = last$1(this._path), node = _a.node, keys = _a.keys;
const { node, keys } = last$1(this._path);
if (last$1(keys) === LEAF) {
return { done: false, value: this.result() };
}
var child = node.get(last$1(keys));
const child = node.get(last$1(keys));
this._path.push({ node: child, keys: Array.from(child.keys()) });
return this.dive();
};
TreeIterator.prototype.backtrack = function () {
}
backtrack() {
if (this._path.length === 0) {
return;
}
var keys = last$1(this._path).keys;
const keys = last$1(this._path).keys;
keys.pop();

@@ -99,16 +48,13 @@ if (keys.length > 0) {

this.backtrack();
};
TreeIterator.prototype.key = function () {
}
key() {
return this.set._prefix + this._path
.map(function (_a) {
var keys = _a.keys;
return last$1(keys);
})
.filter(function (key) { return key !== LEAF; })
.map(({ keys }) => last$1(keys))
.filter(key => key !== LEAF)
.join('');
};
TreeIterator.prototype.value = function () {
}
value() {
return last$1(this._path).node.get(LEAF);
};
TreeIterator.prototype.result = function () {
}
result() {
switch (this._type) {

@@ -119,28 +65,28 @@ case VALUES: return this.value();

}
};
TreeIterator.prototype[Symbol.iterator] = function () {
}
[Symbol.iterator]() {
return this;
};
return TreeIterator;
}());
var last$1 = function (array) {
}
}
const last$1 = (array) => {
return array[array.length - 1];
};
/* eslint-disable no-labels */
/**
* @ignore
*/
var fuzzySearch = function (node, query, maxDistance) {
var results = new Map();
const fuzzySearch = (node, query, maxDistance) => {
const results = new Map();
if (query === undefined)
return results;
// Number of columns in the Levenshtein matrix.
var n = query.length + 1;
const n = query.length + 1;
// Matching terms can never be longer than N + maxDistance.
var m = n + maxDistance;
const m = n + maxDistance;
// Fill first matrix row and column with numbers: 0 1 2 3 ...
var matrix = new Uint8Array(m * n).fill(maxDistance + 1);
for (var j = 0; j < n; ++j)
const matrix = new Uint8Array(m * n).fill(maxDistance + 1);
for (let j = 0; j < n; ++j)
matrix[j] = j;
for (var i = 1; i < m; ++i)
for (let i = 1; i < m; ++i)
matrix[i * n] = i;

@@ -163,62 +109,52 @@ recurse(node, query, maxDistance, results, matrix, 1, n, '');

// ^ term in radix tree, rows are added and removed as needed
var recurse = function (node, query, maxDistance, results, matrix, m, n, prefix) {
var e_1, _a;
var offset = m * n;
try {
key: for (var _b = __values(node.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var key = _c.value;
if (key === LEAF) {
// We've reached a leaf node. Check if the edit distance acceptable and
// store the result if it is.
var distance = matrix[offset - 1];
if (distance <= maxDistance) {
results.set(prefix, [node.get(key), distance]);
}
const recurse = (node, query, maxDistance, results, matrix, m, n, prefix) => {
const offset = m * n;
key: for (const key of node.keys()) {
if (key === LEAF) {
// We've reached a leaf node. Check if the edit distance acceptable and
// store the result if it is.
const distance = matrix[offset - 1];
if (distance <= maxDistance) {
results.set(prefix, [node.get(key), distance]);
}
else {
// Iterate over all characters in the key. Update the Levenshtein matrix
// and check if the minimum distance in the last row is still within the
// maximum edit distance. If it is, we can recurse over all child nodes.
var i = m;
for (var pos = 0; pos < key.length; ++pos, ++i) {
var char = key[pos];
var thisRowOffset = n * i;
var prevRowOffset = thisRowOffset - n;
// Set the first column based on the previous row, and initialize the
// minimum distance in the current row.
var minDistance = matrix[thisRowOffset];
var jmin = Math.max(0, i - maxDistance - 1);
var jmax = Math.min(n - 1, i + maxDistance);
// Iterate over remaining columns (characters in the query).
for (var j = jmin; j < jmax; ++j) {
var different = char !== query[j];
// It might make sense to only read the matrix positions used for
// deletion/insertion if the characters are different. But we want to
// avoid conditional reads for performance reasons.
var rpl = matrix[prevRowOffset + j] + +different;
var del = matrix[prevRowOffset + j + 1] + 1;
var ins = matrix[thisRowOffset + j] + 1;
var dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins);
if (dist < minDistance)
minDistance = dist;
}
// Because distance will never decrease, we can stop. There will be no
// matching child nodes.
if (minDistance > maxDistance) {
continue key;
}
}
else {
// Iterate over all characters in the key. Update the Levenshtein matrix
// and check if the minimum distance in the last row is still within the
// maximum edit distance. If it is, we can recurse over all child nodes.
let i = m;
for (let pos = 0; pos < key.length; ++pos, ++i) {
const char = key[pos];
const thisRowOffset = n * i;
const prevRowOffset = thisRowOffset - n;
// Set the first column based on the previous row, and initialize the
// minimum distance in the current row.
let minDistance = matrix[thisRowOffset];
const jmin = Math.max(0, i - maxDistance - 1);
const jmax = Math.min(n - 1, i + maxDistance);
// Iterate over remaining columns (characters in the query).
for (let j = jmin; j < jmax; ++j) {
const different = char !== query[j];
// It might make sense to only read the matrix positions used for
// deletion/insertion if the characters are different. But we want to
// avoid conditional reads for performance reasons.
const rpl = matrix[prevRowOffset + j] + +different;
const del = matrix[prevRowOffset + j + 1] + 1;
const ins = matrix[thisRowOffset + j] + 1;
const dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins);
if (dist < minDistance)
minDistance = dist;
}
recurse(node.get(key), query, maxDistance, results, matrix, i, n, prefix + key);
// Because distance will never decrease, we can stop. There will be no
// matching child nodes.
if (minDistance > maxDistance) {
continue key;
}
}
recurse(node.get(key), query, maxDistance, results, matrix, i, n, prefix + key);
}
}
catch (e_1_1) { e_1 = { error: e_1_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_1) throw e_1.error; }
}
};
/* eslint-disable no-labels */
/**

@@ -238,3 +174,3 @@ * A class implementing the same interface as a standard JavaScript

*/
var SearchableMap = /** @class */ (function () {
class SearchableMap {
/**

@@ -249,5 +185,3 @@ * The constructor is normally called without arguments, creating an empty

*/
function SearchableMap(tree, prefix) {
if (tree === void 0) { tree = new Map(); }
if (prefix === void 0) { prefix = ''; }
constructor(tree = new Map(), prefix = '') {
this._size = undefined;

@@ -286,37 +220,26 @@ this._tree = tree;

*/
SearchableMap.prototype.atPrefix = function (prefix) {
var e_1, _a;
atPrefix(prefix) {
if (!prefix.startsWith(this._prefix)) {
throw new Error('Mismatched prefix');
}
var _b = __read(trackDown(this._tree, prefix.slice(this._prefix.length)), 2), node = _b[0], path = _b[1];
const [node, path] = trackDown(this._tree, prefix.slice(this._prefix.length));
if (node === undefined) {
var _c = __read(last(path), 2), parentNode = _c[0], key = _c[1];
try {
for (var _d = __values(parentNode.keys()), _e = _d.next(); !_e.done; _e = _d.next()) {
var k = _e.value;
if (k !== LEAF && k.startsWith(key)) {
var node_1 = new Map();
node_1.set(k.slice(key.length), parentNode.get(k));
return new SearchableMap(node_1, prefix);
}
const [parentNode, key] = last(path);
for (const k of parentNode.keys()) {
if (k !== LEAF && k.startsWith(key)) {
const node = new Map();
node.set(k.slice(key.length), parentNode.get(k));
return new SearchableMap(node, prefix);
}
}
catch (e_1_1) { e_1 = { error: e_1_1 }; }
finally {
try {
if (_e && !_e.done && (_a = _d.return)) _a.call(_d);
}
finally { if (e_1) throw e_1.error; }
}
}
return new SearchableMap(node, prefix);
};
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/clear
*/
SearchableMap.prototype.clear = function () {
clear() {
this._size = undefined;
this._tree.clear();
};
}
/**

@@ -326,6 +249,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/delete

*/
SearchableMap.prototype.delete = function (key) {
delete(key) {
this._size = undefined;
return remove(this._tree, key);
};
}
/**

@@ -335,5 +258,5 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/entries

*/
SearchableMap.prototype.entries = function () {
entries() {
return new TreeIterator(this, ENTRIES);
};
}
/**

@@ -343,18 +266,7 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/forEach

*/
SearchableMap.prototype.forEach = function (fn) {
var e_2, _a;
try {
for (var _b = __values(this), _c = _b.next(); !_c.done; _c = _b.next()) {
var _d = __read(_c.value, 2), key = _d[0], value = _d[1];
fn(key, value, this);
}
forEach(fn) {
for (const [key, value] of this) {
fn(key, value, this);
}
catch (e_2_1) { e_2 = { error: e_2_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_2) throw e_2.error; }
}
};
}
/**

@@ -388,5 +300,5 @@ * Returns a Map of all the entries that have a key within the given edit

*/
SearchableMap.prototype.fuzzyGet = function (key, maxEditDistance) {
fuzzyGet(key, maxEditDistance) {
return fuzzySearch(this._tree, key, maxEditDistance);
};
}
/**

@@ -398,6 +310,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/get

*/
SearchableMap.prototype.get = function (key) {
var node = lookup(this._tree, key);
get(key) {
const node = lookup(this._tree, key);
return node !== undefined ? node.get(LEAF) : undefined;
};
}
/**

@@ -408,6 +320,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/has

*/
SearchableMap.prototype.has = function (key) {
var node = lookup(this._tree, key);
has(key) {
const node = lookup(this._tree, key);
return node !== undefined && node.has(LEAF);
};
}
/**

@@ -417,5 +329,5 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/keys

*/
SearchableMap.prototype.keys = function () {
keys() {
return new TreeIterator(this, KEYS);
};
}
/**

@@ -427,3 +339,3 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/set

*/
SearchableMap.prototype.set = function (key, value) {
set(key, value) {
if (typeof key !== 'string') {

@@ -433,24 +345,20 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
const node = createPath(this._tree, key);
node.set(LEAF, value);
return this;
};
Object.defineProperty(SearchableMap.prototype, "size", {
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
*/
get: function () {
if (this._size) {
return this._size;
}
/** @ignore */
this._size = 0;
var iter = this.entries();
while (!iter.next().done)
this._size += 1;
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
*/
get size() {
if (this._size) {
return this._size;
},
enumerable: false,
configurable: true
});
}
/** @ignore */
this._size = 0;
const iter = this.entries();
while (!iter.next().done)
this._size += 1;
return this._size;
}
/**

@@ -476,3 +384,3 @@ * Updates the value at the given key using the provided function. The function

*/
SearchableMap.prototype.update = function (key, fn) {
update(key, fn) {
if (typeof key !== 'string') {

@@ -482,6 +390,6 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
const node = createPath(this._tree, key);
node.set(LEAF, fn(node.get(LEAF)));
return this;
};
}
/**

@@ -503,3 +411,3 @@ * Fetches the value of the given key. If the value does not exist, calls the

*/
SearchableMap.prototype.fetch = function (key, initial) {
fetch(key, initial) {
if (typeof key !== 'string') {

@@ -509,4 +417,4 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
var value = node.get(LEAF);
const node = createPath(this._tree, key);
let value = node.get(LEAF);
if (value === undefined) {

@@ -516,3 +424,3 @@ node.set(LEAF, value = initial());

return value;
};
}
/**

@@ -522,11 +430,11 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/values

*/
SearchableMap.prototype.values = function () {
values() {
return new TreeIterator(this, VALUES);
};
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@iterator
*/
SearchableMap.prototype[Symbol.iterator] = function () {
[Symbol.iterator]() {
return this.entries();
};
}
/**

@@ -538,20 +446,9 @@ * Creates a {@link SearchableMap} from an `Iterable` of entries

*/
SearchableMap.from = function (entries) {
var e_3, _a;
var tree = new SearchableMap();
try {
for (var entries_1 = __values(entries), entries_1_1 = entries_1.next(); !entries_1_1.done; entries_1_1 = entries_1.next()) {
var _b = __read(entries_1_1.value, 2), key = _b[0], value = _b[1];
tree.set(key, value);
}
static from(entries) {
const tree = new SearchableMap();
for (const [key, value] of entries) {
tree.set(key, value);
}
catch (e_3_1) { e_3 = { error: e_3_1 }; }
finally {
try {
if (entries_1_1 && !entries_1_1.done && (_a = entries_1.return)) _a.call(entries_1);
}
finally { if (e_3) throw e_3.error; }
}
return tree;
};
}
/**

@@ -563,52 +460,28 @@ * Creates a {@link SearchableMap} from the iterable properties of a JavaScript object

*/
SearchableMap.fromObject = function (object) {
static fromObject(object) {
return SearchableMap.from(Object.entries(object));
};
return SearchableMap;
}());
var trackDown = function (tree, key, path) {
var e_4, _a;
if (path === void 0) { path = []; }
}
}
const trackDown = (tree, key, path = []) => {
if (key.length === 0 || tree == null) {
return [tree, path];
}
try {
for (var _b = __values(tree.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
if (k !== LEAF && key.startsWith(k)) {
path.push([tree, k]); // performance: update in place
return trackDown(tree.get(k), key.slice(k.length), path);
}
for (const k of tree.keys()) {
if (k !== LEAF && key.startsWith(k)) {
path.push([tree, k]); // performance: update in place
return trackDown(tree.get(k), key.slice(k.length), path);
}
}
catch (e_4_1) { e_4 = { error: e_4_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_4) throw e_4.error; }
}
path.push([tree, key]); // performance: update in place
return trackDown(undefined, '', path);
};
var lookup = function (tree, key) {
var e_5, _a;
const lookup = (tree, key) => {
if (key.length === 0 || tree == null) {
return tree;
}
try {
for (var _b = __values(tree.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
if (k !== LEAF && key.startsWith(k)) {
return lookup(tree.get(k), key.slice(k.length));
}
for (const k of tree.keys()) {
if (k !== LEAF && key.startsWith(k)) {
return lookup(tree.get(k), key.slice(k.length));
}
}
catch (e_5_1) { e_5 = { error: e_5_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_5) throw e_5.error; }
}
};

@@ -618,44 +491,33 @@ // Create a path in the radix tree for the given key, and returns the deepest

// string operations and recursion for performance.
var createPath = function (node, key) {
var e_6, _a;
var keyLength = key.length;
outer: for (var pos = 0; node && pos < keyLength;) {
try {
for (var _b = (e_6 = void 0, __values(node.keys())), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
// Check whether this key is a candidate: the first characters must match.
if (k !== LEAF && key[pos] === k[0]) {
var len = Math.min(keyLength - pos, k.length);
// Advance offset to the point where key and k no longer match.
var offset = 1;
while (offset < len && key[pos + offset] === k[offset])
++offset;
var child_1 = node.get(k);
if (offset === k.length) {
// The existing key is shorter than the key we need to create.
node = child_1;
}
else {
// Partial match: we need to insert an intermediate node to contain
// both the existing subtree and the new node.
var intermediate = new Map();
intermediate.set(k.slice(offset), child_1);
node.set(key.slice(pos, pos + offset), intermediate);
node.delete(k);
node = intermediate;
}
pos += offset;
continue outer;
const createPath = (node, key) => {
const keyLength = key.length;
outer: for (let pos = 0; node && pos < keyLength;) {
for (const k of node.keys()) {
// Check whether this key is a candidate: the first characters must match.
if (k !== LEAF && key[pos] === k[0]) {
const len = Math.min(keyLength - pos, k.length);
// Advance offset to the point where key and k no longer match.
let offset = 1;
while (offset < len && key[pos + offset] === k[offset])
++offset;
const child = node.get(k);
if (offset === k.length) {
// The existing key is shorter than the key we need to create.
node = child;
}
else {
// Partial match: we need to insert an intermediate node to contain
// both the existing subtree and the new node.
const intermediate = new Map();
intermediate.set(k.slice(offset), child);
node.set(key.slice(pos, pos + offset), intermediate);
node.delete(k);
node = intermediate;
}
pos += offset;
continue outer;
}
}
catch (e_6_1) { e_6 = { error: e_6_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_6) throw e_6.error; }
}
// Create a final child node to contain the final suffix of the key.
var child = new Map();
const child = new Map();
node.set(key.slice(pos), child);

@@ -666,4 +528,4 @@ return child;

};
var remove = function (tree, key) {
var _a = __read(trackDown(tree, key), 2), node = _a[0], path = _a[1];
const remove = (tree, key) => {
const [node, path] = trackDown(tree, key);
if (node === undefined) {

@@ -677,11 +539,11 @@ return;

else if (node.size === 1) {
var _b = __read(node.entries().next().value, 2), key_1 = _b[0], value = _b[1];
merge(path, key_1, value);
const [key, value] = node.entries().next().value;
merge(path, key, value);
}
};
var cleanup = function (path) {
const cleanup = (path) => {
if (path.length === 0) {
return;
}
var _a = __read(last(path), 2), node = _a[0], key = _a[1];
const [node, key] = last(path);
node.delete(key);

@@ -692,17 +554,17 @@ if (node.size === 0) {

else if (node.size === 1) {
var _b = __read(node.entries().next().value, 2), key_2 = _b[0], value = _b[1];
if (key_2 !== LEAF) {
merge(path.slice(0, -1), key_2, value);
const [key, value] = node.entries().next().value;
if (key !== LEAF) {
merge(path.slice(0, -1), key, value);
}
}
};
var merge = function (path, key, value) {
const merge = (path, key, value) => {
if (path.length === 0) {
return;
}
var _a = __read(last(path), 2), node = _a[0], nodeKey = _a[1];
const [node, nodeKey] = last(path);
node.set(nodeKey + key, value);
node.delete(nodeKey);
};
var last = function (array) {
const last = (array) => {
return array[array.length - 1];

@@ -709,0 +571,0 @@ };

530

dist/umd/SearchableMap.js

@@ -7,94 +7,43 @@ (function (global, factory) {

/******************************************************************************
Copyright (c) Microsoft Corporation.
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
***************************************************************************** */
/* global Reflect, Promise, SuppressedError, Symbol */
function __values(o) {
var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0;
if (m) return m.call(o);
if (o && typeof o.length === "number") return {
next: function () {
if (o && i >= o.length) o = void 0;
return { value: o && o[i++], done: !o };
}
};
throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
}
function __read(o, n) {
var m = typeof Symbol === "function" && o[Symbol.iterator];
if (!m) return o;
var i = m.call(o), r, ar = [], e;
try {
while ((n === void 0 || n-- > 0) && !(r = i.next()).done) ar.push(r.value);
}
catch (error) { e = { error: error }; }
finally {
try {
if (r && !r.done && (m = i["return"])) m.call(i);
}
finally { if (e) throw e.error; }
}
return ar;
}
typeof SuppressedError === "function" ? SuppressedError : function (error, suppressed, message) {
var e = new Error(message);
return e.name = "SuppressedError", e.error = error, e.suppressed = suppressed, e;
};
/** @ignore */
var ENTRIES = 'ENTRIES';
const ENTRIES = 'ENTRIES';
/** @ignore */
var KEYS = 'KEYS';
const KEYS = 'KEYS';
/** @ignore */
var VALUES = 'VALUES';
const VALUES = 'VALUES';
/** @ignore */
var LEAF = '';
const LEAF = '';
/**
* @private
*/
var TreeIterator = /** @class */ (function () {
function TreeIterator(set, type) {
var node = set._tree;
var keys = Array.from(node.keys());
class TreeIterator {
constructor(set, type) {
const node = set._tree;
const keys = Array.from(node.keys());
this.set = set;
this._type = type;
this._path = keys.length > 0 ? [{ node: node, keys: keys }] : [];
this._path = keys.length > 0 ? [{ node, keys }] : [];
}
TreeIterator.prototype.next = function () {
var value = this.dive();
next() {
const value = this.dive();
this.backtrack();
return value;
};
TreeIterator.prototype.dive = function () {
}
dive() {
if (this._path.length === 0) {
return { done: true, value: undefined };
}
var _a = last$1(this._path), node = _a.node, keys = _a.keys;
const { node, keys } = last$1(this._path);
if (last$1(keys) === LEAF) {
return { done: false, value: this.result() };
}
var child = node.get(last$1(keys));
const child = node.get(last$1(keys));
this._path.push({ node: child, keys: Array.from(child.keys()) });
return this.dive();
};
TreeIterator.prototype.backtrack = function () {
}
backtrack() {
if (this._path.length === 0) {
return;
}
var keys = last$1(this._path).keys;
const keys = last$1(this._path).keys;
keys.pop();

@@ -106,16 +55,13 @@ if (keys.length > 0) {

this.backtrack();
};
TreeIterator.prototype.key = function () {
}
key() {
return this.set._prefix + this._path
.map(function (_a) {
var keys = _a.keys;
return last$1(keys);
})
.filter(function (key) { return key !== LEAF; })
.map(({ keys }) => last$1(keys))
.filter(key => key !== LEAF)
.join('');
};
TreeIterator.prototype.value = function () {
}
value() {
return last$1(this._path).node.get(LEAF);
};
TreeIterator.prototype.result = function () {
}
result() {
switch (this._type) {

@@ -126,28 +72,28 @@ case VALUES: return this.value();

}
};
TreeIterator.prototype[Symbol.iterator] = function () {
}
[Symbol.iterator]() {
return this;
};
return TreeIterator;
}());
var last$1 = function (array) {
}
}
const last$1 = (array) => {
return array[array.length - 1];
};
/* eslint-disable no-labels */
/**
* @ignore
*/
var fuzzySearch = function (node, query, maxDistance) {
var results = new Map();
const fuzzySearch = (node, query, maxDistance) => {
const results = new Map();
if (query === undefined)
return results;
// Number of columns in the Levenshtein matrix.
var n = query.length + 1;
const n = query.length + 1;
// Matching terms can never be longer than N + maxDistance.
var m = n + maxDistance;
const m = n + maxDistance;
// Fill first matrix row and column with numbers: 0 1 2 3 ...
var matrix = new Uint8Array(m * n).fill(maxDistance + 1);
for (var j = 0; j < n; ++j)
const matrix = new Uint8Array(m * n).fill(maxDistance + 1);
for (let j = 0; j < n; ++j)
matrix[j] = j;
for (var i = 1; i < m; ++i)
for (let i = 1; i < m; ++i)
matrix[i * n] = i;

@@ -170,62 +116,52 @@ recurse(node, query, maxDistance, results, matrix, 1, n, '');

// ^ term in radix tree, rows are added and removed as needed
var recurse = function (node, query, maxDistance, results, matrix, m, n, prefix) {
var e_1, _a;
var offset = m * n;
try {
key: for (var _b = __values(node.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var key = _c.value;
if (key === LEAF) {
// We've reached a leaf node. Check if the edit distance acceptable and
// store the result if it is.
var distance = matrix[offset - 1];
if (distance <= maxDistance) {
results.set(prefix, [node.get(key), distance]);
}
const recurse = (node, query, maxDistance, results, matrix, m, n, prefix) => {
const offset = m * n;
key: for (const key of node.keys()) {
if (key === LEAF) {
// We've reached a leaf node. Check if the edit distance acceptable and
// store the result if it is.
const distance = matrix[offset - 1];
if (distance <= maxDistance) {
results.set(prefix, [node.get(key), distance]);
}
else {
// Iterate over all characters in the key. Update the Levenshtein matrix
// and check if the minimum distance in the last row is still within the
// maximum edit distance. If it is, we can recurse over all child nodes.
var i = m;
for (var pos = 0; pos < key.length; ++pos, ++i) {
var char = key[pos];
var thisRowOffset = n * i;
var prevRowOffset = thisRowOffset - n;
// Set the first column based on the previous row, and initialize the
// minimum distance in the current row.
var minDistance = matrix[thisRowOffset];
var jmin = Math.max(0, i - maxDistance - 1);
var jmax = Math.min(n - 1, i + maxDistance);
// Iterate over remaining columns (characters in the query).
for (var j = jmin; j < jmax; ++j) {
var different = char !== query[j];
// It might make sense to only read the matrix positions used for
// deletion/insertion if the characters are different. But we want to
// avoid conditional reads for performance reasons.
var rpl = matrix[prevRowOffset + j] + +different;
var del = matrix[prevRowOffset + j + 1] + 1;
var ins = matrix[thisRowOffset + j] + 1;
var dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins);
if (dist < minDistance)
minDistance = dist;
}
// Because distance will never decrease, we can stop. There will be no
// matching child nodes.
if (minDistance > maxDistance) {
continue key;
}
}
else {
// Iterate over all characters in the key. Update the Levenshtein matrix
// and check if the minimum distance in the last row is still within the
// maximum edit distance. If it is, we can recurse over all child nodes.
let i = m;
for (let pos = 0; pos < key.length; ++pos, ++i) {
const char = key[pos];
const thisRowOffset = n * i;
const prevRowOffset = thisRowOffset - n;
// Set the first column based on the previous row, and initialize the
// minimum distance in the current row.
let minDistance = matrix[thisRowOffset];
const jmin = Math.max(0, i - maxDistance - 1);
const jmax = Math.min(n - 1, i + maxDistance);
// Iterate over remaining columns (characters in the query).
for (let j = jmin; j < jmax; ++j) {
const different = char !== query[j];
// It might make sense to only read the matrix positions used for
// deletion/insertion if the characters are different. But we want to
// avoid conditional reads for performance reasons.
const rpl = matrix[prevRowOffset + j] + +different;
const del = matrix[prevRowOffset + j + 1] + 1;
const ins = matrix[thisRowOffset + j] + 1;
const dist = matrix[thisRowOffset + j + 1] = Math.min(rpl, del, ins);
if (dist < minDistance)
minDistance = dist;
}
recurse(node.get(key), query, maxDistance, results, matrix, i, n, prefix + key);
// Because distance will never decrease, we can stop. There will be no
// matching child nodes.
if (minDistance > maxDistance) {
continue key;
}
}
recurse(node.get(key), query, maxDistance, results, matrix, i, n, prefix + key);
}
}
catch (e_1_1) { e_1 = { error: e_1_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_1) throw e_1.error; }
}
};
/* eslint-disable no-labels */
/**

@@ -245,3 +181,3 @@ * A class implementing the same interface as a standard JavaScript

*/
var SearchableMap = /** @class */ (function () {
class SearchableMap {
/**

@@ -256,5 +192,3 @@ * The constructor is normally called without arguments, creating an empty

*/
function SearchableMap(tree, prefix) {
if (tree === void 0) { tree = new Map(); }
if (prefix === void 0) { prefix = ''; }
constructor(tree = new Map(), prefix = '') {
this._size = undefined;

@@ -293,37 +227,26 @@ this._tree = tree;

*/
SearchableMap.prototype.atPrefix = function (prefix) {
var e_1, _a;
atPrefix(prefix) {
if (!prefix.startsWith(this._prefix)) {
throw new Error('Mismatched prefix');
}
var _b = __read(trackDown(this._tree, prefix.slice(this._prefix.length)), 2), node = _b[0], path = _b[1];
const [node, path] = trackDown(this._tree, prefix.slice(this._prefix.length));
if (node === undefined) {
var _c = __read(last(path), 2), parentNode = _c[0], key = _c[1];
try {
for (var _d = __values(parentNode.keys()), _e = _d.next(); !_e.done; _e = _d.next()) {
var k = _e.value;
if (k !== LEAF && k.startsWith(key)) {
var node_1 = new Map();
node_1.set(k.slice(key.length), parentNode.get(k));
return new SearchableMap(node_1, prefix);
}
const [parentNode, key] = last(path);
for (const k of parentNode.keys()) {
if (k !== LEAF && k.startsWith(key)) {
const node = new Map();
node.set(k.slice(key.length), parentNode.get(k));
return new SearchableMap(node, prefix);
}
}
catch (e_1_1) { e_1 = { error: e_1_1 }; }
finally {
try {
if (_e && !_e.done && (_a = _d.return)) _a.call(_d);
}
finally { if (e_1) throw e_1.error; }
}
}
return new SearchableMap(node, prefix);
};
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/clear
*/
SearchableMap.prototype.clear = function () {
clear() {
this._size = undefined;
this._tree.clear();
};
}
/**

@@ -333,6 +256,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/delete

*/
SearchableMap.prototype.delete = function (key) {
delete(key) {
this._size = undefined;
return remove(this._tree, key);
};
}
/**

@@ -342,5 +265,5 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/entries

*/
SearchableMap.prototype.entries = function () {
entries() {
return new TreeIterator(this, ENTRIES);
};
}
/**

@@ -350,18 +273,7 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/forEach

*/
SearchableMap.prototype.forEach = function (fn) {
var e_2, _a;
try {
for (var _b = __values(this), _c = _b.next(); !_c.done; _c = _b.next()) {
var _d = __read(_c.value, 2), key = _d[0], value = _d[1];
fn(key, value, this);
}
forEach(fn) {
for (const [key, value] of this) {
fn(key, value, this);
}
catch (e_2_1) { e_2 = { error: e_2_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_2) throw e_2.error; }
}
};
}
/**

@@ -395,5 +307,5 @@ * Returns a Map of all the entries that have a key within the given edit

*/
SearchableMap.prototype.fuzzyGet = function (key, maxEditDistance) {
fuzzyGet(key, maxEditDistance) {
return fuzzySearch(this._tree, key, maxEditDistance);
};
}
/**

@@ -405,6 +317,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/get

*/
SearchableMap.prototype.get = function (key) {
var node = lookup(this._tree, key);
get(key) {
const node = lookup(this._tree, key);
return node !== undefined ? node.get(LEAF) : undefined;
};
}
/**

@@ -415,6 +327,6 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/has

*/
SearchableMap.prototype.has = function (key) {
var node = lookup(this._tree, key);
has(key) {
const node = lookup(this._tree, key);
return node !== undefined && node.has(LEAF);
};
}
/**

@@ -424,5 +336,5 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/keys

*/
SearchableMap.prototype.keys = function () {
keys() {
return new TreeIterator(this, KEYS);
};
}
/**

@@ -434,3 +346,3 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/set

*/
SearchableMap.prototype.set = function (key, value) {
set(key, value) {
if (typeof key !== 'string') {

@@ -440,24 +352,20 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
const node = createPath(this._tree, key);
node.set(LEAF, value);
return this;
};
Object.defineProperty(SearchableMap.prototype, "size", {
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
*/
get: function () {
if (this._size) {
return this._size;
}
/** @ignore */
this._size = 0;
var iter = this.entries();
while (!iter.next().done)
this._size += 1;
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
*/
get size() {
if (this._size) {
return this._size;
},
enumerable: false,
configurable: true
});
}
/** @ignore */
this._size = 0;
const iter = this.entries();
while (!iter.next().done)
this._size += 1;
return this._size;
}
/**

@@ -483,3 +391,3 @@ * Updates the value at the given key using the provided function. The function

*/
SearchableMap.prototype.update = function (key, fn) {
update(key, fn) {
if (typeof key !== 'string') {

@@ -489,6 +397,6 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
const node = createPath(this._tree, key);
node.set(LEAF, fn(node.get(LEAF)));
return this;
};
}
/**

@@ -510,3 +418,3 @@ * Fetches the value of the given key. If the value does not exist, calls the

*/
SearchableMap.prototype.fetch = function (key, initial) {
fetch(key, initial) {
if (typeof key !== 'string') {

@@ -516,4 +424,4 @@ throw new Error('key must be a string');

this._size = undefined;
var node = createPath(this._tree, key);
var value = node.get(LEAF);
const node = createPath(this._tree, key);
let value = node.get(LEAF);
if (value === undefined) {

@@ -523,3 +431,3 @@ node.set(LEAF, value = initial());

return value;
};
}
/**

@@ -529,11 +437,11 @@ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/values

*/
SearchableMap.prototype.values = function () {
values() {
return new TreeIterator(this, VALUES);
};
}
/**
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@iterator
*/
SearchableMap.prototype[Symbol.iterator] = function () {
[Symbol.iterator]() {
return this.entries();
};
}
/**

@@ -545,20 +453,9 @@ * Creates a {@link SearchableMap} from an `Iterable` of entries

*/
SearchableMap.from = function (entries) {
var e_3, _a;
var tree = new SearchableMap();
try {
for (var entries_1 = __values(entries), entries_1_1 = entries_1.next(); !entries_1_1.done; entries_1_1 = entries_1.next()) {
var _b = __read(entries_1_1.value, 2), key = _b[0], value = _b[1];
tree.set(key, value);
}
static from(entries) {
const tree = new SearchableMap();
for (const [key, value] of entries) {
tree.set(key, value);
}
catch (e_3_1) { e_3 = { error: e_3_1 }; }
finally {
try {
if (entries_1_1 && !entries_1_1.done && (_a = entries_1.return)) _a.call(entries_1);
}
finally { if (e_3) throw e_3.error; }
}
return tree;
};
}
/**

@@ -570,52 +467,28 @@ * Creates a {@link SearchableMap} from the iterable properties of a JavaScript object

*/
SearchableMap.fromObject = function (object) {
static fromObject(object) {
return SearchableMap.from(Object.entries(object));
};
return SearchableMap;
}());
var trackDown = function (tree, key, path) {
var e_4, _a;
if (path === void 0) { path = []; }
}
}
const trackDown = (tree, key, path = []) => {
if (key.length === 0 || tree == null) {
return [tree, path];
}
try {
for (var _b = __values(tree.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
if (k !== LEAF && key.startsWith(k)) {
path.push([tree, k]); // performance: update in place
return trackDown(tree.get(k), key.slice(k.length), path);
}
for (const k of tree.keys()) {
if (k !== LEAF && key.startsWith(k)) {
path.push([tree, k]); // performance: update in place
return trackDown(tree.get(k), key.slice(k.length), path);
}
}
catch (e_4_1) { e_4 = { error: e_4_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_4) throw e_4.error; }
}
path.push([tree, key]); // performance: update in place
return trackDown(undefined, '', path);
};
var lookup = function (tree, key) {
var e_5, _a;
const lookup = (tree, key) => {
if (key.length === 0 || tree == null) {
return tree;
}
try {
for (var _b = __values(tree.keys()), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
if (k !== LEAF && key.startsWith(k)) {
return lookup(tree.get(k), key.slice(k.length));
}
for (const k of tree.keys()) {
if (k !== LEAF && key.startsWith(k)) {
return lookup(tree.get(k), key.slice(k.length));
}
}
catch (e_5_1) { e_5 = { error: e_5_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_5) throw e_5.error; }
}
};

@@ -625,44 +498,33 @@ // Create a path in the radix tree for the given key, and returns the deepest

// string operations and recursion for performance.
var createPath = function (node, key) {
var e_6, _a;
var keyLength = key.length;
outer: for (var pos = 0; node && pos < keyLength;) {
try {
for (var _b = (e_6 = void 0, __values(node.keys())), _c = _b.next(); !_c.done; _c = _b.next()) {
var k = _c.value;
// Check whether this key is a candidate: the first characters must match.
if (k !== LEAF && key[pos] === k[0]) {
var len = Math.min(keyLength - pos, k.length);
// Advance offset to the point where key and k no longer match.
var offset = 1;
while (offset < len && key[pos + offset] === k[offset])
++offset;
var child_1 = node.get(k);
if (offset === k.length) {
// The existing key is shorter than the key we need to create.
node = child_1;
}
else {
// Partial match: we need to insert an intermediate node to contain
// both the existing subtree and the new node.
var intermediate = new Map();
intermediate.set(k.slice(offset), child_1);
node.set(key.slice(pos, pos + offset), intermediate);
node.delete(k);
node = intermediate;
}
pos += offset;
continue outer;
const createPath = (node, key) => {
const keyLength = key.length;
outer: for (let pos = 0; node && pos < keyLength;) {
for (const k of node.keys()) {
// Check whether this key is a candidate: the first characters must match.
if (k !== LEAF && key[pos] === k[0]) {
const len = Math.min(keyLength - pos, k.length);
// Advance offset to the point where key and k no longer match.
let offset = 1;
while (offset < len && key[pos + offset] === k[offset])
++offset;
const child = node.get(k);
if (offset === k.length) {
// The existing key is shorter than the key we need to create.
node = child;
}
else {
// Partial match: we need to insert an intermediate node to contain
// both the existing subtree and the new node.
const intermediate = new Map();
intermediate.set(k.slice(offset), child);
node.set(key.slice(pos, pos + offset), intermediate);
node.delete(k);
node = intermediate;
}
pos += offset;
continue outer;
}
}
catch (e_6_1) { e_6 = { error: e_6_1 }; }
finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
}
finally { if (e_6) throw e_6.error; }
}
// Create a final child node to contain the final suffix of the key.
var child = new Map();
const child = new Map();
node.set(key.slice(pos), child);

@@ -673,4 +535,4 @@ return child;

};
var remove = function (tree, key) {
var _a = __read(trackDown(tree, key), 2), node = _a[0], path = _a[1];
const remove = (tree, key) => {
const [node, path] = trackDown(tree, key);
if (node === undefined) {

@@ -684,11 +546,11 @@ return;

else if (node.size === 1) {
var _b = __read(node.entries().next().value, 2), key_1 = _b[0], value = _b[1];
merge(path, key_1, value);
const [key, value] = node.entries().next().value;
merge(path, key, value);
}
};
var cleanup = function (path) {
const cleanup = (path) => {
if (path.length === 0) {
return;
}
var _a = __read(last(path), 2), node = _a[0], key = _a[1];
const [node, key] = last(path);
node.delete(key);

@@ -699,17 +561,17 @@ if (node.size === 0) {

else if (node.size === 1) {
var _b = __read(node.entries().next().value, 2), key_2 = _b[0], value = _b[1];
if (key_2 !== LEAF) {
merge(path.slice(0, -1), key_2, value);
const [key, value] = node.entries().next().value;
if (key !== LEAF) {
merge(path.slice(0, -1), key, value);
}
}
};
var merge = function (path, key, value) {
const merge = (path, key, value) => {
if (path.length === 0) {
return;
}
var _a = __read(last(path), 2), node = _a[0], nodeKey = _a[1];
const [node, nodeKey] = last(path);
node.set(nodeKey + key, value);
node.delete(nodeKey);
};
var last = function (array) {
const last = (array) => {
return array[array.length - 1];

@@ -716,0 +578,0 @@ };

8

package.json
{
"name": "minisearch",
"version": "6.3.0",
"version": "7.0.0",
"description": "Tiny but powerful full-text search engine for browser and Node",

@@ -11,9 +11,9 @@ "main": "dist/umd/index.js",

".": {
"types": "./dist/types/index.d.ts",
"require": "./dist/cjs/index.cjs",
"import": "./dist/es/index.js",
"default": "./dist/es/index.js"
},
"./SearchableMap": {
"types": "./dist/types/SearchableMap.d.ts",
"require": "./dist/cjs/SearchableMap.cjs",
"import": "./dist/es/SearchableMap.js",
"default": "./dist/es/SearchableMap.js"

@@ -62,3 +62,3 @@ }

"rollup": "^4.1.0",
"rollup-plugin-dts": "^6.0.0",
"rollup-plugin-dts": "^6.1.0",
"snazzy": "^9.0.0",

@@ -65,0 +65,0 @@ "ts-jest": "^29.0.3",

13

README.md

@@ -331,14 +331,11 @@ # MiniSearch

## Browser compatibility
## Browser and Node compatibility
`MiniSearch` natively supports all modern browsers implementing JavaScript
standards, but requires a polyfill when used in Internet Explorer, as it makes
use functions like `Object.entries`, `Array.includes`, and `Array.from`, which
are standard but not available on older browsers. The package
[`core-js`](https://github.com/zloirock/core-js) is one such polyfill that can
be used to provide those functions.
`MiniSearch` supports all browsers and NodeJS versions implementing the ES6
(ES2015) JavaScript standard. That includes all modern browsers and NodeJS
versions.
## Contributing
Contributions to `MiniSearch` are welcome! Please read the [contributions
Contributions to `MiniSearch` are welcome. Please read the [contributions
guidelines](https://github.com/lucaong/minisearch/blob/master/CONTRIBUTING.md).

@@ -345,0 +342,0 @@ Reading the [design

2

src/SearchableMap/fuzzySearch.ts
/* eslint-disable no-labels */
import { LEAF } from './TreeIterator'
import { RadixTree } from './types'
import type { RadixTree } from './types'

@@ -5,0 +5,0 @@ export type FuzzyResult<T> = [T, number]

4

src/SearchableMap/SearchableMap.ts
/* eslint-disable no-labels */
import { TreeIterator, ENTRIES, KEYS, VALUES, LEAF } from './TreeIterator'
import fuzzySearch, { FuzzyResults } from './fuzzySearch'
import { RadixTree, Entry, Path } from './types'
import fuzzySearch, { type FuzzyResults } from './fuzzySearch'
import type { RadixTree, Entry, Path } from './types'

@@ -6,0 +6,0 @@ /**

2

src/SearchableMap/TreeIterator.ts

@@ -1,2 +0,2 @@

import { RadixTree, Entry, LeafType } from './types'
import type { RadixTree, Entry, LeafType } from './types'

@@ -3,0 +3,0 @@ /** @ignore */

dist/types/index.d.ts
dist/types/SearchableMap.d.ts
dist/cjs/index.cjs

Sorry, the diff of this file is not supported yet

dist/cjs/index.cjs.map

Sorry, the diff of this file is not supported yet

dist/cjs/SearchableMap.cjs

Sorry, the diff of this file is not supported yet

dist/cjs/SearchableMap.cjs.map

Sorry, the diff of this file is not supported yet

dist/es/index.js

Sorry, the diff of this file is too big to display

dist/es/index.js.map

Sorry, the diff of this file is not supported yet

dist/es/SearchableMap.js.map

Sorry, the diff of this file is not supported yet

dist/es5m/index.js

Sorry, the diff of this file is too big to display

dist/es5m/index.js.map

Sorry, the diff of this file is not supported yet

dist/es5m/SearchableMap.js.map

Sorry, the diff of this file is not supported yet

dist/umd/index.js

Sorry, the diff of this file is too big to display

dist/umd/index.js.map

Sorry, the diff of this file is not supported yet

dist/umd/SearchableMap.js.map

Sorry, the diff of this file is not supported yet

src/MiniSearch.test.js

Sorry, the diff of this file is too big to display

src/MiniSearch.ts

Sorry, the diff of this file is too big to display

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc