forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
DisjointSet.js
97 lines (78 loc) · 2.18 KB
/
DisjointSet.js
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
import DisjointSetItem from './DisjointSetItem';
export default class DisjointSet {
/**
* @param {function(value: *)} [keyCallback]
*/
constructor(keyCallback) {
this.keyCallback = keyCallback;
this.items = {};
}
/**
* @param {*} itemValue
* @return {DisjointSet}
*/
makeSet(itemValue) {
const disjointSetItem = new DisjointSetItem(itemValue, this.keyCallback);
if (!this.items[disjointSetItem.getKey()]) {
// Add new item only in case if it not presented yet.
this.items[disjointSetItem.getKey()] = disjointSetItem;
}
return this;
}
/**
* Find set representation node.
*
* @param {*} itemValue
* @return {(string|null)}
*/
find(itemValue) {
const templateDisjointItem = new DisjointSetItem(itemValue, this.keyCallback);
// Try to find item itself;
const requiredDisjointItem = this.items[templateDisjointItem.getKey()];
if (!requiredDisjointItem) {
return null;
}
return requiredDisjointItem.getRoot().getKey();
}
/**
* Union by rank.
*
* @param {*} valueA
* @param {*} valueB
* @return {DisjointSet}
*/
union(valueA, valueB) {
const rootKeyA = this.find(valueA);
const rootKeyB = this.find(valueB);
if (rootKeyA === null || rootKeyB === null) {
throw new Error('One or two values are not in sets');
}
if (rootKeyA === rootKeyB) {
// In case if both elements are already in the same set then just return its key.
return this;
}
const rootA = this.items[rootKeyA];
const rootB = this.items[rootKeyB];
if (rootA.getRank() < rootB.getRank()) {
// If rootB's tree is bigger then make rootB to be a new root.
rootB.addChild(rootA);
return this;
}
// If rootA's tree is bigger then make rootA to be a new root.
rootA.addChild(rootB);
return this;
}
/**
* @param {*} valueA
* @param {*} valueB
* @return {boolean}
*/
inSameSet(valueA, valueB) {
const rootKeyA = this.find(valueA);
const rootKeyB = this.find(valueB);
if (rootKeyA === null || rootKeyB === null) {
throw new Error('One or two values are not in sets');
}
return rootKeyA === rootKeyB;
}
}