forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
DisjointSetItem.js
96 lines (82 loc) · 1.8 KB
/
DisjointSetItem.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
export default class DisjointSetItem {
/**
* @param {*} value
* @param {function(value: *)} [keyCallback]
*/
constructor(value, keyCallback) {
this.value = value;
this.keyCallback = keyCallback;
/** @var {DisjointSetItem} this.parent */
this.parent = null;
this.children = {};
}
/**
* @return {*}
*/
getKey() {
// Allow user to define custom key generator.
if (this.keyCallback) {
return this.keyCallback(this.value);
}
// Otherwise use value as a key by default.
return this.value;
}
/**
* @return {DisjointSetItem}
*/
getRoot() {
return this.isRoot() ? this : this.parent.getRoot();
}
/**
* @return {boolean}
*/
isRoot() {
return this.parent === null;
}
/**
* Rank basically means the number of all ancestors.
*
* @return {number}
*/
getRank() {
if (this.getChildren().length === 0) {
return 0;
}
let rank = 0;
/** @var {DisjointSetItem} child */
this.getChildren().forEach((child) => {
// Count child itself.
rank += 1;
// Also add all children of current child.
rank += child.getRank();
});
return rank;
}
/**
* @return {DisjointSetItem[]}
*/
getChildren() {
return Object.values(this.children);
}
/**
* @param {DisjointSetItem} parentItem
* @param {boolean} forceSettingParentChild
* @return {DisjointSetItem}
*/
setParent(parentItem, forceSettingParentChild = true) {
this.parent = parentItem;
if (forceSettingParentChild) {
parentItem.addChild(this);
}
return this;
}
/**
* @param {DisjointSetItem} childItem
* @return {DisjointSetItem}
*/
addChild(childItem) {
this.children[childItem.getKey()] = childItem;
childItem.setParent(this, false);
return this;
}
}