package algs11;
import stdlib.*;
import java.util.Arrays;

/* ***********************************************************************
 *  Compilation:  javac BinarySearch.java
 *  Execution:    java BinarySearch whitelist.txt input.txt
 *  Data files:   http://algs4.cs.princeton.edu/11model/tinyW.txt
 *                http://algs4.cs.princeton.edu/11model/tinyT.txt
 *                http://algs4.cs.princeton.edu/11model/largeW.txt
 *                http://algs4.cs.princeton.edu/11model/largeT.txt
 *
 *  % java BinarySearch tinyW.txt tinyT.txt
 *  50
 *  99
 *  13
 *
 *  % java BinarySearch largeW.txt largeT.txt
 *  499569
 *  984875
 *  295754
 *  207807
 *  140925
 *  161828
 *  [3,675,966 total values]
 *
 *************************************************************************/
public class BinarySearch {

	// This is a simple rank function
	// It works fine for small arrays
	public static int rank0(double key, double[] a) {
		for (int i = 0; i < a.length; i++)
			if (a[i] == key) return i;
		return -1;
	}

	// Here is more efficient version, coded three ways
	// precondition: array a[] is sorted
	public static int rank(double key, double[] a) {
		return rankHelper1 (key, a, 0, a.length - 1);
	}

	// Here is  a standard
	public static int rankHelper1(double key, double[] a, int lo, int hi) {
		// key is in a[lo..hi] or not present.
		if (lo > hi) return -1;
		int mid = lo + (hi - lo) / 2;
		if      (key < a[mid]) return rankHelper1 (key, a, lo, mid - 1);
		else if (key > a[mid]) return rankHelper1 (key, a, mid + 1, hi);
		else return mid;
	}

	// This is the same, but uses a loop
	public static int rankHelper2(double key, double[] a, int lo, int hi) {
		while (lo <= hi) {
			// key is in a[lo..hi] or not present.
			int mid = lo + (hi - lo) / 2;
			if      (key < a[mid]) hi = mid - 1;
			else if (key > a[mid]) lo = mid + 1;
			else return mid;
		}
		return -1;
	}

	// This is the same, but written with explicit variables
	public static int rankHelper3(double key, double[] a, int lo, int hi) {
		if (lo > hi) return -1;
		int result;
		int mid = lo + (hi - lo) / 2;
		if (key < a[mid])
			result = rankHelper3 (key, a, lo, mid - 1);
		else if (key > a[mid])
			result = rankHelper3 (key, a, mid + 1, hi);
		else
			result = mid;
		return result;
	}

	public static void testTrace(String whitelistFile, int key) {
		// get whitelist from file and sort
		double[] whitelist = new In(whitelistFile).readAllDoubles();
		Arrays.sort(whitelist);
		StdOut.println(Arrays.toString(whitelist));

		int rank = rank(key, whitelist);
		if (rank >= 0) {
			StdOut.println(key + " is in the list");
		} else {
			StdOut.println(key + " is NOT in the list");
		}
	}

	public static void testInteractive(String whitelistFile) {
		// get whitelist from file and sort
		double[] whitelist = new In(whitelistFile).readAllDoubles();
		Arrays.sort(whitelist);
		StdOut.println(Arrays.toString(whitelist));

		// read from the console; type Control-D or Control-Z at the beginning of a blank line to stop.
		StdOut.print("Enter a number: ");
		while (!StdIn.isEmpty()) {
			int key = StdIn.readInt();
			int rank = rank(key, whitelist);
			StdOut.format("%d %s in the list\n", key, (rank >= 0) ? "is" : "is not");
			StdOut.print("Enter a number: ");
		}
	}

	public static void testPerformance(String whitelistFile, String keyFile) {
		// get whitelist from file and sort
		double[] whitelist = new In(whitelistFile).readAllDoubles();
		Arrays.sort(whitelist);

		// open key file and start timer
		double[] keys = new In (keyFile).readAllDoubles();
		Stopwatch sw = new Stopwatch();

		// count number of data entries in the whitelist
		int count = 0;
		for (double key : keys) {
			if (rank0(key, whitelist) == -1) {
				//StdOut.println(key); // print to see the data, comment out for performance
				count = count + 1;
			}
		}

		StdOut.format ("%d misses\n%f seconds\n", count, sw.elapsedTime ());
	}

	public static void main(String[] args) {
		testInteractive("data/tinyW.txt");
		//testTrace("data/tinyW.txt", 28);
		//testPerformance("data/tinyW.txt", "data/tinyT.txt");
		//testPerformance("data/largeW.txt", "data/largeT.txt");
		
		// The following lines show why mid is computed as it is
		//int hi = 2_000_000_010;
		//int lo = 2_000_000_005;		
		//StdOut.format ("(hi+lo)/2    = %,d\n", (hi+lo)/2);
		//StdOut.format ("lo+(hi-lo)/2 = %,d\n", lo+(hi-lo)/2);
		
		// Similar things happen when using bit shifting
		//StdOut.format ("(hi+lo)>>1   = %,d\n", (hi+lo)>>1);
		//StdOut.format ("(hi+lo)>>>1  = %,d\n", (hi+lo)>>>1);
	}
}