/*
COPYRIGHT

The following is a notice of limited availability of the code, and disclaimer
which must be included in the prologue of the code and in all source listings
of the code.

(C) COPYRIGHT 2008 University of Chicago

Permission is hereby granted to use, reproduce, prepare derivative works, and
to redistribute to others. This software was authored by:

D. Levine
Mathematics and Computer Science Division 
Argonne National Laboratory Group

with programming assistance of participants in Argonne National 
Laboratory's SERS program.

GOVERNMENT LICENSE

Portions of this material resulted from work developed under a
U.S. Government Contract and are subject to the following license: the
Government is granted for itself and others acting on its behalf a paid-up,
nonexclusive, irrevocable worldwide license in this computer software to
reproduce, prepare derivative works, and perform publicly and display
publicly.

DISCLAIMER

This computer code material was prepared, in part, as an account of work
sponsored by an agency of the United States Government. Neither the United
States, nor the University of Chicago, nor any of their employees, makes any
warranty express or implied, or assumes any legal liability or responsibility
for the accuracy, completeness, or usefulness of any information, apparatus,
product, or process disclosed, or represents that its use would not infringe
privately owned rights.
*/

/*****************************************************************************
*     File: binary.c: This file contains routines specific to the binary
*                     datatype.
*
*     Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
*              Brian P. Walenz
*****************************************************************************/

#include "pgapack.h"

/*U****************************************************************************
   PGASetBinaryAllele - sets a binary allele to the specified value.

   Category: Fitness & Evaluation

   Inputs:
      ctx - context variable
      p   - string index
      pop - symbolic constant of the population the string is in
      i   - allele index
      val - binary value (either 1 or 0) to set the allele to

   Outputs:
      The allele is changed by side-effect.

   Example:
      Copies the alleles from member p in PGA_OLDPOP to member q PGA_NEWPOP.
      Assumes strings are of the same length.

      PGAContext *ctx;
      int p, q, i;
      :
      for (i=PGAGetStringLength(ctx)-1; i>=0; i--)
          PGASetBinaryAllele(ctx, q, PGA_NEWPOP, i,
                             PGAGetBinaryAllele(ctx, p, PGA_OLDPOP, i))

****************************************************************************U*/
void PGASetBinaryAllele ( PGAContext *ctx, int p, int pop, int i, int val )
{
    int windex;        /* index of the computer word allele i is in      */
    int bix;           /* bit position in word chrom[windex] of allele i */
    PGAIndividual *ind;
    PGABinary *chrom;

    PGADebugEntered("PGASetBinaryAllele");
    PGACheckDataType("PGAGetBinaryAllele", PGA_DATATYPE_BINARY);

    INDEX( windex,bix,i,WL );
    ind = PGAGetIndividual ( ctx, p, pop );
    chrom = (PGABinary *)ind->chrom;
    if ( val == 0 )
        UNSET( bix, chrom[windex] );
    else
        SET( bix, chrom[windex] );

    PGADebugExited("PGASetBinaryAllele");
}

/*U****************************************************************************
   PGAGetBinaryAllele - returns the value of a (binary) allele in a
   PGA_DATATYPE_BINARY string

   Category: Fitness & Evaluation

   Inputs:
      ctx - context variable
      p   - string index
      pop - symbolic constant of the population the string is in
      i   - allele index

   Outputs:
      The value of the ith allele of string p in population pop.

   Example:
      Copies the alleles from member p in PGA_OLDPOP to member q PGA_NEWPOP.
      Assumes the strings are of the same length.

      PGAContext *ctx;
      int p, q, i;
      :
      for (i=PGAGetStringLength(ctx)-1; i>=0; i--)
          PGASetBinaryAllele(ctx, q, PGA_NEWPOP, i,
                             PGAGetBinaryAllele(ctx, p, PGA_OLDPOP, i))

****************************************************************************U*/
int PGAGetBinaryAllele ( PGAContext *ctx, int p, int pop, int i )
{

    int windex;        /* index of the computer word allele i is in      */
    int bix;           /* bit position in word chrom[windex] of allele i */
    PGAIndividual *ind;
    PGABinary *chrom;

    PGADebugEntered("PGAGetBinaryAllele");
    PGACheckDataType("PGAGetBinaryAllele", PGA_DATATYPE_BINARY);

    INDEX( windex,bix,i,WL );
    ind = PGAGetIndividual ( ctx, p, pop );
    chrom = (PGABinary *)ind->chrom;

    PGADebugExited("PGAGetBinaryAllele");
    return( BIT(bix, chrom[windex]) != 0 );
}

