import java.lang.*;
import java.awt.*;
import java.applet.*;


public class Population
{
    private  int            Size;
    private  int            ChromosomeLength;
    private  int            GeneMinValue;
    private  int            GeneMaxValue;
    private  int            TopFitness;
    private  Position       Start;
    public   Chromosome[]   Chromosomes;



    public Population(int _Size, int _ChromosomeLength, int _GeneMinValue, int _GeneMaxValue, Position _Start)
    {
        Size            = _Size;
        ChromosomeLength= _ChromosomeLength;
        GeneMinValue    = _GeneMinValue;
        GeneMaxValue    = _GeneMaxValue;
        TopFitness      = 0;
        Start           = _Start;

        // the full-population to hold solutions
        Chromosomes = new Chromosome[Size];
        for(int i=0; i<Size; i++)
        {
            Chromosomes[i] = new Chromosome(ChromosomeLength, GeneMinValue, GeneMaxValue, Start);
        }
    }




    public void RandomGenerate()
    {
        for(int i=0; i<Size; i++)
        {
            Chromosomes[i].RandomGenerate();
        }

        SortByFitness();
    }




    public void CrossOver()
    {
        Chromosome[]    Children = new Chromosome[Size];
        for(int i=0; i<Size; i++)
        {
            Children[i] = new Chromosome(ChromosomeLength, GeneMinValue, GeneMaxValue, Start);
        }


        // double-population to hold children and parents
        // to choose the fittest and replace the population.
        Chromosome[]    ChildrenAndParents = new Chromosome[2*Size];
        for(int i=0; i<2*Size; i++)
        {
             ChildrenAndParents[i] = new Chromosome(ChromosomeLength, GeneMinValue, GeneMaxValue, Start);
        }


        for (int i=0; i<Size/2; i++)    // Size/2 crossovers of i with Size-1-i
        {
            // randomly generate a crossover location
            int CrossOverLocation = (int)(Math.random() * ChromosomeLength);
            //int CrossOverLocation = (int)(Math.random() * ChromosomeLength) + TopFitness;

            for (int j=0; j<ChromosomeLength; j++)
            {
                if (j < CrossOverLocation)
                {
                    Children[i].Gene(j, Chromosomes[i].Gene(j) );
                    Children[Size-1-i].Gene(j, Chromosomes[Size-1-i].Gene(j) );
                }
                else
                {
                    Children[Size-1-i].Gene(j, Chromosomes[i].Gene(j) );
                    Children[i].Gene(j, Chromosomes[Size-1-i].Gene(j) );
                }
            }

            // CalculateFitness() is taken outside Gene(i, value) for efficency
            Children[i].CalculateFitness();
            Children[Size-1-i].CalculateFitness();
        }

        try { QuickSort(Children, 0, Children.length - 1); } catch (Exception e) {}



        // merge children and parents chromosomes
        for(int i=0; i<2*Size; i++)
        {
            if (i<Size)
            {
                for (int j=0; j<ChromosomeLength; j++)
                {
                    ChildrenAndParents[i].Gene(j, Children[i].Gene(j) );
                }
            }
            else
            {
                for (int j=0; j<ChromosomeLength; j++)
                {
                    ChildrenAndParents[i].Gene(j, Chromosomes[i-Size].Gene(j) );
                }
            }
            ChildrenAndParents[i].CalculateFitness();
        }

        // sort merger by fitness
        try { QuickSort(ChildrenAndParents, 0, ChildrenAndParents.length - 1); } catch (Exception e) {}


        // replace some chromosome with the fittest ChildrenAndParents

        for (int i=0; i<Size/10; i++)
        {
            int any = (int)(Math.random() * Size);
            for (int j=0; j<ChromosomeLength; j++)
            {
                Chromosomes[any].Gene(j, ChildrenAndParents[i].Gene(j) );
            }
            Chromosomes[any].CalculateFitness();
        }


        TopFitness = SortByFitness();
    }






