import java.util.*;
import java.io.*;

class CycleCrossoverDemo
{
    static int searchParent(char [] p, char c)
    {
        for(int i = 0; i < p.length; i++)
            if(p[i] == c)
                return i;
        return 0; //won't get here
    }
    static void printArray(char [] a)
    {
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println("");
    }
    static char [] cycleCrossover(char [] p1, char [] p2, int flag)
    {
        char city;
        int index;
        boolean cycle = true;
        char [] c1 = new char [p1.length];
        for(int i = 0; i < c1.length; i++) //step 1: initialise child with x's
            c1[i] = 'X';

        //start by taking the first city from parent 1.
        c1[0] = p1[0];

        //take next city from parent 2 and put it in the child at that position (i.e. '4' in position 4 in child)
        city = p2[0];
        index = Integer.parseInt(Character.toString(p2[0]))-1;
        c1[index] = city;

        //set up cycle loop
        while(cycle == true)
        {
            index = searchParent(p1, city); //search parent 1 for that char and get index
            city = p2[index]; //look at same index in parent 2, get char
            index = searchParent(p1, city); //search parent 1 for that char, get index
            if(c1[index] == 'X') //if not filled in yet - i.e. haven't had a cycle yet, fill it in
                c1[index] = city;
            else
                cycle = false; //else, have gone in a cycle and exit while loop
        }
        //fill in rest of child path with path of parent 2
        for(int i = 0; i < c1.length; i++)
            if(flag%2==0)
            {
                if(c1[i] == 'X' && c1[i] != p2[i])
                    c1[i] = p2[i];
            }
            else
            {
                if(c1[i] == 'X' && c1[i] != p1[i])
                    c1[i] = p1[i];
            }
        return c1;
    }
    public static void main(String [] args)
    {
        int flag = 1;
        for(int i = 0; i < 100; i++)
        {
            long start = System.currentTimeMillis();
            char [] parent1  = {'1','2','3','4','5','6','7','8','9'};
            char [] parent2 = {'4','1','2','8','7','6','9','3','5'};
            char [] child1;
            child1 = cycleCrossover(parent1, parent2, flag);
            flag++;
            //printArray(child1);
            long end = System.currentTimeMillis();
            long total = end - start;
            System.out.println(total);
        }
        try
        {
            Scanner scan = new Scanner(new File("cctimes.txt"));
            int tot = 0;
            while(scan.hasNextInt())
            {
                tot = tot + scan.nextInt();
            }
            System.out.println("Total is: " + tot);
        }
        catch(IOException e)
        {}

    }
}