-
-
Notifications
You must be signed in to change notification settings - Fork 2
/
HashMultiDict.ts
95 lines (89 loc) · 2.58 KB
/
HashMultiDict.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import { HashIndex } from "./HashIndex";
import { isEqual, isIterable, ResolveAction } from "./util";
import { HashDictOptions } from "./HashDict";
import { MultiDictBase } from "./MultiDictBase";
/**
* A hash-based dictionary that can store multiple items with the same key.
*
* ```ts
* import { HashMultiDict } from "scl"
* ```
*
* Most methods in this collection, given that a proper hashing function is set
* up, are in `Θ(1 + n/k)`. If you're out of luck, this characteristic can grow
* to `O(n)`.
*
* You can add as many items with the same key and value as you want, as the
* items will be stored next to each other.
*
* ```ts
* const d = new HashMultiDict<number, string>()
* d.emplace(1, 'foo') // ok
* assert.strictEqual(d.getValue(1), 'foo')
* d.emplace(1, 'bar') // ok
* d.emplace(1, 'foo') // ok
* const values = [...d.getValues(1)]
* assert.strictEqual(values.length, 3)
* ```
*/
export class HashMultiDict<K, V> extends MultiDictBase<K, V> {
/**
* Construct a new hash-based dictionary.
*
* ```ts
* const d = new HashMultiDict<number, string>()
* ```
*
* Similar to JavaScript's built-in [map type][1], the constructor accepts a
* list of key-value pairs that will immediately be added to the resulting
* dictionary.
*
* ```ts
* const d = new HashMultiDict<number, string>([
* [1, 'one'],
* [2, 'two']
* ])
* ```
*
* The dictionary can be tweaked by providing a [[HashDictOptions]]-object,
* which allows to configure things like the default hashing function and
* value equality.
*
* ```ts
* const d = new HashMultiDict<number, string>({
* hash: num => num,
* keysEqual: (a, b) => a === b,
* valuesEqual: (a, b) => a === b,
* elements: [[1, 'one'], [2, 'two']]
* })
* ```
*
* [1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
*/
constructor(opts: Iterable<[K, V]> | HashIndex<[K, V], K> | HashDictOptions<K, V> = {}) {
if (opts instanceof HashIndex) {
super(opts);
} else {
if (isIterable(opts)) {
opts = { elements: opts };
}
const {
valuesEqual = isEqual,
...restOpts
} = opts;
super(
new HashIndex({
onDuplicateKeys: ResolveAction.Insert,
onDuplicateElements: ResolveAction.Insert,
elementsEqual: (a, b) => valuesEqual(a[1], b[1]),
getKey: pair => pair[0],
...restOpts,
})
);
}
}
public clone() {
return new HashMultiDict<K, V>(this.index.clone());
}
}
export default HashMultiDict;