package algs15;
import java.util.Scanner;
import stdlib.*;

public class TestUF {
	public static enum Order { ZERO_I, I_ZERO, I_MINUS, MINUS_I, RANDOM }
	public static void main(String[] args) {
		show(8,  "1 4, 4 5, 2 6, 2 3, 3 7, 6 3, 5 2"); //notes from textbook
		show(10, "4 3, 3 8, 6 5, 9 4, 2 1, 8 9, 5 0, 7 2, 6 1, 1 0, 6 7"); //textbook tinyUF.txt		
		show(10, "0 1, 0 2, 0 3, 0 4, 0 5, 0 6, 0 7, 0 8, 0 9"); // ZERO_I
		show(10, "1 0, 2 0, 3 0, 4 0, 5 0, 6 0, 7 0, 8 0, 9 0"); // I_ZERO
		show(10, "1 0, 2 1, 3 2, 4 3, 5 4, 6 5, 7 6, 8 7, 9 8"); // I_MINUS
		show(10, "0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9"); // MINUS_I
		show(16, "0 1, 2 3, 4 5, 6 7, 8 9, 10 11, 12 13, 14 15," + "0 2, 4 6, 8 10, 12 14," + "0 4, 8 12," + "0 8");
		showRandom(12);
		double prevUnion = 0;
		double prevConnected = 0;
		for (int N = 128; N<=MAX; N += N) {
			timeTrial(N, Order.RANDOM);
			StdOut.format("N=%,13d Union=%7.3f [%8.3f] Connected=%7.3f [%8.3f]\n", N, timeUnion, timeUnion/prevUnion, timeConnected, timeConnected/prevConnected);
			prevUnion = timeUnion;
			prevConnected = timeConnected;
		}
	}
	private static int MAX=50_000_000;
	private static UF getUF (int N) {
		MAX=500_000; return new QuickFindUF(N);  //   (262_144,RANDOM) Union ~ 36  Connected ~ .006
	    //MAX=500_000; return new QuickUnionUF(N); //   (262_144,RANDOM) Union ~ 17  Connected ~ 18
		//return new WeightedUF(N);                //(33_554_432,RANDOM) Union ~ 10  Connected ~ 10
		//return new CompressionUF(N);             //(33_554_432,RANDOM) Union ~ 16  Connected ~ 7
		//return new XWeightedHalvingUF(N);        //(33_554_432,RANDOM) Union ~  9  Connected ~ 6
		//return new XWeightedCompressionUF(N);    //(33_554_432,RANDOM) Union ~  9  Connected ~ 6
	}
	
	private static double timeUnion;
	private static double timeConnected;
	private static void timeTrial(int N, Order order) {
		UF ufTime = getUF(N);				
		SHOW_COMPRESSION_STEPS = false;
		Stopwatch sw1 = new Stopwatch();
		for (int i=1; i<N; i+= 1) {
			int p = StdRandom.uniform(N);
			int q = StdRandom.uniform(N);
			switch (order) {
			case ZERO_I: ufTime.union (0, i); break; 
			case I_ZERO: ufTime.union (i, 0); break; 
			case I_MINUS: ufTime.union (i, i-1); break;
			case MINUS_I: ufTime.union (i-1, i); break;
			case RANDOM: ufTime.union (p, q); break;
			}
		}
		timeUnion = sw1.elapsedTime();

		Stopwatch sw2 = new Stopwatch();		
		for (int i=1; i<N; i+= 1) {
			int p = StdRandom.uniform(N);
			int q = StdRandom.uniform(N);
			ufTime.connected(p, q);
		}	
		timeConnected = sw2.elapsedTime();
	}
	
	public static boolean SHOW_COMPRESSION_STEPS=false;
	private static void showRandom (int N) {
		SHOW_COMPRESSION_STEPS = true;
		UF uf = getUF(N);
		uf.toGraphviz();
		StdOut.format("       %2d%s\n", uf.count(), uf);
		for (int i=1; i<4*N; i++) {
			int p = StdRandom.uniform(N);
			int q = StdRandom.uniform(N);
			if (uf.connected(p, q)) {
				StdOut.format("%2d %2d: connected\n", p, q); 
			} else {
				uf.union(p, q);
				uf.toGraphviz();
				StdOut.format("%2d %2d: %2d%s\n", p, q, uf.count(), uf);
			}
		}
		StdOut.println();
	}
	private static void show (int N, String input) {
		SHOW_COMPRESSION_STEPS = true;
		Scanner s = new Scanner(input);
		s.useDelimiter("[\\s,]\\s*"); // use comma or space as delimiter

		UF uf = getUF(N);
		uf.toGraphviz();
		StdOut.format("       %2d%s\n", uf.count(), uf);
		while (s.hasNext()) {
			int p = s.nextInt();
			int q = s.nextInt();
			if (uf.connected(p, q)) {
				StdOut.format("%2d %2d: connected\n", p, q); 
			} else {
				uf.union(p, q);
				uf.toGraphviz();
				StdOut.format("%2d %2d: %2d%s\n", p, q, uf.count(), uf);
			}
		}
		StdOut.println();
		s.close();
	}
}