//package ca;

import java.awt.Color;
import java.util.ArrayList;
import java.util.Random;

public class CellularAutomata
{       
	static Color[] colours = {Color.WHITE, Color.RED, Color.BLUE, Color.BLACK, Color.CYAN, Color.GREEN, Color.GRAY, Color.MAGENTA,
		Color.ORANGE, Color.PINK, Color.YELLOW};

	static Chart c;

	static Random randGen;
	static String spatial = "S";
	static String temporal = "bF";
	static int timeStep = 2;
	static boolean metrics = false;

	static int totalPop = 0;
	static int[] population;
	static float[] bProb;
	static float[] dProb;
	static int size;
	static int steps;
	static double gillespTime = 0.0;

	static int[] grid;
	static int[][] neighbours;
	static int[] order;
	static double[][] cells;
	static double width;

	static ArrayList<int[]> changes;

	static boolean[] countedCells;
	static boolean[] addedToPatchIndexes;
	static ArrayList<Integer> patchIndexes;

	/**
	 * program should be started using the following settings:
	 * grid_length no_of_steps {inital_population birth_probabilitiy death_probability}*number of species.
	 * 
	 * optional arguments:
	 * 			-g  --> turn on the Grid 
	 * 			-c  --> turn on the Chart
	 * 			-m  --> turn on the spatial metrics (NP, LPI, Moran's I)
	 * 			-s x--> uses seed value x
	 * 			-r x--> runs with settings x where is can be either:
	 * 							"gil" for Gillespie simulator
	 * 						or
	 * 							update rule combination for CA in the form or Spatial,Temporal,TimeType from the options:
	 * 								Spatial:
	 * 									Sequential (S)
	 * 									Random (R)
	 * 								Temporal:
	 * 									birthFixed (bF)
	 * 									deathFixed(dF)
	 * 									birthConditional (bC)
	 * 									deathConditional (dC)
	 * 									singleRandom (sR)
	 * 									bothRandom (bR)
	 * 								Time Type:
	 * 									(1)
	 * 									(2)
	 */
	public static void main(String[] args)
	{
	    //System.out.println("Blip");
		long startTime = System.currentTimeMillis();
		int flags = 0;
		boolean GUI = false;
		boolean chart = false;
		boolean gillespie = false;
		long seed = System.currentTimeMillis();

		//determines the arguments of the program
		for(int i = 0; i < args.length; i++)
		{
			if(args[i].contains("-"))
			{
				flags++;
				if(args[i].equalsIgnoreCase("-g"))
				{
					GUI = true;
				}
				else if(args[i].equalsIgnoreCase("-c"))
				{
					chart = true;
				}
				else if (args[i].equalsIgnoreCase("-s"))
				{
					seed = Long.parseLong(args[i + 1]);
					flags++;
					i++;
				}
				else if(args[i].equalsIgnoreCase("-m"))
				{
					metrics = true;
				}
				else if (args[i].equalsIgnoreCase("-r"))
				{
					String rules = args[i+1];
					i++;
					flags++;

					if(rules.equalsIgnoreCase("gil"))
					{
						gillespie = true;
					}
					else
					{
						spatial = rules.substring(0, 1);
						temporal = rules.substring(1, 3);
						timeStep = Integer.parseInt(rules.substring(3));
					}
				}
			}
		}

		if((args.length - 2 - flags) % 3 != 0)
		{
			System.out.println("Error with parameters. Please enter any flags " +
					"('-g' for no GUI, '-s' {long} for seed number, '-r' {rules} to change rules) " +
					"and then the size of the grid, " +
					"no. of steps, and then for each data set, the initial size, " +
					"the birth rate (between 0 and 1) and the death rate (between 0 and 1)");
			return;
		}

		randGen = new Random(seed);

		if(((args.length - flags - 2)/3) > 10)
		{
			System.out.println("Too many species, only " + 10 + " allowed.");
			return;
		}

		population = new int[(args.length - flags - 2)/3];
		bProb = new float[(args.length - flags - 2)/3];
		dProb = new float[(args.length - flags - 2)/3];

		initialiseSpecies(args, flags);

		if(totalPop > (size*size))
		{
			System.out.println("There is not enough room on the grid for all of the species");
			return;
		}

		initiateGrid();
		initialiseNeighbours();

		countedCells = new boolean[grid.length];
		addedToPatchIndexes = new boolean[grid.length];
		patchIndexes = new ArrayList<Integer>(grid.length);
		changes = new ArrayList<int[]>(grid.length);

		if(GUI)
		{
			StdDraw.show(0);
			populateCells(grid);
			//done to make the GUI start up faster. Unsure why this stop the long initial load
			initiateGrid(new int[0]);
			initiateGrid(grid);
		}
		if(chart)
		{
			initiateChart();
		}

		order = new int[grid.length];

		//initiates the grid containing the spatial order
		for(int i = 0; i < order.length; i++)
		{
			order[i] = i;
		}

		if(spatial.equalsIgnoreCase("r"))
		{
			order = randomiseOrder(order);
		}
		else if(!(spatial.equalsIgnoreCase("s")))
		{
			System.out.println("Spatial input is incorrect. Must be either \"S\" or \"R\"");
			return;
		}

		int i = steps;
		steps = 0;
		if(gillespie)
		{
			int lastTime = (int)gillespTime;
			printState(steps - 1);
			for(; steps < i && totalPop > 0; steps++)
			{
				while(!((int)gillespTime > lastTime))
				{
					gillespieStep();
				}
				lastTime = (int)gillespTime;
				printState(steps);
				if(GUI)
				{
					updateGrid();
				}
				if(chart)
				{
					updateChart();
				}
				changes.clear();
			}
		}
		//determines the exact setting type before looping to reduce expensive "if" statements for every step
		else
		{
			String tempor = temporal.substring(temporal.length() - 1);
			String ord = temporal.substring(0, 1);
			boolean temporError = false;

			//creates variable which is pointer to the original grid for asynchronous updates
			int[] midstep = grid;

			printState(steps - 1);

			if(tempor.equalsIgnoreCase("f"))
			{
				if(ord.equalsIgnoreCase("b"))
				{
					for(; steps < i && totalPop > 0; steps++)
					{
						bFixedStep(midstep);
						printState(steps);
						if(GUI)
						{
							updateGrid();
						}
						if(chart)
						{
							updateChart();
						}
						changes.clear();
						if(spatial.equalsIgnoreCase("r"))
						{
							//re-randomises the spatial order
							order = randomiseOrder(order);
						}
					}
				}
				else if(ord.equalsIgnoreCase("d"))
				{
					for(; steps < i && totalPop > 0; steps++)
					{
						dFixedStep(midstep);
						printState(steps);
						if(GUI)
						{
							updateGrid();
						}
						if(chart)
						{
							updateChart();
						}
						changes.clear();
						if(spatial.equalsIgnoreCase("r"))
						{
							order = randomiseOrder(order);
						}
					}
				}
				else
				{
					temporError = true;
				}
			}
			else if(tempor.equalsIgnoreCase("c"))
			{
				if(ord.equalsIgnoreCase("b"))
				{
					for(; steps < i && totalPop > 0; steps++)
					{
						bConditionalStep(midstep);
						printState(steps);
						if(GUI)
						{
							updateGrid();
						}
						if(chart)
						{
							updateChart();
						}
						changes.clear();
						if(spatial.equalsIgnoreCase("r"))
						{
							order = randomiseOrder(order);
						}
					}
				}
				else if(ord.equalsIgnoreCase("d"))
				{
					for(; steps < i && totalPop > 0; steps++)
					{
						dConditionalStep(midstep);
						printState(steps);
						if(GUI)
						{
							updateGrid();
						}
						if(chart)
						{
							updateChart();
						}
						changes.clear();
						if(spatial.equalsIgnoreCase("r"))
						{
							order = randomiseOrder(order);
						}
					}
				}
				else
				{
					temporError = true;
				}
			}
			else if(tempor.equalsIgnoreCase("r"))
			{
				if(ord.equalsIgnoreCase("b"))
				{
					for(; steps < i && totalPop > 0; steps++)
					{
						randomStep(true, midstep);
						printState(steps);
						if(GUI)
						{
							updateGrid();
						}
						if(chart)
						{
							updateChart();
						}
						changes.clear();
						if(spatial.equalsIgnoreCase("r"))
						{
							order = randomiseOrder(order);
						}
					}
				}
				else if(ord.equalsIgnoreCase("s"))
				{
					for(; steps < i && totalPop > 0; steps++)
					{
						randomStep(false, midstep);
						printState(steps);
						if(GUI)
						{
							updateGrid();
						}
						if(chart)
						{
							updateChart();
						}
						changes.clear();
						if(spatial.equalsIgnoreCase("r"))
						{
							order = randomiseOrder(order);
						}
					}
				}
				else
				{
					temporError = true;
				}
			}
			else
			{
				temporError = true;
			}

			if(temporError)
			{
				System.out.println("Temporal input is incorrect. Must be either \"bF\", \"dF\", \"bC\", \"dC\", " +
						"\bR\" or \"sR\"");
				return;
			}
		}

		//print statement for system going extinct
		if(totalPop == 0)
		{
			System.out.println("System went extinct at step: " + steps);
		}
		System.out.println("time: " + (System.currentTimeMillis() - startTime));
	}

