/*----------------------------------------------------------------------+
|      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;
  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 score[];
  private int cumulativeScore[];
  private Color genomeColor[];

  public Herd(int population) {
    this.population = population;
    // Create the players
    P = new Genome[population];
    for (int p=0; p<population; ++p) {
      P[p] = new Genome();
      P[p].randomize();
    }
    Q = new int[population];
    score = new int[population];
    cumulativeScore = new int[population];
    partner = new int[population];
    movenumber = new int[population];
    thisMove = new int[population];
    lastMove = new int[population];
    previousMove = new int[population];
    genomeColor = new Color[population];
  }//createPlayers

  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 scores, and set up the quitters array
    for (int p=0; p<P.length; ++p) {
      partner[p] = -1;
      score[p] = 0;
      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+" vs "+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) {
      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
    score[a] += payoff[thisMove[a]][thisMove[b]];
    score[b] += payoff[thisMove[b]][thisMove[a]];
    if (playTrace)
      System.out.print(" move "+movenumber[a]+": "+thisMove[a]+thisMove[b]+
                       " scores: "+score[a]+" "+score[b]);
    // does ether want to break the partnership?
    if (P[a].leave(thisMove[a],thisMove[b]) ||
                P[b].leave(thisMove[b],thisMove[a])) {
      partner[a] = -1;
      partner[b] = -1;
      Q[nQ++] = a;
      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 (double deathRate) {  // animals die at the given rate
    for (int p=0; p<population; ++p)
      if (Math.random() < deathRate) {
        if (matchTrace)
          System.out.println("  Player "+p+" dies.");     
        P[p] = null;
      }
  } // death

  // Create new players to replace the dead ones. Use asexual reproduction
  // according to the rate; sexual otherwise.
  public void birth (double asexualRate) { 
    // Compute the cumulative scores across the players
    int cum=0;
    for (int p=0; p<population;++p) {
      if (P[p] != null)
        cum += score[p];
      cumulativeScore[p] = cum;
    }
    // Now, for each removed player, select another.
    for (int p=0; p<population;++p)
      if (P[p] == null)
        if (Math.random()<asexualRate) {
          int clone = selectPlayer(cumulativeScore);
          P[p]= P[clone].duplicate();
          if (matchTrace)
            System.out.println("  Player "+p+" clones player "+clone+", score: "+score[clone]);
        } else {
          int mom = selectPlayer(cumulativeScore);
          int dad = selectPlayer(cumulativeScore);
          P[p] = Genome.cross(P[mom],P[dad]);
        } //if
  }  // birth

  private int selectPlayer(int cumulativeScore[]) {
    // Simply randomly select an existing player's strategy weighted by its score
    int score =(int)(Math.random()*cumulativeScore[population-1]);
    int p;
    for (p=0; p<population; ++p)
      if (cumulativeScore[p]>=score && P[p] != null)
        break;
    if (p == population || P[p] == null) {// error
      System.out.println("Error in Herd.selectStrategy.");
      System.out.println(" p="+p+" score="+score
         +" cumulativeScore[pop-1]="+cumulativeScore[population-1]);
      System.exit(0);
    }
    return p;
  } // selectStrategy

  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) {
    for (int p=0; p<population && n>0; ++p)
      if (P[p] == null) {
        P[p] = band[--n];
        band[n] = null;
      } // if
  } // migrateIn

  // a band of n players leave the herd
  public void migrateOut (int n, Genome[] band)  {
    // select n players at random and put them in the band
    while (n>0) {
      int p = (int)(population*Math.random());
      if (P[p] != null) {
        band[--n] = P[p];
        P[p] = null;
      } // if
    } // 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);
  } //getStats

} // Herd.java