#define NUMBER_ORGANISMS 100
#define NUMBER_GENES 20
#define FALSE 0
#define TRUE 1
#define ALLELES 4
#define MAXIMUM_FITNESS NUMBER_GENES
#define MUTATION_RATE 0.001

char **currentGeneration;
char **nextGeneration;
char *modelOrganism;
int *organismsFitnesses;
int totalOfFitnesses;
int finalGeneration;



int SelectOneOrganism(void)
{
   int organism;
   int runningTotal;
   int randomSelectPoint;
   
   runningTotal = 0;
   randomSelectPoint = random(totalOfFitnesses+1);
   for(organism=0; organism<NUMBER_ORGANISMS; ++organism)
   {
      runningTotal += organismsFitnesses[organism];
      if(runningTotal >= randomSelectPoint) return organism;
   }
}
void ProduceNextGeneration(void)
{
   int organism;
   int gene;
   int parentOne;
   int parentTwo;
   int crossoverPoint;
   int mutateThisGene;
   
   //fill the nextGeneration data structur with the
   //children
   for(organism=0; organism<NUMBER_ORGANISMS; ++organism)
   {
      parentOne = SelectOneOrganism();
      parentTwo = SelectOneOrganism();
      crossoverPoint = random(NUMBER_GENES);
      for(gene=0; gene<NUMBER_GENES; ++gene)
      {
         //copy over a single gene
         mutateThisGene = random(1.0/ MUTATION_RATE);
         if(mutateThisGene == 0)
         {
            //we decide to make this gene a mutation
            (nextGeneration[organism])[gene] = random(ALLELES);
         } else
         {
            //we decide to copy this gene from a parent
            if(gene< crossoverPoint)
            {
               (nextGeneration[organism])[gene] = (currentGeneration[parentOne])[gene];
            } else
            {
               (nextGeneration[organism])[gene] = (currentGeneration[parentTwo])[gene];
            }
         }
      }
   }
   
   //copy the children in nextGeneration into
   //currentGeneration
   for(organism=0; organism<NUMBER_ORGANISMS; ++organism)
   {
      for(gene=0; gene<NUMBER_GENES; ++gene)
      {
         (currentGeneration[organism])[gene] = (nextGeneration[organism])[gene];
      }
   }
}

int EvaluateOrganisms(void)
{
   int organism;
   int gene;
   int currentOrganismsFitnessTally;
   int curr = 0,mod = 0;
   
   totalOfFitnesses = 0;
   
   for(organism=0; organism<NUMBER_ORGANISMS; ++organism)
   {
      currentOrganismsFitnessTally = 0;
      
      //tally up the current organism's fitness
      for(gene=0; gene<NUMBER_GENES; ++gene)
      {
         curr = (currentGeneration[organism])[gene]; 
         mod = modelOrganism[gene];
         if ( curr == mod )
         {
            ++currentOrganismsFitnessTally;  //sum up, if current generation an model generation has the same genome at the same place
         }
      }
     
      //save the tally in the fitnesses data strucutre
      //and add its fitness to the generation's total
      organismsFitnesses[organism] = currentOrganismsFitnessTally;
      totalOfFitnesses += currentOrganismsFitnessTally;
      //printf("totalFitnesses: %i",totalOfFitnesses);
      //check if wwe have a perfetc generation
      
      if( currentOrganismsFitnessTally == MAXIMUM_FITNESS ) return TRUE;
   }
   return FALSE;
}

void InitializeOrganisms(void)
{
	int organism;
	int gene;
	// initiialzie the normal organisms
	for(organism=0; organism<NUMBER_ORGANISMS; ++organism)
	{
		for(gene=0; gene<NUMBER_GENES; ++gene)
		{
			(currentGeneration[organism])[gene] = random(ALLELES);
		}
	}
	//initialize the model organism
	for(gene=0; gene<NUMBER_GENES; ++gene)
	{
		modelOrganism[gene] = random(ALLELES); //this is the model generation where fitness will be measured
	}
	
}

int DoOneRun(void)
{
   
	int generations = 1;
	int perfectGeneration = FALSE;
	int organism; 
	//intitialize the first generation with random numbers
	InitializeOrganisms();
	
	while(TRUE)
	{
		perfectGeneration = EvaluateOrganisms(); //evaluate the generation for best fitness
		if ( perfectGeneration == TRUE ) //if fittest generation was found then break and put generation number in value
		{
		   return generations;
		}
		ProduceNextGeneration(); //if not, repeat until fittest generation was found
		++generations;
	}
}

void AllocateMemory(void)
{
   //allocate memory to store the genomes and generations
  int organism;
  currentGeneration = sys_malloc(NUMBER_ORGANISMS * sizeof(char) );
  nextGeneration = sys_malloc(NUMBER_ORGANISMS * sizeof(char));
  modelOrganism =  sys_malloc(NUMBER_GENES * sizeof(char));
  organismsFitnesses = sys_malloc(NUMBER_ORGANISMS * sizeof(int) );

  for(organism=0; organism<NUMBER_ORGANISMS; ++organism)
  {
    currentGeneration[organism] =  sys_malloc(NUMBER_GENES * sizeof(char) );
    nextGeneration[organism] =  sys_malloc(NUMBER_GENES * sizeof(char) );
    
  }
}


int main()
{
   random_seed(0);
	
	AllocateMemory();
	finalGeneration = DoOneRun();
	
	printf("The final generation was: %d\n",finalGeneration);
}