class tree {
  
  String[] substitute;
  String[] genotype;
  String[] growstring;
  
  int no, x,y,w, generation, age;
  float stack_rot[], fitness, growspeed, deg = PI*0.25, initthick=6.0, thick;
  int pushlevel = 0, maxpush = 50, symbols, stack_x[], stack_y[]; 
  int startlength = 3, rulelength = 4, freezone = 10;
  int maxgeneration = 17, ownmax = maxgeneration;
  int maxleft, maxright, maxtop, maxbottom, nowx, nowy;
  float boxscaler = 1.0, growfactor = 1.0;
  boolean over, elite = false, parent = false, fitness_check=true, f_counting=false;
  boolean growing = false, growmore=false;
  int toolong = 1000, growcounter = 0;
  int initstep = 40; float step; float stack_step[];
  int f_push, f_arc, f_line, f_rot, f_jump, f_rotmax, f_circle, f_draw, f_not;

  tree(int n, int px, int py, int  boxsize) {
    no = n; x=px; y=py; w=boxsize;
    symbols = abc.length;
    substitute = new String[symbols];
    stack_rot = new float[maxpush];
    stack_step = new float[maxpush];
    genotype = new String[maxgeneration];
    growstring = new String[maxgeneration];
    stack_x = new int[maxpush];
    stack_y = new int[maxpush];
    startup();
  }
  
  void startup() {
    over = false; parent = false; elite=false; growing=false;
    for(int i=0; i<maxpush; i++) stack_rot[i]=0;
    deg = random(PI*0.1,PI*1.0);
    generation = 1;
    make_startgen();
    make_rules();
    build_gen();
  }
  
  void make_startgen() {
    genotype[0]=""; 
    int aimlength = startlength + int(random(freezone));
    boolean havetoclose = false;
    for(int i=0; i<aimlength; i++) {
      if(int(random(symbols+1))==0) {
        //add brackets for push and pop
        if(havetoclose) {
          genotype[0]+=']'; havetoclose=false;
        } else{
          genotype[0]+='['; havetoclose=true;
        }
      } else {
        //add random symbol
        genotype[0] += abc[int(random(symbols))];
      }
    } 
    if(havetoclose) genotype[0]+=']';
    
    genotype[0] = clean(genotype[0]); 
  }
  
  void make_rules() {
    int aimlength;
    boolean havetoclose;
    
    for(int i=0; i<symbols; i++) {
      aimlength = 1+int(random(rulelength));
      substitute[i] = (repeat_first) ? str(abc[i]) : ""; 
      havetoclose = false;
      
      if((abc[i]>='A'&&abc[i]<='Z') || evolve_lowercase) {
        for(int j=0; j<aimlength; j++) {
          if(int(random(symbols+1))==0) {                      //add brackets
            if(havetoclose) {
               substitute[i]+=']'; havetoclose = false;
            } else {
               substitute[i]+='['; havetoclose = true;
            }
          } else substitute[i] += abc[int(random(symbols))];    //add random symbol
        } 
        substitute[i] = clean(substitute[i]);
      } else substitute[i] = str(abc[i]);
    } 
  }

  void build_gen() {
    fitness = 0;  fitness_check=true; 
    growstring[0]="";
    for(int i=0; i<=genotype[0].length(); i++) growstring[0]+='-';
    int n; 
    for(int g=1; g<maxgeneration; g++) {
      genotype[g] = "";
      if(growing) growstring[g]="";
      if(genotype[g-1].length()>toolong) {
        ownmax = g;
        for(; g<maxgeneration; g++) { genotype[g]=""; if(growing) growstring[g]=""; }
        break;
      }
      for(int i=0; i<genotype[g-1].length(); i++) {
        
          n = -1;
          for(int j=0; j<symbols; j++) {
            if(abc[j] == genotype[g-1].charAt(i)) {
              n = j; break;
            }
          }
          if((growing && growstring[g-1].charAt(i)=='X')) n=-2;
          if(n==-2) {
          } else if(n==-1) {
            genotype[g] += genotype[g-1].charAt(i);
            if(growing) growstring[g] += '-';
          } else {
            if(growing) {
              //abc[n]==substitute[n].charAt(0) && substitute[n].length()==1
              if(str(abc[n]).equals(substitute[n])) {
                growstring[g] += '-';
              } else {
                genotype[g] += abc[n]; 
                growstring[g]+='X';
                for(int p=0; p<substitute[n].length(); p++) growstring[g] += 'G';
              }
            }
            genotype[g] += substitute[n];
          }

      }
      if(!growing) genotype[g] = clean(genotype[g]);
    }
  }
    
  void check() {
    int d=5;
    over = (mouseX>x-w/2-d&&mouseX<x+w/2+w*(displgen-1)+d&&mouseY>y-w/2-d&&mouseY<y+w/2+d) ? true : false;
    
    if(over && mousePressed && !menu.visible && mouseleft) {
      menu.visible = true; menu.treeno = no;
      menu.place(mouseX,mouseY);
    }
  }
  
