-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.ts
107 lines (94 loc) · 2.86 KB
/
index.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
106
107
export type Key = string | number;
export interface ItemParam<T> {
key: Key;
value?: T;
}
export interface Item<T> extends ItemParam<T> {
parent: Item<T> | null;
rank: number;
[key: string]: unknown;
}
export interface DisjointSet<T> {
items: Map<Key, Item<T>>;
add(this: DisjointSet<T>, ...values: (ItemParam<T> | Key)[]): boolean;
find(this: DisjointSet<T>, key: Key): Key | undefined;
union(this: DisjointSet<T>, key1: Key, key2: Key): DisjointSet<T>;
isSameSet(this: DisjointSet<T>, key1: Key, key2: Key, ...rest: Key[]): boolean;
}
const disjointSet = <T>(): DisjointSet<T> => {
const createItem = (key: Key, value?: T): Item<T> => {
return {
key,
value,
parent: null,
rank: 1,
};
};
const disjointSetObj: DisjointSet<T> = {
items: new Map<Key, Item<T>>(),
// add items
add: function add(...items) {
// map values to Item and add them to items
items.forEach((item) => {
const obj = typeof item === 'object' ? item : {key: item};
if (!this.items.has(obj.key)) {
this.items.set(obj.key, createItem(obj.key, obj.value));
}
});
return true;
},
// find parent key
find: function find(key) {
// find item
if (!this.items.has(key)) return undefined;
const item = this.items.get(key) as Item<T>;
let current = item;
let i = 0;
while (current.parent) {
current = current.parent;
i++;
}
// collapsing find
// update parent
if (i > 1) this.items.set(key, {...item, parent: current});
// return key
return current.key;
},
// make union out of keys
union: function union(key1, key2) {
const rootKey1 = this.find(key1);
const rootKey2 = this.find(key2);
// items do not exist
if (rootKey1 === undefined || rootKey2 === undefined) {
throw new Error('One or both values do not exist.');
}
// items already in the same set
if (rootKey1 === rootKey2) {
return this;
}
const root1 = this.items.get(rootKey1) as Item<T>;
const root2 = this.items.get(rootKey2) as Item<T>;
// weighted union
// if root2's tree is bigger then make root2 a new root
if (root1.rank < root2.rank) {
root1.parent = root2;
root2.rank += root1.rank;
root1.rank = 1;
return this;
}
// if root1's tree is bigger then make root1 a new root
root2.parent = root1;
root1.rank += root2.rank;
root2.rank = 1;
return this;
},
// check if all keys are in same set
isSameSet: function isSameSet(...keys) {
const key1 = this.find(keys[0]);
// check if all keys have same root as first
return key1 !== undefined && keys.splice(1).every((key) => key1 === this.find(key));
},
};
return disjointSetObj;
};
export default disjointSet;