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

// Contents:
// 1. imports
// 2. utilities, including a main for testing
// 3. map template, suitable for copy/paste (line 45)
// 4. skeletons for two exercises (line 74)
// 5. the complete example of incrementing all elements of an int[]
// 6. code for testing the two exercises (called by Utils.main)
// You can ignore 1, 5, and 6 and for 2 you just need to have
// the right lines in MapUtils.main [un]commented.
// To run tests, make MapUtils your main class.

import java.util.concurrent.ForkJoinPool;
// import java.util.concurrent.RecursiveTask; // maps use RecursiveAction
import java.util.concurrent.RecursiveAction; 

class MapUtils {
	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 Maps");
		MapTests.initializeArrays();
		MapTests.testRedactSWords();
//		MapTests.initializeArrays(); // re-initialize because updated in-place
//		MapTests.testRedactToLower();
//		MapTests.initializeArrays(); // re-initialize because updated in-place
//		MapTests.testRedactFirstChar();
	}
}

////////// TEMPLATE FOR MAPS /////////////
/*
class MY_CLASS extends RecursiveAction {
	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 void compute() {
		if(hi - lo < sequential_cutoff) {
			for(int i=lo; i < hi; i++) {
				// process each arr[i]
			}
		} 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();
			right.compute();
			left.join();
		}
	}
	
	static void MY_ALGORITHM(ARRAY_TYPE[] arr) {
		MapUtils.pool.invoke(new MY_CLASS(arr,0,arr.length));
	}
}
*/

////////// EXERCISE #1: Replace each String starting with "S" with "[redacted]" //////////
// use the template as a guide to complete this class
class RedactSWords { // ADD EXTENDS CLAUSE

	// FILL THIS IN
	
	static void redact(String[] arr) {
		// FILL THIS IN (1 LINE)
	}
}

//// EXERCISE #2: Take as parameter a Changer object and apply Changer.m to each element  ///
// use the template as a guide to complete this class
// NOTE: Have to modify template to pass an extra argument
interface Changer {
	String m(String s);
}
class Redact { // ADD EXTENDS CLAUSE
	
	// FILL THIS IN
	
	static void redact(Changer c, String[] arr) {
		// FILL THIS IN (1 LINE)
	}
}
////////COMPLETE EXAMPLE: ARRAY Increment ///////////

class IncrementArray extends RecursiveAction {
	static int sequential_cutoff = 1000;
	int lo;
	int hi;
	int[] arr;
	IncrementArray(int[] a, int l, int h) { lo=l; hi=h; arr=a; }
	
	public void compute() {
		if(hi - lo < sequential_cutoff) {
			for(int i=lo; i < hi; i++)
				arr[i] += 1;
		} else {
			IncrementArray left  = new IncrementArray(arr, lo, (hi+lo)/2);
			IncrementArray right = new IncrementArray(arr, (hi+lo)/2, hi);
			left.fork();
			right.compute();
			left.join();
		}
	}
	
	static void increment(int[] arr) {
		MapUtils.pool.invoke(new IncrementArray(arr,0,arr.length));
	}
}

// Note: Much of this is copied from ReductionTests just so you can have entire "programs"
//       in one file, but it would probably be better to share the array-creation code.
class MapTests {
	// 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 testRedactSWords() {
		// stop at first error since arrays are large
		System.out.println("\nTest RedactSWords");
		for(int i=0; i < allTests.length; i++) {
			String[] beforeArray = new String[allTests[i].length];
			System.arraycopy(allTests[i],0,beforeArray,0,beforeArray.length);
			RedactSWords.redact(allTests[i]);
			int numReplaced = 0;
			for(int j=0; j < beforeArray.length; ++j) {
				String before = beforeArray[j];
				String after = allTests[i][j];
				if(MapUtils.stringMatches(before)) {
					if(after.equals("[redacted]"))
						++numReplaced;
					else {
						System.out.println("WRONG: did not redact " + before + " at position " + j 
											+ " now have " + after);
						break;
					}
				} else if (before == null && after != null) {
					System.out.println("WRONG: erroneously changed null at position " + j 
									   + " to " + after);
					break; 
				} else if (before != null && !before.equals(after)) {					
					System.out.println("WRONG: erroneously changed " + before + " at position " + j
									   + " to " + after);
					break;
				}
			}
			System.out.println(testNames[i] + " redacted " + numReplaced + " words");
		}
	}
	
	//  
	
	static void testRedactToLower() {
		// stop at first error since arrays are large
		Changer c = new Changer() {
			public String m(String s) {
				return s==null ? null : s.toLowerCase();
			}
		};
		System.out.println("\nTest Redact convert to lowercase");
		// first try converting to all capitals
		for(int i=0; i < allTests.length; i++) {
			System.out.println("test " + i);
			String[] beforeArray = new String[allTests[i].length];
			System.arraycopy(allTests[i],0,beforeArray,0,beforeArray.length);
			Redact.redact(c,allTests[i]);
			for(int j=0; j < beforeArray.length; ++j) {
				String before = beforeArray[j];
				String after = allTests[i][j];
				if(before == null && after == null)
					continue;
				if(before == null || after == null || !before.toLowerCase().equals(after)) {
					System.out.println("WRONG: before: " + before + " after: " + after +  
								       " at position " + j);
					break;
				}
			}
		}
	}
	
	static void testRedactFirstChar() {
		// stop at first error since arrays are large
		Changer c = new Changer() {
			public String m(String s) {
				return s==null || s.length() < 2 ? s : s.substring(0,1);
			}
		};
		System.out.println("\nTest Redact convert to just first character");
		// first try converting to all capitals
		for(int i=0; i < allTests.length; i++) {
			System.out.println("test " + i);
			String[] beforeArray = new String[allTests[i].length];
			System.arraycopy(allTests[i],0,beforeArray,0,beforeArray.length);
			Redact.redact(c,allTests[i]);
			for(int j=0; j < beforeArray.length; ++j) {
				String before = beforeArray[j];
				String after = allTests[i][j];
				if((before == null && after == null) || (before.length()==0 && after.length()==0))
					continue;
				if(before == null || after == null || before.length()==0 || after.length()==0
						|| after.length() != 1 || before.charAt(0) != after.charAt(0)) {
					System.out.println("WRONG: before: " + before + " after: " + after +  
								       " at position " + j);
					break;
				}
			}
		}
	}	
}