001package org.clafer.collection;
002
003import gnu.trove.iterator.TObjectIntIterator;
004import gnu.trove.list.array.TIntArrayList;
005import gnu.trove.map.hash.TIntObjectHashMap;
006import gnu.trove.map.hash.TObjectIntHashMap;
007import java.util.Collection;
008import java.util.HashSet;
009import java.util.Set;
010
011/**
012 *
013 * @param <V> the type of the data
014 * @author jimmy
015 */
016public class DisjointSets<V> {
017
018    private final TObjectIntHashMap<V> nodes = new TObjectIntHashMap<>(16, 0.5f, -1);
019    private final TIntArrayList parents = new TIntArrayList(16);
020
021    private int getNode(V i) {
022        int n = nodes.size();
023        int v = nodes.putIfAbsent(i, n);
024        if (v == -1) {
025            parents.add(n);
026            assert nodes.size() == parents.size();
027            return n;
028        }
029        return v;
030    }
031
032    private int find(int n) {
033        int p = parents.get(n);
034        if (n == p) {
035            return n;
036        }
037        p = find(p);
038        parents.set(n, p);
039        return p;
040    }
041
042    private int find(V i) {
043        return find(getNode(i));
044    }
045
046    public boolean connected(V i1, V i2) {
047        return find(i1) == find(i2);
048    }
049
050    public void union(V i1, V i2) {
051        int r1 = find(i1);
052        int r2 = find(i2);
053
054        if (r1 != r2) {
055            parents.set(r2, r1);
056        }
057    }
058
059    public Collection<Set<V>> connectedComponents() {
060        TIntObjectHashMap<Set<V>> components = new TIntObjectHashMap<>();
061        TObjectIntIterator<V> iter = nodes.iterator();
062        for (int i = nodes.size(); i-- > 0;) {
063            iter.advance();
064            V key = iter.key();
065            int group = find(iter.value());
066            Set<V> component = components.get(group);
067            if (component == null) {
068                component = new HashSet<>();
069                components.put(group, component);
070            }
071            component.add(key);
072        }
073        return components.valueCollection();
074    }
075
076    @Override
077    public String toString() {
078        return connectedComponents().toString();
079    }
080}