/*  lil-gp Genetic Programming System, version 1.0, 11 July 1995
 *  Copyright (C) 1995  Michigan State University
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of version 2 of the GNU General Public License as
 *  published by the Free Software Foundation.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *  
 *  Douglas Zongker       (zongker@isl.cps.msu.edu)
 *  Dr. Bill Punch        (punch@isl.cps.msu.edu)
 *
 *  Computer Science Department
 *  A-714 Wells Hall
 *  Michigan State University
 *  East Lansing, Michigan  48824
 *  USA
 *  
 */


#include <lilgp.h>

typedef struct
{
     int keep_trying;
     int num_times;  /* Number of times we should keep trying. If 0, infinity. --Sean */
     double internal;
     double external;
     double *tree;
     double treetotal;
     char *sname;
     sel_context *sc;
     int method;
     int mindepth, maxdepth;
} mutate_data;

/* operator_mutate_init()
 *
 * initialize a breedphase record for mutation.  much of this is cut and
 * paste from the crossover operator; see that for (a few) more comments.
 */

int operator_mutate_init ( char *options, breedphase *bp )
{
     int errors = 0;
     mutate_data *md;
     int i, j, k, m;
     double r;
     char **argv, **targv;
     int internalset = 0, externalset = 0;
     char *cp;

     md = (mutate_data *)MALLOC ( sizeof ( mutate_data ) );

     /* fill in the breedphase record. */
     bp->operator = OPERATOR_MUTATE;
     bp->data = (void *)md;
     bp->operator_free = operator_mutate_free;
     bp->operator_start = operator_mutate_start;
     bp->operator_end = operator_mutate_end;
     bp->operator_operate = operator_mutate;

     /* default values for the mutation-specific data structure. */
     md->keep_trying = 0;
     md->internal = 0.9;
     md->external = 0.1;
     md->tree = (double *)MALLOC ( tree_count * sizeof ( double ) );
     for ( j = 0; j < tree_count; ++j )
          md->tree[j] = 0.0;
     md->treetotal = 0.0;
     md->sname = NULL;
     md->method = GENERATE_HALF_AND_HALF;
     md->mindepth = -1;
     md->maxdepth = -1;
     
     j = parse_o_rama ( options, &argv );

     for ( i = 0; i < j; ++i )
     {
          if ( strcmp ( "keep_trying", argv[i] ) == 0 )
          {
               md->keep_trying = translate_binary ( argv[++i] );
               if ( md->keep_trying == -1 )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: \"%s\" is not a valid setting for \"keep_trying\".",
                           argv[i] );
               }
          }
	  /* parse number of times to try */
	  else if (strcmp ("num_times", argv[1]) == 0)
	  {
	       md->num_times = translate_binary(argv[++i]);
	       if (md->num_times < 0 )
	       {
	           ++errors;
		   error ( E_ERROR, "mutation: \"%s\" is not a valid setting for \"num_times\".",
			  argv[i] );
	       }
	  }
          else if ( strcmp ( "internal", argv[i] ) == 0 )
          {
               internalset = 1;
               md->internal = strtod ( argv[++i], NULL );
               if ( md->internal < 0.0 )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: \"internal\" must be nonnegative." );
               }
          }
          else if ( strcmp ( "external", argv[i] ) == 0 )
          {
               externalset = 1;
               md->external = strtod ( argv[++i], NULL );
               if ( md->external < 0.0 )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: \"external\" must be nonnegative." );
               }
          }
          else if ( strcmp ( "select", argv[i] ) == 0 )
          {
               if ( !exists_select_method ( argv[++i] ) )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: \"%s\" is not a known selection method.",
                           argv[i] );
               }
               FREE ( md->sname );
               md->sname = (char *)MALLOC ( (strlen(argv[i])+1) * sizeof ( char ) );
               strcpy ( md->sname, argv[i] );
          }
          else if ( strcmp ( "method", argv[i] ) == 0 )
          {
               ++i;
               if ( strcmp ( argv[i], "half_and_half" ) == 0 )
                    md->method = GENERATE_HALF_AND_HALF;
               else if ( strcmp ( argv[i], "grow" ) == 0 )
                    md->method = GENERATE_GROW;
               else if ( strcmp ( argv[i], "full" ) == 0 )
                    md->method = GENERATE_FULL;
               else
               {
                    ++errors;
                    error ( E_ERROR, "mutation: \"%s\" is not a known generation method.",
                           argv[i] );
               }
          }
          else if ( strcmp ( "depth", argv[i] ) == 0 )
          {
               md->mindepth = strtol ( argv[++i], &cp, 10 );
               if ( *cp == 0 )
                    md->maxdepth = md->mindepth;
               else if ( *cp == '-' )
               {
                    md->maxdepth = strtol ( cp+1, &cp, 10 );
                    if ( *cp )
                    {
                         ++errors;
                         error ( E_ERROR, "mutation: malformed depth string \"%s\".",
                                argv[i] );
                    }
               }
               else
               {
                    ++errors;
                    error ( E_ERROR, "mutation: malformed depth string \"%s\".",
                           argv[i] );
               }
          }
          else if ( strcmp ( "tree", argv[i] ) == 0 )
          {
               k = parse_o_rama ( argv[++i], &targv );
               if ( k != tree_count )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: wrong number of tree fields: \"%s\".",
                           argv[i] );
               }
               else
               {
                    for ( m = 0; m < k; ++m )
                    {
                         md->tree[m] = strtod ( targv[m], &cp );
                         if ( *cp )
                         {
                              ++errors;
                              error ( E_ERROR, "mutation: \"%s\" is not a number.",
                                     targv[m] );
                         }
                    }
               }
               
               free_o_rama ( k, &targv );
          }
          else if ( strncmp ( "tree", argv[i], 4 ) == 0 )
          {
               k = strtol ( argv[i]+4, &cp, 10 );
               if ( *cp )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: unknown option \"%s\".",
                           argv[i] );
               }
               if ( k < 0 || k >= tree_count )
               {
                    ++errors;
                    error ( E_ERROR, "mutation: \"%s\" is out of range.",
                           argv[i] );
               }
               else
               {
                    md->tree[k] = strtod ( argv[++i], &cp );
                    if ( *cp )
                    {
                         ++errors;
                         error ( E_ERROR, "mutation: \"%s\" is not a number.",
                                argv[i] );
                    }
               }
          }
          else
          {
               ++errors;
               error ( E_ERROR, "mutation: unknown option \"%s\".",
                      argv[i] );
          }
     }
     
     free_o_rama ( j, &argv );
     
     if ( internalset && !externalset )
          md->external = 0.0;
     else if ( !internalset && externalset )
          md->internal = 0.0;
     
     if ( md->sname == NULL )
     {
          ++errors;
          error ( E_ERROR, "mutation: no selection method specified." );
     }

     if ( md->mindepth == -1 && md->maxdepth == -1 )
     {
          md->mindepth = 0;
          md->maxdepth = 4;
     }
     
     if ( md->mindepth < 0 || md->maxdepth < 0 ||
         md->maxdepth < md->mindepth )
     {
          ++errors;
          error ( E_ERROR, "mutation: bad depth range.\n" );
     }
     
     for ( j = 0; j < tree_count; ++j )
          md->treetotal += md->tree[j];
     if ( md->treetotal == 0.0 )
     {
          for ( j = 0; j < tree_count; ++j )
               md->tree[j] = 1.0;
          md->treetotal = tree_count;
     }
          
     r = 0.0;
     for ( j = 0; j < tree_count; ++j )
          r = (md->tree[j] += r);

