///////////////////////////////////////////////////////////
//                                                       //
// Practice with ForkJoin Reductions                     //
// Originally Prepared for SIGCSE Workshop, March 2011   //
// Dan Grossman                                          //
//                                                       //
///////////////////////////////////////////////////////////

// Contents:
// 1. imports
// 2. utilities, including a main for testing
// 3. reduction template, suitable for copy/paste (line 44)
// 4. skeletons for four exercises (line 76)
// 5. the complete example of summing an int[]
// 6. code for testing the four exercises (called by ReductionUtils.main)
// You can ignore 1, 5, and 6 and for 2 you just need to have
// the right lines in ReductionUtils.main [un]commented.
// To run tests, make ReductionUtils your main class.

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.RecursiveAction; // But RecursiveTask generally preferred for reductions

class ReductionUtils {
	static ForkJoinPool pool = new ForkJoinPool();
	
	static char START_CHAR = 'S'; // could also be argument to constructor
	static boolean stringMatches(String s) {
		return s != null && s.length() > 0 && s.charAt(0)==START_CHAR;
	}

	// calls testing code at the bottom of the file; just uncomment out
	// lines as you go -- sample output provided, tests explained (a little) at bottom of file
	public static void main(String[] args) {
		System.out.println("Testing Reductions");
		ReductionTests.initializeArrays();
		ReductionTests.testLeftMost();
	//	ReductionTests.testLeftMostIndex();
	//	ReductionTests.testSecondLeftmost();
	//	ReductionTests.testKthLeftmost();
	}
}

////////// TEMPLATE FOR REDUCTIONS /////////////
/*
class MY_CLASS extends RecursiveTask<ANS_TYPE> {
	static int sequential_cutoff = 1000;
	int lo;
	int hi;
	ARRAY_TYPE[] arr;
	MY_CLASS(ARRAY_TYPE[] a, int l, int h) { lo=l; hi=h; arr=a; }
	
	public ANS_TYPE compute() {
		if(hi - lo < sequential_cutoff) {
			ANS_TYPE ans; // initialize ans
			for(int i=lo; i < hi; i++) {
				// update ans using arr[i]
			}
			return ans;
		} else {
			MY_CLASS left  = new MY_CLASS(arr, lo, (hi+lo)/2);
			MY_CLASS right = new MY_CLASS(arr, (hi+lo)/2, hi);
			left.fork();
			ANS_TYPE rightAns = right.compute();
			ANS_TYPE leftAns  = left.join();
			return null; // replace null with combination of leftAns and rightAns
		}
	}
	
	static ANS_TYPE MY_ALGORITHM(ARRAY_TYPE[] arr) {
		return ReductionUtils.pool.invoke(new MY_CLASS(arr,0,arr.length));
	}
}
*/

////////// EXERCISE #1: Leftmost String starting with "S" (or null) //////////
// use the template as a guide to complete this class
class LeftmostStartsWith { // ADD EXTENDS CLAUSE
	
	// FILL THIS IN
	
	static String leftmostStartsWith(String[] arr) {
		return null; // CHANGE THIS
	}
}

//////////EXERCISE #2: Index of Leftmost String starting with "S" (or -1) //////////
// use the template as a guide to complete this class
class LeftmostStartsWithIndex  { // ADD EXTENDS CLAUSE
	
	// FILL THIS IN
	
	static int leftmostStartsWithIndex(String[] arr) {
		return 0; // CHANGE THIS
	}
}

//////////EXERCISE #3: Second leftmost String starting with "S" (or null) //////////
// use the template as a guide to complete this class
class SecondLeftmost { // ADD EXTENDS CLAUSE

	// FILL THIS IN
	
	static String secondLeftmost(String[] arr) {
		return null; // CHANGE THIS
	}
}

//////////EXERCISE #4: k^th leftmost String starting with "S" (or null) //////////
// use the template as a guide to complete this class
// NOTE: Need to modify the template to pass k to the constructor (this is not the hard part)
class KthLeftmost { // ADD EXTENDS CLAUSE

	// FILL THIS IN

	static String kthLeftmost(String[] arr, int k) {
		return null; // CHANGE THIS
	}
}

////////COMPLETE EXAMPLE: ARRAY SUM ///////////
class SumArray extends RecursiveTask<Integer> {
	static int sequential_cutoff = 1000;
	int lo;
	int hi;
	int[] arr;
	SumArray(int[] a, int l, int h) { lo=l; hi=h; arr=a; }
	
