/*----------------------------------------------------------------------+
|      Title:	Herd.java                                               |
|                                                                       |
|      Author:	David E. Joyce                                          |
|           Department of Mathematics and Computer Science              |
|           Clark University                                            |
|           Worcester, MA 01610-1477                                    |
|           U.S.A.                                                      |
|                                                                       |
|           http://aleph0.clarku.edu/~djoyce/                           |
|           djoyce@clarku.edu                                           |
|                                                                       |
|      Date:    May, 2002.                                              |
+----------------------------------------------------------------------*/

import java.awt.*;

public class Herd {

  private boolean matchTrace = false;
  private boolean playTrace = false;

  // data about the herd itself
  private int population, maximumPopulation;
  private Genome P[];  // array of players

  // variables used in the simulations
  private int Q[];     // array of quitters' indices
  private int nQ;      // number of quitters
  private int partner[];
  private int movenumber[];
  private int payoff[][];
  private int thisMove[],lastMove[],previousMove[];
  private int vitality[];
  private int highVitals[];
  private Color genomeColor[];

  public Herd(int initialPopulation, int maximumPopulation, int initialVitality) {
    this.population = initialPopulation;
    this.maximumPopulation = maximumPopulation;
    // Create the players
    P = new Genome[maximumPopulation*2];  // can temporarily grow larger
    vitality = new int[maximumPopulation*2];
    for (int p=0; p<population; ++p) {
      P[p] = new Genome();
      P[p].randomize();
      vitality[p] = initialVitality;
    }
    Q = new int[maximumPopulation];
    partner = new int[maximumPopulation];
    movenumber = new int[maximumPopulation];
    thisMove = new int[maximumPopulation];
    lastMove = new int[maximumPopulation];
    previousMove = new int[maximumPopulation];
    genomeColor = new Color[maximumPopulation];
    highVitals = new int[maximumPopulation];
  }//createPlayers

  public int getPopulation() {return population;}

  public Genome getRandomPlayer() {
    return P[(int)(Math.random()*population)];
  }

  public void runMatch(int lengthOfMatch, int payoffIn[][]) {
    if (matchTrace)
      System.out.println("\nBeginning a match...");
    payoff = payoffIn;
    // Clear the partners array and set up the quitters array
    for (int p=0; p<population; ++p) {
      partner[p] = -1;
       Q[p]=p;
    }
    nQ = population;
    // now do all the plays
    for (int r=0; r<lengthOfMatch; ++r) {
      if (playTrace)
        System.out.println("Play number "+r+"...");
      matchPlayers();
      // let each player have a turn
      for (int p=0; p<population; ++p)
        if (partner[p] != -1 && p < partner[p]) {
          if (playTrace)
            System.out.print("  Players "+p+"("+vitality[p]+") vs "
	                     +partner[p]+"("+vitality[partner[p]]+")");
          play(p,partner[p]);
        }
    } //for r
  } // runMatch

  private void matchPlayers() {
     //Shuffle Q
    for (int i=0; i<nQ-1; ++i) {
      int j = i + (int)((nQ-i)*Math.random());
      int temp = Q[i];
      Q[i] = Q[j];
      Q[j] = temp;
    }
    // now adjacent pairs will pair off, starting at the end
    while (nQ>=2) {
// possibly one player won't be matched
      int first = Q[--nQ];
      int second = Q[--nQ];
      if (playTrace)
        System.out.println("  Pairing "+first+" and "+second);
      partner[first] = second;
      partner[second] = first;
      movenumber[first] = 0;
      movenumber[second] = 0;
    }
  } // matchPlayers

  private void play(int a, int b) {
    // determine what move each player is going to make
    if (movenumber[a] == 0) {
      thisMove[a] = P[a].firstMove();
      thisMove[b] = P[b].firstMove();
    } else if (movenumber[a] == 1) {
      thisMove[a] = P[a].secondMove(previousMove[a],previousMove[b]);
      thisMove[b] = P[b].secondMove(previousMove[b],previousMove[a]);
    } else  {
      thisMove[a] = P[a].thirdMove(lastMove[a],lastMove[b],
        previousMove[a],previousMove[b]);
      thisMove[b] = P[b].thirdMove(lastMove[b],lastMove[a],
        previousMove[b],previousMove[a]);
    }
    // add their payoffs
    vitality[a] += payoff[thisMove[a]][thisMove[b]];
    vitality[b] += payoff[thisMove[b]][thisMove[a]];
    if (playTrace)
      System.out.print(" move "+movenumber[a]+": "+thisMove[a]+thisMove[b]+
                       " vitals: "+vitality[a]+" "+vitality[b]);
    // does ether want to break the partnership, or does either have
    // a negative vitality?
    if (P[a].leave(thisMove[a],thisMove[b]) ||
        P[b].leave(thisMove[b],thisMove[a]) ||
        vitality[a]<0 || vitality[b]<0) {
      partner[a] = -1;
      partner[b] = -1;
      if (vitality[a] >= 0)
        Q[nQ++] = a;
      if (vitality[b] >= 0)
        Q[nQ++] = b;
      if (playTrace)
        System.out.println(" leaves");
    } else {
      previousMove[a] = lastMove[a];
      previousMove[b] = lastMove[b];
      lastMove[a] = thisMove[a];
      lastMove[b] = thisMove[b];
      movenumber[a]++;
      movenumber[b]++;
      if (playTrace)
        System.out.println();
    }
    return;
  } // play

