View Javadoc

1   /*--------------------------------------------------------------------------
2    *  Copyright 2010 utgenome.org
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   *--------------------------------------------------------------------------*/
16  //--------------------------------------
17  // utgb-core Project
18  //
19  // DisjointSet.java
20  // Since: 2010/10/19
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   * Union-Find disjoint set implementation
34   * 
35   * @author leo
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  	 * @param element
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 	 * Find the disjoint set ID of the given element
120 	 * 
121 	 * @param x
122 	 *            element
123 	 * @return
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 }