/** Testing code for persistent binary search tree */
import java.util.Random;
public final class Assignment6 {
	
	public static final void main(String[] args) {
		BST<Integer, Integer> t;
		boolean rollback = true, rand = false;
		
 		System.out.println("Worst-case:");
		System.out.println("Cputime (ms): 1000 2000 3000 4000 5000");
		System.out.print("Baseline;Ephemeral-RBTree:\n");
		for (int a = 1000; a <= 6e3; a += 2000) {
			t = new EphemeralBST<Integer,Integer>();
			bench(t, a, false, rand);
		}
		System.out.println("");
		
		System.out.print("AA-Tree;Node-Copying:\n");
		for (int a = 1000; a <= 6e3; a += 2000) {
			t = new NodeCopyingAATree<Integer,Integer>();
			bench(t, a, rollback, rand);
		}
		System.out.println("");
		
		rand = true;
		System.out.println("Average case:");
		System.out.println("Cputime (ms): 1000 2000 3000 4000 5000");
		System.out.print("Baseline;Ephemeral-RBTree:\n");
		for (int a = 1000; a <= 6e3; a += 2000) {
			t = new EphemeralBST<Integer,Integer>();
			bench(t, a, false, rand);
		}
		System.out.println("");
		
		System.out.print("AA-Tree;Node-Copying:\n");
		for (int a = 1000; a <= 6e3; a += 2000) {
			t = new NodeCopyingAATree<Integer,Integer>();
			bench(t, a, rollback, rand);
		}
		System.out.println("");
		
		System.out.print("BST;Node-Copying:\n");
		for (int a = 1000; a <= 6e3; a += 2000) {
			t = new NodeCopyingBST<Integer,Integer>();
			bench(t, a, rollback, rand);
		}
		System.out.println("");
		
		System.out.print("BST;Path-Copying:\n");
		for (int a = 1000; a <= 6e3; a += 2000) {
			t = new PathCopyingBST<Integer,Integer>();
			bench(t, a, rollback, rand);
		}
		System.out.println("");
	}

	public static final void bench(BST<Integer,Integer> t, int iterations, 
		boolean rollback, boolean rand) {
		Integer[] keys = new Integer[iterations * 2];
		long[] memusage = new long[30], cputime = new long[30];
		long mem, begin;
		Random rnd = new Random(0);

		/* get pseudo-random numbers to use as keys */ 
		for (int a = 0; a < iterations * 2; a++)
			if (rand)
				keys[a] = rnd.nextInt(iterations * iterations);
			else
				keys[a] = a;
		
		
		for (int n = 0; n < 30; n++) {
			if (!rollback)
				((EphemeralBST)t).clear();
			for (int a = 0; a <= 16; a++)
				System.gc();
			mem = Runtime.getRuntime().totalMemory() -
				Runtime.getRuntime().freeMemory();
			begin = System.currentTimeMillis();
		    
			for (int a = 0; a < iterations * 2; a++) {
				t.insert(keys[a], new Integer(keys[a]));
			}
			
			for (int a = iterations * 2; a == iterations; 
				a--) {
				if (rollback) {
					t.rollback();
					assert(t.search(keys[a]) == null);
				}
			}

			for (int a = 0; a < iterations; a++) {
				assert(t.search(keys[a]).equals(keys[a]));
			}

			for (int a = 0; a < iterations; a++) {
				t.delete(keys[a]);
				assert(t.search(keys[a]) == null);
			}

			if (rollback) {
				for (int a = iterations - 1; a == 0; a--) {
					t.rollback();
					assert(t.search(keys[a]) == keys[a]);
				}
			}
			
			for (int a = 0; a < iterations; a++) {
				t.delete(keys[a]);
				assert(t.search(keys[a]) == null);
			}
			
			cputime[n] = System.currentTimeMillis() - begin;
			for (int a = 0; a <= 16; a++)
				System.gc();
			memusage[n] = Runtime.getRuntime().totalMemory()
				- Runtime.getRuntime().freeMemory() - mem;
		}

		System.out.printf("cpu%d <- c(", iterations);
		for (int n = 0; n < 30; n++)
			System.out.printf("%d, ", cputime[n]);
		System.out.printf("\b\b)\nmem%d <- c(", iterations);
		for (int n = 0; n < 30; n++)
			System.out.printf("%d, ", memusage[n]);
		System.out.printf("\b\b) ; print(c(min(cpu%d), mean(cpu%d), sd(cpu%d), max(cpu%d)), 3) ; print(c(min(mem%d), mean(mem%d), sd(mem%d), max(mem%d)), 3)\n", iterations, iterations, iterations, iterations, iterations, iterations, iterations, iterations);
	}
}