/*U****************************************************************************
   PGASetBinaryInitProb - specify the probability of initializing an allele to
   "1" when creating a PGA_DATATYPE_BINARY string.  The default value is 0.5.

   Category: Initialization

   Inputs:
      ctx - context variable
      p   - the binary initialization probability

   Outputs:
      None

   Example:
      Set approximately 1 percent of all binary alleles to "1" when randomly
      initializing the population.

      PGAContext *ctx;
      :
      PGASetBinaryInitProb(ctx, 0.01);

****************************************************************************U*/
void PGASetBinaryInitProb ( PGAContext *ctx, double probability )
{
    PGADebugEntered("PGASetBinaryInitProb");
    PGAFailIfSetUp("PGASetBinaryInitProb");
    PGACheckDataType("PGASetBinaryInitProb", PGA_DATATYPE_BINARY);

     if ( (probability <= 1.0) && (probability >= 0.0) )
          ctx->init.BinaryProbability = probability;
     else
          PGAError( ctx, "PGASetBinaryInitProb: Invalid value of probability:",
                   PGA_FATAL, PGA_DOUBLE, (void *) &probability );

    PGADebugExited("PGASetBinaryInitProb");
}

/*U***************************************************************************
   PGAGetBinaryInitProb - Returns the probability that an allele will be
   randomly initialized to "1" in a PGA_DATATYPE_BINARY string.

   Category: Initialization

   Inputs:
      ctx - context variable

   Outputs:
      The probability that a bit will be randomly initialized to one

   Example:
      PGAContext *ctx;
      double prob;
      :
      prob = PGAGetBinaryInitProb(ctx);

***************************************************************************U*/
double PGAGetBinaryInitProb (PGAContext *ctx)
{
    PGADebugEntered("PGAGetBinaryInitProb");
    PGAFailIfNotSetUp("PGAGetBinaryInitProb");
    PGACheckDataType("PGAGetBinaryInitProb", PGA_DATATYPE_BINARY);

    PGADebugExited("PGAGetBinaryInitProb");
    return(ctx->init.BinaryProbability);
}


/*I****************************************************************************
   PGABinaryCreateString - Allocate a PGA_DATATYPE_BINARY string for member
   p of population pop.  If initflag is PGA_TRUE, randomly initialize all
   alleles, otherwise clear all alleles.

   Inputs:
      ctx      - context variable
      p        - string index
      pop      - symbolic constant of the population string p is in
      initflag - a flag, if set, randomly initialize, else clear alleles

   Outputs:
      Member p in population pop is allocated and initialized.

   Example:
      Allocates and clears alleles for all strings in PGA_NEWPOP

      PGAContext *ctx;
      int p;
      :
      for (p=PGAGetPopSize(ctx)-1; p>=0; p--)
          PGABinaryCreateString( ctx, p, PGA_NEWPOP, PGA_FALSE );

****************************************************************************I*/
void PGABinaryCreateString(PGAContext *ctx, int p, int pop, int initflag)
{
    int i, fp;
    PGABinary *s;
    PGAIndividual *new = PGAGetIndividual(ctx, p, pop);
    
    PGADebugEntered("PGABinaryCreateString");
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR, "PGABinaryCreateString",
		  "initflag = ", PGA_INT, (void *) &initflag );
    
    new->chrom = (void *)malloc(ctx->ga.tw * sizeof(PGABinary));
    if (new->chrom == NULL)
	PGAError(ctx, "PGABinaryCreateString: No room to allocate "
		 "new->chrom", PGA_FATAL, PGA_VOID, NULL);
    
    s = (PGABinary *)new->chrom;
    if (initflag)
	if (ctx->fops.InitString) {
	    fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
            (*ctx->fops.InitString)(&ctx, &fp, &pop);
	} else {
	    (*ctx->cops.InitString)(ctx, p, pop);
	}
    else
	for ( i=0; i<ctx->ga.tw; i++ )
	    s[i] = 0;
    
    PGADebugExited("PGABinaryCreateString");
}