  void draw_frame() {
    int d=5; noStroke(); 
    if(elite && showone==-1)  fill(markc); else if(parent && showone==-1) fill(markc2); else fill(tc0); 
    rect(-w/2,-w/2,w,w);
    if(over || (menu.visible && menu.treeno==no) ) fill(tc1); else fill(tc2); 
    if(menu.visible && menu.treeno!=no) fill(tc2);
    rect(-w/2+d,-w/2+d,w-2*d,w-2*d);
  }
  
  void draw_family(int g1, int g2) {
    pushMatrix(); translate(x,y);
    for(int i=g1; i<g2; i++) {
      if(!fitness_check) {
        f_counting = true;
      }
      if(showone==no && (i%(int)(Math.floor((width-100)/w)))==0 && i!=0) {
        translate(-w*(int)(Math.floor((width-100)/w)),w);
      } else if (showone==no && (i==g2-1) && (i%(int)(Math.floor((width-100)/w)))>4) {
        int tab = (i%(int)(Math.floor((width-100)/w)));
        translate( -w* (int) Math.min( Math.floor((width-100)/w), float(tab))  , w);
      }
      if(showone==no && i==g2-1) { w*=3; translate(w/3,w/3); }
      draw_frame();
      if(genotype[i]!="") draw_tree(i);
      if(showone==no && i==g2-1) w/=3;
      if(i==g1) { fill(255); noStroke(); textFont(pixelfont, 8); 
      text(fitness,-w/2-3,w/2+9); textFont(lucida, 11); }
      translate(w,0);
      //if(showone==no && (i%(int)(Math.floor((width-200)/w)))==0 && i!=0) {
      
      
      if(!fitness_check) { compute_fitness(); f_counting = false; }
    }
    
    popMatrix();
  }
  
  void compute_fitness() {

    fitness_check=true;
    fitness = 0;
    
    int totallength = 0;
    for(int i=0; i<g; i++) totallength+=genotype[i].length();
    if(bt_f_length) if(totallength!=0) fitness += 1.0/totallength;
    
    int ww = abs(maxright-maxleft); int hh = abs(maxtop-maxbottom);
    float rmax = max(ww,hh); float rmin = min(ww,hh);
    float ratio = (rmax==0) ? 0 : rmin/rmax;
    if(bt_f_ratio) fitness += ratio;
    
    if(bt_f_maxh) fitness += hh/100.0;
    if(bt_f_maxw) fitness += ww/100.0;
    
    if(bt_f_growh) fitness += (maxleft>=0) ? 1.0 : 1.0/(float)maxleft;
    
    int dim = 200;
    if(bt_f_dim200) fitness += (abs(dim-ww)==0) ? 0.5 : 0.5/abs(dim-ww);
    if(bt_f_dim200) fitness += (abs(dim-hh)==0) ? 0.5 : 0.5/abs(dim-hh);
    
    dim = 500;
    if(bt_f_dim500) fitness += (abs(dim-ww)==0) ? 0.5 : 0.5/abs(dim-ww);
    if(bt_f_dim500) fitness += (abs(dim-hh)==0) ? 0.5 : 0.5/abs(dim-hh);
    
    dim = 1000;
    if(bt_f_dim1000) fitness += (abs(dim-ww)==0) ? 0.5 : 0.5/abs(dim-ww);
    if(bt_f_dim1000) fitness += (abs(dim-hh)==0) ? 0.5 : 0.5/abs(dim-hh);
    
    if(bt_f_linesp) fitness += (float)f_line/100.0;
    if(bt_f_linesn) fitness += (f_line==0) ? 1 : 1.0/(float)f_line;
    if(bt_f_push) fitness += (float)f_push/100.0;
    if(bt_f_arc) fitness += (float)f_arc/100.0;
    
    if(bt_f_circle) fitness += (f_circle==0) ? 1 : 1.0/(float)f_circle;
    if(bt_f_jump) fitness += (f_jump==0) ? 1 : 1.0/(float)f_jump;
    if(bt_f_rot) fitness += (f_rot==0) ? 1 : 1.0/(float)f_rot;
    if(bt_f_rotmax) fitness += (f_rotmax==0) ? 1 : 1.0/(float)f_rotmax;
    
    if(bt_f_notdraw) fitness += (f_not==0) ? 1 : 1.0/(float)f_not;
    if(bt_f_draw) fitness += (float)f_draw/100.0;

     if(fitness < 0.1 || f_draw<=1) {
       startup();
       fitness_check = false;
     }
  }
  
  void start_growing() {
    maxleft=0; maxright=0; maxtop=0; maxbottom=0; boxscaler=1.0;
    growmore = true; growing = true;
    growspeed = 0.05; growfactor = 0.0; age = 1; build_gen(); 
  }
  
  void grow() {
    if(age<ownmax && growmore) {
      if(growcounter==0) {
      growfactor+=growspeed;
      if(growfactor>=1.0) {
        age++; growfactor=0.0;
        //growcounter=10;
        if(genotype[age].length()>toolong || age==maxgeneration-1) {
          growmore=false; age--; growfactor=1.0;
        }
      }
      } else {
        growcounter--;
      }
    } else { growmore=false; growfactor=1.0; }
    pushMatrix(); translate(x,y);
    //draw_frame(); 
    draw_tree(age); 
    popMatrix();
  }
  
  void draw_tree(int g) {
    
    maxleft=0; maxright=0; maxtop=0; maxbottom=0; boxscaler=1.0; 
    nowx=0; nowy=0; step = initstep; stack_step[0] = step;
    int boxmedx = 0, boxmedy = 0;
    boolean testscale;
    float growfactor2 = 1.0;
    pushMatrix(); rotate(-PI/2);
    for(int t=0; t<2; t++) {
      testscale = (t==0) ? true : false;    
      for(int i=0; i<maxpush; i++) stack_rot[i] = 0;
      pushMatrix(); noFill();
      translate(boxmedx, boxmedy);
      if(testscale) noStroke(); else {
        stroke(black); 
        if(showone==no && growing) strokeWeight(thick/boxscaler); 
      }
      if(f_counting) { f_draw=0; f_not=0; f_push=0; f_arc=0; f_line=0; f_rot=0; f_jump=0; f_rotmax=0; f_circle=0; }
      for(int i=0; i<genotype[g].length(); i++) {
        if(growing) {
          if(growstring[g].charAt(i)=='G') growfactor2 = growfactor;
          else if(growstring[g].charAt(i)=='X') growfactor2 = 1.0-growfactor;
          else growfactor2=1.0;
        }
        //color
        if(showone==no && growing && !testscale) stroke((((float) i/ (float) genotype[g].length()))*205,0,0);
        //char[] abc = { 'r','b','j','F','A','J','C','R','K','+','-' };
        switch(genotype[g].charAt(i)) {
          case 'r': do_r(growfactor2); break;
          case 'b': do_b(growfactor2); break;
          case 'j': do_j(growfactor2); break;
          case 'F': do_F(growfactor2); break;
          case 'A': do_A(growfactor2); break;
          case 'R': do_R(growfactor2); break;
          case '[': do_push();        break;
          case ']': do_pop();         break;
          case 'C': do_C(growfactor2); break;
          case '+': do_plus(growfactor2); break;
          case '-': do_minus(growfactor2); break;
        }
      }
      popMatrix();
      
      if(testscale) {
        int maximal = max( abs(maxright-maxleft), abs(maxtop-maxbottom) );
        if(maximal!=0 && maximal > w ) boxscaler = float(w)/float(maximal);
        if(maximal!=0) {
          step = initstep * boxscaler;
          stack_step[0] = step;
        }
        thick = initthick * boxscaler;
        boxmedx =  -int(   (maxleft+(maxright-maxleft)/2)* boxscaler  );
        boxmedy =  -int(   (maxbottom+(maxtop-maxbottom)/2)*boxscaler  );
        
        //if(showone==no && !test) {
        //  if(g==5) test=true;
        //  print(g); print("\tl="+maxleft+"\tr="+maxright);
        //  print("\tw="+abs(maxright-maxleft)); print("\th="+abs(maxtop-maxbottom));
        //  print("\tsc="+boxscaler); //print("\tst="+step);
        //  print("\tx="+boxmedx+"\ty="+boxmedy); println();
        //}
      }
    }
    popMatrix(); 
    strokeWeight(1.0);
  }
    
  void check_overflow() {
    maxleft = (maxleft<nowx) ? maxleft : nowx;
    maxright = (maxright>nowx) ? maxright : nowx;
    maxtop = (maxtop>nowy) ? maxtop : nowy;
    maxbottom = (maxbottom<nowy) ? maxbottom : nowy;
  }
  
  void do_r(float t) {
    if(t!=0) {
    rotate((deg)*t); stack_rot[pushlevel] += (deg)*t; 
    if(f_counting) { f_not++; f_rot++; f_rotmax = max(f_rotmax,abs(f_rot)); }
    }
  }
  
  void do_b(float t) {
    if(t!=0) {
    rotate((-deg)*t); stack_rot[pushlevel] -= (deg)*t; 
    if(f_counting) { f_not++; f_rot--; f_rotmax = max(f_rotmax,abs(f_rot)); }
    }
  }
  
