import java.util.*;
import com.jake.*;

/**
  * P4
  *
  * Name: Jacob Whitehill
  */
public class DeduceTheMysteryDataStructureSolution {
	private static void permute (int[] array) {
		final Random random = new Random();
                for (int i = array.length - 1; i >= 0; i--) {
                        final int j = random.nextInt(i+1);
                        final int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                }
        }

	public static void main (String[] args) {
		if (args.length < 2) {
			System.out.println("Usage example: java -cp .:P4Stuff.jar DeduceTheMysteryDataStructure cs12uZZ 3");
			System.exit(1);
		}

		final String cs12UserID = args[0];
		final int mdsIdx = new Integer(args[1]).intValue();

		System.out.println("Assessing time costs for user " + cs12UserID + " structure #" + mdsIdx);
		final Collection12<Integer> mds = MysteryDataStructure.getMysteryDataStructure(cs12UserID, mdsIdx, new Integer(0));

		System.out.println("add(o)");
		measureMethod(mds, 0);
		System.out.println("contains(o)");
		measureMethod(mds, 1);
		System.out.println("remove(o)");
		measureMethod(mds, 2);
	}

	private static void measureMethod (Collection12<Integer> mds, int methodNum) {
		final int[] Ns = { 1, 2, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000 };
		final Random random = new Random();

		for (int i = 0; i < Ns.length; i++) {
			final int N = Ns[i];
			long total = 0;
			final int NUM_TRIALS = 1000;
			for (int trial = 0; trial < NUM_TRIALS; trial++) {
				final int[] numbers = new int[N+1];  // one more than N
				for (int j = 0; j < numbers.length; j++) {
					numbers[j] = j;
				}
				permute(numbers);

				mds.clear();
				for (int j = 0; j < N; j++) {  // don't add last number
					mds.add(numbers[j]);
				}

				final long start = ArtificialClock.getNumTicks();
				if (methodNum == 0) {  // add(o)
					mds.add(N);  // bigger than everything else  -- WHAT ACTUALLY WORKS BETTER (sorry!)
					//mds.add(numbers[N]);  // definitely not contained in structure -- WHAT I HAD SUGGESTED
				} else if (methodNum == 1) { // contains(o)
					mds.contains(numbers[random.nextInt(numbers.length)]);  // definitely already in structure
				} else {  // remove(o)
					mds.remove(numbers[random.nextInt(numbers.length)]);  // definitely already in structure
				}
				final long end = ArtificialClock.getNumTicks();
				total += (end - start);
			}
			final float avg = (float) total / NUM_TRIALS;
			System.out.println(N + "\t" + avg);
		}
	}
}