#include "types.h"
#include "utility.h"

#include <string.h>

#if defined(APP_INDIVIDUALS_ARE_STRINGS)
static INT
compare_by_genome(a, b)
INDIVIDUAL *a;
INDIVIDUAL *b;
{
#if defined(APP_LOW_FITNESS_IS_BETTER)
    return strcmp(b->genome, a->genome);
#else
    return strcmp(a->genome, b->genome);
#endif
}
#else
#define compare_by_genome app_compare_genomes
#endif


static INT
compare_by_fitness(a, b)
INDIVIDUAL *a;
INDIVIDUAL *b;
{
    if (a->fitness == b->fitness){
	return 0;
    }

#if defined(APP_LOW_FITNESS_IS_BETTER)
    return a->fitness > b->fitness;
#else
    return a->fitness < b->fitness;
#endif
}


VOID
sort_population(how_to_sort, context)
INT how_to_sort;
CONTEXT *context;
{
    POPULATION pop = context->population;
    register INT population_size = context->population_size;
    
    switch(how_to_sort){
	case NO_SORT:{
	    break;
	}

	case BY_FITNESS:{
	    qsort((CHAR *)pop, population_size, sizeof(INDIVIDUAL), compare_by_fitness);
	    break;
	}
	    
	case BY_GENOME:{
	    qsort((CHAR *)pop, population_size, sizeof(INDIVIDUAL), compare_by_genome);
	    break;
	}
		
	case BY_FITNESS_THEN_BY_GENOME:{
	    register INT index = 0;
	    
	    sort_population(BY_FITNESS, context);
	    
	    while (index < population_size){
		FITNESS starting_fitness = pop[index].fitness;
		INT starting_index = index;
		
		index++;
		
		while (index < population_size && pop[index].fitness == starting_fitness){
		    index++;
		}
		
		/* Only sort if there is more than one of them. */
		if (index - starting_index > 1){
		    /* 
		     * Now we know that all the strings from pop[starting_index] to
		     * pop[index - 1] have the same fitness. Sort them by genome.
		     */
		    
		    qsort((CHAR *)(pop + starting_index), index - starting_index, sizeof(INDIVIDUAL), compare_by_genome);
		}
	    }
	    break;
	}
		
	case BY_GENOME_THEN_BY_FITNESS:{
	    register INT index = 0;
	    
	    sort_population(BY_GENOME, context);
	    
	    while (index < population_size){
		STRING starting_genome = pop[index].genome;
		INT starting_index = index;
		
		index++;
		
		while (index < population_size && !strcmp(pop[index].genome, starting_genome)){
		    index++;
		}
		
		/* Only sort if there is more than one of them. */
		if (index - starting_index > 1){
		    /* 
		     * Now we know that all the strings from pop[starting_index] to
		     * pop[index - 1] have the same fitness. Sort them by genome.
		     */
		    
		    qsort((CHAR *)(pop + starting_index), index - starting_index, sizeof(INDIVIDUAL), compare_by_fitness);
		}
	    }
	    break;
	}
	
	default:{
	    error("unknown sorting method (%d) in sort_population()", how_to_sort);
	    break;
	}
    }
    return;
}

VOID
general_crossover(function, selections, nselected, nreproducers, new_population, context)
PFV function;
INT *selections;
INT nselected;
INT nreproducers;
POPULATION new_population;
CONTEXT *context;
{
    register INT i;
    register INT pos;
    register INT crossover_point;
    register INT half = nreproducers >> 1;
    /* Somewhere to have a child put that we don't want. If nreproducers is odd. */
    static STRING dummy = (STRING) 0;

    /*
     * We only do the crossover if the crossover probability threshold is larger than a randomly
     * chosen number between 0.0 and 1.0 and the parents are different. If we are not crossing 
     * over, we copy the strings directly.
     */
    
    for (i = 0; i < half; i++){
	register INT mum = selections[uniform(nselected)];
	register INT dad = selections[uniform(nselected)];
	register INT two_i = i << 1;
	register INT two_i_plus_one = two_i + 1;
	
	if (mum != dad && DO_CROSSOVER){
	    register INDIVIDUAL_TYPE parent_1 = context->population[mum].genome;
	    register INDIVIDUAL_TYPE parent_2 = context->population[dad].genome;
	    register INDIVIDUAL_TYPE child_1 = new_population[two_i].genome;
	    register INDIVIDUAL_TYPE child_2 = new_population[two_i_plus_one].genome;
    
	    (*function)(parent_1, parent_2, child_1, child_2, context);
	    
	    new_population[two_i].evaluated = FALSE;
	    new_population[two_i_plus_one].evaluated = FALSE;
	}
	else {
	    /* 
	     * No crossover. Copy mum and dad reproducers to the two kid locations. 
	     */
	    copy_individual(&new_population[two_i], &context->population[mum], context);
	    copy_individual(&new_population[two_i_plus_one], &context->population[dad], context);
	}
    }
    
    /*
     * Now do one more crossover to fill the new population if
     * nreproducers was odd. Just take one of the children - it
     * doesn't matter which as the parents were selected randomly.
     */
    if (nreproducers % 2){
	register INT mum = selections[uniform(nselected)];
	register INT dad = selections[uniform(nselected)];
	
	if (dummy == (STRING) 0){
	    dummy = Malloc(context->genome_size * sizeof(CHAR));
	}

	if (mum != dad && DO_CROSSOVER){
	    register INDIVIDUAL_TYPE parent_1 = context->population[mum].genome;
	    register INDIVIDUAL_TYPE parent_2 = context->population[dad].genome;
	    register INDIVIDUAL_TYPE child = new_population[nreproducers - 1].genome;
    
	    (*function)(parent_1, parent_2, child, dummy, context);
	    
	    new_population[nreproducers - 1].evaluated = FALSE;
	}
	else {
	    copy_individual(&new_population[nreproducers - 1], &context->population[mum], context);
	}
    }
    
    return;
}

UNSIGNED
chars_to_int(where, len)
STRING where;
INT len;
{
    register INT i;
    register UNSIGNED value = 0x0;
    
    for (i = 0; i < len; i++){
	value <<= 1;
	if (where[i] == '1'){
	    value++;
	}
    }
    
    return value;
}

VOID
int_to_chars(value, where, length)
UNSIGNED value;
STRING where;
INT length;
{
    for (length--; length >= 0; length--){
	where[length] = (value & 0x1) ? '1' : '0';
	value >>= 1;
    }
    
    return;
}


/*
 * The Gray coding that follows is adapted from
 *
 * "Elements of Combinatorial Computing" by Mark B. Wells.
 *
 * Section 3.1.2, page 60. Pergamon Press, 1971.
 * ISBN not apparent.
 * Library of Congress Catalog Card No. 77-129633.
 */

#define XOR(a, b) ((a == b) ? '0' : '1')

VOID
to_gray(where, length)
register STRING where;
register INT length;
{
    for (length--; length > 0; length--) {
	where[length] = XOR(where[length], where[length - 1]);
    }
    
    return;
}

VOID
from_gray(where, length)
register STRING where;
register INT length;
{
    register INT i;

    for (i = 1; i < length; i++) {
	where[i] = XOR(where[i], where[i - 1]);
    }
    
    return;
}

#undef XOR