#482

pending completion

Build # #482

Build Type

push

GitHub Actions

Committed by

web-flow

Commit Message

Pass stored fields to boostDocument callback (#213)

This makes it more convenient to perform dynamic boosting.

Run Details

211 of 216 branches covered (97.69%)

Branch coverage included in aggregate %.

1 of 1 new or added line in 1 file covered. (100.0%)

664 of 664 relevant lines covered (100.0%)

763.99 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.46

/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'

/**
 * A class implementing the same interface as a standard JavaScript
 * [`Map`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map)
 * with string keys, but adding support for efficiently searching entries with
 * prefix or fuzzy search. This class is used internally by [[MiniSearch]] as
 * the inverted index data structure. The implementation is a radix tree
 * (compressed prefix tree).
 *
 * Since this class can be of general utility beyond _MiniSearch_, it is
 * exported by the `minisearch` package and can be imported (or required) as
 * `minisearch/SearchableMap`.
 *
 * @typeParam T  The type of the values stored in the map.
 */
export default class SearchableMap<T = any> {
  /**
   * @internal
   */
  _tree: RadixTree<T>

  /**
   * @internal
   */
  _prefix: string

  private _size: number | undefined = undefined

  /**
   * The constructor is normally called without arguments, creating an empty
   * map. In order to create a [[SearchableMap]] from an iterable or from an
   * object, check [[SearchableMap.from]] and [[SearchableMap.fromObject]].
   *
   * The constructor arguments are for internal use, when creating derived
   * mutable views of a map at a prefix.
   */
  constructor (tree: RadixTree<T> = new Map(), prefix = '') {
    this._tree = tree
    this._prefix = prefix
  }

  /**
   * Creates and returns a mutable view of this [[SearchableMap]], containing only
   * entries that share the given prefix.
   *
   * ### Usage:
   *
   * ```javascript
   * let map = new SearchableMap()
   * map.set("unicorn", 1)
   * map.set("universe", 2)
   * map.set("university", 3)
   * map.set("unique", 4)
   * map.set("hello", 5)
   *
   * let uni = map.atPrefix("uni")
   * uni.get("unique") // => 4
   * uni.get("unicorn") // => 1
   * uni.get("hello") // => undefined
   *
   * let univer = map.atPrefix("univer")
   * univer.get("unique") // => undefined
   * univer.get("universe") // => 2
   * univer.get("university") // => 3
   * ```
   *
   * @param prefix  The prefix
   * @return A [[SearchableMap]] representing a mutable view of the original Map at the given prefix
   */
  atPrefix (prefix: string): SearchableMap<T> {
    if (!prefix.startsWith(this._prefix)) { throw new Error('Mismatched prefix') }

    const [node, path] = trackDown(this._tree, prefix.slice(this._prefix.length))

    if (node === undefined) {
      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)
        }
      }
    }

    return new SearchableMap<T>(node, prefix)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/clear
   */
  clear (): void {
    this._size = undefined
    this._tree.clear()
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/delete
   * @param key  Key to delete
   */
  delete (key: string): void {
    this._size = undefined
    return remove(this._tree, key)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/entries
   * @return An iterator iterating through `[key, value]` entries.
   */
  entries () {
    return new TreeIterator(this, ENTRIES)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/forEach
   * @param fn  Iteration function
   */
  forEach (fn: (key: string, value: T, map: SearchableMap) => void): void {
    for (const [key, value] of this) {
      fn(key, value, this)
    }
  }

  /**
   * Returns a Map of all the entries that have a key within the given edit
   * distance from the search key. The keys of the returned Map are the matching
   * keys, while the values are two-element arrays where the first element is
   * the value associated to the key, and the second is the edit distance of the
   * key to the search key.
   *
   * ### Usage:
   *
   * ```javascript
   * let map = new SearchableMap()
   * map.set('hello', 'world')
   * map.set('hell', 'yeah')
   * map.set('ciao', 'mondo')
   *
   * // Get all entries that match the key 'hallo' with a maximum edit distance of 2
   * map.fuzzyGet('hallo', 2)
   * // => Map(2) { 'hello' => ['world', 1], 'hell' => ['yeah', 2] }
   *
   * // In the example, the "hello" key has value "world" and edit distance of 1
   * // (change "e" to "a"), the key "hell" has value "yeah" and edit distance of 2
   * // (change "e" to "a", delete "o")
   * ```
   *
   * @param key  The search key
   * @param maxEditDistance  The maximum edit distance (Levenshtein)
   * @return A Map of the matching keys to their value and edit distance
   */
  fuzzyGet (key: string, maxEditDistance: number): FuzzyResults<T> {
    return fuzzySearch<T>(this._tree, key, maxEditDistance)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/get
   * @param key  Key to get
   * @return Value associated to the key, or `undefined` if the key is not
   * found.
   */
  get (key: string): T | undefined {
    const node = lookup<T>(this._tree, key)
    return node !== undefined ? node.get(LEAF) : undefined
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/has
   * @param key  Key
   * @return True if the key is in the map, false otherwise
   */
  has (key: string): boolean {
    const node = lookup(this._tree, key)
    return node !== undefined && node.has(LEAF)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/keys
   * @return An `Iterable` iterating through keys
   */
  keys () {
    return new TreeIterator(this, KEYS)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/set
   * @param key  Key to set
   * @param value  Value to associate to the key
   * @return The [[SearchableMap]] itself, to allow chaining
   */
  set (key: string, value: T): SearchableMap<T> {
    if (typeof key !== 'string') { throw new Error('key must be a string') }
    this._size = undefined
    const node = createPath(this._tree, key)
    node.set(LEAF, value)
    return this
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
   */
  get size (): number {
    if (this._size) { return this._size }
    /** @ignore */
    this._size = 0

    const iter = this.entries()
    while (!iter.next().done) this._size! += 1

    return this._size
  }

  /**
   * Updates the value at the given key using the provided function. The function
   * is called with the current value at the key, and its return value is used as
   * the new value to be set.
   *
   * ### Example:
   *
   * ```javascript
   * // Increment the current value by one
   * searchableMap.update('somekey', (currentValue) => currentValue == null ? 0 : currentValue + 1)
   * ```
   *
   * If the value at the given key is or will be an object, it might not require
   * re-assignment. In that case it is better to use `fetch()`, because it is
   * faster.
   *
   * @param key  The key to update
   * @param fn  The function used to compute the new value from the current one
   * @return The [[SearchableMap]] itself, to allow chaining
   */
  update (key: string, fn: (value: T | undefined) => T): SearchableMap<T> {
    if (typeof key !== 'string') { throw new Error('key must be a string') }
    this._size = undefined
    const node = createPath(this._tree, key)
    node.set(LEAF, fn(node.get(LEAF)))
    return this
  }

  /**
   * Fetches the value of the given key. If the value does not exist, calls the
   * given function to create a new value, which is inserted at the given key
   * and subsequently returned.
   *
   * ### Example:
   *
   * ```javascript
   * const map = searchableMap.fetch('somekey', () => new Map())
   * map.set('foo', 'bar')
   * ```
   *
   * @param key  The key to update
   * @param defaultValue  A function that creates a new value if the key does not exist
   * @return The existing or new value at the given key
   */
  fetch (key: string, initial: () => T): T {
    if (typeof key !== 'string') { throw new Error('key must be a string') }
    this._size = undefined
    const node = createPath(this._tree, key)

    let value = node.get(LEAF)
    if (value === undefined) {
      node.set(LEAF, value = initial())
    }

    return value
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/values
   * @return An `Iterable` iterating through values.
   */
  values () {
    return new TreeIterator(this, VALUES)
  }

  /**
   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@iterator
   */
  [Symbol.iterator] () {
    return this.entries()
  }

  /**
   * Creates a [[SearchableMap]] from an `Iterable` of entries
   *
   * @param entries  Entries to be inserted in the [[SearchableMap]]
   * @return A new [[SearchableMap]] with the given entries
   */
  static from<T = any> (entries: Iterable<Entry<T>> | Entry<T>[]) {
    const tree = new SearchableMap()
    for (const [key, value] of entries) {
      tree.set(key, value)
    }
    return tree
  }

  /**
   * Creates a [[SearchableMap]] from the iterable properties of a JavaScript object
   *
   * @param object  Object of entries for the [[SearchableMap]]
   * @return A new [[SearchableMap]] with the given entries
   */
  static fromObject<T = any> (object: { [key: string]: T }) {
    return SearchableMap.from<T>(Object.entries(object))
  }
}

const trackDown = <T = any>(tree: RadixTree<T> | undefined, key: string, path: Path<T> = []): [RadixTree<T> | undefined, Path<T>] => {
  if (key.length === 0 || tree == null) { return [tree, 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)
    }
  }

  path.push([tree, key]) // performance: update in place
  return trackDown(undefined, '', path)
}

const lookup = <T = any>(tree: RadixTree<T>, key: string): RadixTree<T> | undefined => {
  if (key.length === 0 || tree == null) { return tree }

  for (const k of tree.keys()) {
    if (k !== LEAF && key.startsWith(k)) {
      return lookup(tree.get(k)!, key.slice(k.length))
    }
  }
}

// Create a path in the radix tree for the given key, and returns the deepest
// node. This function is in the hot path for indexing. It avoids unnecessary
// string operations and recursion for performance.
const createPath = <T = any>(node: RadixTree<T>, key: string): RadixTree<T> => {
  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
      }
    }

    // Create a final child node to contain the final suffix of the key.
    const child = new Map()
    node.set(key.slice(pos), child)
    return child
  }

  return node
}

const remove = <T = any>(tree: RadixTree<T>, key: string): void => {
  const [node, path] = trackDown(tree, key)
  if (node === undefined) { return }
  node.delete(LEAF)

  if (node.size === 0) {
    cleanup(path)
  } else if (node.size === 1) {
    const [key, value] = node.entries().next().value
    merge(path, key, value)
  }
}

const cleanup = <T = any>(path: Path<T>): void => {
  if (path.length === 0) { return }

  const [node, key] = last(path)
  node!.delete(key)

  if (node!.size === 0) {
    cleanup(path.slice(0, -1))
  } else if (node!.size === 1) {
    const [key, value] = node!.entries().next().value
    if (key !== LEAF) {
      merge(path.slice(0, -1), key, value)
    }
  }
}

const merge = <T = any>(path: Path<T>, key: string, value: RadixTree<T>): void => {
  if (path.length === 0) { return }

  const [node, nodeKey] = last(path)
  node!.set(nodeKey + key, value)
  node!.delete(nodeKey)
}

const last = <T = any>(array: T[]): T => {
  return array[array.length - 1]
}

1	/* eslint-disable no-labels */
2	import { TreeIterator, ENTRIES, KEYS, VALUES, LEAF } from './TreeIterator'	2✔
3	import fuzzySearch, { FuzzyResults } from './fuzzySearch'	2✔
4	import { RadixTree, Entry, Path } from './types'
5
6	/**
7	* A class implementing the same interface as a standard JavaScript
8	* [`Map`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map)
9	* with string keys, but adding support for efficiently searching entries with
10	* prefix or fuzzy search. This class is used internally by [[MiniSearch]] as
11	* the inverted index data structure. The implementation is a radix tree
12	* (compressed prefix tree).
13	*
14	* Since this class can be of general utility beyond _MiniSearch_, it is
15	* exported by the `minisearch` package and can be imported (or required) as
16	* `minisearch/SearchableMap`.
17	*
18	* @typeParam T The type of the values stored in the map.
19	*/
20	export default class SearchableMap<T = any> {	2✔
21	/**
22	* @internal
23	*/
24	_tree: RadixTree<T>
25
26	/**
27	* @internal
28	*/
29	_prefix: string
30
31	private _size: number \| undefined = undefined	378✔
32
33	/**
34	* The constructor is normally called without arguments, creating an empty
35	* map. In order to create a [[SearchableMap]] from an iterable or from an
36	* object, check [[SearchableMap.from]] and [[SearchableMap.fromObject]].
37	*
38	* The constructor arguments are for internal use, when creating derived
39	* mutable views of a map at a prefix.
40	*/
41	constructor (tree: RadixTree<T> = new Map(), prefix = '') {	706✔
42	this._tree = tree	378✔
43	this._prefix = prefix	378✔
44	}
45
46	/**
47	* Creates and returns a mutable view of this [[SearchableMap]], containing only
48	* entries that share the given prefix.
49	*
50	* ### Usage:
51	*
52	* ```javascript
53	* let map = new SearchableMap()
54	* map.set("unicorn", 1)
55	* map.set("universe", 2)
56	* map.set("university", 3)
57	* map.set("unique", 4)
58	* map.set("hello", 5)
59	*
60	* let uni = map.atPrefix("uni")
61	* uni.get("unique") // => 4
62	* uni.get("unicorn") // => 1
63	* uni.get("hello") // => undefined
64	*
65	* let univer = map.atPrefix("univer")
66	* univer.get("unique") // => undefined
67	* univer.get("universe") // => 2
68	* univer.get("university") // => 3
69	* ```
70	*
71	* @param prefix The prefix
72	* @return A [[SearchableMap]] representing a mutable view of the original Map at the given prefix
73	*/
74	atPrefix (prefix: string): SearchableMap<T> {	2✔
75	if (!prefix.startsWith(this._prefix)) { throw new Error('Mismatched prefix') }	145✔
76
77	const [node, path] = trackDown(this._tree, prefix.slice(this._prefix.length))	144✔
78
79	if (node === undefined) {	144✔
80	const [parentNode, key] = last(path)	107✔
81
82	for (const k of parentNode!.keys()) {	495✔
83	if (k !== LEAF && k.startsWith(key)) {	495✔
84	const node = new Map()	12✔
85	node.set(k.slice(key.length), parentNode!.get(k)!)	12✔
86	return new SearchableMap(node, prefix)	12✔
87	}
88	}
89	}
90
91	return new SearchableMap<T>(node, prefix)	132✔
92	}
93
94	/**
95	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/clear
96	*/
97	clear (): void {	2✔
98	this._size = undefined	2✔
99	this._tree.clear()	2✔
100	}
101
102	/**
103	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/delete
104	* @param key Key to delete
105	*/
106	delete (key: string): void {	2✔
107	this._size = undefined	644✔
108	return remove(this._tree, key)	644✔
109	}
110
111	/**
112	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/entries
113	* @return An iterator iterating through `[key, value]` entries.
114	*/
115	entries () {	2✔
116	return new TreeIterator(this, ENTRIES)	407✔
117	}
118
119	/**
120	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/forEach
121	* @param fn Iteration function
122	*/
123	forEach (fn: (key: string, value: T, map: SearchableMap) => void): void {	2✔
124	for (const [key, value] of this) {	15✔
125	fn(key, value, this)	15✔
126	}
127	}
128
129	/**
130	* Returns a Map of all the entries that have a key within the given edit
131	* distance from the search key. The keys of the returned Map are the matching
132	* keys, while the values are two-element arrays where the first element is
133	* the value associated to the key, and the second is the edit distance of the
134	* key to the search key.
135	*
136	* ### Usage:
137	*
138	* ```javascript
139	* let map = new SearchableMap()
140	* map.set('hello', 'world')
141	* map.set('hell', 'yeah')
142	* map.set('ciao', 'mondo')
143	*
144	* // Get all entries that match the key 'hallo' with a maximum edit distance of 2
145	* map.fuzzyGet('hallo', 2)
146	* // => Map(2) { 'hello' => ['world', 1], 'hell' => ['yeah', 2] }
147	*
148	* // In the example, the "hello" key has value "world" and edit distance of 1
149	* // (change "e" to "a"), the key "hell" has value "yeah" and edit distance of 2
150	* // (change "e" to "a", delete "o")
151	* ```
152	*
153	* @param key The search key
154	* @param maxEditDistance The maximum edit distance (Levenshtein)
155	* @return A Map of the matching keys to their value and edit distance
156	*/
157	fuzzyGet (key: string, maxEditDistance: number): FuzzyResults<T> {	2✔
158	return fuzzySearch<T>(this._tree, key, maxEditDistance)	141✔
159	}
160
161	/**
162	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/get
163	* @param key Key to get
164	* @return Value associated to the key, or `undefined` if the key is not
165	* found.
166	*/
167	get (key: string): T \| undefined {	2✔
168	const node = lookup<T>(this._tree, key)	915✔
169	return node !== undefined ? node.get(LEAF) : undefined	915✔
170	}
171
172	/**
173	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/has
174	* @param key Key
175	* @return True if the key is in the map, false otherwise
176	*/
177	has (key: string): boolean {	2✔
178	const node = lookup(this._tree, key)	1,158✔
179	return node !== undefined && node.has(LEAF)	1,158✔
180	}
181
182	/**
183	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/keys
184	* @return An `Iterable` iterating through keys
185	*/
186	keys () {	2✔
187	return new TreeIterator(this, KEYS)	106✔
188	}
189
190	/**
191	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/set
192	* @param key Key to set
193	* @param value Value to associate to the key
194	* @return The [[SearchableMap]] itself, to allow chaining
195	*/
196	set (key: string, value: T): SearchableMap<T> {	2✔
197	if (typeof key !== 'string') { throw new Error('key must be a string') }	787✔
198	this._size = undefined	786✔
199	const node = createPath(this._tree, key)	786✔
200	node.set(LEAF, value)	786✔
201	return this	786✔
202	}
203
204	/**
205	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size
206	*/
207	get size (): number {	2✔
208	if (this._size) { return this._size }	223✔
209	/** @ignore */
210	this._size = 0	222✔
211
212	const iter = this.entries()	222✔
213	while (!iter.next().done) this._size! += 1	562✔
214
215	return this._size	222✔
216	}
217
218	/**
219	* Updates the value at the given key using the provided function. The function
220	* is called with the current value at the key, and its return value is used as
221	* the new value to be set.
222	*
223	* ### Example:
224	*
225	* ```javascript
226	* // Increment the current value by one
227	* searchableMap.update('somekey', (currentValue) => currentValue == null ? 0 : currentValue + 1)
228	* ```
229	*
230	* If the value at the given key is or will be an object, it might not require
231	* re-assignment. In that case it is better to use `fetch()`, because it is
232	* faster.
233	*
234	* @param key The key to update
235	* @param fn The function used to compute the new value from the current one
236	* @return The [[SearchableMap]] itself, to allow chaining
237	*/
238	update (key: string, fn: (value: T \| undefined) => T): SearchableMap<T> {	2✔
239	if (typeof key !== 'string') { throw new Error('key must be a string') }	3✔
240	this._size = undefined	2✔
241	const node = createPath(this._tree, key)	2✔
242	node.set(LEAF, fn(node.get(LEAF)))	2✔
243	return this	2✔
244	}
245
246	/**
247	* Fetches the value of the given key. If the value does not exist, calls the
248	* given function to create a new value, which is inserted at the given key
249	* and subsequently returned.
250	*
251	* ### Example:
252	*
253	* ```javascript
254	* const map = searchableMap.fetch('somekey', () => new Map())
255	* map.set('foo', 'bar')
256	* ```
257	*
258	* @param key The key to update
259	* @param defaultValue A function that creates a new value if the key does not exist
260	* @return The existing or new value at the given key
261	*/
262	fetch (key: string, initial: () => T): T {	2✔
263	if (typeof key !== 'string') { throw new Error('key must be a string') }	2,786!
264	this._size = undefined	2,786✔
265	const node = createPath(this._tree, key)	2,786✔
266
267	let value = node.get(LEAF)	2,786✔
268	if (value === undefined) {	2,786✔
269	node.set(LEAF, value = initial())	1,714✔
270	}
271
272	return value	2,786✔
273	}
274
275	/**
276	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/values
277	* @return An `Iterable` iterating through values.
278	*/
279	values () {	2✔
280	return new TreeIterator(this, VALUES)	3✔
281	}
282
283	/**
284	* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@iterator
285	*/
286	[Symbol.iterator] () {	2✔
287	return this.entries()	80✔
288	}
289
290	/**
291	* Creates a [[SearchableMap]] from an `Iterable` of entries
292	*
293	* @param entries Entries to be inserted in the [[SearchableMap]]
294	* @return A new [[SearchableMap]] with the given entries
295	*/
296	static from<T = any> (entries: Iterable<Entry<T>> \| Entry<T>[]) {	2✔
297	const tree = new SearchableMap()	18✔
298	for (const [key, value] of entries) {	208✔
299	tree.set(key, value)	208✔
300	}
301	return tree	18✔
302	}
303
304	/**
305	* Creates a [[SearchableMap]] from the iterable properties of a JavaScript object
306	*
307	* @param object Object of entries for the [[SearchableMap]]
308	* @return A new [[SearchableMap]] with the given entries
309	*/
310	static fromObject<T = any> (object: { [key: string]: T }) {	2✔
311	return SearchableMap.from<T>(Object.entries(object))	5✔
312	}
313	}	2✔
314
315	const trackDown = <T = any>(tree: RadixTree<T> \| undefined, key: string, path: Path<T> = []): [RadixTree<T> \| undefined, Path<T>] => {	2,472✔
316	if (key.length === 0 \|\| tree == null) { return [tree, path] }	1,684✔
317
318	for (const k of tree.keys()) {	1,978✔
319	if (k !== LEAF && key.startsWith(k)) {	1,978✔
320	path.push([tree, k]) // performance: update in place	787✔
321	return trackDown(tree.get(k)!, key.slice(k.length), path)	787✔
322	}
323	}
324
325	path.push([tree, key]) // performance: update in place	109✔
326	return trackDown(undefined, '', path)	109✔
327	}
328
329	const lookup = <T = any>(tree: RadixTree<T>, key: string): RadixTree<T> \| undefined => {	2✔
330	if (key.length === 0 \|\| tree == null) { return tree }	3,556✔
331
332	for (const k of tree.keys()) {	7,387✔
333	if (k !== LEAF && key.startsWith(k)) {	7,387✔
334	return lookup(tree.get(k)!, key.slice(k.length))	1,483✔
335	}
336	}
337	}
338
339	// Create a path in the radix tree for the given key, and returns the deepest
340	// node. This function is in the hot path for indexing. It avoids unnecessary
341	// string operations and recursion for performance.
342	const createPath = <T = any>(node: RadixTree<T>, key: string): RadixTree<T> => {	2✔
343	const keyLength = key.length	3,574✔
344
345	outer: for (let pos = 0; node && pos < keyLength;) {	3,574✔
346	for (const k of node.keys()) {	28,621✔
347	// Check whether this key is a candidate: the first characters must match.
348	if (k !== LEAF && key[pos] === k[0]) {	28,621✔
349	const len = Math.min(keyLength - pos, k.length)	4,484✔
350
351	// Advance offset to the point where key and k no longer match.
352	let offset = 1	4,484✔
353	while (offset < len && key[pos + offset] === k[offset]) ++offset	4,484✔
354
355	const child = node.get(k)!	4,484✔
356	if (offset === k.length) {	4,484✔
357	// The existing key is shorter than the key we need to create.
358	node = child	3,762✔
359	} else {
360	// Partial match: we need to insert an intermediate node to contain
361	// both the existing subtree and the new node.
362	const intermediate = new Map()	722✔
363	intermediate.set(k.slice(offset), child)	722✔
364	node.set(key.slice(pos, pos + offset), intermediate)	722✔
365	node.delete(k)	722✔
366	node = intermediate	722✔
367	}
368
369	pos += offset	4,484✔
370	continue outer	4,484✔
371	}
372	}
373
374	// Create a final child node to contain the final suffix of the key.
375	const child = new Map()	2,359✔
376	node.set(key.slice(pos), child)	2,359✔
377	return child	2,359✔
378	}
379
380	return node	1,215✔
381	}
382
383	const remove = <T = any>(tree: RadixTree<T>, key: string): void => {	2✔
384	const [node, path] = trackDown(tree, key)	644✔
385	if (node === undefined) { return }	644✔
386	node.delete(LEAF)	642✔
387
388	if (node.size === 0) {	642✔
389	cleanup(path)	602✔
390	} else if (node.size === 1) {	40✔
391	const [key, value] = node.entries().next().value	15✔
392	merge(path, key, value)	15✔
393	}
394	}
395
396	const cleanup = <T = any>(path: Path<T>): void => {	2✔
397	if (path.length === 0) { return }	706✔
398
399	const [node, key] = last(path)	596✔
400	node!.delete(key)	596✔
401
402	if (node!.size === 0) {	596✔
403	cleanup(path.slice(0, -1))	104✔
404	} else if (node!.size === 1) {	492✔
405	const [key, value] = node!.entries().next().value	165✔
406	if (key !== LEAF) {	165✔
407	merge(path.slice(0, -1), key, value)	145✔
408	}
409	}
410	}
411
412	const merge = <T = any>(path: Path<T>, key: string, value: RadixTree<T>): void => {	2✔
413	if (path.length === 0) { return }	160✔
414
415	const [node, nodeKey] = last(path)	67✔
416	node!.set(nodeKey + key, value)	67✔
417	node!.delete(nodeKey)	67✔
418	}
419
420	const last = <T = any>(array: T[]): T => {	2✔
421	return array[array.length - 1]	770✔
422	}

lucaong / minisearch / #482

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous