/* Hills and trenches added 5/23/00:
   Binary operations Bel,Trx,Try


*/
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "rtree.h"


//control variables and structures for terminals
int nvars=1;    //number of variables
double minC=-1; //minimum size for an ephemeral constant
double maxC=1;  //maximum size for an ephemeral constant

//control variables and structures for unary operations
//number of uops in the system
#define maxUOp 9
int curUOp=9;                           //number currently authorized 
int UOpActive[maxUOp]={1,1,1,1,1,1,1,   //boolean array: authorized?
		       1,1};
int UOpCurrent[maxUOp]={0,1,2,3,4,5,    //integer array: current indices
			6,7,8};
char *UOpNames[maxUOp]={"Neg","Com",    //Operation names
      "Del","Sin","Cos","Atn","Sqt",
      "UA1","UA2"};

//control variables and structures for binary operations
//number of uops in the system
#define maxBOp 17
int curBOp=17;                          //number currently authorized 
int BOpActive[maxBOp]={1,1,1,1,1,1,1,  //boolean array: authorized?
                       1,1,1,1,1,1,1,
                       1,1,1};
int BOpCurrent[maxBOp]={0,1,2,3,4,5,6, //integer array: current indices
                        7,8,7,10,11,12,13,14,15,16};
char *BOpNames[maxBOp]={"Add","Sub",    //Operation names
      "Mul","Div","Max","Min","Eql",
      "Gtr","Les","Geq","Leq","Neq",
      "BA1","BA2","Bel","Trx","Try"};

//control variables and structures for binary operations
//number of uops in the system
#define maxTOp 1
int curTOp=1;                          //number currently authorized 
int TOpActive[maxTOp]={1};             //boolean array: authorized?
int TOpCurrent[maxTOp]={0};            //integer array: current indices
char *TOpNames[maxTOp]={"ITE"};        //Operation names

/* routine local to tree.cpp */

node *emptynode(){//generates a typeless initialized node without arguments

node *bld;

   bld=new node;
   bld->type=0;
   bld->val=0.0;
   bld->args[0]=0;
   bld->args[1]=0;
   bld->args[2]=0;
   return(bld);

}

node *ValidTerminal(){  //used to generate an ephemeral constant or
                        //variable in a single node tree
node *bld;

   bld = emptynode();
   
   if(lrand48()%2){ /* 50% chance of an ephemeral constant */
      bld->type=0;
      bld->val=drand48()*(maxC-minC)+minC;
   } else {
      bld->type=lrand48()%nvars+1;
   }

   return(bld);
}

int UOpCode(){ //generate an enabled unary opcode

   if(curUOp==0){
     cout << "All unary operations disabled" << endl;
     return(256);
   }
   return(UOpCurrent[lrand48()%curUOp])+256;

}

int BOpCode(){ //generate an enabled binary opcode

   if(curBOp==0){
     cout << "All binary operations disabled" << endl;
     return(512);
   }
   return(BOpCurrent[lrand48()%curBOp])+512;

}

int TOpCode(){ //generate an enabled trinary opcode

   if(curTOp==0){
     cout << "All trinary operations disabled" << endl;
     return(768);
   }
   return(TOpCurrent[lrand48()%curTOp])+768;

}

/***********Utility Routines for Parameter Setting*************/
void SetNumberOfVariables(int n){

   nvars=n;

}


void SetConstantRange(double min,double max){

  if(min>max)return;  //failsafe
   minC=min;
   maxC=max;

}

void RatUnary(int id,int onP){ //set the given unary operation to 
	                        //the given on/off state.
int i;

   id%=256;
   if((id>=maxUOp)||(id<0))return;
   UOpActive[id]=onP;
   curUOp=0;
   for(i=0;i<maxUOp;i++){
      if(UOpActive[i])UOpCurrent[curUOp++]=i;
   }      
}
void RatBinary(int id,int onP){ //set the given binary operation to 
	                        //the given on/off state.
int i;

   id%=256;
   if((id>=maxBOp)||(id<0))return;
   BOpActive[id]=onP;
   curBOp=0;
   for(i=0;i<maxBOp;i++){
      if(BOpActive[i])BOpCurrent[curBOp++]=i;
   }      
}