	/**
	 * Obtains the initial values for the species, grid and number of steps.
	 * 
	 * @param args - arguments
	 * @param flags - no. of flags
	 */
	private static void initialiseSpecies(String[] args, int flags)
	{
		int counter = 0;

		String[] data = new String[args.length - flags];

		for(int i = 0; i < args.length; i++)
		{
			if(!args[i].contains("-"))
			{
				data[counter] = args[i];
				counter++;
			}
			else
			{
				if(args[i].equalsIgnoreCase("-s") || args[i].equalsIgnoreCase("-r"))
				{
					i++;
				}
			}
		}
		counter = 0;

		size = Integer.parseInt(data[0]);
		steps = Integer.parseInt(data[1]);

		for(int i = 2; i < data.length - 2; i++)
		{
			population[counter] = Integer.parseInt(data[i]);
			totalPop += population[counter];
			bProb[counter] = Float.parseFloat(data[i+1]);
			dProb[counter] = Float.parseFloat(data[i+2]);
			i += 2;
			counter++;
		}
	}

	/**
	 * Sets the initial locations for the cells of each species randomly
	 * 
	 * @param grid - grid to be placed
	 */
	private static void initiateGrid()
	{
		grid = new int[size*size];
		for(int i = 0; i < grid.length; i++)
		{
			grid[i] = 0;
		}

		int space = randGen.nextInt(grid.length);
		//for all species
		for(int i = 0; i < population.length; i++)
		{
			//for all organisms of that species
			for(int j = 0; j < population[i]; j++)
			{
				//until and empty cell is found
				while(grid[space] != 0)
				{
					space = randGen.nextInt(grid.length);
				}
				grid[space] = i + 1;
			}
		}
	}

