public class QuickUnionWeighted {
	private int[] id;
	
	QuickUnionWeighted(int n){
		id = new int[n];
		
		for(int i=0;i<n;i++){
			id[i] = -1;
		}
		
	}
	
	public boolean isConnected(int p, int q){
		return root(p)==root(q);
	}
	
	private int root(int r){
		
		if(id[r]<0){
			return r;
		}
		else{
			id[r]= root(r);
			
			return id[r];
		}

		
	}

	
	public void union(int p, int q){
		
		if(id[p] < id[q]){
			id[p] += id[q];
			id[q] = p;
		}
		else{
			id[q] += id[p];
			id[p]=q;
		}
		
	}
	}

public class PercolationTest {
	
	private int n;
	private boolean[][] perc;
	private QuickUnionWeighted uf;
	private QuickUnionWeighted ufo;
	private int openSites;
	
	
	public PercolationTest(int n){
		this.n = n;
		openSites=0;
		uf= new QuickUnionWeighted((n * n) + 2);
		ufo= new QuickUnionWeighted((n * n) + 1);
		perc = new boolean[n][n];
		
		for(int i=0; i<= n-1;i++){
			uf.union(0,encode( 0, i));
			ufo.union((n*n)+1, encode((n-1),i));
		}
		
	}

	public void open(int i, int j ){
		if(!isOpen(j, j)){
			perc[i][j]=true;
			openSites++;
		}
		
		if((i<0 || j<0) && (i>=n || j>=n)){
			throw new IndexOutOfBoundsException("i, j out of bound");
		}
		
		if(n >j && j>=0 &&  n>i && i>=0){
			if((i-1) >= 0 && (i-1)<n && isOpen(i-1,j)){
				uf.union(encode(i-1,j), encode(i,j));
				ufo.union(encode(i-1,j), encode(i,j));
			}
			
			if((i+1)<n && (i+1) >=0 && isOpen(i+1,j)){
				uf.union(encode(i+1,j), encode(i,j));
			}
			
			if((j-1)>=0 && (j-1)<n && isOpen(i,j-1)){
				uf.union(encode(i,j-1), encode(i,j));
				ufo.union(encode(i,j-1), encode(i,j));
			}
			
			if((j+1)>=0 && (j+1) <n && isOpen(i,j+1)){
				uf.union(encode(i,j+1), encode(i,j));
				ufo.union(encode(i,j+1), encode(i,j));
			}
		}
	}
	
	public boolean isFull(int i, int j){
		
		if((i<0 || j<0) && (i>=n || j>= n)){
			throw new IndexOutOfBoundsException("either i or j out of bounds.");
		}
		return uf.isConnected(encode(i,j),0) && isOpen(i,j) && isOpen(i,j) &&
				ufo.isConnected(encode(n-1,j),0);
		
	}
	
	public boolean isOpen(int i,int j){
		if((i<0 || j<0) && (i>=n || j>=n)){
			throw new IndexOutOfBoundsException("out of bound either i or j");
		}
		
		return perc[i][j];	
	}
	
	public boolean percolates(){
		return uf.isConnected((n*n)+1, 0);
		
	}
	private int encode(int i, int j){
		return (n * i) + j + 1;
	}
	public static void main(String[] args) {
		
		 PercolationTest p = new PercolationTest(3);
		 p.open(0,2);
	        p.open(1,2);
	        p.open(2,2);
	        p.open(2,0);

	        System.out.println("Percolate: " + p.percolates());
	        System.out.println("is 3.1 full : " + p.isFull(2,0));

}
}