/*I****************************************************************************
   PGABinaryMutation - randomly mutates a bit with a specified probability.
   This routine is called from PGAMutation.

   Inputs:
      ctx - context variable
      p   - string index
      pop - symbolic constant for the population string p is in
      mr  - probability of mutating (toggling) a bit

   Outputs:
      Returns the number of mutations

   Example:
      Mutates string p in population PGA_NEWPOP with a probability of 0.001
      for each bit.

      PGAContext *ctx;
      int p;
      :
      PGABinaryMutation( ctx, p, PGA_NEWPOP, .001 );

****************************************************************************I*/
int PGABinaryMutation( PGAContext *ctx, int p, int pop, double mr )
{
     int i,wi;
     int count = 0;
     PGABinary *c;

     PGADebugEntered("PGABinaryMutation");

     c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
     for(wi=0; wi<ctx->ga.fw; wi++)
          for(i=0; i<WL; ++i)
               if ( PGARandomFlip(ctx, mr) )
               {
                    TOGGLE(i,c[wi]);
                    count++;
               }

     /* clean up the partial word if eb > 0 */
     if (ctx->ga.eb > 0 )
          for(i=0;i<ctx->ga.eb;++i)
               if ( PGARandomFlip(ctx, mr) )
               {
                    TOGGLE(i,c[ctx->ga.fw]);
                    count++;
               }

    PGADebugExited("PGABinaryMutation");
    return(count);

}

/*I****************************************************************************
   PGABinaryOneptCrossover - performs one-point crossover on two parent strings
   to create two children via side-effect

   Inputs:
      ctx  - context variable
      p1   - the first parent string
      p2   - the second parent string
      pop1 - symbolic constant of the population containing p1 and p2
      c1   - the first child string
      c2   - the second child string
      pop2 - symbolic constant of the population containing c1 and c2

   Outputs:
      None.

   Example:
      Performs crossover on the two parent strings m and d, producing
      children s and b.

      PGAContext *ctx;
      int m, d, s, b;
      :
      PGABinaryOneptCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryOneptCrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1,
                             int c2, int pop2)
{
    PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
    PGABinary *child1  = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
    PGABinary *child2  = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;

    /*
      If the bits are numbered from 0 as follows:

      b   b   b   b   b   b   b   b          b  b
      0   1   2   3   4   5   6   7         30 31

      Then if the cross site is bit 5 (which is the sixth bit by our
      numbering scheme) we would get

      o   o   o   o   o   n   n   n          n  n
      0   1   2   3   4   5   6   7         30 31

      where o indicates the original bit and n is a new bit from the crossover
      operator.
    */

    PGABinary mask;
    int windex;   /* index of the word the crossover bit position is in */
    int bix;      /* bit position to perform crossover (mod WL)         */
    int i;
    int xsite;

    PGADebugEntered("PGABinaryOneptCrossover");

    xsite = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);

    INDEX(windex,bix,xsite,WL);

    for(i=0;i<windex;i++) {
        child1[i] = parent1[i];
        child2[i] = parent2[i];
    }

    mask = ~0;
    mask = mask >> bix;

    child1[windex] = (~mask & parent1[windex])|(mask & parent2[windex]);
    child2[windex] = (~mask & parent2[windex])|(mask & parent1[windex]);

    for(i=windex+1;i<ctx->ga.tw;i++) {
        child1[i] = parent2[i];
        child2[i] = parent1[i];
    }

    PGADebugExited("PGABinaryOneptCrossover");
}