  public void death () {  // Remove players with negative scores
    for (int p=0; p<population; ++p)
      if (vitality[p] <= 0) {
        if (matchTrace)
          System.out.println("  Player "+p+" dies.");     
        P[p] = P[--population];
      }
  } // death

  // Create new players.
  public void birth (int thresholdVitality, double asexual) {
    // First find the animals with high vitalities
    int h = 0;
    for (int p=population-1; p>=0;--p)
      if (vitality[p] >= thresholdVitality)
        highVitals[h++] = p;
    // Next, determine how many will breed sexually
    int sexual = (int)(h*(1.0-asexual));
    if (sexual%2 == 1)
      sexual--;  // must be even
    if (matchTrace)
      System.out.println("  Reproduction, sexual="+sexual+" asexual="+(h-sexual));
    // first do the sexual reproduction
    for (int i=0; i<sexual; i+=2) {
      // select two for the parents
      int tempIndex = i + (int)(Math.random()*(h-i));
      int temp = highVitals[i];
      highVitals[i] = highVitals[tempIndex];
      highVitals[tempIndex] = temp;
      tempIndex = i+1 + (int)(Math.random()*(h-i-1));
      temp = highVitals[i+1];
      highVitals[i+1] = highVitals[tempIndex];
      highVitals[tempIndex] = temp;
      int mom = highVitals[i];
      int dad = highVitals[i+1];
      // create two new animals from them
      P[population] = Genome.cross(P[mom],P[dad]);
      P[population+1] = Genome.cross(P[mom],P[dad]);
      vitality[mom] /= 2;
      if (vitality[mom] > thresholdVitality) // no player is allowed too much vitality
          vitality[mom] = thresholdVitality;
      vitality[dad] /= 2;
      if (vitality[dad] > thresholdVitality) // no player is allowed too much vitality
          vitality[dad] = thresholdVitality;
      vitality[population] = (vitality[mom] + vitality[dad])/2;
      vitality[population+1] = vitality[population];
      if (matchTrace)
        System.out.println("  Players "+population+" and "+(population+1)
          +" created with parents "+mom+" and "+dad+", vitality: "+vitality[population]);
      population += 2;
    }
    // then do the asexual reproduction
    for (int i=sexual; i<h; ++i) {
        int p = highVitals[i];
        P[population] = P[p].duplicate();
        vitality[p] /= 2;
        if (vitality[p] > thresholdVitality)   // no player is allowed too much vitality
          vitality[p] = thresholdVitality;
        vitality[population] = vitality[p];
        if (matchTrace)
          System.out.println("  Player "+population+" clones player "+p+", vitality: "+vitality[p]);
        population++;
      } //if
  }  // birth

  public void reduce(int maximumPopulation) {
    // Next, if there are too many players, randomly kill some off
    while (population > maximumPopulation || population > this.maximumPopulation) {
      int d = (int)(Math.random()*population);  // player d goes
      P[d] = P[--population];
      vitality[d] = vitality[population];
      if (matchTrace)
        System.out.println("  Player "+d+" randomly dies.");
    } //while
  }  // birth

  public void mutate(double mutationRate, double mutationSize) {
    for (int p=0; p<population; ++p)
      if (Math.random() < mutationRate)
        P[p].mutate(mutationSize);
  } // mutate

  // a band of n players joins the herd
  public void migrateIn (int n, Genome[] band, int[] vitals) {
    while (n > 0) {
      P[population] = band[--n];
      vitality[population++] = vitals[n];
    } // while
  } // migrateIn

  // a band of n players leave the herd
  public void migrateOut (int n, Genome[] band, int[] vitals)  {
    // select n players at random and put them in the band
    while (n > 0) {
      int p = (int)(population*Math.random());
      band[--n] = P[p];
      vitals[n] = vitality[p];
      P[p] = P[--population];
      vitality[p] = vitality[population];
     } // while
  } // migrateOut

  public Color[] getGenomeColor() {
    for (int p=0; p<population; ++p)
      genomeColor[p] = P[p].toColor();
    return genomeColor;
  } //getGenomeColor

  public Stats[] getStats() {
    return Genome.getStats(P,population);
  } //getStats

} // Herd.java