	/**
	 * Sets the indexes for all of the neighbours for each site
	 */
	private static void initialiseNeighbours()
	{
		neighbours = new int[size * size][];

		for(int i = 0; i < neighbours.length; i++)
		{
			neighbours[i] = correctNumbers(i, neighbours.length);
		}
	}

	/**
	 * randomizes the order for the sites to be visited
	 * 
	 * @param order
	 * @return
	 */
	private static int[] randomiseOrder(int[] order)
	{
		int randNum;
		int temp;

		for(int i = 0; i < order.length; i++)
		{
			randNum = randGen.nextInt(order.length);
			temp = order[i];
			order[i] = order[randNum];
			order[randNum] = temp;
		}
		return order;
	}

	/**
	 * prints the current step, populations of each species and the total population of the system
	 *  also prints the LPI, NP and Moran's I is the -m flag is entered
	 * @param step
	 */
	private static void printState(int step)
	{
		System.out.print(step + 1 + " ");
		for(int i : population)
		{
			System.out.print(i + " ");
		}
		if(metrics)
		{
			int[] patch = countPatches(grid);
			System.out.println(totalPop + " | " + patch[0] + " " + patch[1] +  " " + moransI(grid));
		}
		else
		{
			System.out.println(totalPop);
		}
		//printGrid(grid);
	}

