// Adam Campbell
// 3/10/05
// Solution to COP 3530 Homework #3 Programming Problem
//
// These algorithms are taken from pages 150-160 in Algorithms by Johnsonbaugh and Schaefer
//
// Uses: Union by Rank

public class DisjointSet{

	private int[] parent;
	private int[] rank;
	
	// simple DisjointSet constructor
	public DisjointSet(int size){
	
		parent = new int[size];
		rank = new int[size];
		
		// initially, all elements are in their own set
		for(int i = 0; i < size; i++){
			parent[i] = i;
			rank[i] = 0;
		}

	}
	
	// returns the set that the given element is in
	// performs path compression to make the algorithm more efficient
	public int find(int i){

		int j, root = i;
		
		// find the representative element for the set
		while(root != parent[root]){
			root = parent[root];
		}
		
		j = parent[i];
		
		// compress the path
		while(j != root){
			parent[i] = root;
			i = j;
			j = parent[i];
		}
		
		return root;
		
	}
	
	// unions the sets that elements i and j are in
	public void union(int i, int j){
		mergeTrees(find(i), find(j));
	}
	
	// unions the trees rooted at i and j
	public void mergeTrees(int i, int j){
	
		// unions the two sets and also tries to keep the height of the trees as small as possible
		if(rank[i] < rank[j]){
			parent[i] = j;
		}else if(rank[i] > rank[j]){
			parent[j] = i;
		}else{
			parent[i] = j;
			rank[j]++;
		}
		
	}
	
}