diff options
Diffstat (limited to 'src/uk/ac/ox/cs/pagoda/util/UFS.java')
| -rw-r--r-- | src/uk/ac/ox/cs/pagoda/util/UFS.java | 45 |
1 files changed, 0 insertions, 45 deletions
diff --git a/src/uk/ac/ox/cs/pagoda/util/UFS.java b/src/uk/ac/ox/cs/pagoda/util/UFS.java deleted file mode 100644 index 0869fb7..0000000 --- a/src/uk/ac/ox/cs/pagoda/util/UFS.java +++ /dev/null | |||
| @@ -1,45 +0,0 @@ | |||
| 1 | package uk.ac.ox.cs.pagoda.util; | ||
| 2 | |||
| 3 | import java.util.HashMap; | ||
| 4 | import java.util.Map; | ||
| 5 | import java.util.Set; | ||
| 6 | |||
| 7 | public class UFS<T> { | ||
| 8 | |||
| 9 | private Map<T, T> groups = new HashMap<T, T>(); | ||
| 10 | |||
| 11 | public boolean merge(T t1, T t2) { | ||
| 12 | t1 = find(t1); t2 = find(t2); | ||
| 13 | if (t1.equals(t2)) return false; | ||
| 14 | if (t2.toString().contains("cs.ox.ac.uk")) | ||
| 15 | groups.put(t2, t1); | ||
| 16 | else | ||
| 17 | groups.put(t1, t2); | ||
| 18 | return true; | ||
| 19 | } | ||
| 20 | |||
| 21 | public Set<T> keySet() { | ||
| 22 | return groups.keySet(); | ||
| 23 | } | ||
| 24 | |||
| 25 | public T find(T u) { | ||
| 26 | T v, w = u; | ||
| 27 | while ((v = groups.get(u)) != null) | ||
| 28 | u = v; | ||
| 29 | |||
| 30 | while ((v = groups.get(w)) != null) { | ||
| 31 | groups.put(w, u); | ||
| 32 | w = v; | ||
| 33 | } | ||
| 34 | |||
| 35 | return u; | ||
| 36 | } | ||
| 37 | |||
| 38 | public void clear() { | ||
| 39 | groups.clear(); | ||
| 40 | } | ||
| 41 | |||
| 42 | public boolean isEmpty() { | ||
| 43 | return groups.isEmpty(); | ||
| 44 | } | ||
| 45 | } | ||