	/**
	 * performs each of the gillespie steps
	 */
	private static void gillespieStep()
	{
		double lambda = 0.0;

		double[] birthRates = new double[bProb.length];
		double[] deathRates = new double[dProb.length];

		double[] birthProb = new double[bProb.length];
		double[] deathProb = new double[dProb.length];

		double time;
		double eventProb;
		double lowerBound = 0.0;

		for(int i = 0; i < population.length; i++)
		{
			//math function figures out the average rate from the probability using a negative exponential distribution
			//then multiplies by the population to get an overall rate.
			birthRates[i] = (-Math.log(1-bProb[i])) * population[i];
			deathRates[i] = (-Math.log(1-dProb[i])) * population[i];

			lambda += birthRates[i] + deathRates[i];
		}

		for(int i = 0; i < birthRates.length; i++)
		{
			birthProb[i] = birthRates[i]/lambda;
			deathProb[i] = deathRates[i]/lambda;
		}

		//determines time until next step
		time = -Math.log(1 - randGen.nextDouble())/lambda;
		eventProb = randGen.nextFloat();
		gillespTime += time;

		for(int i = 0; i < population.length; i++)
		{
			//checks all possible birth events
			if(eventProb >= lowerBound && eventProb < birthProb[i] + lowerBound)
			{
				gillespieEvent(i, true);
				break;
			}
			lowerBound += birthProb[i];
			//checks all possible death events
			if(eventProb >= lowerBound && eventProb < deathProb[i] + lowerBound)
			{
				gillespieEvent(i, false);
				break;
			}
			lowerBound += deathProb[i];
		}
	}

	/**
	 * performs either a birth or death event on index i
	 * 
	 * @param i
	 * @param birth
	 */
	private static void gillespieEvent(int i, boolean birth)
	{
		int cell = randGen.nextInt(grid.length);

		//keeps randomly selecting cells until one of the correct species is found
		while(grid[cell] == 0 || grid[cell] != (i + 1))
		{
			cell = randGen.nextInt(grid.length);
		}

		if(birth)
		{
			//performs a birth
			int[] hood = neighbours[cell];
			int birthSite = hood[randGen.nextInt(hood.length)];
			if (grid[birthSite] == 0)
			{
				population[i]++;
				totalPop++;
				grid[birthSite] = i + 1;
				changes.add(new int[]{birthSite, i + 1});
			}
		}
		else
		{
			//performs a death
			grid[cell] = 0;
			population[i]--;
			totalPop--;
			changes.add(new int[] {cell, 0});
		}

	}

	/**
	 * performs the births for all of the cells and then the deaths
	 */
	private static void bFixedStep(int[] midstep)
	{
		if(timeStep == 2)
		{
			//changes array to become its own grid if a synchronous option is chosen
			midstep = new int[grid.length];
		}

		midstep = births(grid, midstep);

		grid = deaths(grid, midstep);

	}

	/**
	 * performs the deaths for all of the cells and then the births
	 */
	private static void dFixedStep(int[] midstep)
	{
		if(timeStep == 2)
		{
			//changes array to become its own grid if a synchronous option is chosen
			midstep = new int[grid.length];
		}

		grid = deaths(grid, grid);

		grid = births(grid, midstep);
	}

	/**
	 * performs a birth, then death for each cell
	 */
	private static void bConditionalStep(int[] midstep)
	{
		if(timeStep == 2)
		{
			//changes array to become its own grid if a synchronous option is chosen
			midstep = new int[grid.length];
		}

		//performs the checks in the specified order
		for(int i : order)
		{
			if(grid[i] != 0)
			{
				// birth step
				midstep[i] = grid[i];

				if(randGen.nextFloat() < bProb[grid[i] - 1])
				{
					int[] hood = neighbours[i];

					//randomly pick a neighoburing cell
					int birthSite = hood[randGen.nextInt(hood.length)];
					//birth only occurs if the chosen cell is empty in both the origninal and new grid
					if(grid[birthSite] == 0 && midstep[birthSite] == 0)
					{
						population[grid[i] - 1]++;
						totalPop++;
						midstep[birthSite] = grid[i];
						changes.add(new int[]{birthSite, grid[i]});
					}
				}

				//death step
				if(randGen.nextFloat() < dProb[grid[i] - 1])
				{
					population[grid[i] - 1]--;
					midstep[i] = 0;
					totalPop--;
					changes.add(new int[] {i, 0});
				}
			}
		}
		grid = midstep;
	}