  void do_j(float t) {
    if(t!=0) {
    translate((step)*t,0); 
    if(f_counting) f_jump++;
    nowx += cos(stack_rot[pushlevel])*step*t;
    nowy += sin(stack_rot[pushlevel])*step*t;
    if(f_counting) f_not++;
    }
  }
  
  void do_F(float t) {
    if(t!=0) {
    line(0,0,step*t,0); translate(step*t,0);
    //rect(0,-thick/2,step*t,thick); 
    nowx += cos(stack_rot[pushlevel])*step*t;
    nowy += sin(stack_rot[pushlevel])*step*t;
    check_overflow(); 
    if(f_counting) { f_line++; f_draw++; }
    }
  }
  
  void do_A(float t) {
    if(t!=0) {
    arc(0,(step/2),step,step,PI*1.5,PI*1.5+(deg)*t);
    translate( sin(deg*t)*step/2, step/2-cos(deg*t)*step/2);
    
    rotate(deg*t); stack_rot[pushlevel] += deg*t;
    nowx += sin(stack_rot[pushlevel])*step*t/2;
    nowy += cos(stack_rot[pushlevel])*step*t/2;

    //rotate(deg*t); stack_rot[pushlevel] += deg*t;
    //translate(step/2-sin((deg))*step*(1.0-t)/2,cos((deg)*t)*step/2-step/2);
    //nowx += cos(stack_rot[pushlevel])*step*t + sin(stack_rot[pushlevel])*step*t;
    //nowy += sin(stack_rot[pushlevel])*step*t - cos(stack_rot[pushlevel])*step*t;
    if(f_counting) { f_draw++; f_arc++; f_rot++; f_rotmax = max(f_rotmax,abs(f_rot)); }
    check_overflow(); 
    }
  }
  
   void do_R(float t) {
     if(t!=0) {
    arc(0,-(step/2),step,step,PI/2-deg*t,PI/2);
    translate( sin(deg*t)*step/2, -step/2+cos(deg*t)*step/2);
    rotate(-deg*t);  stack_rot[pushlevel] -= deg*t;
    nowx -= sin(stack_rot[pushlevel])*step*t/2;
    nowy -= cos(stack_rot[pushlevel])*step*t/2;
    //translate(step/2-sin((deg))*step*(1.0-t)/2,step/2-cos(deg*t)*step/2);
    //rotate(-(deg)*t); stack_rot[pushlevel] -= (deg)*t;
    //nowx += cos(stack_rot[pushlevel])*step*t - sin(stack_rot[pushlevel])*step*t;;
    //nowy += sin(stack_rot[pushlevel])*step*t + cos(stack_rot[pushlevel])*step*t;;
    if(f_counting) { f_draw++; f_arc++; f_rot--; f_rotmax = max(f_rotmax,abs(f_rot)); }
    check_overflow(); 
    }
  }
  
  void do_C(float t) {
    if(t!=0) {
    ellipse(step*t/2,0,step*t,step*t);
    translate(step*t,0);
    nowx += cos(stack_rot[pushlevel])*step*t;
    nowy += sin(stack_rot[pushlevel])*step*t;
    maxleft = (maxleft<nowx-step*t*0.5) ? maxleft : int(nowx-step*t*0.5);
    maxright = (maxright>nowx+step*t*0.5) ? maxright : int(nowx+step*t*0.5);
    maxtop = (maxtop>nowy+step*t*0.5) ? maxtop : int(nowy+step*t*0.5);
    maxbottom = (maxbottom<nowy-step*t*0.5) ? maxbottom : int(nowy-step*t*0.5);
    if(f_counting) { f_circle++; f_draw++; }
    }
  }
  
  void do_push() {
    if(pushlevel+1<maxpush) {
      pushMatrix();
      stack_x[pushlevel] = nowx; stack_y[pushlevel] = nowy;
      pushlevel++;
      stack_step[pushlevel] = stack_step[pushlevel-1];
      stack_rot[pushlevel] = stack_rot[pushlevel-1];
      if(f_counting) { f_push=max(f_push,pushlevel); f_not++; }
    }
  }
  
  void do_pop() {
    if(pushlevel-1>=0) {
      popMatrix();
      pushlevel--;
      step = stack_step[pushlevel];
      nowx = stack_x[pushlevel]; nowy = stack_y[pushlevel];
    }
  }
  
  void do_plus(float t) {
    step = ((step + (initstep/3) * boxscaler)*t + step*(1.0-t));
    //step += initstep/3 * boxscaler;
    stack_step[pushlevel] = step;
    if(f_counting) f_not++;
  }
  
  void do_minus(float t) {
    step = ((step - (initstep/3) * boxscaler)*t + step*(1.0-t));
    //step -= initstep/3 * boxscaler;
    if(step<(initstep/3)*boxscaler) step = (initstep/3) * boxscaler;
    stack_step[pushlevel] = step;
     if(f_counting) f_not++;
  }

}