/*I****************************************************************************
   PGABinaryTwoptCrossover - performs two-point crossover on two parent strings
   producing two children via side-effect

   Inputs:
      ctx  - context variable
      p1   - the first parent string
      p2   - the second parent string
      pop1 - symbolic constant of the population containing string p1 and p2
      c1   - the first child string
      c2   - the second child string
      pop2 - symbolic constant of the population to contain string c1 and c2

   Outputs:
      None.

   Example:
      Performs crossover on the two parent strings m and d, producing
      children s and b.

      PGAContext *ctx;
      int m, d, s, b;
      :
      PGABinaryTwoptCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryTwoptCrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1,
                             int c2, int pop2)
{
    PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
    PGABinary *child1  = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
    PGABinary *child2  = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;

    PGABinary mask, mask1, mask2;
    int windex1, windex2;
    int bix1, bix2;
    int i;
    int xsite1, xsite2;
    int temp;

    PGADebugEntered("PGABinaryTwoptCrossover");

    /* pick two cross sites such that xsite2 > xsite1 */
    xsite1 = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
    xsite2 = xsite1;
    while ( xsite2 == xsite1 )
        xsite2 = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
    if ( xsite1 > xsite2 ) {
        temp   = xsite1;
        xsite1 = xsite2;
        xsite2 = temp;
    }

    INDEX(windex1,bix1,xsite1,WL);
    INDEX(windex2,bix2,xsite2,WL);

    if ( windex1 == windex2 ) {     /* both cross sites in the same word */

        for(i=0;i<windex1;i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }

        mask1 = ~0;
        if (bix1 == 0)
             mask1 = 0;
        else
             mask1 = mask1 << (WL-bix1);
        mask2 = ~0;
        mask2 = mask2 >> bix2;
        mask  = mask1 | mask2;

        child1[windex1] = (mask & parent1[windex1])|(~mask & parent2[windex1]);
        child2[windex1] = (mask & parent2[windex1])|(~mask & parent1[windex1]);

        for(i=windex1+1;i<ctx->ga.tw;i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }
    }
    else {                          /* cross sites in different words */

        for(i=0;i<windex1;i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }

        mask = ~0;
        mask = mask >> bix1;

        child1[windex1] = (~mask & parent1[windex1])|(mask & parent2[windex1]);
        child2[windex1] = (~mask & parent2[windex1])|(mask & parent1[windex1]);

        for(i=windex1+1; i<windex2; i++) {
            child1[i] = parent2[i];
            child2[i] = parent1[i];
        }

        mask = ~0;
        mask = mask >> bix2;

        child1[windex2] = (mask & parent1[windex2])|(~mask & parent2[windex2]);
        child2[windex2] = (mask & parent2[windex2])|(~mask & parent1[windex2]);

        for(i=windex2+1; i<ctx->ga.tw; i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }
    }

    PGADebugExited("PGABinaryTwoptCrossover");
}


