| 1 | import { NotFindInSetException } from "../exception/NotFindInSetException";
|
| 2 | import { DisjointSetItem } from "./DisjointSetItem";
|
| 3 | export class DisjointSet {
|
| 4 | constructor(key) {
|
| 5 | this.key = key;
|
| 6 | this.items = {};
|
| 7 | this.rootItems = {};
|
| 8 | }
|
| 9 | get RootItems() {
|
| 10 | return this.rootItems;
|
| 11 | }
|
| 12 | makeSet(value) {
|
| 13 | const disjointSetItem = new DisjointSetItem(value);
|
| 14 | if (!this.items[disjointSetItem.getKey(this.key)]) {
|
| 15 | this.items[disjointSetItem.getKey(this.key)] = disjointSetItem;
|
| 16 | this.rootItems[disjointSetItem.getKey(this.key)] = disjointSetItem;
|
| 17 | }
|
| 18 | return this;
|
| 19 | }
|
| 20 | find(value) {
|
| 21 | const disjointSetItem = new DisjointSetItem(value);
|
| 22 | const foundDisjointSetItem = this.items[disjointSetItem.getKey(this.key)];
|
| 23 | if (!foundDisjointSetItem) {
|
| 24 | return null;
|
| 25 | }
|
| 26 | return foundDisjointSetItem.getRoot().getKey(this.key);
|
| 27 | }
|
| 28 | union(value1, value2) {
|
| 29 | const rootKeyA = this.find(value1);
|
| 30 | const rootKeyB = this.find(value2);
|
| 31 | if (rootKeyA === null || rootKeyB === null) {
|
| 32 | throw new NotFindInSetException();
|
| 33 | }
|
| 34 | if (rootKeyA === rootKeyB) {
|
| 35 | return this;
|
| 36 | }
|
| 37 | const rootA = this.items[rootKeyA];
|
| 38 | const rootB = this.items[rootKeyB];
|
| 39 | if (rootA.getRank() < rootB.getRank()) {
|
| 40 | rootB.addChild(rootA);
|
| 41 | delete this.rootItems[rootKeyA];
|
| 42 | return this;
|
| 43 | }
|
| 44 | rootA.addChild(rootB);
|
| 45 | delete this.rootItems[rootKeyB];
|
| 46 | return this;
|
| 47 | }
|
| 48 | inSameSet(value1, value2) {
|
| 49 | const rootKeyA = this.find(value1);
|
| 50 | const rootKeyB = this.find(value2);
|
| 51 | if (rootKeyA === null || rootKeyB === null) {
|
| 52 | throw new NotFindInSetException();
|
| 53 | }
|
| 54 | return rootKeyA === rootKeyB;
|
| 55 | }
|
| 56 | }
|
| 57 | export default DisjointSet;
|