package neuralnets;
/**
 *Dustin Stevens-Baier
 *
 *original code by Vania Sarieva modified and fine tuned by Dustin
 *
 * TSPGA is the main simulation file. First Cities are initialized. Then random tours are created.
 * The order and distance recombination methods are implemented.
 * 
 * The simulation sets up the correct parameters to write the results to file IO.
 * It then begins the simulation with a maximum number of iterations defined.
 */
import java.io.*;
import java.text.*;
import java.util.*;

public class TSPGA 
{
	private final int numCities = 20;
	private final int maxIterations = 10000;
	private int actualIterations = 0;
	
	private City3[] cities = new City3[numCities];
	private TourCity[] tours = new TourCity[numCities];
	
	private double[] bestTour = new double[maxIterations];
	private double[] worstTour = new double[maxIterations];
	
	public static final double MUTATION_0_PERCENT = 0.0;
	public static final double MUTATION_2_PERCENT = 0.02;
	public static final double MUTATION_4_PERCENT = 0.04;
	public static final double MUTATION_6_PERCENT = 0.06;
	
	public static final int MUTATE_ORDER_METHOD = 1;
	public static final int MUTATE_DIST_METHOD = 2;
	
	private String saveName = "";
	private BufferedWriter bw;
	private NumberFormat nf;
	
	public TSPGA()
	{
		// Initialize all the cities
		for(int i = 0; i < numCities; i++)
		{
			cities[i] = new City3();
		}
		
		// Calculate the random tours for each tour based on city.
		for(int i = 0; i < numCities; i++)
		{
			tours[i] = new TourCity(numCities);
			tours[i].initializeTours();
			tours[i].calculateDistance(cities);
		}
	}
	
	public void runSimulation(double MUTATE_RATE_OPTION, int MUTATE_METHOD, boolean debug)
	{
		setUpFileIO(MUTATE_RATE_OPTION, MUTATE_METHOD);
		System.out.println("RUNING SIMULATION:" + MUTATE_METHOD);
		TourCity dad;
		TourCity mom;
		TourCity child;
		
		int dadIndex = 0;
		int momIndex = 0;
	
		for(int i = 0; i < maxIterations; i++)
		{
			//System.out.println("*************** " + i);
			//showTours();
			// Sort tours by fitness
			sortTourByDistance();		
			bestTour[i] = tours[0].getTraveledDistance();
			worstTour[i] = tours[numCities - 1].getTraveledDistance();
			
			double changeInDist = tours[numCities - 1].getTraveledDistance() - tours[0].getTraveledDistance();
			if(changeInDist == 0)
			{
				System.out.println("CONVERGED at " + i);
				showTours();
				return;
			}
			
			if(debug)
			{
				System.out.println("Before Child: Tour is ");
				showTours();
			}
			
			// Create random dad and mom index
            momIndex = (int)Math.floor(Math.random() * ((numCities - 1) / 2)); //from top half
            dadIndex = (int)Math.floor(Math.random() * (numCities - 1)); //from all
            
            if (momIndex == dadIndex) 
            	dadIndex = (dadIndex + 1) % (numCities - 1);
            
            // Create mom, dad, and child
            mom = tours[momIndex];
            dad = tours[dadIndex];
			child = new TourCity(numCities);
			
            if(debug)
            {
	            System.out.println("Mom Index " + momIndex);
	            System.out.println("Dad Index " + dadIndex);            
	            System.out.print("Mom: " );
				mom.displayTourInfo();
				System.out.print("Dad: " );
				dad.displayTourInfo();
            }

            if(MUTATE_METHOD == MUTATE_ORDER_METHOD)
    		{
            	// Create the child from the order method
            	child = orderMethod(mom, dad, debug);
            	 // Calculate the child distance and set child to last of population.
    		}
            else if(MUTATE_METHOD == MUTATE_DIST_METHOD)
            {
            	// Create the child from the distance method
            	child = distanceMethod(mom, dad, debug);
            	//Calculate the child distance and set child to last of population.
            }
            
            child.calculateDistance(cities);
            tours[numCities - 1] = child;
            
            for(int j = 0; j < numCities; j++)
            {
            	double r = Math.random();
            	if(r < MUTATE_RATE_OPTION)
            	{
        			tours[numCities - 1].mutatorOperatorOne();
        			//tours[numCities - 1].calculateDistance(cities);                   
            	}
            }	            
    		actualIterations = i;
		}
		System.out.println("Converged at " + actualIterations);
		return;
	}
	
