/*SGPC: Simple Genetic Programming in C(c) 1993 by Walter Alden Tackett and Aviram Carmi  This code and documentation is copyrighted and is not in the public domain. All rights reserved.   - This notice may not be removed or altered.  - You may not try to make money by distributing the package or by using the   process that the code creates.  - You may not distribute modified versions without clearly documenting your   changes and notifying the principal author.  - The origin of this software must not be misrepresented, either by   explicit claim or by omission.  Since few users ever read sources,   credits must appear in the documentation.  - Altered versions must be plainly marked as such, and must not be   misrepresented as being the original software.  Since few users ever read   sources, credits must appear in the documentation.  - The authors are not responsible for the consequences of use of this    software, no matter how awful, even if they arise from flaws in it. If you make changes to the code, or have suggestions for changes,let us know!  (gpc@ipld01.hac.com)*/#ifndef lintstatic char crossover_c_rcsid[]="$Id: crossover.c,v 2.6 1993/04/22 07:39:12 gpc-avc Exp gpc-avc $";#endif/* * * $Log: crossover.c,v $ * Revision 2.6  1993/04/22  07:39:12  gpc-avc * Removed old log messages * * Revision 2.5  1993/04/14  05:07:57  gpc-avc * removed #ifdef TRACE code * * */#include <stdio.h>#include <malloc.h>#include <errno.h>#include "gpc.h"/*#define TRACEcaap#define TRACEcafp*/#ifdef ANSI_FUNCVOID crossover_at_any_pt(  pop_struct 	*pop,  tree 		*p1,  tree 		*p2,  tree 		**o1,  tree 		**o2  )#elseVOID crossover_at_any_pt(pop,p1, p2, o1, o2)  pop_struct	*pop;  tree		*p1, *p2, **o1, **o2;#endif{  tree	*st1, *st2, **st1ptr, **st2ptr;  int	xpt1, xpt2;  xpt1 = random_int(count_crossover_pts(p1));  xpt2 = random_int(count_crossover_pts(p2));  *o1 = copy_tree(p1);  *o2 = copy_tree(p2);  st1 = get_subtree(*o1, xpt1);  st2 = get_subtree(*o2, xpt2);  st1ptr = pointer_to_subtree(o1, st1);  st2ptr = pointer_to_subtree(o2, st2);  *st1ptr = st2;  *st2ptr = st1;  validate_crossover(pop, p1, p2, o1, o2);}#ifdef ANSI_FUNCVOID crossover_at_func_pt(  pop_struct 	*pop,  tree 		*p1,  tree 		*p2,  tree 		**o1,  tree 		**o2  )#elseVOID crossover_at_func_pt(pop, p1, p2, o1, o2)  pop_struct 	*pop;  tree		*p1, *p2, **o1, **o2;#endif{  tree	*st1, *st2, **st1ptr, **st2ptr;  int	xpt1, xpt2;  xpt1 = random_int(count_function_pts(p1));  xpt2 = random_int(count_function_pts(p2));  *o1 = copy_tree(p1);  *o2 = copy_tree(p2);  st1 = get_function_subtree(*o1, xpt1);  st2 = get_function_subtree(*o2, xpt2);  st1ptr = pointer_to_subtree(o1, st1);  st2ptr = pointer_to_subtree(o2, st2);  *st1ptr = st2;  *st2ptr = st1;  validate_crossover(pop, p1, p2, o1, o2);}#ifdef ANSI_FUNCVOID validate_crossover(  pop_struct 	*pop,  tree 		*p1,  tree 		*p2,  tree 		**o1,  tree 		**o2  )#elseVOID validate_crossover(pop, p1, p2, o1, o2)  pop_struct 	*pop;  tree		*p1, *p2, **o1, **o2;#endif{  int	d1, d2;  d1 = depth_of_tree(*o1);  d2 = depth_of_tree(*o2);  if (d1 > pop[(*o1)->pop].max_depth_after_crossover) {    free_tree(*o1);    *o1 = copy_tree(p1);  }	        if (d2 > pop[(*o2)->pop].max_depth_after_crossover) {    free_tree(*o2);    *o2 = copy_tree(p2);  }	      }#ifdef ANSI_FUNCint depth_of_tree(	tree *t	)#elseint depth_of_tree(t)tree	*t;#endif{  int	i, n, maxn=0;  pop_struct *pop = POP;  if (t->nodetype == FUNCTION) {    for (i=0; i<function_arity(t); i++) {      n = depth_of_tree(t->type.func->arg[i]);      maxn = max(maxn,n);    }    return 1+maxn;  } else {    return 0;  }}  #ifdef ANSI_FUNCint count_crossover_pts(	tree *t	)#elseint count_crossover_pts(t)tree	*t;#endif{  int	i, n=1;  pop_struct *pop = POP;  if (t->nodetype == FUNCTION) {    for (i=0; i<function_arity(t); i++) {      n += count_crossover_pts(t->type.func->arg[i]);    }  }  return n;}#ifdef ANSI_FUNCint count_function_pts(	tree *t	)#elseint count_function_pts(t)tree	*t;#endif{  int	i, n=1;  pop_struct *pop = POP;  if (t->nodetype == FUNCTION) {    for (i=0; i<function_arity(t); i++) {      n += count_function_pts(t->type.func->arg[i]);    }    return n;  } else {    return 0;  }}#ifdef ANSI_FUNCtree *get_subtree(	tree *t,	int n	)#elsetree *get_subtree(t,n)tree	*t;int	n;#endif{  int	m;  m = n;  return gs(t,&m);}  #ifdef ANSI_FUNCtree *gs(	tree *t,	int *n	)#elsetree *gs(t,n)tree	*t;int	*n;#endif{  tree	*st;  int	i;  pop_struct *pop = POP;  if (!(*n)) return(t);  else if (t->nodetype == FUNCTION) {    for (i=0; i<function_arity(t); i++) {            --(*n);      st = gs(t->type.func->arg[i],n);      if (!(*n)) break;    }    return st;  } else {    return (tree *) NULL;  }}#ifdef ANSI_FUNCtree *get_function_subtree(	tree *t,	int n	)#elsetree *get_function_subtree(t,n)tree	*t;int	n;#endif{  int	m;    m = n;  return gfs(t,&m);}  #ifdef ANSI_FUNCtree *gfs(	tree *t,	int *n	)#elsetree *gfs(t,n)tree	*t;int	*n;#endif{  tree	*st;  int	i;  pop_struct *pop = POP;  if (!(*n)) return(t);  for (i=0; i<function_arity(t); i++) {          if (t->type.func->arg[i]->nodetype == FUNCTION) {      --(*n);      st = gfs(t->type.func->arg[i],n);      if (!(*n)) break;    }  }  return st;}#ifdef ANSI_FUNCtree **pointer_to_subtree(	tree **pointer,	tree *subt	)#elsetree 	**pointer_to_subtree(pointer, subt)tree	**pointer, *subt;#endif{  int	i;  tree	**pos;  pop_struct *pop = POP;  if (*pointer == subt) {    return pointer;  }    for (i=0; i<function_arity(*pointer); i++) {    if ((*pointer)->type.func->arg[i]->nodetype == FUNCTION) {      pos = pointer_to_subtree(&((*pointer)->type.func->arg[i]), subt);      if ((pos != NULL) && ((*pos) == subt)) return pos;    } else {      if ((*pointer)->type.func->arg[i] == subt)	return &((*pointer)->type.func->arg[i]);    }  }  return ((tree **)NULL); /* make lint happy */}