	public Integer compute() {
		if(hi - lo < sequential_cutoff) {
			int ans = 0;
			for(int i=lo; i < hi; i++)
				ans += arr[i];
			return ans;
		} else {
			SumArray left  = new SumArray(arr, lo, (hi+lo)/2);
			SumArray right = new SumArray(arr, (hi+lo)/2, hi);
			left.fork();
			int rightAns = right.compute();
			int leftAns  = left.join();
			return leftAns + rightAns; 
		}
	}
	
	static int sum(int[] arr) {
		return ReductionUtils.pool.invoke(new SumArray(arr,0,arr.length));
	}
}

//////////////////////////// Testing ///////////////////////////////////
// You shouldn't have to read/modify the rest of this file --
// it has code to build 5 different large String arrays
// and use them to test each of the four exercises.
//
// This code assumes the classes and static methods are named as provided to you.
////////////////////////////////////////////////////////////////////////

class ReductionTests {
	// test1 is 5042 "AS" followed by repeating pattern of "SUCHi" then 2500 "AS" where i increments
	static int test1_len = 100000;
	static String [] test1 = new String[test1_len];
	
	// test2 is the alphabet "A" "B" "C" repeated (not a good test because of sequential threshold)
	static int test2_len = 100500;
	static String [] test2 = new String[test2_len];
	
	// test3 is like test2 except it has no "S"
	static int test3_len = 100001;
	static String [] test3 = new String[test3_len];
	
	// test4 has exactly one "S" -- at position 99997
	static int test4_len = 150079;
	static String [] test4 = new String[test4_len];
	
	// test5 has exactly two "S" -- at position 5042 and at position 75042
	static int test5_len = 99982;
	static String [] test5 = new String[test5_len];
	
	static String[][] allTests = {test1, test2, test3, test4, test5};
	static String[] testNames = {"test1", "test2", "test3", "test4", "test5"};
	
	static void initializeArrays() {
		int i=0;
		for(; i < 5042; i++)
			test1[i] = "AS";
		for(int k=0; i < test1_len; i+=2501, k++ ) { 
		    test1[i] = "SUCH" + k;
			for(int j=1; j <= 2500 && i+j < test1_len; j++)
				test1[i+j] = "AS";
		}
		i=0;
		for(; i < test2_len; i+=26) {
			for(int j=0; j < 26 && i+j < test2_len; j++)
				test2[i+j] = Character.toString((char)('A' + j));
		}
		i=0;
		for(; i < test3_len; i+=26) {
			for(int j=0; j < 26 && i+j < test3_len; j++) 
				if(j != 'S'-'A')
					test3[i+j] = Character.toString((char)('A' + j));
				else
					test3[i+j] = "";
		}
		i=0;
		for(; i < test4_len; i++)
			test4[i] = "Aardvark";
		test4[99997] = "Salamander";
		i=0;
		for(; i < test5_len; i++)
			test5[i] = "Boa";
		test5[5042] = "Swan";
		test5[75042] = "Sloth";
	}
	
	static void testLeftMost() {
		System.out.println("\nTest LeftmostStartsWith");
		for(int i=0; i < allTests.length; i++) {
			String ans = LeftmostStartsWith.leftmostStartsWith(allTests[i]);
			System.out.println(testNames[i] + " " + ans);
		}
	}

	static void testLeftMostIndex() {
		System.out.println("\nTest LeftmostStartsWithIndex");
		for(int i=0; i < allTests.length; i++) {
			int ans = LeftmostStartsWithIndex.leftmostStartsWithIndex(allTests[i]);
			System.out.println(testNames[i] + " " + ans);
		}
	}

	static void testSecondLeftmost() {
		System.out.println("\nTest SecondLeftmost");
		for(int i=0; i < allTests.length; i++) {
			String ans = SecondLeftmost.secondLeftmost(allTests[i]);
			System.out.println(testNames[i] + " " + ans);
		}
	}
		
	static void testKthLeftmost() {
		// k^th left-most S for k=1,2,7,19,150
		// note: The 5 test arrays aren't ideal for testing here; could add more 
		int[] kValues = {1,2,7,19,150};
		for(int j=0; j < kValues.length; j++) {
			System.out.println("\nTest KthLeftmost with k = " + kValues[j]);
			for(int i=0; i < allTests.length; i++) {
				String ans = KthLeftmost.kthLeftmost(allTests[i], kValues[j]);
				System.out.println(testNames[i] + " " + ans);
			}
		}
	}		
}