	/**
	 * performs a death, then a birth for each cell
	 */
	private static void dConditionalStep(int[] midstep)
	{
		if(timeStep == 2)
		{
			//changes array to become its own grid if a synchronous option is chosen
			midstep = new int[grid.length];
		}

		for(int i : order)
		{
			if(grid[i] != 0)
			{
				//death step

				if(randGen.nextFloat() < dProb[grid[i] - 1])
				{
					population[grid[i] - 1]--;
					midstep[i] = 0;
					totalPop--;
					changes.add(new int[] {i, 0});
				}
				else
				{
					// birth step

					midstep[i] = grid[i];                                   
					if(randGen.nextFloat() < bProb[grid[i] - 1])
					{
						int[] hood = neighbours[i];

						//randomly picks a neighbouring cell
						int birthSite = hood[randGen.nextInt(hood.length)];
						//only gives birth if the randomly selected cell is empty in both the original grid and the new one
						if(grid[birthSite] == 0 && midstep[birthSite] == 0)
						{
							population[grid[i] - 1]++;
							totalPop++;
							midstep[birthSite] = grid[i];
							changes.add(new int[]{birthSite, grid[i]});
						}
					}
				}
			}
		}
		grid = midstep;
	}

	/**
	 * performs a full step for a random setting, either both or single
	 * 
	 * @param both - true if bR, false if sR
	 * @param midstep
	 */
	private static void randomStep(boolean both, int[] midstep)
	{
		Boolean prev[] = new Boolean[order.length];
		Boolean second = false;

		if(timeStep == 2)
		{
			//changes array to become its own grid if a synchronous option is chosen
			midstep = new int[grid.length];
		}

		for(int i = 0; i < prev.length; i++)
		{
			//an array which holds 1 if the event is randomly evaluated to be a birth, otherwise 0
			prev[i] = (randGen.nextInt(2) == 0);
		}

		for(int i = 0; i < order.length; i++)
		{
			int index = order[i];

			if(grid[index] != 0)
			{
				midstep[index] = grid[index];
				//if the event was earlier evalauted to be birth-first
				if(prev[i])
				{
					//performs a birth
					if(randGen.nextFloat() < bProb[grid[index] - 1])
					{
						int[] hood = neighbours[index];

						int birthSite = hood[randGen.nextInt(hood.length)];
						if(grid[birthSite] == 0 && midstep[birthSite] == 0)
						{
							population[grid[index] - 1]++;
							totalPop++;
							midstep[birthSite] = grid[index];
							changes.add(new int[]{birthSite, grid[index]});
						}
					}
					//if both events are to occur
					if(both)
					{
						//performs a death
						if(randGen.nextFloat() < dProb[grid[index] - 1])
						{
							population[grid[index] - 1]--;
							midstep[index] = 0;
							grid[index] = 0;
							totalPop--;
							changes.add(new int[] {index, 0});
						}
					}
					//if single
					else
					{
						//switches the value for the next iteration
						prev[i] = false;
					}
				}
				//if the event was earlier evaluated to be death-first
				else
				{
					//evaluated for death
					if(randGen.nextFloat() < dProb[grid[index] - 1])
					{
						population[grid[index] - 1]--;
						midstep[index] = 0;
						grid[index] = 0;
						totalPop--;
						changes.add(new int[] {index, 0});
					}
					//if death does not occur, evaulated for birth
					else
					{
						//if bR
						if(both)
						{
							if(randGen.nextFloat() < bProb[grid[index] - 1])
							{
								int[] hood = neighbours[index];

								int birthSite = hood[randGen.nextInt(hood.length)];
								if(grid[birthSite] == 0 && midstep[birthSite] == 0)
								{
									population[grid[index] - 1]++;
									totalPop++;
									midstep[birthSite] = grid[index];
									changes.add(new int[]{birthSite, grid[index]});
								}
							}
						}
						//if sR sets value to be true for next iteration
						else
						{
							prev[i] = true;
						}
					}
				}
			}
			//the grid has been fully iterated through for the first time, and sR was chosen (so needs to iterate twice)
			if((i == order.length - 1) && !second && !both)
			{
				//resets counter
				i = -1;
				second = true;
			}
		}
		//updates original grid for all changes
		grid = midstep;
	}

	/**
	 * performs the births for all of the cells in original grid, placing new data on the changed grid
	 * 
	 * @param orig
	 * @param changed
	 * @return
	 */
	private static int[] births(int[] orig, int[] changed)
	{
		//goes in the defined order
		for(int i: order)
		{
			if(orig[i] != 0)
			{
				//this cell survives this step no matter what
				changed[i] = orig[i];

				if((randGen.nextFloat() < bProb[orig[i] - 1]))
				{
					int[] hood = neighbours[i];
					//picks random neighbour
					int birthSite = hood[randGen.nextInt(hood.length)];
					//only gives birth if the selected neighbour is free in both the original and new grid
					if(orig[birthSite] == 0 && changed[birthSite] == 0)
					{
						population[orig[i]- 1]++;
						totalPop++;
						changed[birthSite] = orig[i];
						changes.add(new int[]{birthSite, orig[i]});
					}
				}

			}
		}

		return changed;
	}