/*I****************************************************************************
   PGABinaryUniformCrossover - performs uniform crossover on two parent strings
   producing two children via side-effect

   Inputs:
      ctx  - context variable
      p1   - the first parent string
      p2   - the second parent string
      pop1 - symbolic constant of the population containing string p1 and p2
      c1   - the first child string
      c2   - the second child string
      pop2 - symbolic constant of the population to contain string c1 and c2

   Outputs:
      None.

   Example:
      Performs crossover on the two parent strings m and d, producing
      children s and b.

      PGAContext *ctx;
      int m, d, s, b;
      :
      PGABinaryUniformCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryUniformCrossover(PGAContext *ctx, int p1, int p2, int pop1,
                               int c1, int c2, int pop2)
{
     PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
     PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
     PGABinary *child1  = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
     PGABinary *child2  = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;
     PGABinary mask;
     int j,wi;

    PGADebugEntered("PGABinaryUniformCrossover");

    for(wi=0;wi<ctx->ga.tw;wi++) {
        if ( parent1[wi] == parent2[wi] ) {
            child1[wi] = parent1[wi];
            child2[wi] = parent2[wi];
        }
        else {
            mask = 0;
            for (j=0;j<WL;j++)
                if(PGARandomFlip(ctx, ctx->ga.UniformCrossProb))
                    SET(j,mask);
            child1[wi] = (mask & parent1[wi])|(~mask & parent2[wi]);
            child2[wi] = (mask & parent2[wi])|(~mask & parent1[wi]);
        }
    }

    PGADebugExited("PGABinaryUniformCrossover");
}

/*I****************************************************************************
   PGABinaryPrintString - writes a bit string to a file.

   Inputs:
      ctx - context variable
      fp  - file pointer to file to write bit string to
      p   - index of the string to write out
      pop - symbolic constant of the population string p is in

   Outputs:
      None.

   Example:
      Write string s to stdout.

      PGAContext *ctx;
      int s;
      :
      PGABinaryPrintString( ctx, stdout, s, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryPrintString( PGAContext *ctx, FILE *fp, int p, int pop )
{
     PGABinary *c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
     int i;

     PGADebugEntered("PGABinaryPrintString");

     for( i=0; i<ctx->ga.fw; i++ ) {
          fprintf(fp,"[ ");
          PGABinaryPrint( ctx, fp, (c+i), WL );
          fprintf(fp," ]\n");
     }
     if ( ctx->ga.eb > 0 ) {
          fprintf(fp,"[ ");
          PGABinaryPrint( ctx, fp, (c+ctx->ga.fw), ctx->ga.eb );
          fprintf(fp," ]");
     }

     PGADebugExited("PGABinaryPrintString");
}

/*I****************************************************************************
   PGABinaryCopyString - Copy one bit string to another

   Inputs:
      ctx  - context variable
      p1   - string to copy
      pop1 - symbolic constant of population containing string p1
      p2   - string to copy p1 to
      pop2 - symbolic constant of population containing string p2

   Outputs:
      None.

   Example:
      Copy bit string x to y (both are implicitly assumed to have the same
      length).

      PGAContext *ctx;
      int x, y
      :
      PGABinaryCopyString ( ctx, x, PGA_OLDPOP, y, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryCopyString (PGAContext *ctx, int p1, int pop1, int p2, int pop2)
{
    PGABinary *source = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    PGABinary *dest   = (PGABinary *)PGAGetIndividual(ctx, p2, pop2)->chrom;
    int i;

    PGADebugEntered("PGABinaryCopyString");

    for (i = ctx->ga.tw-1; i>=0; i--)
        dest[i] = source[i];

    PGADebugExited("PGABinaryCopyString");
}

/*I****************************************************************************
   PGABinaryDuplicate - Returns true if bit string a is a duplicate of bit
   string b, else returns false.

   Inputs:
      ctx  - context variable
      p1   - string index of the first string to compare
      pop1 - symbolic constant of the population string p1 is in
      p2   - string index of the second string to compare
      pop2 - symbolic constant of the population string p2 is in

   Outputs:
      Returns true/false if strings are duplicates

   Example:
      Compare bit string x with y and print a message if they are the same.

      PGAContext *ctx;
      int x, y;
      :
      if ( PGABinaryDuplicate( ctx, x, PGA_NEWPOP, y, PGA_NEWPOP ) )
          printf("strings are duplicates\n");

****************************************************************************I*/
int PGABinaryDuplicate( PGAContext *ctx, int p1, int pop1, int p2, int pop2)
{
     PGABinary *a = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
     PGABinary *b = (PGABinary *)PGAGetIndividual(ctx, p2, pop2)->chrom;
     int wi;

     PGADebugEntered("PGABinaryDuplicate");

     wi = ctx->ga.tw-1;
     if (a[0] == b[0])
         for (; (wi>0) && (a[wi] == b[wi]); wi--);

     PGADebugExited("PGABinaryDuplicate");

     return((wi==0) ? PGA_TRUE : PGA_FALSE);
}

/*I****************************************************************************
   PGABinaryInitString - randomly initialize a string of type PGABinary

   Inputs:
      ctx - context variable
      p   - index of string to randomly initialize
      pop - symbolic constant of the population string p is in

   Outputs:

   Example:
      PGAContext *ctx;
      int p;
      :
      PGABinaryInitString ( ctx, p, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryInitString(PGAContext *ctx, int p, int pop)
{
     PGABinary *c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
     int i;
     int windex;        /* index of the computer word allele i is in      */
     int bix;           /* binary position in word chrom[windex] of allele i */

     PGADebugEntered("PGABinaryInitString");

     for (i = 0; i < ctx->ga.tw; i++)
          c[i] = 0;
     for (i = 0; i < ctx->ga.StringLen; i++)
     {
          INDEX(windex,bix,i,WL);
          if ( PGARandomFlip(ctx, ctx->init.BinaryProbability) )
               SET  ( bix, c[windex] );
     }

     PGADebugExited("PGABinaryInitString");
}


