1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 package org.utgenome.util.repeat;
24
25 import java.util.ArrayList;
26 import java.util.HashSet;
27 import java.util.List;
28 import java.util.Set;
29
30 import org.xerial.util.IndexedSet;
31
32
33
34
35
36
37
38 public class DisjointSet<E> {
39
40 private IndexedSet<E> elementIndex = new IndexedSet<E>();
41
42 private List<Integer> parentID = new ArrayList<Integer>();
43 private List<Integer> rank = new ArrayList<Integer>();
44
45
46
47
48 public void add(E element) {
49 boolean isNewElement = elementIndex.add(element);
50 if (isNewElement) {
51 int id = elementIndex.getID(element);
52 parentID.add(id);
53 rank.add(0);
54 }
55 }
56
57 public Set<E> rootNodeSet() {
58 Set<E> roots = new HashSet<E>();
59 for (E each : elementIndex) {
60 int id = elementIndex.getID(each);
61 int pid = findByID(id);
62 if (id == pid)
63 roots.add(each);
64 }
65 return roots;
66 }
67
68 public List<E> disjointSetOf(E x) {
69 final int setID = find(x);
70
71 List<E> result = new ArrayList<E>();
72 for (int id = 0; id < parentID.size(); id++) {
73 int pid = parentID.get(id);
74 if (pid == setID) {
75 result.add(elementIndex.getByID(id));
76 }
77 }
78
79 return result;
80 }
81
82 public void union(E x, E y) {
83 linkByID(find(x), find(y));
84 }
85
86 private void link(E x, E y) {
87 int xID = elementIndex.getID(x);
88 int yID = elementIndex.getID(y);
89
90 if (xID == IndexedSet.INVALID_ID) {
91 add(x);
92 xID = elementIndex.getID(x);
93 }
94
95 if (yID == IndexedSet.INVALID_ID) {
96 add(y);
97 yID = elementIndex.getID(y);
98 }
99
100 linkByID(xID, yID);
101 }
102
103 private void linkByID(int xID, int yID) {
104 if (rank.get(xID) > rank.get(yID)) {
105 parentID.set(yID, xID);
106 }
107 else {
108 parentID.set(xID, yID);
109 if (rank.get(xID) == rank.get(yID))
110 rank.set(yID, rank.get(yID) + 1);
111 }
112 }
113
114 public int numElements() {
115 return elementIndex.size();
116 }
117
118
119
120
121
122
123
124
125 public int find(E x) {
126 return findByID(elementIndex.getID(x));
127 }
128
129 private int findByID(int id) {
130 if (id != parentID.get(id))
131 parentID.set(id, findByID(parentID.get(id)));
132 return parentID.get(id);
133 }
134
135 }