	/**
	 * performs the deaths for all of the cells in original grid, placing new data on the changed grid
	 * 
	 * @param orig
	 * @param changed
	 * @return
	 */
	private static int[] deaths(int[] grid, int[] changed)
	{
		//performs the checks in the specified order
		for(int i: order)
		{
			if(grid[i] != 0)
			{
				if((randGen.nextFloat() < dProb[grid[i] - 1]))
				{
					population[grid[i] - 1]--;
					changed[i] = 0;
					totalPop--;
					changes.add(new int[] {i, 0});
				}
			}
		}

		return changed;
	}

	/**
	 * returns a list of all of the correct indexes for the neighbours of the provided cell (i)
	 * 
	 * @param i - index of the cell to find neighbours for
	 * @param length - size of the array
	 * @returns a list of indexes for the grid for the neighbours of the given cell
	 */
	private static int[] correctNumbers(int i, int length)
	{
		int[] neighbourIndex = new int[8];
		int rowLength = (int)Math.sqrt(length);

		// for the top-left neighbour
		neighbourIndex[0] = (i - rowLength - 1);
		if(i < rowLength)
		{
			if(i == 0)
			{
				neighbourIndex[0] = length - 1; 
			}
			else
			{
				neighbourIndex[0] += length;
			}
		}
		else if(i % rowLength == 0)
		{
			neighbourIndex[0] = i - 1;
		}


		// for the neighbour directly above 
		neighbourIndex[1] = (i - rowLength);
		if(i < rowLength)
		{
			neighbourIndex[1] += length;
		}

		//for the top-right neighbour
		neighbourIndex[2] = (i - rowLength + 1);
		if(i < rowLength)
		{
			if(i == rowLength - 1)
			{
				neighbourIndex[2] = length - rowLength;
			}
			else
			{
				neighbourIndex[2] += length;
			}
		}
		else if((i + 1) % rowLength == 0)
		{
			neighbourIndex[2] -= rowLength;
		}

		// for the left neighbour
		neighbourIndex[3] = i - 1;
		if(i % rowLength == 0)
		{
			neighbourIndex[3] += rowLength;
		}

		// for the right neighbour
		neighbourIndex[4] = i + 1;
		if((i + 1) % rowLength == 0)
		{
			neighbourIndex[4] -= rowLength;
		}

		// for the bottom-left neighbour
		neighbourIndex[5] = (i + rowLength - 1);
		if(i > length - rowLength - 1)
		{
			if(i == (length - rowLength))
			{
				neighbourIndex[5] = rowLength - 1;
			}
			else
			{
				neighbourIndex[5] -= length;
			}
		}
		else if(i % rowLength == 0)
		{
			neighbourIndex[5] += rowLength; 
		}

		// for the neighbour directly bellow
		neighbourIndex[6] = i + rowLength;
		if(i > length - rowLength - 1)
		{
			neighbourIndex[6] -= length;
		}

		// for the bottom-right neighbour
		neighbourIndex[7] = i + rowLength + 1;
		if(i > length - rowLength - 1)
		{
			if(i == length - 1)
			{
				neighbourIndex[7] = 0;
			}
			else
			{
				neighbourIndex[7] -= length;
			}
		}
		else if((i + 1) % rowLength == 0)
		{
			neighbourIndex[7] -= rowLength;
		}

		return neighbourIndex;
	}

	/**
	 * textual print-out of the grid
	 * 
	 * @param grid
	 */
	private static void printGrid(int[] grid)
	{
		int l = (int) Math.sqrt(grid.length);
		for(int i = 0; i < grid.length; i++)
		{

			System.out.print(grid[i] + " ");

			if((i + 1)%l == 0)
			{
				System.out.println("");
			}
		}
		System.out.println("");
	}

