From 9ce65c5a963b03ee97fe9cb6c5aa65a3c04a80a8 Mon Sep 17 00:00:00 2001
From: yzhou <yujiao.zhou@gmail.com>
Date: Tue, 21 Apr 2015 10:34:27 +0100
Subject: initial version

---
 src/uk/ac/ox/cs/pagoda/util/UFS.java | 45 ++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
 create mode 100644 src/uk/ac/ox/cs/pagoda/util/UFS.java

(limited to 'src/uk/ac/ox/cs/pagoda/util/UFS.java')

diff --git a/src/uk/ac/ox/cs/pagoda/util/UFS.java b/src/uk/ac/ox/cs/pagoda/util/UFS.java
new file mode 100644
index 0000000..0869fb7
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/util/UFS.java
@@ -0,0 +1,45 @@
+package uk.ac.ox.cs.pagoda.util;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+public class UFS<T> {
+	
+	private Map<T, T> groups = new HashMap<T, T>();
+
+	public boolean merge(T t1, T t2) {
+		t1 = find(t1); t2 = find(t2);
+		if (t1.equals(t2)) return false;
+		if (t2.toString().contains("cs.ox.ac.uk"))
+			groups.put(t2, t1); 
+		else 
+			groups.put(t1, t2); 
+		return true; 
+	}
+	
+	public Set<T> keySet() {
+		return groups.keySet(); 
+	}
+
+	public T find(T u) {
+		T v, w = u;
+		while ((v = groups.get(u)) != null) 
+			u = v; 
+		
+		while ((v = groups.get(w)) != null) {
+			groups.put(w, u);
+			w = v; 
+		}
+		
+		return u; 
+	}
+	
+	public void clear() {
+		groups.clear();
+	}
+
+	public boolean isEmpty() {
+		return groups.isEmpty();
+	}
+}
-- 
cgit v1.2.3