public class Main {


	/* TODO: checkForInterleaving method must call itself recursively
	 * in order to find different permutations of x and y within itself.
	 *
	 * Example is on line 38
	 *
	 */

	public static int[] copyArrayFromPosition(int[] array, int position) {
		int[] newArray = new int[array.length-position];
		for (int i = 0; i <array.length-position; i++) {
			newArray[i] = array[i+position];
		}
		return newArray;
	}


	public static boolean checkForInterleaving(int[] x, int[] y, int[] s, String priority) {

		int x_counter = 0;
		int y_counter = 0;
		int matchedUpto;
		boolean is_interleaving = true;


		for (int i = 0; i < s.length; i++) {

			/* This needs to be recursive
			 * A large array needs to be created in order to keep track of all
			 * permutations of organizing x and y
			 * ie, if x and y match at some point the remaining indices
			 * need to also interleave given that certain Xes and Yes have matched
			 * to a certain point.
			 */
			if(s[i] != x[x_counter] && s[i] != y[y_counter]) {
				is_interleaving = false;
				break;
			}
			if(s[i] == x[x_counter] && s[i] == y[y_counter]) {
				s = copyArrayFromPosition(s, i);

			}

			if(priority == "x") {
			if(s[i] == x[x_counter]) {
				x_counter++;
			} else if(s[i] == y[y_counter]) {
				y_counter++;
			}
			else {
				if (s[i] == y[y_counter]) {
					y_counter++;
				}
				else if(s[i] == x[x_counter]) {
					x_counter++;
				}
			}

			}


			if(x_counter > x.length-1 ) {
				x_counter = 0;
			}

			if(y_counter > y.length-1) {
				y_counter = 0;
			}
		}
		if(x_counter != x.length || y_counter != y.length) {
			is_interleaving = false;
		}
		return is_interleaving;
	}

	/* Returns an array with last element deleted */

	public static int[] deleteFromEnd(int[] array) {
		int[] newArray;
		newArray = new int[array.length-2];
		for(int i = 0; i < array.length-2; i++) {
			newArray[i] = array[i];
		}
		return newArray;
	}

	public static int[] deleteFromBeginning(int[] array) {
		int[] newArray;
		newArray = new int[array.length-2];
		for( int i = 0; i < array.length-2; i++) {
			newArray[i] = array[i+1];
		}
		return newArray;
	}


	public static void printOutArray(int[] array) {
		for(int i = 0; i < array.length; i++ ) {
			System.out.print(array[i] + ", ");
		}
		System.out.println("");
	}



	public static void main(String[] args) {
		int s[] = new int[] {1,0,0,0,1,0,1,0,1,1,1,1};
		int x[] = new int[] {1,0,1};
		int y[] = new int[] {0};
		int x_size = x.length;
		int y_size = y.length;
		int s_size = s.length;
		int[] deleteFromEndS = s;
		int[] deleteFromBeginningS = s;

		printOutArray(s);
		while(checkForInterleaving(x,y,s,"x") != true && s_size > (x_size + y_size)) {
			deleteFromEndS =deleteFromEnd(s);
		}
		while(checkForInterleaving(x,y,s,"x") != true && s_size > (x_size + y_size)) {
			deleteFromBeginningS= deleteFromBeginning(s);
		}


		printOutArray(s);

		// TODO: Check for interleaving from the front, Backtrack if failing to check for
		// different orderings of x and y
	}



	}