	/**
	 * calculates moran's I for the given grid
	 * @param grid
	 * @return
	 */
	private static float moransI(int[] grid)
	{
		float moransI = 0;
		float xBar = 0;
		float sac = 0;
		float tv = 0;

		for(int i:population)
		{
			xBar += i;
		}
		xBar /= grid.length;

		//for all cells
		for(int i = 0; i < grid.length; i++)
		{
			//for each of its neighbours
			for(int j:neighbours[i])
			{
				if(grid[i] == grid[j])
				{
					//for two empty cells
					if(grid[i] == 0)
					{
						sac += (0-xBar)*(0-xBar);
					}
					//for two cells of the same species
					else
					{
						sac += (1-xBar)*(1-xBar);
					}
				}
				//one empty cell and a non-matching cell
				else
				{
					sac += (0-xBar)*(1-xBar);
				}
			}
			if(grid[i] == 0)
			{
				tv += (0 - xBar)*(0 - xBar);
			}
			else
			{
				tv += (1 - xBar)*(1 - xBar);
			}
		}

		float n = grid.length;
		float connections = n*neighbours[0].length;

		moransI = (n/connections) * (sac/tv);

		return moransI;
	}

	/**
	 * counts the number of patches and the largest patch index
	 * 
	 * @param grid
	 * @returns the number of patches, largest patch size
	 */
	private static int[] countPatches(int[] grid)
	{
		int patches = 0;
		int biggestPatch = 0, currentPatch = 0;

		//initiates the two boolean arrays
		for(int i = 0; i < countedCells.length; i++)
		{
			countedCells[i] = false;
			addedToPatchIndexes[i] = false;
		}

		for(int i = 0; i < grid.length; i++)
		{
			//all non-empty, uncounted cells
			if(!countedCells[i] && grid[i] != 0)
			{
				currentPatch = 0;
				//add to arrayList
				patchIndexes.add(i);
				addedToPatchIndexes[i] = true;
				//for all neighbours
				while(!patchIndexes.isEmpty())
				{
					int currentIndex = patchIndexes.remove(0);
					currentPatch++;
					countedCells[currentIndex] = true;
					addedToPatchIndexes[currentIndex] = false;
					for(int n:neighbours[currentIndex])
					{
						if(grid[n] != 0 && grid[n] == grid[i] && !countedCells[n] && !addedToPatchIndexes[n])
						{
							patchIndexes.add(n);
							addedToPatchIndexes[n] = true;
						}
					}
				}

				patches++;
				//checks for new biggest
				if (currentPatch > biggestPatch)
				{
					biggestPatch = currentPatch;
				}

			}
		}

		return new int[]{patches, biggestPatch};
	}

	/**
	 * populates the array cells with the coordinates for each cell
	 * 
	 * @param grid
	 */
	public static void populateCells(int[] grid)
	{
		int rowLength = (int)Math.sqrt(grid.length);
		int i = 0;
		double incr = ((double)1/rowLength) * (StdDraw.xmax - StdDraw.xmin);
		width = incr/2;
		cells = new double[grid.length][];

		double y = 0;
		double x = 0;

		for(int row = 0; row < (int)Math.sqrt(grid.length); row++)
		{
			for(int column = 0; column < (int)Math.sqrt(grid.length); column++)
			{
				cells[i] = new double[]{x, y};
				i++;
				x += incr;
			}
			y += incr;
			x = 0;
		}
		StdDraw.show(0);
	}

	public static void initiateChart()
	{
		c = new Chart(population);;
	}

	public static void updateChart()
	{
		c.updatePopulations(population);
	}

	/**
	 * displays the initial layout of the system
	 * 
	 * @param grid
	 */
	public static void initiateGrid(int[] grid)
	{
		for(int i = 0; i < grid.length; i++)
		{
			StdDraw.setPenColor(colours[grid[i]]);
			StdDraw.filledSquare(cells[i][0], cells[i][1], width);
		}
	}

	/**
	 * updates the display to show which cells have changed 
	 */
	public static void updateGrid()
	{
		while(changes.size() != 0)
		{
			int[] change = changes.remove(0);

			StdDraw.setPenColor(colours[(change[1])]);
			if(StdDraw.getPenColor() == Color.WHITE)
			{
				StdDraw.filledSquare(cells[change[0]][0], cells[change[0]][1], width + 0.001);
			}
			else
			{
				StdDraw.filledSquare(cells[change[0]][0], cells[change[0]][1], width);
			}
		}
		StdDraw.show(1);
	}
}