//
// Discrete Time CA
//
import java.util.*;
import java.io.*;
import java.awt.*;

public class DTCA {

    private int[][] A;
    private int[][] B;
    private int[] neighbourhood;  // Moore neighbourhood
    private int n;                // n X n grid, as a torus
    private int m;                // m species
    private int totalPopulation;  // sum of all populations of species
    private double pointSize;
    private boolean trace;
    private int[] population;     // m population sizes
    private double[] pBirth;      // m birth probabilities
    private double[] pDeath;      // m death probabilities
    private RandomSet freeSpace;  // initially all points on the grid
    private Random gen;
    private boolean draw;         // true <-> plot
    private static int empty = -1;
    private static Color background = Color.LIGHT_GRAY;
    private static Color[] color = {Color.BLUE,Color.RED,Color.YELLOW,Color.GREEN,Color.CYAN,Color.MAGENTA};

    public DTCA(int n,int m,boolean draw){
	this.n          = n;
	this.m          = m;
	totalPopulation = 0;
	pointSize       = 0.4;
	gen             = new Random();
	A               = new int[n][n];
	B               = new int[n][n];
	population      = new int[m];
	pBirth          = new double[m];
	pDeath          = new double[m];
	freeSpace       = new RandomSet(n*n);
	gen             = new Random();
	this.draw       = draw;
	neighbourhood   = new int [9]; // see getNeighbourhood() for explanation
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		freeSpace.add(i*n+j);
		A[i][j] = B[i][j] = -1;
	    }
	Arrays.fill(population,0);
	Arrays.fill(pBirth,0.0);
	Arrays.fill(pDeath,0.0);
	if (draw) plot();
    }
    //
    // n x n grid with m species
    //

    public void add(int species) throws RandomSetException {
	int x = freeSpace.delete();
	int i = x/n;
	int j = x%n;
	A[i][j] = species;
	population[species]++;
	totalPopulation++;
	if (draw) plot(i,j,color[species]);
    }
    //
    // add a new member of species randomly to the population
    //

    public void birth(int species,int[][] X,int i,int j) {
	getToroidalNeighbourhood(X,i,j);
	if (neighbourhood[0] > 0){
	    int k = gen.nextInt(neighbourhood[0]) + 1;
	    int y = neighbourhood[k];
	    X[y/n][y%n] = species;
	    population[species]++;
	    totalPopulation++;
	}
    }

    public void death(int species,int[][] X,int i,int j) {
	X[i][j] = empty;
	population[species]--;
	totalPopulation--;
    }	

    private void getToroidalNeighbourhood(int[][]X,int x,int y){
	int k = 0;
	int xt,yt; // x and y coords on torus
	for (int i=x-1;i<=x+1;i++)
	    for (int j=y-1;j<=y+1;j++){
		xt = i;
		if (i<0) xt = i + n;
                if (i>n-1) xt = n - i;
		yt = j;
		if (j<0) yt = j + n;
                if (j>n-1) yt = n - j;
		if (X[xt][yt] == empty){
		    k++;
		    neighbourhood[k] = xt*n + yt;
		}
	    }
	neighbourhood[0] = k;	
    }

    public void plot() {
	StdDraw.clear(background);
	StdDraw.setXscale(-2,n);
        StdDraw.setYscale(-2,n);
        StdDraw.show(0);	
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++)
		if (A[i][j] != empty){
		    StdDraw.setPenColor(color[A[i][j]]);
		    StdDraw.filledSquare(i,j,pointSize);
		}
	StdDraw.show(0);
    }

    public void plot(int x,int y,Color color){
	StdDraw.setPenColor(color);
	StdDraw.filledSquare(x,y,pointSize);
	StdDraw.show(0);
    }

    public void unPlot(int x,int y){
	StdDraw.setPenColor(background);
	StdDraw.filledSquare(x,y,pointSize+0.02);
	StdDraw.show(0);
    }

    public boolean trace(){trace = !trace; return trace;}
    public boolean getTrace(){return trace;}
    public void    setPointSize(double x){pointSize = x;}
    public int     size(){return n;}
    public int     getPopulation(){return totalPopulation;}
    public void    setPBirth(int species,double p){pBirth[species] = p;}
    public void    setPDeath(int species,double p){pDeath[species] = p;}

    public void pause(long l){
	try{Thread.sleep(l);}
	catch (Exception e) {e.printStackTrace();}
    }

    private void copy(int[][] X,int[][]Y ){
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++)
		Y[i][j] = X[i][j];
    }
    //
    // copy X into Y
    //

    private void doBirths(int[][]X,int[][]Y){
	int species = -1;
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		species = X[i][j];
		if (species != empty && gen.nextDouble() <= pBirth[species])
		    birth(species,Y,i,j);
	    }
    }
    //
    // do births in X onto Y
    //

    private void doDeaths(int[][] X){
	int species = -1;
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		species = X[i][j];
		if (species != empty && gen.nextDouble() <= pDeath[species])
		    death(species,X,i,j);
	    }
    }
    //
    // do deaths on X
    //

    public void doGeneration(int generation){
	copy(A,B);
	doBirths(A,B);
	doDeaths(B);
	copy(B,A);
	if (draw) plot();
	System.out.print(generation +" ");
	for (int i=0;i<m;i++) System.out.print(population[i] + " ");
	System.out.println(totalPopulation);
    }

}