    public void Mutate()
    {
        for (int i=0; i<Size; i++)
        {
            int MutationLocation = (int)(Math.random() * (ChromosomeLength));
            Chromosomes[i].Gene(MutationLocation, (int)(Math.random() * (GeneMaxValue+1)));

            // CalculateFitness() is taken outside Gene(i, value) for efficency
            Chromosomes[i].CalculateFitness();
        }
    }






    public void Evolve(Applet _applet, Piece _piece)
    {
        _applet.showStatus("Genetic Algorithms: Generating Initial Population ...");

        RandomGenerate();
        //Display();

        int  NoImprovement  = 0;
        int  LastTopFitness = 0;
        long Generation     = 0L;

        do
        {
            Generation++;
            LastTopFitness = TopFitness;

            if ( (Generation%10L) != 0L)
            {
                CrossOver();
            }
            else
            {
                Mutate();
            }

            if (TopFitness == LastTopFitness)
            {
                NoImprovement++;
            }
            else
            {
                // fill up board with best solution
                _piece.board.Clear();
                _piece.path.Clear();

                int I = Start.i;
                int J = Start.j;
                int[]   dI = {-1, +1, +2, +2, +1, -1, -2, -2};
                int[]   dJ = {-2, -2, -1, +1, +2, +2, +1, -1};
                Position position;
                position = new Position(I, J);
                _piece.board.Visit(position);
                _piece.path.Add(position);
                for(int i=0; i<TopFitness; i++)
                {
                    I = I + dI[Chromosomes[0].Gene(i)];
                    J = J + dJ[Chromosomes[0].Gene(i)];
                    position = new Position(I, J);
                    _piece.board.Visit(position);
                    _piece.path.Add(position);
                }

                _applet.paint(_applet.getGraphics());

                //reset
                NoImprovement = 0;
            }

            _applet.showStatus("Genetic Algorithms:  Generation " + Generation + "   TopFitness " + (TopFitness+1));


        } while( (TopFitness < ChromosomeLength) && (NoImprovement < 100) );

//        if (TopFitness < ChromosomeLength)  // success
        {
      		_applet.play(_applet.getCodeBase(), "audio/whinney.au");
        }
//        else
        {
//      	    _applet.play(_applet.getCodeBase(), "audio/sorry.au");
        }

        Display();
        Chromosomes[0].Display();
    }




    // display progress for debugging
    public void Display()
    {
        System.out.println();
        for (int i=0; i<Size; i++)
        {
            System.out.print(" " + Chromosomes[i].Fitness());
        }
        System.out.println();
    }


    private int SortByFitness()
    {
        try { QuickSort(Chromosomes, 0, Chromosomes.length - 1); } catch (Exception e) {}
        return Chromosomes[0].Fitness();
    }



   private void QuickSort(Chromosome a[], int lo0, int hi0) throws Exception
   {
      int lo = lo0;
      int hi = hi0;
      int midval;

      if ( hi0 > lo0)
      {

         // Arbitrarily establishing partition element as the midpoint of the array.
         midval = a[ ( lo0 + hi0 ) / 2 ].Fitness();

         // loop through the array until indices cross
         while( lo <= hi )
         {
            // starting from the left index.
            // find the first element that is less than or equal to the partition element
	        while( ( lo < hi0 ) && ( a[lo].Fitness() > midval ))
		    {
		        ++lo;
		    }

            // starting from the right index.
            // find an element that is graeter than or equal to the partition element
	        while( ( hi > lo0 ) && ( a[hi].Fitness() < midval ))
		    {
		        --hi;
		    }

            // if the indexes have not crossed, swap
            if( lo <= hi )
            {
               Chromosome temp;
               temp  = a[lo];
               a[lo] = a[hi];
               a[hi] = temp;

               ++lo;
               --hi;
            }
         }

         // If the right index has not reached the left side of array
         // then sort the left partition.
         if( lo0 < hi )
         {
            QuickSort( a, lo0, hi );
         }

         // If the left index has not reached the right side of array
         // then sort the right partition.
         if( lo < hi0 )
         {
            QuickSort( a, lo, hi0 );
         }

      }
   }




}