#ifdef DEBUG
     if ( !errors )
     {
          printf ( "mutation options:\n" );
          printf ( "   internal: %lf  external: %lf\n", md->internal, md->external );
          printf ( "   keep_trying: %d\n", md->keep_trying );
          printf ( "   selection: %s\n", md->sname==NULL?"NULL":md->sname );
          printf ( "   method: %d    mindepth: %d   maxdepth: %d\n",
                  md->method, md->mindepth, md->maxdepth );
          printf ( "   tree total: %lf\n", md->treetotal );
          for ( j = 0; j < tree_count; ++j )
               printf ( "   tree %d: %lf\n", j, md->tree[j] );
     }
#endif
     
     return errors;
}

/* operator_mutate_free()
 *
 * free mutation stuff.
 */

void operator_mutate_free ( void *data )
{
     mutate_data * md;

     md = (mutate_data *)data;
     FREE ( md->sname );
     FREE ( md->tree );
     FREE ( md );
}

/* operator_mutate_start()
 *
 * get selection context for mutation operator.
 */

void operator_mutate_start ( population *oldpop, void *data )
{
     mutate_data * md;
     select_context_func_ptr select_con;

     md = (mutate_data *)data;
     select_con = get_select_context ( md->sname );
     md->sc = select_con ( SELECT_INIT, NULL, oldpop, md->sname );
}

