/*
 * $ java-algs4 RBBSTDraw 255 888
 * $ java-algs4 RBBSTDraw 255 888 -
 * $ java-algs4 RBBSTDraw 255 888 +
 * $ java-algs4 RBBSTDraw 255 888 Z
 * $ 
 */

public class RBBSTDraw
{
    // assume N > 0
    public static int lgfloor(int N) {
	int t = 0;
	while (N > 1) {
	    t++;
	    N /= 2;
	}
	return t;
    }

    // assume N > 0
    public static int log3floor(int N) {
	int t = 0;
	while (N >= 3) {
	    t++;
	    N /= 3;
	}
	return t;
    }

    public static int log3ceil(int N) {
	if (N == 1) return 0;
	return log3floor(N - 1) + 1;
    }

    public static int bestIPL(int N) {
	int q = lgfloor(N + 1);
	return (N + 1) * q - (1 << (q + 1)) + 2;
    }

    public static int[] input(String[] args) {
	int N = Integer.parseInt(args[0]);
	long seed = Long.parseLong(args[1]);
	StdRandom.setSeed(seed);

	int[] a = new int[N];	
	if (args.length < 3) { // random
	    for (int i = 0; i < N; i++)
		a[i] = i;
	    StdRandom.shuffle(a);
	} else if (args[2].equals("-")) // decreasing
	    for (int i = 0; i < N; i++)
		a[i] = -i;
	else if (args[2].equals("+")) // increasing
	    for (int i = 0; i < N; i++)
		a[i] = i;
	else if (args[2].equals("Z")) { // zigzag
	    int s = -1;
	    for (int i = 0; i < N; i++) {
		a[i] = s * (N - i);
		s *= -1;
	    }
	}
	return a;
    }
    
    public static void main(String[] args)
    {
	int N = Integer.parseInt(args[0]);
	if (N >= 1050) { // some ad hoc limit
	    StdOut.println("N should be less than 1050");
	    System.exit(-1);
	}
	int[] a = input(args);

	RedBlackBSTDraw<Integer, Integer> st = new RedBlackBSTDraw<>();	

	st.drawPrepare(800);
	StdDraw.enableDoubleBuffering();
	for (int i = 0; i < N; i++) { 
	    st.put(a[i], i); 
	    int NN = i + 1; // number of nodes
	    st.draw(.95, .003, .004);
	    StdDraw.setPenColor(StdDraw.BLACK);
	    StdDraw.textLeft(0.02, 0.33, "N = " + NN);
	    StdDraw.textLeft(0.02, 0.28,
			     String.format("2-3 height = %d  (best possible = %d)\n",
					   st.height23P(), log3ceil(NN) - 1));
	    StdDraw.textLeft(0.02, 0.23,
			     String.format("Plain height = %d  (best possible = %d)",
					   st.height(), lgfloor(NN)
					   ));
	    int ipl = st.iplP();
	    StdDraw.textLeft(0.02, 0.18, "IPL = " + ipl);
	    StdDraw.textLeft(0.02, 0.13,
			     String.format("Average depth = %.4f  (best possible = %.4f)",
					   (double)ipl / (NN),
					   (double)bestIPL(NN) / NN
					   ));
	    int reds = st.sizeRP();
	    StdDraw.textLeft(0.02, 0.08,
			     String.format("No. red links = %d  (%.2f%% of the nodes are red)\n",
					   reds, 100.0 * reds / NN
					   ));
	    StdDraw.textLeft(0.02, 0.03,
			     String.format("Average no. of red links to an external node = %.4f",
					   st.aveRedLinks()
					   ));
	    StdDraw.show();
	    StdDraw.pause(100);		
	}
    }
}