package utils;

import java.util.HashMap;
import java.util.Map;

public class DynamicDisjointSetUnion<T> {
	
	private Map<T, T> parent;
	private Map<T, Integer> size;
	
	public DynamicDisjointSetUnion() {
		parent = new HashMap<>();
		size = new HashMap<>();
	}
	
	public void add(T x) {
		if (! parent.containsKey(x)) {
			parent.put(x, x);
			size.put(x, 1);
		}
	}
	
	public T find(T x) {
		if (! parent.containsKey(x)) {
			throw new RuntimeException(x.toString() + " does not exist");
		}
		
		if (! parent.get(x).equals(x)) {
			parent.put(x, find(parent.get(x)));
		}
		return parent.get(x);
	}
	
	public void union(T x, T y) {
		add(x);
		add(y);
		
		T rx = find(x);
		T ry = find(y);
		
		if (rx.equals(ry)) {
			return;
		}
		
		if (size.get(rx) < size.get(ry)) {
			T tmp = rx;
			rx = ry;
			ry = tmp;
		}
		
		parent.put(ry, rx);
		size.put(rx, size.get(rx) + size.get(ry));
	}
	
	public boolean same(T x, T y) {
		if ((! parent.containsKey(x)) || (! parent.containsKey(y))) {
			return false;
		}
		return find(x).equals(find(y));
	}
	
	public int componentSize(T x) {
		return size.get(x);
	}
	
}