www.pudn.com > dgpc.rar > newops.c
/*======================================================================+
| PGPC: Parallel Genetic Programming in C |
| (c) 1994 Genetic Algorithm Technology Corp. all rights reserved |
written by David Andre
+======================================================================*/
/*======================================================================+
| FILE: newops.c |
| DESCRIPTION: Implements adaptive ADF architecture operators for |
| the DGPC module. |
| REVISIONS: |
| Nov 30, 1994: Fixed to make it work with all the changes. |
| Jan 24, 1995: Works as of today, no known bugs. |
+======================================================================*/
/*==============================+
| HEADERS |
+==============================*/
/* System headers */
#include
#include
#include
#include "gp.h"
/*#ifndef __BORLANDC__
#include
#endif*/
#ifdef _ICC
#include
#include
#include
#include
#include "mncommon.h"
#endif
/* User headers */
#include "proto.h"
#include "newops.h"
#ifdef _ICC
#include "gpi.h"
#else
#include "gpi_stub.h"
#endif
extern Population gpop;
/*==============================+
| LOCAL DECLARATIONS |
+==============================*/
/*from newops.c*/
static void modify_adf_references(Branch *br, int new, int old);
/*from brdelete.c*/
static void brdel_replace_adf_call(int brnum, Branch *br);
static void brdel_insert_seg(
Branch *br,
int point,
int endpoint,
Fnode *new_subtree_seg,
int new_subtree_size);
static int brdel_make_new_seg(
int brdel_type, /* LEXUS or PINTO */
int brnum,
Branch *br,
int point,
int endpoint,
Fnode *new_subtree_seg,
int *new_subtree_size);
static int gen_random_legal_term(
Branch *br,int brnum);
static void brdel_fix_function_vector(
int brnum,
Branch *br);
static void brdel_rename_refs(Branch *br, int from, int to);
/*from brcreate.c*/
#define ALLOW_GLOBALS_IN_CREATED_BRANCHES 1
#define FALSE 0
#define MAX_NUMBER_OF_CUTSETS_TO_TRY 64
/* START OF brcreate.c: ********** CUT HERE ************ */
static int count_terminals_in_subtree(
Branch *br,
int subtree_start,
int subtree_size);
static int compute_cut_set(
Branch *br,
int size,
int num_cuts);
static void replace_donor_with_adf_call(
Branch *pbr,
Branch *newbr,
int opcode,
int site,
int size,
int num_cuts);
static void replace_danglers_with_parameters(
Branch *br,
int num_args);
static void adjust_created_branch_parameters(
struct ind *child,
int num_new_adf_args,
Branch * from_branch);
static void adjust_created_branch_parameters_only(
struct ind *child,
int num_new_adf_args,
Branch * from_branch);
/* symbolic names for cut_set indices */
#define START 0
#define END 1
#define INDEX 2
#define MAXARGS 20
static int cut_set[MAXARGS][3];
/*from argdup.c*/
#define PROB_SWITCH_ARG 0.50
static int DuplicateArgument(
int bchoice, int argchoice,
Branch * cbranch);
void SwitchOccurencesOfFunction(
Branch *br, int old,
int new, float prob);
static int doDuplicateArgument(
int bchoice, int argchoice,
Branch * br,
Branch * tbr,
int index, int * end_of_br);
/*from argdel.c*/
static int DeleteArgument(
int bchoice, int argchoice,
Branch * cbranch);
static void ReplaceArg(Branch *br, int ArgChoice, int FirstArg, int NumArgs);
static int doDeleteArgument(
int bchoice, int argchoice,
Branch * br,
Branch * tbr,
int index, int * end_of_br);
/*END OF DECLARATIONS*/
/*FROM NEWOPS.c*/
/* NOTE: this operation may do nothing if the Individual already has a
full complement of ADFs or if it has no ADFs to duplicate */
int DoBranchDuplication(Individual * child, Individual * parent)
{
int i;
int dup_branch_index, new_branch_index;
Branch *dup_branch_ptr, *new_branch_ptr;
CompInd tind;
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
parent = parent; /* keeps the compiler from complaining */
if (child->current_number_of_adfs == MAX_NUM_ADFS) {
/* Can't do branch duplication: Individual is maxed out on ADFs */
return 1;
} else if (child->current_number_of_adfs == 0) {
/* Can't do branch duplication: no branches to duplicate */
return 2;
}
/* Randomly select an ADF branch for duplication */
dup_branch_index = RandomInt(child->current_number_of_adfs);
#if (USE_BRDUP_FAILURE_HOOK)
if (BRDUPFailureHook(parent,dup_branch_index))
return(1);
#endif
dup_branch_ptr = &(child->adfs[dup_branch_index]);
/* The new branch will be located at the end of the list (which
will therefore need to be incremented in size). */
new_branch_index = child->current_number_of_adfs;
new_branch_ptr = &(child->adfs[new_branch_index]);
(child->current_number_of_adfs)++;
/* Copy the old branch into the new... */
CopyTree(dup_branch_ptr, new_branch_ptr);
child->adf_arity[new_branch_index] = child->adf_arity[dup_branch_index];
child->rpbs[0].function_vector[_FIRST_ADF+new_branch_index] =
child->adf_arity[new_branch_index];
for (i=_FIRST_ADF; i<=_LAST_ADF; i++) {
child->adfs[new_branch_index].function_vector[i] =
child->adfs[dup_branch_index].function_vector[i];
}
for (i=_FIRST_ADF_ARG; i<=_LAST_ADF_ARG; i++) {
child->adfs[new_branch_index].function_vector[i] =
child->adfs[dup_branch_index].function_vector[i];
}
for (i=0; icurrent_number_of_adfs; i++) {
modify_adf_references(&(child->adfs[i]),
_FIRST_ADF+new_branch_index,
_FIRST_ADF+dup_branch_index);
}
for (i=0; irpbs[i]),
_FIRST_ADF+new_branch_index,
_FIRST_ADF+dup_branch_index);
}
/* Normal termination */
/* i = TraverseSubtree(new_branch_ptr,0);*/
if (ErrorInDude(child))
{
gpi_SendError("Error in branch duplication, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
#if (USE_BRDUP_END_HOOK)
BRDUPEndHook(child, dup_branch_index);
#endif
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
return 0;
}
static void modify_adf_references(Branch *br, int new, int old)
{
int br_size;
int i;
br_size = TraverseSubtree(br, 0)+1;
for (i=0; itree[i].opcode == old) {
if (RandomInt(2)) {
br->tree[i].opcode = new;
}
}
}
/* Whether or not there were any actual references, any branch which
was allowed to call the old ADF is allowed to call the new one as
well. */
br->function_vector[new] = br->function_vector[old];
}
/* utility function copies a function_vector from one branch to another */
void CopyFunctionVector(Branch *br1, Branch *br2)
{
int i;
for (i=0; ifunction_vector[i] = br1->function_vector[i];
}
}
void CopyNonStaticFunctionVector(Branch *br1, Branch *br2)
{
int i;
for (i=_FIRST_ADF; i<_LAST_ADF_ARG; i++) {
br2->function_vector[i] = br1->function_vector[i];
}
}
/* utility function copies a subtree from one place to another, using
an intermediate buffer so that if from_br and to_br are in the same
tree then the operation will not get clobbered */
#define SAFE_COPY_SIZE_LIMIT 4096
static Fnode safe_copy_buf[SAFE_COPY_SIZE_LIMIT];
void SafeCopySubtree(Branch * from_br, int from_start, int from_end,
Branch * to_br, int to_start)
{
int i,j;
char str[256];
if (((from_end - from_start)+1)>SAFE_COPY_SIZE_LIMIT) {
sprintf(str,
"Error,oops, in SafeCopySubtree(): block size greater than limit ");
gpi_SendError(str);
sprintf(str,"(%d)\nUsing regular CopySubtree() instead...",
SAFE_COPY_SIZE_LIMIT);
gpi_SendError(str);
CopySubtree (from_br, from_start, from_end, to_br, to_start);
}
for (i=from_start, j=from_start; i <= from_end; i++,j++) {
safe_copy_buf[j].opcode = from_br->tree[i].opcode;
}
for (i=from_start, j=to_start; i <= from_end; i++,j++) {
to_br->tree[j].opcode = safe_copy_buf[i].opcode;
}
}
/* yet another handy utility function */
void MoveBranch(Branch *src, Branch *dest)
{
dest->num_nodes = src->num_nodes;
#if (USE_MULTI_TYPED_ADFS)
dest->ind->adf_type[dest->branchnum - NUM_RPBS] = src->ind->adf_type[src->branchnum - NUM_RPBS];
#endif
CopyTree(src, dest);
CopyFunctionVector(src, dest);
}
/*FROM brdelete.c*/
int DoBranchDeletion(Individual * child, Individual * parent)
{
int del_brnum, i, j;
CompInd tind;
parent = parent;
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
/* can't delete branches if there are no branches... */
if (child->current_number_of_adfs == 0) return 1;
/* randomly (?) pick ADF to delete */
/* Comment: ultimately, it is probably best to delete
preferentially those single-terminal branches, replacing
the call with the arg. */
del_brnum = RandomInt(child->current_number_of_adfs);
/* Go thru the other branches and remove calls to the
deleted ADF. replace_call_to_adf() is probably the
function in which the difference between the cadillac
and pinto versions is expressed */
for (i=0; irpbs[i]));
}
for (i=0; icurrent_number_of_adfs; i++) {
brdel_replace_adf_call(del_brnum, &(child->adfs[i]));
}
for (i=del_brnum+1; icurrent_number_of_adfs;i++) {
/* Move all physical contents of other branches
to fill the "hole" left by the deleted branch. */
/* code for MoveBranch is in newops.c */
MoveBranch(&(child->adfs[i]), &(child->adfs[i-1]));
}
#if (USE_MULTI_TYPED_ADFS)
child->adf_type[child->current_number_of_adfs-1] = -1;
#endif
/* Likewise fix function vector references to fill the
hole, essentially shifting all adf references above
the deleted branch down by one slot. */
for (i=0; irpbs[i]));
}
for (i=0; icurrent_number_of_adfs; i++) {
brdel_fix_function_vector(del_brnum, &(child->adfs[i]));
}
/* Rename all calls to adf branches numbered higher than
the deleted branch. */
for (i=0; icurrent_number_of_adfs;j++) {
brdel_rename_refs(&(child->rpbs[i]), j, j-1);
}
}
for (i=0; icurrent_number_of_adfs; i++) {
for (j=del_brnum+1; jcurrent_number_of_adfs;j++) {
brdel_rename_refs(&(child->adfs[i]), j, j-1);
}
}
/* kind of a kludge; this may change: the adf_arity field of the Individual
needs to be changed to reflect new arrangement. Copy it from RPB 0
function vector */
for (i=0; icurrent_number_of_adfs; i++)
child->adf_arity[i] = -1;
for (i=0; icurrent_number_of_adfs; i++)
{
for (j=0;jrpbs[j].function_vector[i])>=0)
{
child->adf_arity[i] = ((int) child->rpbs[j].function_vector[i]);
j = NUM_RPBS;
}
}
(child->current_number_of_adfs)--;
if (ErrorInDude(child))
{
gpi_SendError("Error in branch del, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
/*
*/
return 0;
}
/*===============================================================*/
/*=== the following routines support brdel_replace_adf_call() ===*/
/*===============================================================*/
#define BIG_BUFFER_SIZE 4096
static void brdel_replace_adf_call(int brnum, Branch *br)
{
int point, endpoint, new_subtree_size;
int old_subtree_size, expanded_subtree_size;
static Fnode new_subtree_seg[BIG_BUFFER_SIZE];
/* start at end of tree and work bass-ackwards: this
guarantees that deepest nested calls will be substituted
first */
for (point = TraverseSubtree(br,0); point >= 0; point--) {
if (br->tree[point].opcode == (brnum)) {
/* then this is a call to the deleted branch */
/* compute start and end of segment to be replaced */
endpoint = TraverseSubtree(br,point);
old_subtree_size = (endpoint-point)+1;
expanded_subtree_size = TraverseSubtree(br, 0)+1;
/* the new segment to be inserted in place of the
ADF call is new_subtree_seg */
/*
if ( brdel_make_new_seg(LEXUS, brnum, br, point, endpoint,
new_subtree_seg, &new_subtree_size)
== 0) {}*/
/*Using PINTO -- THERE IS A BUG IN THE LEXUS VERSION!!!*/
(void) brdel_make_new_seg(PINTO, brnum, br, point, endpoint,
new_subtree_seg,
&new_subtree_size);
/* Must check the size to make sure the new expanded
branch will not be made bigger than the max size: if it
is, then we force the PINTO option, which replaces the
ADF call with a single terminal, which cannot make the
expanded branch bigger */
/* NOTE: this condition should not be true if the routine above
returned 0 and PINTO option was already forced above. */
if ( (expanded_subtree_size +
(new_subtree_size - old_subtree_size )) >=
br->num_nodes-1) {
(void) brdel_make_new_seg(PINTO, brnum, br, point, endpoint,
new_subtree_seg, &new_subtree_size);
}
/* the new segement is inserted and the branch is
resized appropriately */
brdel_insert_seg(br, point, endpoint,
new_subtree_seg,
new_subtree_size);
}
}
point = TraverseSubtree(br,0);
}
static void brdel_insert_seg(
Branch *br,
int point,
int endpoint,
Fnode *new_subtree_seg,
int new_subtree_size)
{
int br_endpt, i;
br_endpt = TraverseSubtree(br,0);
SafeCopySubtree(br, endpoint+1, br_endpt, br,
point+new_subtree_size);
for (i=0; itree[point+i].opcode = new_subtree_seg[i].opcode;
}
}
/* This routine returns a new segment to be inserted
into the branch. In the Pinto version, it is a
random terminal (size one). In the Cadillac (Lexus?)
version it is the inline expanded call to the
deleted branch code. */
static int brdel_make_new_seg(
int brdel_type, /* LEXUS or PINTO */
int brnum, /* branch num of deleted branch */
Branch *br, /* branch being modified */
int point,/*start of ADF call to be expanded (index in br)*/
int endpoint, /* end of ADF call to be expanded */
Fnode *new_subtree_seg,
int *new_subtree_size)
{
static Branch fake_branch;
int apar_start, apar_end, apar_len;
int fpar_point, current_endpoint, argnum;
char str[256];
if (brdel_type == PINTO) {
*new_subtree_size = 1;
#if SPICE_PROBLEM && USE_CONSTRAINED_STRUCTURE /* THIS IS TERRIBLE!! GET IT OUT OF HERE!! */
new_subtree_seg[0].opcode = GetFuncNumber("dend",&gpop);
#else
new_subtree_seg[0].opcode = gen_random_legal_term(br,brnum);
#endif
return 1;
} else {
sprintf (str,"in brdel_make_new_seg(): WRONG brdel_type\n");
gpi_SendError(str);
exit(1001);
}
}
static int gen_random_legal_term(Branch *br,int brnum)
{
int random_atom;
while(1) {
random_atom = RandomInt(TOTAL_NUMBER_OF_FUNCTIONS);
if (random_atom != brnum && br->function_vector[random_atom] == 0)
{
if (random_atom != TOTAL_NUMBER_OF_FUNCTIONS-1)
return random_atom;
else
{
return(TOTAL_NUMBER_OF_FUNCTIONS-1 + RandomInt(_min(MAXNUMFORARANDOMCONSTANT,
gpop.num_constants) -
(gpop.num_general_functions-1)));
}
}
}
}
/*===========================================================*/
/*=== end of routines supporting brdel_replace_adf_call() ===*/
/*===========================================================*/
static void brdel_fix_function_vector(int brnum, Branch *br)
{
int i;
for ( i=_FIRST_ADF+brnum+1;
i<_FIRST_ADF+br->ind->current_number_of_adfs;
i++ ) {
br->function_vector[i-1] = br->function_vector[i];
}
br->function_vector[_FIRST_ADF+br->ind->current_number_of_adfs-1] = EMPTY;
}
static void brdel_rename_refs(Branch *br, int from, int to)
{
int i;
for (i=0; inum_nodes; i++) {
if (br->tree[i].opcode == (_FIRST_ADF + from)) {
br->tree[i].opcode = _FIRST_ADF + to;
}
}
}
#if (USE_ITERATION_GROUP_CREATION)
int DoNoHarmIterationPerformingBranchCreation(Individual * child,Individual * parent)
{
int i,j;
int ipb_count;
int nadf_count;
int num_new_adf_args;
int donor_size;
int donor_index, donor_site, donor_segment_size,
num_terminals_in_donor_segment;
Branch *new_adf_branch;
Branch * from_branch;
CompInd tind;
ipb_count=0;
nadf_count=0;
for (i=0;iadf_type[i] == ADF_TYPE_ADF)
nadf_count++;
else if (parent->adf_type[i] == ADF_TYPE_IPB)
ipb_count++;
}
parent = parent; /* keeps the compiler from complaining */
/* There's only room for so many ADFs, so return (with nonzero
status) if there's no more space for ADFs */
if (child->current_number_of_adfs == MAX_NUM_ADFS)
{
return 1;
}
/*There is only room for so many ipbs*/
if (ipb_count >= MAX_NUM_IPBS)
{
return(1);
}
/* Randomly pick number of args for ADF. */
num_new_adf_args = 0; /*_dmin(MAX_NUM_ADF_ARGS, (_dmin(1,MIN_NUM_ADF_ARGS) +
RandomInt(MAX_NUM_ADF_ARGS)));*/
/* Pick which branch to choose from */
donor_index = RandomInt(NUM_RPBS);
from_branch = GetRightBranch(child,donor_index);
/* Pick a point within RPB to be the new ADF. */
donor_size = TraverseSubtree(from_branch, 0) + 1;
donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
donor_segment_size =
(TraverseSubtree(from_branch, donor_site)
- donor_site) + 1;
if (donor_segment_size >= GetBranchSize(NUM_RPBS+child->current_number_of_adfs)-1)
{
CopyIndividual(parent, child);
return 2;
}
num_terminals_in_donor_segment =
count_terminals_in_subtree(from_branch,
donor_site, donor_segment_size);
if (num_terminals_in_donor_segment < num_new_adf_args) {
num_new_adf_args = num_terminals_in_donor_segment;
}
/* Copy the "raw" code from the RPB into the appropriate ADF
branch. */
(child->current_number_of_adfs)++;
new_adf_branch = &(child->adfs[child->current_number_of_adfs - 1]);
CopySubtree(from_branch, donor_site,
(donor_site + donor_segment_size) - 1,
new_adf_branch, 0);
/* Copy the function vector verbatim, for now. This is not the
same as the final contents of the adjusted function_vector of
the new ADF, but it is usable, and does not produce errors as
would using an uninitialized f.v. (note, for example that the
_function_arity() macro depends on the function vector to have
arity of preexisting ADFs set right). */
/*THIS IS WRONG!!!*/ /* AT BEST, COPY THE ADF_ARITIES INTO THE APPROPRIATE
SPOTS -- BUT NOT THE WHOLE F-vector!!!*/
CopyNonStaticFunctionVector(from_branch, new_adf_branch); /*CHANGE*/
/*SetJumpsAndVals(new_adf_branch);*/
/* Perform the cut algorithm over and over until the right number of
dangling subexpressions, which will be the arguments, is found.
The cut algorithm is certainly the "area for improvement" in
this operator. Array cut_set[][2] contains starting and ending
indices of subexpressions which will be the arguments, or
"danglers" of the new ADF. */
for (i=MAX_NUMBER_OF_CUTSETS_TO_TRY; i>0; i--) {
if (compute_cut_set(new_adf_branch, donor_segment_size, num_new_adf_args)) {
break;
}
}
if (i == 0 || TraverseSubtree(from_branch,0) >= (from_branch->num_nodes-1))
{
CopyIndividual(parent, child);
return 2;
}
/*THIS CODE IS COMMENTED OUT SO THAT THE PARENT BRANCH DOES NOT CHANGE*/
/* Replace RPB code with ADF call, using "danglers" as arguments */
/* replace_donor_with_adf_call(from_branch,
new_adf_branch,
(child->current_number_of_adfs) - 1,
donor_site, donor_segment_size,
num_new_adf_args);
*/
/* Replace danglers with appropriate formal parameters in the ADF
branch code. */
/* CAUTION: do this last, since it tweaks the contents of the cut
set array. */
/* replace_danglers_with_parameters(new_adf_branch,num_new_adf_args);*/
/*END OF NO HARM REGION*/
/* Adjust Individual and RPB parameters appropriately: change
function vector of RPB, setup function vector of new ADF, set
number of arguments of new ADF. */
/*NO HARM VERSION*/
adjust_created_branch_parameters_only(child, num_new_adf_args,from_branch);
/* Done- normal termination. */
if (ErrorInDude(child))
{
gpi_SendError("Error in brc, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
child->adf_type[child->current_number_of_adfs-1] = ADF_TYPE_IPB;
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
/* printf("successful brc\n");*/
return 0;
}
#endif
#if (USE_ITERATION_GROUP_CREATION)
int DoIterationGroupCreation(Individual * child,Individual * parent)
{
int i,j;
int ipb_count;
int nadf_count;
ipb_count=0;
nadf_count=0;
for (i=0;iadf_type[i] == ADF_TYPE_ADF)
nadf_count++;
else if (parent->adf_type[i] == ADF_TYPE_IPB)
ipb_count++;
}
/* There's only room for so many ADFs, so return (with nonzero
status) if there's no more space for ADFs */
if (child->current_number_of_adfs == MAX_NUM_ADFS) return 1;
/*There is only room for so many ipbs*/
if (ipb_count+4 > MAX_NUM_IPBS)
return(1);
for (i=0;i<3;i++)
{
j = DoNoHarmIterationPerformingBranchCreation(child,parent);/*&(gpop.parent2)); */
if (j>0)
{
CopyIndividual(parent,child);
return(1);
}
}
j = DoIterationPerformingBranchCreation(child,parent);
if (j>0)
{
CopyIndividual(parent,child);
return(1);
}
}
#endif
#if (USE_IPBCO || USE_ITERATION_GROUP_CREATION)
int DoIterationPerformingBranchCreation(Individual * child,Individual * parent)
{
int i,j;
int ipb_count;
int nadf_count;
int num_new_adf_args;
int donor_size;
int donor_index, donor_site, donor_segment_size,
num_terminals_in_donor_segment;
Branch *new_adf_branch;
Branch * from_branch;
CompInd tind;
ipb_count=0;
nadf_count=0;
for (i=0;iadf_type[i] == ADF_TYPE_ADF)
nadf_count++;
else if (parent->adf_type[i] == ADF_TYPE_IPB)
ipb_count++;
}
parent = parent; /* keeps the compiler from complaining */
/* There's only room for so many ADFs, so return (with nonzero
status) if there's no more space for ADFs */
if (child->current_number_of_adfs == MAX_NUM_ADFS) return 1;
/*There is only room for so many ipbs*/
if (ipb_count >= MAX_NUM_IPBS)
return(1);
/* Randomly pick number of args for ADF. */
num_new_adf_args = 0; /*_dmin(MAX_NUM_ADF_ARGS, (_dmin(1,MIN_NUM_ADF_ARGS) +
RandomInt(MAX_NUM_ADF_ARGS)));*/
/* Pick which branch to choose from */
#if (RPB_ONLY_IPBCO)
donor_index = RandomInt(NUM_RPBS);
#else
donor_index = RandomInt(NUM_RPBS+ parent->current_number_of_adfs);
#endif
from_branch = GetRightBranch(child,donor_index);
/* Pick a point within RPB to be the new ADF. */
donor_size = TraverseSubtree(from_branch, 0) + 1;
donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
donor_segment_size =
(TraverseSubtree(from_branch, donor_site)
- donor_site) + 1;
if (donor_segment_size >= GetBranchSize(NUM_RPBS+child->current_number_of_adfs)-1)
{
CopyIndividual(parent, child);
/* printf("Bailing on BRC -- donor size too big\n");*/
return 2;
}
num_terminals_in_donor_segment =
count_terminals_in_subtree(from_branch,
donor_site, donor_segment_size);
if (num_terminals_in_donor_segment < num_new_adf_args) {
num_new_adf_args = num_terminals_in_donor_segment;
}
/* Copy the "raw" code from the RPB into the appropriate ADF
branch. */
(child->current_number_of_adfs)++;
new_adf_branch = &(child->adfs[child->current_number_of_adfs - 1]);
CopySubtree(from_branch, donor_site,
(donor_site + donor_segment_size) - 1,
new_adf_branch, 0);
/* Copy the function vector verbatim, for now. This is not the
same as the final contents of the adjusted function_vector of
the new ADF, but it is usable, and does not produce errors as
would using an uninitialized f.v. (note, for example that the
_function_arity() macro depends on the function vector to have
arity of preexisting ADFs set right). */
/*THIS IS WRONG!!!*/ /* AT BEST, COPY THE ADF_ARITIES INTO THE APPROPRIATE
SPOTS -- BUT NOT THE WHOLE F-vector!!!*/
CopyNonStaticFunctionVector(from_branch, new_adf_branch); /*CHANGE*/
/*SetJumpsAndVals(new_adf_branch);*/
/* Perform the cut algorithm over and over until the right number of
dangling subexpressions, which will be the arguments, is found.
The cut algorithm is certainly the "area for improvement" in
this operator. Array cut_set[][2] contains starting and ending
indices of subexpressions which will be the arguments, or
"danglers" of the new ADF. */
for (i=MAX_NUMBER_OF_CUTSETS_TO_TRY; i>0; i--) {
if (compute_cut_set(new_adf_branch, donor_segment_size, num_new_adf_args)) {
break;
}
}
if (i == 0 || TraverseSubtree(from_branch,0) >= (from_branch->num_nodes-1))
{
CopyIndividual(parent, child);
/* printf("Bailing on BRC\n");*/
return 2;
}
/* Replace RPB code with ADF call, using "danglers" as arguments */
replace_donor_with_adf_call(from_branch,
new_adf_branch,
(child->current_number_of_adfs) - 1,
donor_site, donor_segment_size,
num_new_adf_args);
/* Replace danglers with appropriate formal parameters in the ADF
branch code. */
/* CAUTION: do this last, since it tweaks the contents of the cut
set array. */
replace_danglers_with_parameters(new_adf_branch,num_new_adf_args);
/* Adjust Individual and RPB parameters appropriately: change
function vector of RPB, setup function vector of new ADF, set
number of arguments of new ADF. */
adjust_created_branch_parameters(child, num_new_adf_args,from_branch);
/* Done- normal termination. */
if (ErrorInDude(child))
{
gpi_SendError("Error in brc, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
child->adf_type[child->current_number_of_adfs-1] = ADF_TYPE_IPB;
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
/* printf("successful brc\n");*/
return 0;
}
#endif
/*From BRCREATE.c*/
/* These new operations have a slight violation of Dave's original spec
in the sense that they return int rather than void: a return
value less than 0 indicates failure. */
/* DoBranchCreation():
This function creates a child which is semantically identical
to its parent but with one extra ADF, which is created from a
subexpression within the result producing branch. The subexpression
in the RPB is replaced by the appropriate call to the new ADF. The
new ADF is the highest-numbered ADF, and can contain calls to any
functions and terminals which are present in the parent RPB. The
"parent" argument is a pointer to the existing parent, while the "child"
argument is a pointer to a valid existing block of storage presumed
large enough to hold an Individual. In practice both locations
presumably point to locations in the same array of Population
Members, although there are cases (in some implementations of
generational selection, for example) where that may not be true. */
int DoBranchCreation(Individual * child, Individual * parent)
{
int num_new_adf_args;
int donor_size;
int donor_index, donor_site, donor_segment_size,
num_terminals_in_donor_segment;
Branch *new_adf_branch;
int i,j,ct,done;
Branch * from_branch;
CompInd tind;
#if (USE_CONSTRAINED_STRUCTURE)
int fvector[TOTAL_NUMBER_OF_FUNCTIONS];
#endif
/* printf("In BRC\n");*/
parent = parent; /* keeps the compiler from complaining */
#if (USE_BRC_FAILURE_HOOK)
if (BRCFailureHook(parent))
return(2);
#endif
/* There's only room for so many ADFs, so return (with nonzero
status) if there's no more space for ADFs */
if (child->current_number_of_adfs == MAX_NUM_ADFS) return 1;
/* Randomly pick number of args for ADF. */
num_new_adf_args = _dmin(MAX_NUM_ADF_ARGS, (_dmin(1,MIN_NUM_ADF_ARGS) +
RandomInt(MAX_NUM_ADF_ARGS)));
/* Pick which branch to choose from */
donor_index = RandomInt(NUM_RPBS + parent->current_number_of_adfs);
from_branch = GetRightBranch(child,donor_index);
/* Pick a point within RPB to be the new ADF. */
donor_size = TraverseSubtree(from_branch, 0) + 1;
#if USE_CONSTRAINED_STRUCTURE
done =0;
ct =0;
while (!done && ct < MAX_ATTEMPTS)
{
ct++;
donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
done =1;
#if (USE_CONSTRAINED_STRUCTURE)
if (done)
{
new_adf_branch = &(child->adfs[child->current_number_of_adfs]);
CopyFVector(new_adf_branch->function_vector,fvector);
ConstrainedSyntaxFilters(fvector,new_adf_branch,
TOP_OF_TREE,0,&gpop);
}
/*Compare male_fvector with point fvector. If no match, done=0*/
if (!ValidSubtreeGivenFVector(from_branch, donor_site,fvector))
done=0;
#endif
}
if (!done)
{
CopyIndividual(parent, child);
/* printf("Bailing on BRC\n");*/
return 2;
}
else
/* printf("BRC succeeded!\n");*/
#else
donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
#endif
donor_segment_size =
(TraverseSubtree(from_branch, donor_site)
- donor_site) + 1;
if (donor_segment_size >= GetBranchSize(NUM_RPBS+child->current_number_of_adfs)-1)
{
CopyIndividual(parent, child);
/* printf("Bailing on BRC -- donor size too big\n");*/
return 2;
}
num_terminals_in_donor_segment =
count_terminals_in_subtree(from_branch,
donor_site, donor_segment_size);
if (num_terminals_in_donor_segment < num_new_adf_args) {
num_new_adf_args = num_terminals_in_donor_segment;
}
/* Copy the "raw" code from the RPB into the appropriate ADF
branch. */
(child->current_number_of_adfs)++;
new_adf_branch = &(child->adfs[child->current_number_of_adfs - 1]);
CopySubtree(from_branch, donor_site,
(donor_site + donor_segment_size) - 1,
new_adf_branch, 0);
/* Copy the function vector verbatim, for now. This is not the
same as the final contents of the adjusted function_vector of
the new ADF, but it is usable, and does not produce errors as
would using an uninitialized f.v. (note, for example that the
_function_arity() macro depends on the function vector to have
arity of preexisting ADFs set right). */
/*THIS IS WRONG!!!*/ /* AT BEST, COPY THE ADF_ARITIES INTO THE APPROPRIATE
SPOTS -- BUT NOT THE WHOLE F-vector!!!*/
CopyNonStaticFunctionVector(from_branch, new_adf_branch); /*CHANGE*/
/*SetJumpsAndVals(new_adf_branch);*/
/* Perform the cut algorithm over and over until the right number of
dangling subexpressions, which will be the arguments, is found.
The cut algorithm is certainly the "area for improvement" in
this operator. Array cut_set[][2] contains starting and ending
indices of subexpressions which will be the arguments, or
"danglers" of the new ADF. */
for (i=MAX_NUMBER_OF_CUTSETS_TO_TRY; i>0; i--) {
if (compute_cut_set(new_adf_branch, donor_segment_size, num_new_adf_args)) {
break;
}
}
if (i == 0 || TraverseSubtree(from_branch,0) >= (from_branch->num_nodes-1))
{
CopyIndividual(parent, child);
/* printf("Bailing on BRC\n");*/
return 2;
}
/* Replace RPB code with ADF call, using "danglers" as arguments */
replace_donor_with_adf_call(from_branch,
new_adf_branch,
(child->current_number_of_adfs) - 1,
donor_site, donor_segment_size,
num_new_adf_args);
/* Replace danglers with appropriate formal parameters in the ADF
branch code. */
/* CAUTION: do this last, since it tweaks the contents of the cut
set array. */
replace_danglers_with_parameters(new_adf_branch,num_new_adf_args);
/* Adjust Individual and RPB parameters appropriately: change
function vector of RPB, setup function vector of new ADF, set
number of arguments of new ADF. */
adjust_created_branch_parameters(child, num_new_adf_args,from_branch);
/* Done- normal termination. */
if (ErrorInDude(child))
{
gpi_SendError("Error in brc, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
#if (USE_BRC_END_HOOK)
BRCEndHook(child);
#endif
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
/* printf("successful brc\n");*/
return 0;
}
static void adjust_created_branch_parameters_only(
struct ind *child,
int num_new_adf_args,
Branch * from_branch)
{
int i;
int br_size;
Branch *br;
/* IMPORTANT NOTE ABOUT INDEXING THE NEW ADF:
(child->current_number_of_adfs)-1 is the index of the last valid
ADF in the Individuals poiinted to by "child." Since new
branches are now appended to the end of the ADF list regardless,
then this newest ADF is the highest numbered one, last in the
list. */
/* br is just shorthand for the pointer to this ADF branch */
br = &(child->adfs[(child->current_number_of_adfs)-1]);
/* br_size is the size of the new ADF. Executing
TraverseSubtree() starting from element 0 of the branch returns
the index of the last valid node in the linear array which
represents the tree. We add 1 since the array is numbered from
0. */
br_size = TraverseSubtree(br, 0)+1;
/* set the arity of the new ADF */
/*NO_HARM child->adf_arity[(child->current_number_of_adfs)-1] = num_new_adf_args;
for (i=0;irpbs[i].function_vector[_FIRST_ADF+
(child->current_number_of_adfs)-1] = num_new_adf_args;
NO HARM */
/*NO_HARM from_branch->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] =
num_new_adf_args;
*/
/* ADJUST THE FUNCTION VECTOR OF THE NEW ADF */
/* PART 0: Set ADF references in the function vector to EMPTY */
/*
Changed: see below
for (i=_FIRST_ADF; i<=_LAST_ADF; i++) {
br->function_vector[i] = EMPTY;
}
*/
/* Modification: only disallow this ADF from calling itself */
/* also, it cannot call any adfs that could 'call' it -- i.e. all
those lower than the from_branch */
br->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] = EMPTY;
/* PART 1: This loop makes sure that all functions and terminals
(well, particularly ADF calls- funcs and terms were taken care of
in the calling troutine, which copied the RPB functiion vector))
which were copied from the RPB into the new ADF branch are
enabled in the ADF function vector, e.g., if the ADF contains
"global" terminals, for example. But that's not quite enough
(see below). */
for (i=0; ifunction_vector[_fv_map(br->tree[i].opcode)] =
from_branch->function_vector[_fv_map(br->tree[i].opcode)];
}
/* PART 2: The new ADF contains arguments (arg0, arg1, etc.) which
were not enabled in the RPB (and therefore not enabled in the
loop above). Enable them, and for good measure make sure those
args which should not be present in this branch are indeed
disabled. */
for (i=_FIRST_ADF_ARG; i<=_LAST_ADF_ARG; i++) {
if (i < (_FIRST_ADF_ARG+num_new_adf_args)) {
br->function_vector[i] = 0;
} else {
br->function_vector[i] = (-1);
}
}
}
static void adjust_created_branch_parameters(
struct ind *child,
int num_new_adf_args,
Branch * from_branch)
{
int i;
int br_size;
Branch *br;
/* IMPORTANT NOTE ABOUT INDEXING THE NEW ADF:
(child->current_number_of_adfs)-1 is the index of the last valid
ADF in the Individuals poiinted to by "child." Since new
branches are now appended to the end of the ADF list regardless,
then this newest ADF is the highest numbered one, last in the
list. */
/* br is just shorthand for the pointer to this ADF branch */
br = &(child->adfs[(child->current_number_of_adfs)-1]);
/* br_size is the size of the new ADF. Executing
TraverseSubtree() starting from element 0 of the branch returns
the index of the last valid node in the linear array which
represents the tree. We add 1 since the array is numbered from
0. */
br_size = TraverseSubtree(br, 0)+1;
/* set the arity of the new ADF */
child->adf_arity[(child->current_number_of_adfs)-1] = num_new_adf_args;
for (i=0;irpbs[i].function_vector[_FIRST_ADF+
(child->current_number_of_adfs)-1] = num_new_adf_args;
from_branch->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] =
num_new_adf_args;
/* ADJUST THE FUNCTION VECTOR OF THE NEW ADF */
/* PART 0: Set ADF references in the function vector to EMPTY */
/*
Changed: see below
for (i=_FIRST_ADF; i<=_LAST_ADF; i++) {
br->function_vector[i] = EMPTY;
}
*/
/* Modification: only disallow this ADF from calling itself */
/* also, it cannot call any adfs that could 'call' it -- i.e. all
those lower than the from_branch */
br->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] = EMPTY;
/* PART 1: This loop makes sure that all functions and terminals
(well, particularly ADF calls- funcs and terms were taken care of
in the calling troutine, which copied the RPB functiion vector))
which were copied from the RPB into the new ADF branch are
enabled in the ADF function vector, e.g., if the ADF contains
"global" terminals, for example. But that's not quite enough
(see below). */
for (i=0; ifunction_vector[_fv_map(br->tree[i].opcode)] =
from_branch->function_vector[_fv_map(br->tree[i].opcode)];
}
/* PART 2: The new ADF contains arguments (arg0, arg1, etc.) which
were not enabled in the RPB (and therefore not enabled in the
loop above). Enable them, and for good measure make sure those
args which should not be present in this branch are indeed
disabled. */
for (i=_FIRST_ADF_ARG; i<=_LAST_ADF_ARG; i++) {
if (i < (_FIRST_ADF_ARG+num_new_adf_args)) {
br->function_vector[i] = 0;
} else {
br->function_vector[i] = (-1);
}
}
}
void replace_danglers_with_parameters(Branch * br, int num_cuts)
{
int i, j, point;
for (i=0; itree[point].opcode = MAX_NUM_ADFS + i;
point++;
/* delete the rest of the cut branch */
SafeCopySubtree(br, cut_set[i][END]+1, br->num_nodes, br, point);
/* the next cut branch has been moved up by the number of deleted
nodes, which is just the size of branch i minus 1 */
for (j=i+1; jtree[site].opcode = opcode;
point = site+1;
for (i=0; i=0; j--) {
if ((cut_set[i][START] > cut_set[j][END]) ||
(cut_set[i][END] < cut_set[j][START])) {
/* then the two do not overlap */
} else {
/* then cut point i falls within cut point j: return failure */
return 0;
}
}
}
/* sort cut set in order to collapse code properly */
for (i=0; ifunction_vector,fvector);
ConstrainedSyntaxFilters(fvector,br, GetFuncNumber("adf0",&gpop), i,&gpop);
/*Compare male_fvector with point fvector. If no match, done=0*/
if (!ValidSubtreeGivenFVector(br, cut_set[i][START],fvector))
return(0);
}
#endif
/* This next loop is to insure that no 'unallowed' functions show up in the
part that will become the new adf */
for (i=0, j=0; itree[i].opcode) == -1) {
return 0;
}
}
/*This next is to prevent there from being dummy arguments in the non-cut
sub-expressions -- i.e., all dummy args from an adf must be in the cut-
expressions*/
for (i=0, j=0; itree[i].opcode)) {
return 0;
}
}
return 1;
}
int count_terminals_in_subtree( Branch *br,
int subtree_start,
int subtree_size)
{
int i, subtree_end = subtree_start + subtree_size;
int term_count = 0;
for (i=subtree_start; itree[i].opcode))) {
term_count++;
}
}
return (term_count);
}
/* END OF brcreate.c: ********** CUT HERE ************ */
/*FROM ARGDUP.c*/
int DoArgumentDuplication(Individual *child, Individual * parent)
{
int i,error;
int bchoice,argchoice;
CompInd tind;
/*Check to see if there are any adfs--if not, return*/
if (child->current_number_of_adfs < 1)
return(-1);
/*Choose a branch in the Individual upon which to do arg
duplication*/
bchoice = RandomInt(child->current_number_of_adfs);
/*Check to see if this adf has args, else return*/
if (child->adf_arity[bchoice] < 1) {
return(-1);
} else if (child->adf_arity[bchoice] >= MAX_NUM_ADF_ARGS) {
return(-1);
}
/*Choose an argument to duplicate*/
argchoice = RandomInt(child->adf_arity[bchoice]);
/*Duplicate the arguments in each place where the ADF is internally
invoked*/
error = 0;
for (i=0;irpbs[i]));
if (error >0)
error=0;
}
for (i=0;icurrent_number_of_adfs;i++)
{
if (error ==0)
if (parent->adfs[i].function_vector[bchoice] > -1 )
error = DuplicateArgument(bchoice, argchoice,
&(child->adfs[i]));
if (error >0)
error=0;
}
/*error will be non-zero when there was an error in duplication,
this will often be due to overwriting the space available for the
Individual's branch b/c of the arg duplication, which can be
exponentially explosive wrt memory*/
if (error < 0)
{
CopyIndividual(parent,child);
return(-1);
}
/*Tidy up the function_vectors and the adf_arity*/
for (i=0;i< NUM_RPBS;i++)
if (child->rpbs[i].function_vector[bchoice] > -1)
(child->rpbs[i].function_vector[bchoice])++;
for (i=0;i< child->current_number_of_adfs;i++)
if (child->adfs[i].function_vector[bchoice] > -1)
(child->adfs[i].function_vector[bchoice])++;
(child->adf_arity[bchoice])++;
child->adfs[bchoice].function_vector[MAX_NUM_ADFS + child->adf_arity[bchoice] -1 ] = 0;
/*Switch half of the references of the arg being duplicated
inside the branch upon which arg duplication is taking place*/
SwitchOccurencesOfFunction(&(child->adfs[bchoice]),
MAX_NUM_ADFS+argchoice,
MAX_NUM_ADFS+(child->adf_arity[bchoice]-1),
(float)PROB_SWITCH_ARG);
/* i = TraverseSubtree(&(child->adfs[bchoice]),0);*/
if (ErrorInDude(child))
{
gpi_SendError("Error in arg dup, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
return(0);
}
void SwitchOccurencesOfFunction(Branch *br, int old,
int new, float prob)
{
int br_size;
int i;
br_size = TraverseSubtree(br, 0)+1;
for (i=0; itree[i].opcode == old) {
if (RandomFloat((float)1.0)<= prob) {
br->tree[i].opcode = new;
}
}
}
}
static int DuplicateArgument(int bchoice, int argchoice,
Branch * cbranch)
{
int i;
int size_error =0;
Branch temp_tree;
int end_of_br;
temp_tree.branchnum = cbranch->branchnum;
temp_tree.num_nodes = cbranch->num_nodes;
temp_tree.ind = cbranch->ind;
for (i=0;ifunction_vector[i];
temp_tree.tree = (Fnode *)calloc(temp_tree.num_nodes,sizeof(Fnode));
end_of_br = TraverseSubtree(cbranch,0);
size_error = doDuplicateArgument(bchoice, argchoice, cbranch,
&temp_tree, 0, &end_of_br);
free(temp_tree.tree);
/* i=TraverseSubtree(cbranch,0); */
return(size_error);
}
static int doDuplicateArgument(int bchoice, int argchoice,
Branch * br,
Branch * tbr,
int index,
int * end_of_br)
{
int i,num,start_pt,end_pt,tindex;
if (br->tree[index].opcode == EMPTY)
{
return(-1);
}
if (index >= br->num_nodes)
{
return(-1);
}
else
{
num = index;
for (i=0;i< _function_arity(br->tree[num].opcode);i++)
{
if ((br->tree[num].opcode == bchoice) && i == argchoice)
{
start_pt = index+1;
end_pt = TraverseSubtree(br,start_pt);
if (((*end_of_br)+ 1 + end_pt-start_pt+1) >= br->num_nodes)
return(-1);
CopySubtree(br,start_pt,(*end_of_br),tbr,0);
CopySubtree(tbr,0,(*end_of_br)-start_pt, br,end_pt+1);
(*end_of_br) = (*end_of_br) + (end_pt - start_pt) +1;
tindex = doDuplicateArgument(bchoice,argchoice,br,tbr,index+1,end_of_br);
if (tindex >= br->num_nodes || tindex == -1)
return(-1);
index = tindex;
}
index = doDuplicateArgument(bchoice, argchoice, br,tbr, index+1,end_of_br);
if (index+1 >= br->num_nodes || index == -1)
return(-1);
}
}
return(index);
}
/*from ARGDEL.c*/
int DoArgumentDeletion(Individual *child, Individual * parent)
{
int i,error;
int bchoice,argchoice;
char str[256];
CompInd tind;
/* We assume that the parent has already been copied into the
child */
/*Check to see if there are any adfs--if not, return*/
if (child->current_number_of_adfs < 1)
return(-1);
/*Choose a branch in the Individual upon which to do arg
deletion*/
bchoice = RandomInt(child->current_number_of_adfs);
/*Check to see if this adf has enough args to delete one, else return*/
if (child->adf_arity[bchoice] < 2) {
return(-1);
} else if (child->adf_arity[bchoice] > MAX_NUM_ADF_ARGS) {
sprintf(str,"child->adf_arity is too high.\n");
gpi_SendError(str);
exit(-1);
}
/*Choose an argument to delete*/
argchoice = RandomInt(child->adf_arity[bchoice]);
/*Delete the arguments in each place where the ADF is internally
invoked*/
error = 0;
for (i=0;irpbs[i]));
if (error >0)
error=0;
}
for (i=0;icurrent_number_of_adfs;i++)
{
if (error ==0)
if (parent->adfs[i].function_vector[bchoice] > -1 )
error = DeleteArgument(bchoice, argchoice, &(child->adfs[i]));
if (error >0)
error=0;
}
/*error will be not often be non-zero when there was an error in deletion,
but may occur */
if (error < 0)
{
CopyIndividual(parent,child);
return(-1);
}
/*Tidy up the function_vectors and the adf_arity*/
for (i=0;i< NUM_RPBS;i++)
if (child->rpbs[i].function_vector[bchoice] > -1)
(child->rpbs[i].function_vector[bchoice])--;
for (i=0;i< child->current_number_of_adfs;i++)
if (child->adfs[i].function_vector[bchoice] > -1)
(child->adfs[i].function_vector[bchoice])--;
(child->adf_arity[bchoice])--;
child->adfs[bchoice].function_vector[MAX_NUM_ADFS + (child->adf_arity[bchoice])] = -1;
/*Replace all occurances of the arg to be deleted with a randomly chosen one of
the other arguments (there must be one, due to the fact that only adfs with 2 args can
undergo arg deletion */
ReplaceArg(&(child->adfs[bchoice]),MAX_NUM_ADFS+argchoice,MAX_NUM_ADFS,(child->adf_arity[bchoice])+1);
/*Rename any arguments ABOVE the once being deleted in the branch to one lower
starting with moving n+1 to n, then n+2 to n+1, etc*/
for (i=(MAX_NUM_ADFS+argchoice+1);i<(MAX_NUM_ADFS+child->adf_arity[bchoice] +1);i++)
SwitchOccurencesOfFunction(&(child->adfs[bchoice]), i, i-1,(float) 1.0);
/* i = TraverseSubtree(&(child->adfs[bchoice]),0);*/
if (ErrorInDude(child))
{
gpi_SendError("Error in arg del, operation aborted, child set to parent\n");
CopyIndividual(parent, child);
return(1);
}
/* printf("right before compress ind in arg deletion\n");*/
CompressIndividual(child,&tind);
UnCompressIndividual(&tind,child);
return(0);
}
static void ReplaceArg(Branch *br, int ArgToBeReplaced,
int FirstArg, int NumArgs)
{
int br_size;
int i;
int temp;
FirstArg = FirstArg;
br_size = TraverseSubtree(br,0)+1;
for (i=0;itree[i].opcode == ArgToBeReplaced)
{
temp = RandomInt(NumArgs-1);
if (temp == ArgToBeReplaced)
temp = NumArgs-1;
br->tree[i].opcode = temp+MAX_NUM_ADFS;
}
}
}
static int DeleteArgument(int bchoice, int argchoice,
Branch * cbranch)
{
int i;
int size_error =0;
Branch temp_tree;
int end_of_br;
temp_tree.branchnum = cbranch->branchnum;
temp_tree.num_nodes = cbranch->num_nodes;
temp_tree.ind = cbranch->ind;
for (i=0;ifunction_vector[i];
temp_tree.tree = (Fnode *)calloc(temp_tree.num_nodes,sizeof(Fnode));
end_of_br = TraverseSubtree(cbranch,0);
size_error = doDeleteArgument(bchoice, argchoice, cbranch,
&temp_tree, 0, &end_of_br);
free(temp_tree.tree);
/* i = TraverseSubtree(cbranch,0);*/
return(size_error);
}
static int doDeleteArgument(int bchoice, int argchoice,
Branch * br,
Branch * tbr,
int index,
int * end_of_br)
{
int i,num,start_pt,end_pt;
if (br->tree[index].opcode == EMPTY)
{
return(-1);
}
if (index >= br->num_nodes)
{
return(-1);
}
else
{
num = index;
for (i=0;i< _function_arity(br->tree[num].opcode);i++)
{
if ((br->tree[num].opcode == bchoice) && i == argchoice)
{
start_pt = index+1;
end_pt = TraverseSubtree(br,start_pt);
SafeCopySubtree(br,end_pt+1,(*end_of_br),br,start_pt);
(*end_of_br) = (*end_of_br) - ( (end_pt - start_pt) +1);
}
else
{
index = doDeleteArgument(bchoice, argchoice, br,tbr, index+1,end_of_br);
}
if (index+1 >= br->num_nodes || index == -1)
return(-1);
}
}
return(index);
}