void RatTrinary(int id,int onP){ //set the given trinary operation to 
	                         //the given on/off state.
int i;

   id%=256;
   if((id>=maxTOp)||(id<0))return;
   TOpActive[id]=onP;
   curTOp=0;
   for(i=0;i<maxTOp;i++){
      if(TOpActive[i])TOpCurrent[curTOp++]=i;
   }      
}

/******************I/O I/O it's off to work we go*************/
//Overload << to output parse trees
ostream& operator <<(ostream &aus,node *t){

   switch(t->type/256){
   case 0: if(t->type==0) aus << t->val;
                          else aus << "X" << t->type;
           break;
   case 1: aus << "(" << UOpNames[t->type%256] 
                << " " << t->args[0] << ")";
           break;
   case 2: aus << "(" << BOpNames[t->type%256] 
                << " " << t->args[0] << " " << t->args[1] << ")";   
           break;
   case 3: aus << "(" << TOpNames[t->type%256] 
                << " " << t-> args[0] << " " << t->args[1] 
                << " " << t->args[2] << ")";
           break;
   }

}

/********************Operation set controls******************/


//Controls for Operations
void TurnOn(int OpCode){

  switch(OpCode/256){
  case 0: cout << "Attempt to turn off a terminal" << endl;
          break;
  case 1: RatUnary(OpCode%256,1);
          break;
  case 2: RatBinary(OpCode%256,1);
          break;
  case 3: RatTrinary(OpCode%256,1);
          break;
  }

}

void TurnOff(int OpCode){

  switch(OpCode/256){
  case 0: cout << "Attempt to turn off a terminal" << endl;
          break;
  case 1: RatUnary(OpCode%256,0);
          break;
  case 2: RatBinary(OpCode%256,0);
          break;
  case 3: RatTrinary(OpCode%256,0);
          break;
  }

}

/**************Tree Generation and Manipulation**************/


/*
   The random tree generator operates by generating an operation 
and recursively generating its arguments.  To this end...

   One node trees are terminals, genrated by calling ValidTerminal()
   Two node trees are a unary operation with a one node argument.
   Three node trees are binary opeartions with one node arguments.
   Four or more node trees are a random operation, with the arity
      chosen accoring to a distribution implemented as a switch 
      statement with remaming nodes broken up among arguments.

 */
node *RandTree(int n){  //generate a random tree of size n

node *bld;
int a,b;

   if(n==0)return(0); else
   if(n==1)return(ValidTerminal()); else
   if(n==2){
      bld=emptynode();
      bld->type=UOpCode();
      bld->args[0]=ValidTerminal();
      return(bld);
   } else if (n==3) {
      bld=emptynode();
      bld->type=BOpCode();
      bld->args[0]=ValidTerminal();
      bld->args[1]=ValidTerminal();
      return(bld);
   } else {
     switch(lrand48()%10){
     case 0:
     case 1:
     case 2:bld=emptynode();
            bld->type=UOpCode();
            bld->args[0]=RandTree(n-1);
            return(bld);
            break;

     case 3:
     case 4:
     case 5:
     case 6:
     case 7:
     case 8:bld=emptynode();
            bld->type=BOpCode();
            a=1+lrand48()%(n-2);
            b=n-a-1;
            bld->args[0]=RandTree(a);
            bld->args[1]=RandTree(b);
            return(bld);
            break;
     case 9://cout << n << " ";
            a=1+lrand48()%(n-3);  //notice this isn't uniformly at random
            n-=a;                 //a tends to hog the remaining nodes
            b=1+lrand48()%(n-2);
            n-=b;
            bld=emptynode();
            bld->type=TOpCode();
            bld->args[0]=RandTree(n-1);  //favor small if clauses
            bld->args[1]=RandTree(b);    
            bld->args[2]=RandTree(a);
            //cout << a << " " << b << " " << n-1 << endl;
            return(bld);
            break;

     }

   }
}

