/************************************************************
;                                                           *
;  William M. Spears					    *
;  Navy Center for Applied Research in AI                   *
;  Naval Research Laboratory                                *
;                                                           *
;  This software is the property of the Department of the   *
;  Navy. Permission is hereby granted to copy all or any    *
;  part of this program for free distribution, however      *
;  this header is required on all copies.		    *
;                                                           *
; File: cross.c                                             *
;************************************************************/

#include "header.h"

int cross_change;

/* Swap one bit position in two individuals.*/

void cross_swap (i, j, x)
int i, j, x;
{
   int tempi, tempj;

   tempi = c[i][x];
   tempj = c[j][x];

   if (tempi != tempj) {
	cross_change = 1;
	c[i][x] = tempj;
	c[j][x] = tempi;
   }
}

/* Either One or Two point cross-over. Mark for re-evaluation if
   a change has occurred.. */

void cross_over (i, j, x1, y1)
int i, j, x1, y1;
{
   int x;

   for (x = 1 + x1; x <= y1; x++) cross_swap(i, j, x);
}

/* Do cross-over of two individuals. The following diagram should help.

 		1	2	3					*B*
 	+---------------------------------------------------------------+
  i:	|   1	|   2	|   3	|	|	|	|	|  *B*	|
 	+---------------------------------------------------------------+

 		1	2	3					*B*
 	+---------------------------------------------------------------+
  j:	|   1	|   2	|   3	|	|	|	|	|  *B*	|
 	+---------------------------------------------------------------+

*/

/* Standard n-point crossover, n is the number of crossover points. */

void cross (n, i, j)
int n, i, j;
{
   int x, y, temp;
   int myrand();
   int cross_array[MAX_BITS];

   /* Fill in crossover points into an array. */

   for (temp = 0; temp < n; temp++) {
     cross_array[temp] = myrand(length);
   }

   /* If odd number of crossover points, make an even number
      by using the length as the last crossover point. */

   if ((n % 2) == 1) {
     n++;
     cross_array[n - 1] = length;
   }

   /* Sort the array. */

   selectsort(n, cross_array);

   /* Perform crossover over the right sections. */

   cross_change = 0;

   for (temp = 0; temp < n; temp = temp + 2) {
     x = cross_array[temp];
     y = cross_array[temp+1];
     if (x != y) cross_over(i, j, x, y);
   }

   if (cross_change) {
        reevaluations = reevaluations + 2;
	c_value[i] = -1.0;		/* re_evaluate */
	c_value[j] = -1.0;		/* re_evaluate */
   }

}

/* Cross-over a percentage of the population, based on the
   cross-over rate and the population size. The number of
   crossover points (n) should be less than the length of
   the chromosome (string). */

void cross_population (n)
int n;
{
   int i;

   reevaluations = 0;
   for (i = 1; i <= (CROSS_OVER * size); i = i + 2) {
	cross(n, i, i + 1);
   }
}

/* Standard uniform crossover with .5 probability of swapping
   alleles. Could be generalized to arbitrary probability. */

void uniform_cross (i, j)
int i, j;
{
     int x;

     cross_change = 0;

     for (x = 1; x <= length; x++) {
       if (brand() == 1) cross_swap(i, j, x);
     }

     if (cross_change) {
       reevaluations = reevaluations + 2;
       c_value[i] = -1.0;		/* re_evaluate */
       c_value[j] = -1.0;		/* re_evaluate */
     }
}

/* Apply uniform crossover to a percentage of the population. */

void uniform_cross_population ()
{
     int i;

     reevaluations = 0;

     for (i = 1; i <= (CROSS_OVER * size); i = i + 2) {
       uniform_cross(i, i + 1);
     }
}