import java.util.Arrays;

/**
 * http://stackoverflow.com/questions/5566190/is-this-searching-algorithm-optimal
 * 
 * I have two lists, L and M, each containing thousands of 64-bit unsigned integers. I need to find out whether the sum of any two members of L is itself a member of M.
 */
public abstract class SumSearch {

	private static final String QUESTION_TITLE = "Is this searching algorithm optimal?";
	private static final String QUESTION_URL = "http://stackoverflow.com/questions/5566190/is-this-searching-algorithm-optimal";
	private static final int BAKER_REP = 1981;
	private static final int LARSEN_REP = 4182;
	private static final int ANDERSON_REP = 4152;

	private static final int WARMUP_INNERLOOPS = 250; // empirically seems to be enough at n=50
	private static final int REPLICATES = 100;

	public static void main(String[] args) {
		int n = (ANDERSON_REP + LARSEN_REP + BAKER_REP) / 3;
		int sparsity = 10;
		boolean covering = true;
		long seed = (long) QUESTION_URL.hashCode() * (long) QUESTION_TITLE.hashCode();

		for (int i = 0; i < 3; ++i) {
			main(new BakerSearch(), n, sparsity, covering, seed);
			main(new LarsenSearch(0.75f), n, sparsity, covering, seed);
			main(new AndersonSearch(), n, sparsity, covering, seed);
		}
	}

	public static void main(SumSearch searcher, int n, int sparsity, boolean covering, long seed) {
		long[] l = new long[n];
		long[] m = new long[n];

		ArrayFiller filler = new ArrayFiller(seed, sparsity, covering);

		filler.fillArrays(l, m);
		int count = new BakerSearch().search(l, m); // use Baker's algorithm to define the correct count

		// warm up
		for (int i = 0; i < Math.min((WARMUP_INNERLOOPS / n), 1); i++) {
			long time = time(searcher, l, m, filler, count);
			System.out.println("" + time);
		}

		// measure
		long[] timings = new long[REPLICATES];
		for (int i = 0; i < timings.length; i++) {
			timings[i] = time(searcher, l, m, filler, count);
		}

		Arrays.sort(timings);
		System.out.println(searcher);
		System.out.println("min: " + timings[0]);
		System.out.println("med: " + timings[timings.length / 2]);
		System.out.println("95%: " + timings[(int) (timings.length * 0.95)]);
		System.out.println("max: " + timings[timings.length - 1]);
		System.out.println();
	}

	private static long time(SumSearch searcher, long[] l, long[] m, ArrayFiller filler, int expectedCount) {
		filler.fillArrays(l, m);

		long t0 = System.nanoTime();
		int count = searcher.search(l, m);
		long t1 = System.nanoTime();
		if (count != expectedCount) throw new AssertionError("expected " + expectedCount + " but got " + count);

		return t1 - t0;
	}

	protected abstract int search(long[] l, long[] m);

}