void KillTree(node *t){  //deallocate a tree

   if(t==0)return;       //recursion stops on nil pointers
   KillTree(t->args[0]); //Kill the arguments - the nil stop makes this okay
   KillTree(t->args[1]); //ditto
   KillTree(t->args[2]); //ditto
   delete t;             //now execute the node and we're done|enod

}

node *CopyTree(node *t){ //copy a tree

node *bld;

   if(t==0)return(0);        //copy nil nodes by returning a nil pointer
   bld=emptynode();          //othewise create a node for the copy
   bld->type=t->type;                  //equality ransfters non-
   bld->val=t->val;                    //pointer fields
   bld->args[0]=CopyTree(t->args[0]);  //Use a recursive call
   bld->args[1]=CopyTree(t->args[1]);  //to make copies of the 
   bld->args[2]=CopyTree(t->args[2]);  //argument fields
   return(bld);       //done with the current node - return
}

int SizeTree(node *t){  //count the nodes in a tree

   if(t==0)return(0);
   return(1+SizeTree(t->args[0])+
            SizeTree(t->args[1])+
            SizeTree(t->args[2]));
}

node* SubTree(node *t,int &n){ //return the nth nub-node of tree t

node *temp;  

   if(n==0)return(t);
   else {
      if(t->type<256)return((node*) 0);
      else {
         temp=SubTree(t->args[0],--n);
         if(n==0)return(temp);
         else{
            if(t->type<512)return((node*) 0);
            else{
               temp=SubTree(t->args[1],--n);
               if(n==0) return(temp);
               else{
                  if(t->type<768)return((node*) 0);
                  else{
                     temp=SubTree(t->args[2],--n);
                     if(n==0) return(temp);
                     else return((node *) 0);
                  }
	       }
	    }
	 }
   
      }
   }
}

node *RandSubTree(node *t){

int n;

   n=lrand48()%SizeTree(t);
   return(SubTree(t,n));
}

/*******************Evaluation routines******************/


void InitDelay(node *t){ //zero out the delay operators before evaluation

  if((t==0)||(t->type<256))return;   //return on leaves or nil pointers
  if(t->type==DelOP)t->val=0;        //zero val if node is delay
  InitDelay(t->args[0]);  //               
  InitDelay(t->args[0]);  //   Recurse!
  InitDelay(t->args[0]);  //

}