/*I****************************************************************************
  PGABinaryBuildDatatype - Build an MPI_Datatype for a binary string
  datatype.

  Inputs:
      ctx  - context variable
      p    - index of the string to build a datatype from
      pop  - symbolic constant of the population string p is in

  Outputs:
      MPI_Datatype.

  Example:
      Called only by MPI routines.  Not for user consumption.

****************************************************************************I*/
MPI_Datatype PGABinaryBuildDatatype(PGAContext *ctx, int p, int pop)
{

     int            counts[4];      /* Number of elements in each
                                       block (array of integer) */
     MPI_Aint       displs[4];      /* byte displacement of each
                                       block (array of integer) */
     MPI_Datatype   types[4];       /* type of elements in each block (array
                                       of handles to datatype objects) */
     MPI_Datatype   individualtype; /* new datatype (handle) */
     PGAIndividual *traveller;      /* address of individual in question */

     PGADebugEntered("PGABinaryBuildDatatype");

     traveller = PGAGetIndividual(ctx, p, pop);
     MPI_Address(&traveller->evalfunc, &displs[0]);
     counts[0] = 1;
     types[0]  = MPI_DOUBLE;

     MPI_Address(&traveller->fitness, &displs[1]);
     counts[1] = 1;
     types[1]  = MPI_DOUBLE;

     MPI_Address(&traveller->evaluptodate, &displs[2]);
     counts[2] = 1;
     types[2]  = MPI_INT;

     MPI_Address(traveller->chrom, &displs[3]);
     counts[3] = ctx->ga.tw;
     types[3]  = MPI_UNSIGNED_LONG;

     MPI_Type_struct(4, counts, displs, types, &individualtype);
     MPI_Type_commit(&individualtype);

     PGADebugExited("PGABinaryBuildDatatype");

     return (individualtype);
}


/*I****************************************************************************
   PGABinaryHammingDistance - Returns the Hamming distance between two strings

   Inputs:
      ctx - context variable
      s1  - the first string to compare
      s2  - the second string to compare

   Outputs:
      The Hamming distance between two strings

   Example:
      Returns the Hamming distance between bit strings x and y.

      PGAContext *ctx;
      PGABinary *x, *y;
      int d;
      :
      d = PGABinaryHammingDistance( ctx, x, y );

****************************************************************************I*/
int PGABinaryHammingDistance ( PGAContext *ctx, PGABinary *s1, PGABinary *s2 )
{
    int        j, wi, distance;
    PGABinary  t1, t2, mask;

    PGADebugEntered("PGABinaryHammingDistance");

    distance = 0;
    for(wi=0; wi<ctx->ga.tw; wi++)  /* step through each word in the string */
        if ( s1[wi] != s2[wi] ) {   /* if equal, no bits are different      */
            /*fprintf(stdout,"s1[wi] = %x, s2[wi] = %x\n",s1[wi],s2[wi]);*/
            mask = 1;
            for(j=0;j<WL;++j) {     /* not equal, compare all bits          */
                /* Build bit mask in position j. Mask bit from each         */
                /* string into t1 and t2 and test if bits are the same      */
                t1 = s1[wi] & mask;
                t2 = s2[wi] & mask;
                /*fprintf(stdout,"mask = %u, t1 = %u, t2 = %u, j = %d, wi = %d\n",mask,t1,t2,j,wi);*/
                if ( t1 != t2 )
                    distance++;
                mask <<= 1;          /* shift mask 1 position */
            }
        }

    PGADebugExited("PGABinaryHammingDistance");

    return(distance);
}

/*I****************************************************************************
   PGABinaryPrint - writes a bit string to a file.  Puts the binary
   representation of the bit string pointed to by chrom into a character
   string and writes that out. Assumes the maximum length of string to
   print is WL, and that all bits are in the same word.

   Inputs:
      ctx   - context variable
      fp    - file to write the bit string to
      chrom - pointer to the bit string to write
      nb    - number of bits to write out

   Outputs:

   Example:
      Internal function.  Use PGABinaryPrintString to print a binary string.

****************************************************************************I*/
void PGABinaryPrint( PGAContext *ctx, FILE *fp, PGABinary *chrom, int nb )
{
     char *s, string[WL+1];
     PGABinary mask;
     int i;

     PGADebugEntered("PGABinaryPrint");

     mask = ((PGABinary)1)<<(WL-1);
     s = string;
     for(i=0; i<nb; mask>>=1,i++)              /* mask each bit and set the  */
          *s++ = (mask&(*chrom)?'1':'0');      /* appropriate character      */
     *s=0;                                     /* string terminator          */
     fprintf(fp, "%s", string);                /* print out character string */

     PGADebugExited("PGABinaryPrint");
}