import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.ArrayList;

import javax.swing.JOptionPane;

public class GeneticAlgorithm {

	public static void main(String args[]) throws IOException {
		int x = 0;
		int z = 0;
		int P = 100;
		int Tr = 20;
		int G = 100;
		int Pr = 80;
		int Pm = 10;
		int Pc = 10;

		PrintWriter out = new PrintWriter(new FileWriter("src/output.txt"));

		String input = JOptionPane.showInputDialog("Please enter the number of generations: ");
		G = Integer.parseInt(input);



		String y;
		ArrayList<Integer> holder = new ArrayList<Integer>();
		int index = 0;
		try {
			//FileInputStream fis = new FileInputStream("src/newfile");
			FileInputStream fis = new FileInputStream("src/CS4006_input_file.txt");
			// FileInputStream("src/CS4006_input_file.txt");

			while ((x = fis.read()) != -1) {
				y = Character.toString((char) x);
				if (Character.isDigit(y.charAt(0))) {
					z = Character.getNumericValue(y.charAt(0));
					holder.add(z);
				}

			}
			fis.close();
		} catch (FileNotFoundException e) {
			System.out.println("error, could not find file");
		}

		// get the number of rows and columns
		int rows = (int) Math.sqrt(holder.size());

		// fill a 2d integer array with the values from the arrayList
		int myArray[][] = new int[rows][rows];
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < rows; j++) {
				myArray[i][j] = (int) holder.get(index);
				index++;
			}
		}

		// makes the array symmetrical and makes sure there are only 0's and 1's
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < rows; j++) {
				if (myArray[i][j] > 1 || myArray[i][j] < 0) {
					myArray[i][j] = 1;
				}
				if (myArray[i][j] != myArray[j][i]) {
					myArray[j][i] = 1;
					myArray[i][j] = 1;
				}
			}
		}
		// end of file reading
		//-------------------------------------------------------------------------------------------------------------------------------------

		//System.out.println("The fitness is: " + getFitness(myArray));

		// creates first population
		ArrayList<int[]> population = new ArrayList<int[]>();
		for (int i = 0; i < P; i++) {
			boolean ready = false;
			boolean equal = false;
			int[] order = generateOrder(rows);

			while (ready == false) {
				order = generateOrder(rows);
				ready = false;
				equal = false;
				for (int j = 0; j < population.size(); j++) {
					if (areOrdersEqual(order, population.get(j)) == true) {
						equal = true;
					}
				}

				if (equal == true) {
					ready = false;
				} else {
					ready = true;
				}
			}
			population.add(order);
		}

		//start generation for loop
		for(int g = 0; g< G; g++){

		ArrayList<int[]> matingPool = new ArrayList<int[]>();
		matingPool = tournament(P, Tr, population, myArray);
		ArrayList<int[]> generation = new ArrayList<int[]>();

		System.out.println("MatingPool ----------------------------------------------------------------------------------");
		for(int i = 0; i < matingPool.size(); i++){
			System.out.print("Mating i: " + i + " ");
			int[] temp = matingPool.get(i);
			//String output = "";
			for (int j = 0; j < temp.length; j++) {
				//System.out.print(temp[j]);
				//output += temp[j];
			}
			System.out.print(" Fitness: " + applyOrder(myArray, temp ,rows));
			System.out.println();
		}
		System.out.println("-----------------------------------------------------------------------------------------------");

		//
		//
		// Error below this. reproduction is grabbing orderings from mutation for some reason
		//
		//
		for(int i = 0; i< P; i++){
		int number =  (int) (Math.random() * 100);
		if(number < Pr){
			System.out.println("------------------------Reproduction");
			//Reproduction
			/*System.out.println("MatingPool ----------------------------------------------------------------------------------");
			for(int j = 0; j < matingPool.size(); j++){
				System.out.print("Mating j: " + j + " ");
				int[] temp = matingPool.get(j);
				//String output = "";
				for (int k = 0; k < temp.length; k++) {
					System.out.print(temp[k]);
					//output += temp[j];
				}
				System.out.print(" Fitness: " + applyOrder(myArray, temp ,rows));
				System.out.println();
			}
			*/
			//System.out.println("-----------------------------------------------------------------------------------------------");
			System.out.println("Mating Pool size is: " + matingPool.size());
			int num = (int) (Math.random() * matingPool.size());
			System.out.println("num is: " + num);
			int[] temp = matingPool.get(num);
			System.out.print("Temp is: ");
			System.out.println(applyOrder(myArray, temp, rows));
			matingPool.remove(num);
			int[] order = reproduction(temp);
			System.out.print("Reproduction: ");
			System.out.println(applyOrder(myArray, order, rows));
			//System.out.println();
			generation.add(order);

			}
		if(number >= Pr && number < (Pr+Pm)){
			//Mutation
			System.out.println("--------------------------------------------------Mutation");
			int num2 = (int) (Math.random() * matingPool.size());
			int[] temp2 = matingPool.get(num2);
			System.out.println("temp2 is: ");
			System.out.println(applyOrder(myArray, temp2, rows));
			matingPool.remove(num2);
			int[] order2 = mutation(temp2);
			generation.add(order2);
			System.out.print("Mutation: ");
			System.out.println(applyOrder(myArray, order2, rows));
			}
		if(number >= (Pr+Pm) && number < (Pr+Pm+Pc)){
			//Crossover
			if(matingPool.size()!=1){
				System.out.println("-----------------------------------------------------Crossover");
				int num = (int) (Math.random() * matingPool.size());
				int[] temp1 = matingPool.get(num);
				matingPool.remove(num);

				int num2 = (int) (Math.random() * matingPool.size());
				int[] temp2 = matingPool.get(num2);
				matingPool.remove(num2);

				ArrayList<int[]> results = crossover(temp1, temp2);
				int[] child1 = results.get(0);
				int[] child2 = results.get(1);

				generation.add(child1);
				System.out.print("Crossover1: ");
				System.out.println(applyOrder(myArray, child1, rows));
				generation.add(child2);
				System.out.print("Crossover2: ");
				System.out.println(applyOrder(myArray, child2, rows));
				i++;
				}else{
					//if matingPool size is 1 then crossover can't be performed so a reproduction is performed instead
					int num = (int) (Math.random() * matingPool.size());
					int[] temp = matingPool.get(num);
					matingPool.remove(num);
					int[] order = reproduction(temp);
					generation.add(order);
					System.out.print("Unusual Reproduction: ");
					System.out.println(applyOrder(myArray, order, rows));
				}
			}
		}






		for(int i = 0; i < generation.size(); i++){
			int[] temp = generation.get(i);
			String output = "";
			for (int j = 0; j < temp.length; j++) {
				//System.out.print(temp[j]);
				output += temp[j];
			}

			output += " Fitness: " + applyOrder(myArray, temp ,rows);
			out.write(output);
			out.write("\r\n");
			out.flush();

			//System.out.print(" Fitness: " + applyOrder(myArray, temp ,rows));
			//System.out.println();
		}

		int[] temp = generation.get(0);
		int lowest = applyOrder(myArray, temp, rows);

		for(int i = 0; i < generation.size(); i++){
			 temp = generation.get(i);
			 int num = applyOrder(myArray, temp, rows);
			 if(num < lowest){lowest = num;}
		}


		population =  generation;

		System.out.println("The lowest fitness in this generation was: " + lowest);
		System.out.println();
		System.out.println();
		out.println("The lowest fitness in this generation was: " + lowest);
		out.println();
		out.println();
		out.flush();


		//end generation forloop
		}



	}

	// end of main





	//-----------------------------------------------------------------------------------------------------------------------------------------




	public static ArrayList<int[]> crossover(int[] parent1, int[] parent2){
		int[] child1 = new int[parent1.length];
		//orders filled with -1 to stop comparison with generated 0's
		for(int q = 0; q < child1.length; q++){
			child1[q] = -1;
		}
		int[] child2 = new int[parent1.length];
		for(int q = 0; q < child2.length; q++){
			child2[q] = -1;
		}
		int added1 = 0;
		int added2 = 0;
		int turn = 1;
		boolean flag = false;
		int i = 0;
		int j = 0;
		ArrayList<int[]> results = new ArrayList<int[]>();




		//loop to generate the first child
		while(added1 < parent1.length){


			if(turn == 1){
				for (int k = 0; k < child1.length; k++) {
					if (parent1[i] == child1[k]) {
						flag = true;
					}
				}

				if(flag == false){
					child1[added1] = parent1[i];
					added1++;
				}
				i++;
				flag = false;
				turn = 2;
			}


			if(turn == 2){
				for (int k = 0; k < child1.length; k++) {
					if (parent2[j] == child1[k]) {
						flag = true;
					}
				}

				if(flag == false){
					child1[added1] = parent2[j];
					added1++;
				}
				j++;
				flag = false;
				turn = 1;
			}
		}

		i = 0;
		j = 0;
		turn = 2;

		//loop to generate the second child
		while(added2 < parent1.length){
			if(turn == 1){
				for (int k = 0; k < child2.length; k++) {
					if (parent1[i] == child2[k]) {
						flag = true;

					}
				}

				if(flag == false){
					child2[added2] = parent1[i];
					added2++;
				}
				i++;
				flag = false;
				turn = 2;
			}

			if(turn == 2){
				for (int k = 0; k < child2.length; k++) {
					if (parent2[j] == child2[k]) {
						flag = true;
					}
				}

				if(flag == false){
					child2[added2] = parent2[j];
					added2++;
				}
				j++;
				flag = false;
				turn = 1;
			}
		}

		//System.out.print("parent1 is: ");
		//printOrder(parent1);
		//System.out.print("parent2 is: ");
		//printOrder(parent2);
		//System.out.print("child1 is: ");
		//printOrder(child1);
		//System.out.print("child2 is: ");
		//printOrder(child2);

		results.add(child1);
		results.add(child2);
		return results;

	}

	//---------------------------------------------------------------------------------------

	public static int[] mutation(int[] order){

		int index1 = (int) (Math.random() * order.length);
		int index2 = (int) (Math.random() * order.length);

		int temp = order[index1];
		order[index1] = order[index2];
		order[index2] = temp;

		return order;

	}

	//---------------------------------------------------------------------------------------

	public static int[] reproduction(int[] order){
		return order;
	}


	//---------------------------------------------------------------------------------------
	public static ArrayList<int[]> tournament(int P, int Tr, ArrayList<int[]> population, int[][] myArray){
		ArrayList<int[]> matingPool = new ArrayList<int[]>();
		int rows = myArray[0].length;


		for(int k = 0; k < P; k++){

		ArrayList<int[]> tournament = new ArrayList<int[]>();

		// pick Tr orders from the population and add them to an ArrayList
		for (int i = 0; i < Tr; i++) {
			int num = (int) (Math.random() * population.size());
			tournament.add(population.get(num));
		}


		// Get the Fitness of the candidates and add them to an ArrayList
		ArrayList<Integer> candidatesFitness = new ArrayList<Integer>();
		for (int i = 0; i < Tr; i++) {

			int[] candidate = tournament.get(i);
			int canFitness = applyOrder(myArray, candidate, rows);
			candidatesFitness.add(canFitness);
		}

		int fit = candidatesFitness.get(0);
		int pos = 0;
		for (int i = 0; i < candidatesFitness.size(); i++) {
			//System.out.println("candidatesFitness.get(i) is: " + candidatesFitness.get(i));
			if (candidatesFitness.get(i) < fit) {
				fit = candidatesFitness.get(i);
				pos = i;
			}
		}

		int[] winner = tournament.get(pos);

		int winFitness = applyOrder(myArray, winner, rows);
		System.out.println("winner fitness is: " + winFitness);

		matingPool.add(winner);
		}
		return matingPool;
		}

	//---------------------------------------------------------------------------------------
	public static int applyOrder(int[][] oldArray, int[] anOrder, int rows) {
		int newFitness = 0;
		int[] firstOrder = new int[rows];
		for (int i = 0; i < rows; i++) {
			firstOrder[i] = i;
		}
		int[][] newArray = oldArray.clone();
		for (int j = 0; j < oldArray.length; j++) {
			newArray[j] = oldArray[j].clone();
		}

		for (int i = 0; i < rows; i++) {

			int num1 = firstOrder[i];
			int num2 = anOrder[i];
			newArray = swapColumns(newArray, rows, num1, num2);
			newArray = swapRows(newArray, rows, num1, num2);

		}

		newFitness = getFitness(newArray);
		return newFitness;
	}

	//---------------------------------------------------------------------------------------
	public static int[][] swapColumns(int[][] array, int rows, int index1, int index2) {
		int[][] anArray = array;

		for (int i = 0; i < rows; i++) {
			int temp = anArray[i][index1];
			anArray[i][index1] = anArray[i][index2];
			anArray[i][index2] = temp;
		}

		return anArray;
	}

	//---------------------------------------------------------------------------------------
	public static int[][] swapRows(int[][] array, int rows, int index1,
			int index2) {
		int[][] anArray = array;

		for (int i = 0; i < rows; i++) {
			int temp = anArray[index1][i];
			anArray[index1][i] = anArray[index2][i];
			anArray[index2][i] = temp;
		}

		return anArray;
	}

	//---------------------------------------------------------------------------------------
	public static boolean areOrdersEqual(int[] order1, int[] order2) {
		boolean answer = true;

		for (int i = 0; i < order1.length; i++) {
			if (order1[i] != order2[i]) {
				answer = false;
			}
		}

		return answer;
	}

	//---------------------------------------------------------------------------------------
	public static int[] generateOrder(int rows) {
		int[] anOrder = new int[rows];
		for (int i = 0; i < rows; i++) {
			boolean ready = false;
			boolean flag = false;
			int num = 0;

			while (ready == false) {
				// System.out.println("generateOrder while");
				flag = false;

				num = (int) (Math.random() * rows);
				num++;

				// check to see if the num is already in the order
				for (int j = 0; j < anOrder.length; j++) {
					if (num == anOrder[j]) {
						flag = true;
					}
				}

				if (flag == false) {
					ready = true;
				}

			}

			anOrder[i] = num;
		}

		// because the array is filled with 0's to begin with all numbers are
		// increased by 1 when generated to stop comparisons between
		// the generated 0's and the 0's in the array from showing a used space.
		// this loop drops the ordering by 1 to show the real numbers generated
		for (int i = 0; i < anOrder.length; i++) {
			anOrder[i]--;
		}

		return anOrder;
	}

	//---------------------------------------------------------------------------------------
	public static void printOrder(int[] order) {
		for (int i = 0; i < order.length; i++) {
			System.out.print(order[i]);
		}
	}


	//---------------------------------------------------------------------------------------
	static int getFitness(int[][] myArray) {
		int[] ar = myArray[0];
		int rows = ar.length;
		int fitness = 0;
		int temp = 0;
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < rows; j++) {
				if (myArray[i][j] != 0) {
					temp = i - j;
					if (temp < 0) {
						temp = (temp * -1);
					}
					fitness = fitness + temp;
				}
			}
		}
		return fitness;
	}

}