	/************************************** ORDER METHOD ********************************************/
	private TourCity orderMethod(TourCity mom, TourCity dad, boolean debug)
	{
		int indexStart = 0;
		int indexEnd = 0;
		int tempIndex = 0;
		int flag = 0;
		
		TourCity child = new TourCity(numCities);
		
		 // Create random mom indices for extraction to child
        indexStart = (int)Math.floor(Math.random() * (numCities - 1));
        indexEnd = (int)Math.floor(Math.random() * (numCities - 1));
                    
        // Make sure indices are not the same
        if(indexStart == indexEnd)
        {
        	indexEnd = (indexEnd + 1) % (numCities - 1);
        }

        if(indexStart > indexEnd)
        {
        	tempIndex = indexStart;
        	indexStart = indexEnd;
        	indexEnd = tempIndex;
        }
        
	    // Set child tour to -1 for later use
		for(int j = 0; j < numCities; j++)
		{
			child.setTourCityVisited(j, -1);
		}
		
		// Extract to child from mom first
        for(int j = indexStart; j <= indexEnd; j++)
        {
        	child.setTourCityVisited(j, mom.getTourCityVisited(j));
        }
		
        // Add father's tour stops (DNA)
        for (int e = 0; e < numCities; e++) 
        {
        	if(child.getTourCityVisited(e) == -1)
            {
                outer:
                for (int f = 0; f < numCities; f++) 
                {
                    flag = 1;
                    for (int m = 0; m < numCities; m++) 
                    {
                           	if(dad.getTourCityVisited(f) == child.getTourCityVisited(m))
                            flag = 0;
                    }

                    if (flag == 1) 
                    {
                    	child.setTourCityVisited(e, dad.getTourCityVisited(f));
                        break outer;
                    }
                }
            }
        }
        
        if(debug)
        {
            System.out.print("After dad: ");
            child.displayTourInfo();
        	System.out.println("After Child: Tour is ");
			showTours();
        }
		return child;
	}

	/************************************* DISTANCE METHOD ****************************************/

	
	private TourCity distanceMethod(TourCity mom, TourCity dad, boolean debug)
	{
		Random r = new Random();
		TourCity child = new TourCity(numCities);
		int z = 0;
		int c1 = 0;
		int c2 = 0;
		int c3 = 0;
		int c4 = 0; 
		int q1 = 0;
		boolean flag;
		
		double distance[][] = new double[numCities][numCities];
		HashMap hm = new HashMap();
		HashSet hs = new HashSet();
		
		// Reset child to -1
		for(int j = 0; j < numCities; j++)
		{
			child.setTourCityVisited(j, -1);
		}
		
		for(int i = 0; i < numCities; i++)
		{
			flag = false;
			for(Iterator itr = hm.values().iterator(); itr.hasNext();)
			{
				q1 = ((Integer)itr.next()).intValue();
                if(hs.add(new Integer(q1)))
                {
                    z = q1;
                    flag = true;
                    break;
                }
	        }
			if(!flag)
			{
	           while(!hs.add(new Integer(z = r.nextInt(numCities))));
	        }
			 
			child.setTourCityVisited(i, mom.getTourCityVisited(z));
			 
			for(int j = 0; j < numCities; ++j)
			{
                if(mom.getTourCityVisited(j) == z)
                {
                    c1 = mom.getTourCityVisited((j - 1 + numCities) % numCities);
                    c2 = mom.getTourCityVisited((j + 1) % numCities);
                }
                if(dad.getTourCityVisited(j) == z)
                {
                    c3 =  dad.getTourCityVisited((j - 1 + numCities) % numCities);
                    c4 =  dad.getTourCityVisited((j + 1) % numCities);
                }
			}
			
			hm.clear();
			hm.put(new Double(distance[c1][z]), new Integer(c1));
			hm.put(new Double(distance[c2][z]), new Integer(c2));
			hm.put(new Double(distance[c3][z]), new Integer(c3));
			hm.put(new Double(distance[c4][z]), new Integer(c4));  
		}
		return child;
	}
	/* Sort tours */
	private void sortTourByDistance() 
	{
        TourCity phTour = new TourCity(numCities);
        TourCity tmpTour1;
        TourCity tmpTour2;

        for (int s1 = numCities - 1; s1 >= 0; s1--) 
        {
            for (int s2 = 0; s2 < s1; s2++) 
            {
                tmpTour1 = tours[s2];
                tmpTour2 = tours[(s2+1)];

                // Swap if necessary
                if (tmpTour1.getTraveledDistance() > tmpTour2.getTraveledDistance()) 
                {
                    for (int x = 0; x < numCities; x++) 
                    {
                        phTour.setTourCityVisited(x, tmpTour1.getTourCityVisited(x));
                    }
                    phTour.setTraveledDistance(tmpTour1.getTraveledDistance());

                    for (int x = 0; x < numCities; x++) 
                    {
                        tmpTour1.setTourCityVisited(x, tmpTour2.getTourCityVisited(x));
                    }
                    tmpTour1.setTraveledDistance(tmpTour2.getTraveledDistance());

                    for (int x = 0; x < numCities; x++) 
                    {
                        tmpTour2.setTourCityVisited(x, phTour.getTourCityVisited(x));
                    }
                    tmpTour2.setTraveledDistance(phTour.getTraveledDistance());
                    
                    tours[s2] = tmpTour1;
                    tours[(s2+1)] = tmpTour2;
                }
            }
        }
	}
	
