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

public abstract class CA {

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

    public CA(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];
	pBirth          = new double[m];
	pDeath          = new double[m];
	birthRate       = new double[m];
	deathRate       = new double[m];
	population      = new int[m];
	freeSpace       = new RandomSet(n*n);
	gen             = new Random();
	this.draw       = draw;
	time            = 0.0;
	maxTime         = 0;
	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;
	    }
    }
    //
    // n x n grid with m species
    //

    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
    //

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

    void doDeaths(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() <= pDeath[species])
		    death(species,Y,i,j);
	    }
    }
    //
    // do deaths on X
    //

    void birth(int species,int[][] X,int i,int j) {
	int point = chooseRandomNeighbour(i,j);
	if (X[point/n][point%n] == empty){
	    X[point/n][point%n] = species;
	    population[species]++;
	    totalPopulation++;
	}
    }

    int chooseRandomNeighbour(int i,int j){
	int select = gen.nextInt(8);
	int newX = j + deltaX[select];
	int newY = i + deltaY[select];
	if (newX == n) newX = 0;
	if (newX == -1) newX = n-1;
	if (newY == n) newY = 0;
	if (newY == -1) newY = n-1;
	return newY*n + newX;
    }

    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);
    }

    void show(){
	System.out.printf("%.5f",time);
	for (int i=0;i<m;i++) System.out.print(" " + population[i]);
	System.out.println(" "+ totalPopulation);
    }

    public boolean getTrace(){return trace;}
    public void    setTrace(boolean trace){this.trace = trace; draw = draw || trace;}
    public void    setPointSize(double x){pointSize = x;}
    public int     size(){return n;}
    public int     getPopulation(){return totalPopulation;}
    public int     getPopulation(int species){return population[species];}
    public void    setPBirth(int species,double p){pBirth[species] = p;}
    public void    setPDeath(int species,double p){pDeath[species] = p;}
    public void    setBirthRate(int species,double rate){birthRate[species] = rate;}
    public void    setDeathRate(int species,double rate){deathRate[species] = rate;}
    public void    setMaxTime(int maxTime){this.maxTime = maxTime;}

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

    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
    //

    abstract void doGeneration();
    //
    // one click update of births and deaths
    // also update time
    //
}