double Eval(node *t,node *U1,node *U2,node *B1, node *B2,double *vars){

double v[3];

  if(t==0)return(0);
  if(t->type<256){
    if(t->type==0)return(t->val); else return(vars[(t->type)-1]);
  } else {
    v[0]=Eval(t->args[0],vars); 
    v[1]=Eval(t->args[1],vars); 
    v[2]=Eval(t->args[2],vars); 
    switch(t->type){
    case 256: return(-v[0]);       //negate
              break;
    case 257: return(1-v[0]);      //complement (1-x)
              break;
    case 258: v[1]=t->val;         //delay 
              t->val=v[0];
              return(v[1]);
    case 259: return(sin(v[0]));   //sin
              break;
    case 260: return(cos(v[0]));   //cos
              break;
    case 261: return(atan(v[0]));  //arctangent
              break;
    case 262: if(v[0]>0)return(sqrt(v[0]));   //sqrt, with negcorrection
                   else return(-sqrt(-v[0])); // 
              break;
    case 263: return(Eval(U1,0,0,0,0,v));  //Unary ADF 2
              break;
    case 264: return(Eval(U2,0,0,0,0,v));  //Unary ADF 2 nb
              break;
    case 512: return(v[0]+v[1]);   //add
              break;
    case 513: return(v[0]-v[1]);   //minus
              break;
    case 514: return(v[0]*v[1]);   //times
              break;
    case 515: if((v[1]>0.00000001)||(v[1]<-0.00000001)){//Mung division
                 return(v[0]/v[1]);
              } else return(0);
    case 516: if(v[0]>v[1])return(v[0]);else return(v[1]); //Maximum
              break;
    case 517: if(v[0]>v[1])return(v[1]);else return(v[0]); //Maximum
              break;
    case 518: return(v[0]==v[1]);  //equality
              break;
    case 519: return(v[0]>v[1]);   //greater than
              break;
    case 520: return(v[0]<v[1]);   //less than
              break; 
    case 521: return(v[0]>=v[1]);  //greater than or equal to
              break;
    case 522: return(v[0]<=v[1]);  //less than or equal to
              break;
    case 523: return(v[0]!=v[1]);  //inequality
              break;
    case 524: return(Eval(B1,0,0,0,0,v));  //Binary ADF 1
              break;
    case 525: return(Eval(B2,0,0,0,0,v));  //Binary ADF 2
              break;
    case 526: return(1/(1+v[0]*v[0]+v[1]*v[1]));  //Hill
              break;
    case 527: return(1/(1+v[0]*v[0])); //X-trench
              break;
    case 528: return(1/(1+v[1]*v[1])); //Y-trench
              break;
    case 768: if(v[0]>=0)return(v[1]);else return(v[2]);  //ITE
              break;
    }
  }
}

double Eval(node *t,double *vars){

   return(Eval(t,0,0,0,0,vars));

}

double EvalU1(node *t,node *u,         //evaluate with one unary ADF
              double *vars){

   return(Eval(t,u,0,0,0,vars));

}

double EvalU2(node *t,node *u1,        //evaluate with two unary ADFs
              node *u2,double *vars){ 

   return(Eval(t,u1,u2,0,0,vars));

}

double EvalB1(node *t,node *b,         //evaluate with one unary ADF
              double *vars){

   return(Eval(t,0,0,b,0,vars));

}

double EvalB2(node *t,node *b1,        //evaluate with two binary ADFs
              node *b2,double *vars){ 

   return(Eval(t,0,0,b1,b2,vars));

}

double EvalUB(node *t,node *u,         //evaluate with one unary,
              node *b,double *vars){   //one binary ADF

   return(Eval(t,u,0,b,0,vars));

}

double EvalUB2(node *t,node *u1,        //evaluate with two unary,
               node *u2,node* b1,       //two binary ADF
               node *b2,double *vars){

   return(Eval(t,u1,u2,b1,b2,vars));

}

/**************************Genetic Operators*********************/

void mutateST(node *t){//replace a subtree with another subtree the same size

node sw,*s,*r;

   s=RandSubTree(t);
   r=RandTree(SizeTree(s));
   sw=*s;
   *s=*r;
   *r=sw;
   KillTree(r);
}

void mutateND(node *t){ //perform a node mutation

node *s,*r;

   s=RandSubTree(t);
   switch(s->type/256){
   case 0: r=RandTree(1);
           *s=*r;
           delete r;
           break;
   case 1: s->type=UOpCode();
           break; 
   case 2: s->type=BOpCode();
           break; 
   case 3: s->type=TOpCode();
           break; 
   }

}

void cross(node *t,node *s){ //two point crossover

node sw,*u,*v;

   u=RandSubTree(t);
   v=RandSubTree(s);
   sw=*u;
   *u=*v;
   *v=sw;
}

//chop reduces the size of a tree
void chop(node *t, //Tree to chop
          int k    //size bound to meet
	  ){

node *kl;
int i,who;
     
   if(k<2)return;  //Forget it if they want the tree shrunk too small

   while(SizeTree(t)>k){
      who=lrand48()%(t->type/256);
      for(i=0;i<3;i++)if(i!=who)KillTree(t->args[i]);
      kl=t->args[who]; 
      *t=*(t->args[who]);
      delete kl;
   }
}