import java.awt.Font;
import java.util.ArrayList;


public class RasterVisualization {

	private static final int N = 16;
	private static final int T = 1;
	
	public static void main(String[] args)
	{	
		double worstTotal = 0;
		double average = 0;
		int worstWorst = 0;
		int[][] worstWorstGrid = new int[N][N];
		int[][] worstTotalGrid = new int[N][N];
		for (int t = 0; t < T; t++)
		{
			int[][] grid = new int[N][N];
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < N; j++)
				{
					if (Math.random() < .5)
						grid[i][j] = 0;
					else
						grid[i][j] = 1;
				}
			}
		
			SuperUnionFind suf = new SuperUnionFind(N * N, 2, 2);
			
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < N; j++)
				{
					if (j != 0)
					{
						if (grid[i][j] == grid[i][j-1])
							suf.union(N*i + j, N*i + j - 1);
					}
					if (i != 0)
					{
						if (grid[i][j] == grid[i-1][j])
							suf.union(N*i + j, N*(i-1) + j);
					}
				}
				for (int j = 0; j < N; j++)
				{
					suf.findU(N*i + j);
				}
			}
			
			double avg = ((double)suf.getUnionPointers())/suf.getUnions();
			average += avg;
			if (avg > worstTotal)
			{
				worstTotal = avg;
				for (int i = 0; i < N; i++)
				{
					for (int j = 0; j < N; j++)
					{
						worstTotalGrid[i][j] = grid[i][j];
					}
				}
			}
			if (suf.getWorstCaseUnion() > worstWorst)
			{	
				worstWorst = suf.getWorstCaseUnion();
				for (int i = 0; i < N; i++)
				{
					for (int j = 0; j < N; j++)
					{
						worstWorstGrid[i][j] = grid[i][j];
					}
				}
			}
			//draw(grid, suf);
			//System.out.println("Total OPS: " + suf.getUnionPointers());
			//System.out.println("Worst OP: " + suf.getWorstCaseUnion());
		}
		double totalOps = average/T;
		System.out.println("Total OPS: " + totalOps);
		System.out.println("Worst Total OPS: " + worstTotal);
		System.out.println("Worst OP: " + worstWorst);
		SuperUnionFind suf = new SuperUnionFind(N * N, 2, 0);
		
		StdDraw.show(10);
		draw(worstTotalGrid, suf, -1, true);
		StdDraw.setPenRadius(.005);
		StdDraw.setPenColor(StdDraw.BOOK_RED);
		draw2(worstTotalGrid, suf);
		StdDraw.show(1200);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (j != 0)
				{
					if (worstTotalGrid[i][j] == worstTotalGrid[i][j-1])
						suf.union(N*i + j, N*i + j - 1);
					StdDraw.clear();
					draw(worstTotalGrid, suf, N*i + j, true);
					StdDraw.setPenRadius(.005);
					StdDraw.setPenColor(StdDraw.BOOK_RED);
					draw2(worstTotalGrid, suf);
					StdDraw.show(50);
				}
				if (i != 0)
				{
					if (worstTotalGrid[i][j] == worstTotalGrid[i-1][j])
						suf.union(N*i + j, N*(i-1) + j);
					StdDraw.clear();
					draw(worstTotalGrid, suf, N*i + j, false);
					StdDraw.setPenRadius(.005);
					StdDraw.setPenColor(StdDraw.BOOK_RED);
					draw2(worstTotalGrid, suf);
					StdDraw.show(50);
				}
			}
		}
		draw(worstTotalGrid, suf, -1, true);
		StdDraw.setPenRadius(.005);
		StdDraw.setPenColor(StdDraw.BOOK_RED);
		draw2(worstTotalGrid, suf);
		StdDraw.show(10);
	}
	
	public static void draw(int[][] grid, SuperUnionFind suf, int curr, boolean left)
	{
		Font f = new Font(Font.SANS_SERIF, Font.BOLD, 12);
		StdDraw.setFont(f);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				double l = 1./N;
				if (grid[i][j] == 1)
					StdDraw.setPenColor(StdDraw.BLACK);
				else
					StdDraw.setPenColor(StdDraw.BLUE);
				if (N*i + j == curr)
					StdDraw.setPenColor(StdDraw.GREEN);
				if (N*(i+1) + j == curr && !left)
					StdDraw.setPenColor(StdDraw.ORANGE);
				if (N*i + j + 1 == curr && left)
					StdDraw.setPenColor(StdDraw.ORANGE);
				//StdDraw.square(l*i + l/2, l* j + l/2, l/2);
				StdDraw.text(l*j + l/2, 1-l* i - l/2, suf.find(N*i + j) + "");
			}
		}
	}
	
	public static void draw2(int[][] grid, SuperUnionFind suf)
	{
		ArrayList<Point>[] components = new ArrayList[N*N];

		for (int i = 0; i < components.length; i++)
		{
			components[i] = new ArrayList();
		}
		double l = 1./N;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				int f = suf.find(N*i + j);
				components[f].add(new Point(i, j));
			}
		}
		
		
		for (int i = 0; i < N*N; i++)
		{
			for (int j = 0; j < components[i].size(); j++)
			{
				Point point = components[i].get(j);
				double x = point.getX();
				double y = point.getY();
				boolean test = true;
				
				for (int k = 0; k < components[i].size(); k++)
				{
					Point point2 = components[i].get(k);
					double x2 = point2.getX();
					double y2 = point2.getY();
					if ((x2 == (x-1)) && (y2 == y ))
						test = false;;
				}
				if (test)
					StdDraw.line(y*l, 1-x*l, (y+1)*l, 1-x*l);
				test = true;
				
				for (int k = 0; k < components[i].size(); k++)
				{
					Point point2 = components[i].get(k);
					double x2 = point2.getX();
					double y2 = point2.getY();
					if ((x2 == x) && (y2 == (y - 1)))
						test = false;
				}
				if (test)
					StdDraw.line(y*l, 1-x*l, y*l, 1-(x+1)*l);
				test = true;
				
				for (int k = 0; k < components[i].size(); k++)
				{
					Point point2 = components[i].get(k);
						double x2 = point2.getX();
					double y2 = point2.getY();
					if ((x2 == (x + 1)) && (y2 == y))
						test = false;
				}
				if (test)
					StdDraw.line(y*l, 1-(x+1)*l, (y+1)*l, 1-(x+1)*l);
				test = true;
				
				for (int k = 0; k < components[i].size(); k++)
				{
					Point point2 = components[i].get(k);
					double x2 = point2.getX();
					double y2 = point2.getY();
					if ((x2 == x) && (y2 == (y + 1)))
						test = false;
				}
				if (test)
					StdDraw.line((y+1)*l, 1-x*l, (y+1)*l, 1-(x+1)*l);
			}
			
			
			
			int x = 2;
			/*double[] py = new double[y.size()];
			
			for (int j = 0; j < x.size(); j++)
			{
				px[j] = x.get(j)*l;
				py[j] = y.get(j)*l;
			}
			if (px.length > 0)
				StdDraw.polygon(px, py);*/
		}
		
		
	}
}