	/*********************************** FILE IO FOR SIMULATION RESULTS *****************************/
	public void writeSimulation(double MUTATION_RATE, int MUTATION_METHOD)
	{
		int cityVisit = 0;
		nf = NumberFormat.getInstance();
		nf.setMinimumFractionDigits(4);
		
		try
		{
			if(MUTATION_METHOD == MUTATE_ORDER_METHOD)
			{
				//System.out.println("Order Method");
				bw.write("Order Method\n");
			}
			else
			{
				//System.out.println("Distance Method");
				bw.write("Distance Method\n");
			}
			
			if(MUTATION_RATE == MUTATION_0_PERCENT)
			{
				//System.out.println("Mutation Rate 0%");
				bw.write("Mutation Rate 0%\n");
			}
			else if(MUTATION_RATE == MUTATION_2_PERCENT)
			{
				//System.out.println("Mutation Rate 10%");
				bw.write("Mutation Rate 2%\n");
			}
			else if(MUTATION_RATE == MUTATION_4_PERCENT)
			{
				//System.out.println("Mutation Rate 4%");
				bw.write("Mutation Rate 4%\n");
			}
			else if(MUTATION_RATE == MUTATION_4_PERCENT)
			{
				//System.out.println("Mutation Rate 6%");
				bw.write("Mutation Rate 6%\n");
			}
			// Display Generations
			//System.out.println("Generations: " + actualIterations);
			//System.out.println("****************** BEST TOUR *******************");
			
			bw.write("Generations: " + actualIterations + "\n");
			bw.write("\n****************** BEST TOUR *******************\n");
			
			
//			Capture best Tour Data to file
			FileWriter tourWriter = new FileWriter("bestTour8.csv");
			tourWriter.flush();
			//tourWriter.write(bestTour.weight + "\n");
			//City3[] bestCities = bestTour.getCities();
			//for (int i = 0; i < cities.length; i++) {
				
			//}
			
			
			//System.out.println("Best Distance: " + nf.format(tours[0].getTraveledDistance()));
			bw.write("Best Distance: " + nf.format(tours[0].getTraveledDistance()) + "\n");
			
		
			for(int i = 0; i < numCities; i++)
			{
				cityVisit = tours[0].getTourCityVisited(i);
				String cityCoord = "";
				if(cityVisit < 9)
					cityCoord = "0";
				
				tourWriter.write(cities[cityVisit].getXCoord() + "," + cities[cityVisit].getYCoord() + "\n");
				cityCoord += (cityVisit + 1) + ", " + 
			    			 nf.format(cities[cityVisit].getXCoord()) + ", " + 
						     nf.format(cities[cityVisit].getYCoord());
							
				//System.out.println(cityCoord);
			    bw.write(cityCoord + "\n");
			}
			
			
			
			
			cityVisit = tours[0].getTourCityVisited(0);
			String cityCoord = "";
			
			if(cityVisit < 9)
				cityCoord = "0";
			tourWriter.write(cities[cityVisit].getXCoord() + "," + cities[cityVisit].getYCoord() + "\n");
			
			cityCoord += (cityVisit + 1) + ", " + 
			 		      nf.format(cities[cityVisit].getXCoord()) + ", " + 
		                  nf.format(cities[cityVisit].getYCoord());
			tourWriter.close();
			//System.out.println(cityCoord);
			bw.write(cityCoord + "\n");
			
			
			//System.out.println("************** BEST/WORST TOUR DISTANCE***************");
			bw.write("\n************** BEST/WORST TOUR DISTANCE***************\n");
			FileWriter tourWriter2 = new FileWriter("fitness8.csv");
			tourWriter2.flush();
			for(int i = 0; i < actualIterations; i++)
			{
				tourWriter2.write(bestTour[i] + "," + worstTour[i] + "\n");
				
				//System.out.println(i + ", " + nf.format(bestTour[i]) + ", " + nf.format(worstTour[i]));
				bw.write(i + ", " + nf.format(bestTour[i]) + ", " + nf.format(worstTour[i]) + "\n");
			}
			tourWriter2.close();
			bw.close();
		}
		catch(IOException e)
		{System.err.println(e);}
		
	}
	private void showTours()
	{
		for(int i = 0; i < numCities; i++)
		{
			tours[i].displayTourInfo();
		}
	}
	
	private void setUpFileIO(double MUTATION_RATE, int MUTATION_OPTION)
	{
		if(MUTATION_RATE == MUTATION_0_PERCENT)
		{
			saveName = "mut_0";
		}
		else if(MUTATION_RATE == MUTATION_2_PERCENT)
		{
			saveName = "mut_2";
		}
		else if(MUTATION_RATE == MUTATION_4_PERCENT)
		{
			saveName = "mut_4";
		}
		else if(MUTATION_RATE == MUTATION_6_PERCENT)
		{
			saveName = "mut_6";
		}
		if(MUTATION_OPTION == MUTATE_ORDER_METHOD)
		{
			saveName += "_order.txt";
		}
		else if(MUTATION_OPTION == MUTATE_DIST_METHOD)
		{
			saveName += "_distance.txt";
		}
		
		try
		{
			bw = new BufferedWriter(new FileWriter(saveName));
		}
		catch(IOException e)
		{System.err.println(e);}
	}
}