-
Notifications
You must be signed in to change notification settings - Fork 0
/
StructuralMap.ts
105 lines (88 loc) · 2.31 KB
/
StructuralMap.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
96
97
98
99
100
101
102
103
104
105
import findAndRemove from "./findAndRemove";
export type Key = {
equals(other: unknown): boolean;
hashCode(): HashCode;
};
export type HashCode = bigint | number | string;
class Pair<K extends Key, V> {
constructor(public key: K, public value: V) {}
}
const EMPTY_ARRAY: any[] = [];
export default class StructuralMap<K extends Key, V> implements Map<K, V> {
readonly [Symbol.toStringTag]: string = "xtjs-lib.StructuralMap";
private readonly map = new Map<HashCode, Pair<K, V>[]>();
private _size = 0;
get size(): number {
return this._size;
}
[Symbol.iterator](): IterableIterator<[K, V]> {
return this.entries();
}
clear(): void {
this.map.clear();
this._size = 0;
}
delete(key: K): boolean {
const hc = key.hashCode();
const pairs = this.map.get(hc) ?? EMPTY_ARRAY;
const deleted = findAndRemove(pairs, (p) => key.equals(p.key));
if (deleted) {
this._size--;
}
return !!deleted;
}
*entries(): IterableIterator<[K, V]> {
for (const pairs of this.map.values()) {
for (const pair of pairs) {
yield [pair.key, pair.value];
}
}
}
forEach(
callbackfn: (value: V, key: K, map: Map<K, V>) => void,
thisArg?: any
): void {
for (const [key, value] of this.entries()) {
callbackfn.call(thisArg, value, key, this);
}
}
get(key: K): V | undefined {
const hc = key.hashCode();
const pairs = this.map.get(hc) ?? EMPTY_ARRAY;
return pairs.find((p) => key.equals(p.key))?.value;
}
has(key: K): boolean {
const hc = key.hashCode();
const pairs = this.map.get(hc) ?? EMPTY_ARRAY;
return !!pairs.find((p) => key.equals(p.key));
}
*keys(): IterableIterator<K> {
for (const pairs of this.map.values()) {
for (const pair of pairs) {
yield pair.key;
}
}
}
set(key: K, value: V): this {
const hc = key.hashCode();
let pairs = this.map.get(hc);
if (!pairs) {
this.map.set(hc, (pairs = []));
}
const pair = pairs.find((p) => key.equals(p.key));
if (!pair) {
pairs.push(new Pair(key, value));
this._size++;
} else {
pair.value = value;
}
return this;
}
*values(): IterableIterator<V> {
for (const pairs of this.map.values()) {
for (const pair of pairs) {
yield pair.value;
}
}
}
}