/* operator_mutate_end()
 *
 * free selection context for mutation operator.
 */

void operator_mutate_end ( void *data )
{
     mutate_data * md;

     md = (mutate_data *)data;
     md->sc->context_method ( SELECT_CLEAN, md->sc, NULL, NULL );
}


/* operator_mutate()
 *
 * do the mutation.
 */

void operator_mutate ( population *oldpop, population *newpop,
                      void *data )
{
     int i;
     int ps;
     lnode *replace[2];
     int l, ns;
     int badtree;
     int repcount;
     mutate_data * md;
     int t;
     double r;
     int depth;
     int totalnodes;
     int p;
     int forceany;
     double total;
     int count=0;
     
     md = (mutate_data *)data;
     total = md->internal + md->external;

     /* choose a tree to mutate. */
     r = random_double() * md->treetotal;
     for ( t = 0; r >= md->tree[t]; ++t );

     /* select an individual to mutate. */
     p = md->sc->select_method ( md->sc ); 
     ps = tree_nodes ( oldpop->ind[p].tr[t].data );
     forceany = (ps==1||total==0.0);

#ifdef DEBUG_MUTATE
     fprintf ( stderr, "the parent size is %d\n", ps );
     fprintf ( stderr, "    parent %4d: ", p );
     print_tree ( oldpop->ind[p].tr[t].data, stderr );
#endif          

     while(1)
     {
          count++;
	  
	  if ( forceany )
	  {
	       /* choose any point. */
	       l = random_int ( ps );
	       replace[0] = get_subtree ( oldpop->ind[p].tr[t].data, l );
	  }
	  else if ( total*random_double() < md->internal )
	  {
	       /* choose an internal point. */
	       l = random_int ( tree_nodes_internal ( oldpop->ind[p].tr[t].data ) );
	       replace[0] = get_subtree_internal ( oldpop->ind[p].tr[t].data, l );
	  }
	  else
	  {
	       /* choose an external point. */
	       l = random_int ( tree_nodes_external ( oldpop->ind[p].tr[t].data ) );
	       replace[0] = get_subtree_external ( oldpop->ind[p].tr[t].data, l );
	  }
	  
#ifdef DEBUG_MUTATE
          fprintf ( stderr, "selected for replacement: " );
          print_tree ( replace[0], stderr );
#endif

          gensp_reset ( 1 );
	  /* pick a value from the depth ramp. */
          depth = md->mindepth + random_int ( md->maxdepth - md->mindepth + 1 );
	  /* grow the tree. */
          switch ( md->method )
          {
             case GENERATE_GROW:
	       /* Look up the return type of the parent */
               generate_random_grow_tree ( 1, depth, fset+tree_map[t].fset,
					  replace[0]->f->return_type);
               break;
             case GENERATE_FULL:
               generate_random_full_tree ( 1, depth, fset+tree_map[t].fset,
					   replace[0]->f->return_type);
               break;
             case GENERATE_HALF_AND_HALF:
               if ( random_double() < 0.5 )
                    generate_random_grow_tree ( 1, depth, fset+tree_map[t].fset,
					   replace[0]->f->return_type);
               else
                    generate_random_full_tree ( 1, depth, fset+tree_map[t].fset ,
					  replace[0]->f->return_type);
               break;
          }

#ifdef DEBUG_MUTATE
          fprintf ( stderr, "the new subtree is: " );
          print_tree ( gensp[1].data, stderr );
#endif

	  /* count the nodes in the new tree. */
          ns = ps - tree_nodes ( replace[0] ) + tree_nodes ( gensp[1].data );
          totalnodes = ns;

	  /* check the mutated tree against node count and/or size limits. */
          badtree = 0;
          if ( tree_map[t].nodelimit > -1 && ns > tree_map[t].nodelimit )
               badtree = 1;
          else if ( tree_map[t].depthlimit > -1 )
          {
               ns = tree_depth_to_subtree ( oldpop->ind[p].tr[t].data,
                                           replace[0] ) +
                    tree_depth ( gensp[1].data );
               if ( ns > tree_map[t].depthlimit )
                    badtree = 1;
          }

	  /* if tree is too big and keep_trying is set, then skip to the
	     stop and choose a new mutation point/mutant subtree. */
          if ( md->keep_trying && badtree &&
	      (md->num_times==0 ||
	      md->num_times > count) )
               continue;

	  /* check mutated tree against whole-individual node limits. */
          if ( ind_nodelimit > -1 )
          {
               for ( i = 0; i < tree_count; ++i )
                    if ( i != t )
                         totalnodes += oldpop->ind[p].tr[i].nodes;
               badtree |= (totalnodes > ind_nodelimit);
          }

	  /* if tree is too big and keep_trying is set, then skip to the
	     stop and choose a new mutation point/mutant subtree. */
          if ( md->keep_trying && badtree &&
	      (md->num_times==0 ||
	      md->num_times > count))
               continue;

          if ( badtree )
          {
#ifdef DEBUG_MUTATE
               fprintf ( stderr,
                        "new tree is too big; reproducing parent.\n" );
#endif
	       /* tree too big but keep_trying not set, just reproduce
		  parent tree. */
               duplicate_individual ( (newpop->ind)+newpop->next,
                                     (oldpop->ind)+p );
          }
          else
          {
#ifdef DEBUG_MUTATE
               fprintf ( stderr, "new tree is permissible.\n" );
#endif
	       /* copy the parent tree to the offspring position. */
               duplicate_individual ( (newpop->ind)+newpop->next,
                                     (oldpop->ind)+p );
	       /* free the tree selected for mutation. */
               free_tree ( newpop->ind[newpop->next].tr+t );
               
               /* copy the selected tree, replacing the subtree at the
		  mutation point with the randomly generated tree. */
               replace[1] = gensp[1].data;
               copy_tree_replace_many ( 0, oldpop->ind[p].tr[t].data,
                                       replace, replace+1, 1, &repcount );
               if ( repcount != 1 )
               {
                    error ( E_FATAL_ERROR,
                           "botched mutation:  this can't happen." );
               }
	       /* copy the tree to the new individual. */
               gensp_dup_tree ( 0, newpop->ind[newpop->next].tr+t );
               newpop->ind[newpop->next].evald = EVAL_CACHE_INVALID;
               newpop->ind[newpop->next].flags = FLAG_NONE;
               
#ifdef DEBUG_MUTATE
               fprintf ( stderr, "    the mutated individual is: " );
               print_individual ( newpop->ind+newpop->next, stderr );
#endif
          }

          ++newpop->next;
          break;
     }

#ifdef DEBUG_MUTATE
     printf ( "MUTATION COMPLETE.\n\n\n" );
#endif
}