package org.psjava.ds.set;

import org.psjava.ds.map.MutableMap;
import org.psjava.goods.GoodMutableMapFactory;

public class DisjointSetForest<T> implements DisjointSet<T> {

	/**
	 * see http://en.wikipedia.org/wiki/Disjoint-set_data_structure
	 */

	private static class NodeInfo<T> {
		T parent;
		int rank;

		NodeInfo(T p, int rank) {
			this.parent = p;
			this.rank = rank;
		}
	}

	final MutableMap<T, NodeInfo<T>> nodeInfo = GoodMutableMapFactory.getInstance().create();

	@Override
	public void makeSet(T value) {
		nodeInfo.add(value, new NodeInfo<T>(value, 0));
	}

	@Override
	public void union(T x, T y) {
		T xrep = find(x);
		T yrep = find(y);
		if (xrep == yrep)
			return;
		NodeInfo<T> xinfo = nodeInfo.get(xrep);
		NodeInfo<T> yinfo = nodeInfo.get(yrep);
		if (xinfo.rank > yinfo.rank) {
			yinfo.parent = xrep;
		} else {
			xinfo.parent = yrep;
			if (xinfo.rank == yinfo.rank)
				yinfo.rank++;
		}
	}

	@Override
	public T find(T x) {
		NodeInfo<T> info = nodeInfo.get(x);
		if (!info.parent.equals(x))
			info.parent = find(info.parent);
		return info.parent;
	}

}

@@ -110,78 +110,10 @@
 y;%0A%0A
-public class DisjointSetForest%3CT%3E implements DisjointSet%3CT%3E %7B%0A%0A%09/**%0A%09 
+/*
 * se
@@ -174,15 +174,76 @@
 ture
-%0A%09
  */%0A%0A
+public class DisjointSetForest%3CT%3E implements DisjointSet%3CT%3E %7B%0A%0A
 %09pri

improve comment