-
Notifications
You must be signed in to change notification settings - Fork 15
/
trie.ts
54 lines (46 loc) · 1.72 KB
/
trie.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// A [trie](https://en.wikipedia.org/wiki/Trie) data structure that holds
// object keys weakly, yet can also hold non-object keys, unlike the
// native `WeakMap`.
// If no makeData function is supplied, the looked-up data will be an empty,
// null-prototype Object.
const defaultMakeData = () => Object.create(null);
// Useful for processing arguments objects as well as arrays.
const { forEach, slice } = Array.prototype;
export class Trie<Data> {
// Since a `WeakMap` cannot hold primitive values as keys, we need a
// backup `Map` instance to hold primitive keys. Both `this._weakMap`
// and `this._strongMap` are lazily initialized.
private weak?: WeakMap<any, Trie<Data>>;
private strong?: Map<any, Trie<Data>>;
private data?: Data;
constructor(
private weakness = true,
private makeData: (array: any[]) => Data = defaultMakeData,
) {}
public lookup<T extends any[]>(...array: T): Data {
return this.lookupArray(array);
}
public lookupArray<T extends IArguments | any[]>(array: T): Data {
let node: Trie<Data> = this;
forEach.call(array, key => node = node.getChildTrie(key));
return node.data || (node.data = this.makeData(slice.call(array)));
}
private getChildTrie(key: any) {
const map = this.weakness && isObjRef(key)
? this.weak || (this.weak = new WeakMap<any, Trie<Data>>())
: this.strong || (this.strong = new Map<any, Trie<Data>>());
let child = map.get(key);
if (!child) map.set(key, child = new Trie<Data>(this.weakness, this.makeData));
return child;
}
}
function isObjRef(value: any) {
switch (typeof value) {
case "object":
if (value === null) break;
// Fall through to return true...
case "function":
return true;
}
return false;
}