/* ga-morphism.js  gm.js (agfact)

   algorithmes génétiques appliqués à la factorisation des mots
   Problème inverse de l'automate fini et algorithmes génétiques 
   
   page http: concernée
   perso.wanadoo.fr/jean-paul.davalan/mots/agfact/index.html
   
   Jean-Paul Davalan 22 mai 2003 <jpdvl@wanadoo.fr>

   Utiliser astyle (Artistic Style) pour remettre en forme le texte
   astyle gm.js
 */


var MaxLCh=80;      // longueur maxi du mot à analyser
var MaxML=8;         // l maxi des images des lettres
var nmax=100;         // nb maxi d'itérations
var garde=0.4;
var pmute=0.3;
var psupp=0.01;
var pcut=0.05;
var pdbl=0.05;
var padd=0.01;
var nbpop = 10;
var pop;

function nulf(a,n){
  document.frm.tin.value=a;
  document.frm.n.value=n;
}

function nulf2(x, y,n){
  document.frm2.alp.value=x;
  document.frm2.txt.value=y;
  document.frm.n.value=n;
  eff();
}

function clr() {
  document.frm2.alp.value="";
  document.frm2.txt.value="";
}
// --------- EFF ---------
// 

function initie() {
  var s = document.frm.tin.value;
  
  document.frm.tpop.value = nbpop;
  document.frm.tmorph.value = MaxML;
  document.frm.tmot.value = MaxLCh;
  
  s = s.replace(/^\s+/,"");
  if(s.substr(0,9)=="configure") {
    configure(s);
  } else {
  if(pop != void(0)) 
    delete pop;
  pop = new population(s, nbpop);
  var st = "Nouvelle population créée\n"
  for(var i=0;i< pop.alphabet.length;i++)
    st = st + pop.alphabet[i]+" ";
  st = st +"\n";
  document.frm.ar.value = st;
  }
}

function conftaille() {
  nbpop = parseInt(document.frm.tpop.value);
  MaxML = parseInt(document.frm.tmorph.value);
  MaxLCh = parseInt(document.frm.tmot.value);  
  if(pop != void(0)) delete pop;
}

function reconf(a,b,c) {
  nbpop =  parseInt(a); 
  document.frm.tpop.value = nbpop;
  MaxML = parseInt(b);
  document.frm.tmorph.value = b;
  MaxLCh = parseInt(c);
  document.frm.tmot.value = MaxLCh;
  if(pop != void(0)) delete pop;
}

function configure(s) {
  var i, a = new Array(), t = new Array(), st = s.substr(9,s.length-9);
   help();
  st= st.replace(/^\s+/,"");
  a = st.split(/[;]\s*/);
  for(i=0; i < a.length;i++) {
    a[i]=a[i].replace(/^\s+/,"");
    a[i]=a[i].replace(/\s+$/,"");
    t=a[i].split(/\s+/);
    u = parseInt(t[1]);
    v = parseFloat(t[1]);
    var s1 = t[0];
    switch(t[0]) {
      case 'pop' : ;
      case 'population' :  nbpop = u; break;
      case 'mot' : ;
      case 'word' :  MaxLCh = u; break;
      case 'morph' : ;
      case 'morphism' : MaxML = u; break;
      case 'garde' : ;
      case 'keep' : garde = v; break;
      case 'pmute' : ;
      case 'mute' : pmute = v; break;
      case 'add' : ;
      case 'padd' : padd = v; break;
      case 'supp': ;
      case 'psupp': psupp = v; break;
      case 'cut' : ;
      case 'pcut' : pcut = v; break;
      case 'dbl' :;
      case 'pdbl' : pdbl = v; break;
      default : break;
    }
  }
}

function help() {
  var s = "configure param valeur; param valeur; ...\n";
  s = s + "param : population  "+nbpop+"\n";
  s = s + "        word        "+MaxLCh+"\n";
  s = s + "        morphism    "+MaxML+"\n";
  s = s + "        keep        "+garde+"\n";
  s = s + "pmute "+pmute+", padd "+padd+",\n";
  s = s + "psupp "+psupp+", pcut "+pcut+",\n";
  s = s + "pdbl " +pdbl+"\n";
  s = s + "avec des probabilités 0<= p <= 1\n";
  document.frm.ar.value=s;
}

// --------- EFF ---------
// construit une chaîne à partir du morphisme

function eff() {
  var alpha, nlettres;
  var a=document.frm2.alp.value;
  a = a.replace(/^\s+/,"");
  a = a.replace(/\s+$/,"");
  alpha=a.split(/\s+/);
  nlettres = alpha.length;
  var s0 = document.frm2.txt.value;
  var arr=new Array();
  arr = s0.split(/\s/);
  var s=alpha[0];
  for(var n=0;s.length<MaxLCh && n<nmax;n++) {
    var str="";
    for(var j=0;j<s.length;j++) {
      var lt=s.charAt(j);
      for(var i=0;i<nlettres && lt != alpha[i];i++) ;
      str = str + ""+ arr[i];
    }
    s = str;
  }
 document.frm.tmot.value=s.length;
 MaxLCh=s.length;
 document.frm.tin.value=s;
}

// ======== MORPH ========
// crée aleatoirement des morphismes
// arguments :
//    alpha : tableau de lettres alpha[i]
//    g     : la génération (date de création)
//    ch    : la chaîne
// 
// this.m   : this.m[i]
// this.g   : génération de création
// this.f   : adaptation
//
// img(alpha, ch)
// mulimg(alpha, ch)
// fitness(alpha, ch)
//

function morph(alpha, g, ch) {

//  function malea(alpha, g, ch) {
    var  n, u, i, j, s = new Array(), st;
    for(i=0;i<alpha.length;i++) {
      st = "";
      n = 1 + Math.floor(MaxML* Math.random());      
      for(j=0;j<n;j++) {
        u = Math.floor(alpha.length*Math.random());
        v = alpha[u];
        st = st+"" + v;
      }
      s[i] = st;
    }
    this.m = s; 
    this.g=g; 
    this.f=-1;
//  }
//  this.malea = malea;
  

  // --------- IMG ---------
  // applique le morphisme sur s

  function img(alpha, s) {
    var s2="", i, l=s.length;
    for(i=0;i<l;i++) {
      c=s.charAt(i);
      // cherche la lettre dans l'alphabet
      for(j=0;j< alpha.length && alpha[j] != c ;j++) ;
      u = this.m[j];
      s2 = s2+""+u;
    }
    return s2;
  }
  this.img = img;

  // --------- MULIMG ---------
  // applique plusieurs fois le morphisme sur s

  function mulimg(alpha, s) {
    var s2 = s;
    for(n=0;n<MaxLCh && s2.length<MaxLCh;n++) {
      s2 = this.img(alpha, s2);
    }
    return s2;
  }
  this.mulimg = mulimg;

  // --------- FITNESS ---------

  function fitness(alpha, ch) {
    var c, pr=1, f, i, u, l = ch.length, s = ch.charAt(0);
    if(l>MaxLCh) l = MaxLCh;
    f = l;
    for(i=0; i < alpha.length; i++) {
      if(this.m[i].length > MaxML) {
        return 0;
      }
      pr = pr * (1+this.m[i].length);
    }
    s = this.mulimg(alpha, s);
    var s1 = this.img(alpha,s);
    u = s.length;
    if(f>u) f = u;

    if(document.frm.rd[0].checked==true) {
      for(i=0; i<f && i < u && i < l; i++) {
        c = s.charAt(i);
        if( c != s1.charAt(i) || c != ch.charAt(i))  
          f = i;
      }
    } else {
      f = 0;
      for(i=0; i < u && i < l; i++) {
        c = s.charAt(i);
        if(c== s1.charAt(i) && c == ch.charAt(i))
          f++;
      }
    }
    if(f > 2)
      return (f+2/pr);
    else
      return f;
  }
  this.fitness = fitness;
  
  this.f = this.fitness(alpha, ch);
}

// chaîne fille de deux ch a et b 
function mix2(a, b) {
    var u=a, v=b, w, st="", l, i,ul,vl;
    if(v.length < u.length) {
      w=u; u=v; v=w;
    } 
    vl = v.length; 
    ul = u.length; 
    for(i=0; i<ul; i++) {
      if(Math.random()<0.5) 
        st = st+""+u.charAt(i);
      else st = st+""+v.charAt(i);
    }
    l = ul + Math.floor((vl-ul+1)*Math.random());
    for(i=ul;i<l;i++) st = st+"" + v.charAt(i); 
    if(st.length==0) st = a;
    return st;
}

function mix3(a, b) {
    var u, v, st="",k,r;
    if(Math.random()<0.5) {
      u=a; v=b;
    }else {
      u=b;v=a;
    }
    k=Math.floor((u.length+1)*Math.random());
    st = u.substr(0,k);
    r = v.length-k;
    if(r>0) { 
      r = Math.floor(Math.random()*(r+1));
      st = st + v.substr(k,r);
    }
    if(st.length==0) st = u.charAt(0);
    return st;
}


function mix(a, b) {
    var u, v, st="",k,r,l;
    
    if(Math.random()<0.5) {
      u=a; v=b;
    }else {
      u=b;v=a;
    }
    l=Math.ceil((u.length+v.length)/2+3);
    r = Math.floor((u.length+1)*Math.random());
    st = u.substr(0,r);
    r = Math.floor((v.length+1)*Math.random());
    st = st + v.substr(r,v.length-r);
    if(st.length>l)
     st = st.substr(0,l);
    if(st.length==0) st = u.charAt(0);
    return st;
}


//   POPULATION    
// crée aléatoirement une population 
//
//   p   tableau population de morphismes
//       p[i] est un morphisme
//           p[i].m tableau
//           p[i].g (date de naissance)
//           p[i].f fitness
//   n   effectif
//   g   numéro de génération
//   r   tableau  r[0] = k : p[k] le meilleur
//   pmute
//
//   range()
//   gensuivante()
//   mute(s)
//

function population(s, n) {
  var i;
//  alert("population "+ s);
  var pop = new Array();
  var rang = new Array();

  this.fc=0;
  this.fcp=0;
  this.s = s;       // chaîne
  this.n = n;       // effectif
  this.g = 0;       // generation
  this.pmute = pmute;
  // les meilleurs auront le plus petit rang
  
  // ---------- GET_ALPHABET ----------
  
  var u, v, k, s1 = this.s, s2, alp=new Array();
  
  for(k=0; s1.length>0; k++) {
    u = s1.charAt(0); // 1e lettre de l'alphabet = 1e let. de s 
    alp[k] = u;
    s2 = "";
    for(i=0;i<s1.length;i++) {
      v = s1.charAt(i)
      if( v != u) { // on ne recopie que les lettres
        s2 = s2 + v;   // non encore dans l'alphabet
      }
    }
    s1 = s2;
  }              // jusqu'à épuisement de la chaîne
  this.alphabet = alp;

  ngen=0;
  for(i=0; i < n; i++) {
    rang[i] = i;
    pop[i] = new morph(this.alphabet, 0, this.s);
    pop[i].f = pop[i].fitness(this.alphabet, this.s);
    this.fc += 1;
    if(pop[i].f>MaxLCh && this.fcp == 0)this.fcp = this.fc;
  }

  this.p = pop;     // population de morphismes
  this.r = rang;    // pointe sur les morphismes

  // ---------- RANGE ----------
  
  function range() {
    for(var i=0;i<this.n-1;i++) {
      for(var j=i+1; j<this.n;j++) {
        var u = this.fcomp(i,j);
        if(this.fcomp(i,j)<0) {
          var a = this.r[i];
          this.r[i] = this.r[j];
          this.r[j]=a;
        }
      }
    }
  }
  this.range = range;
  
//  this.range();
  range();

  function fcalc() {
    if(this.p == void(0)) return;
    for(i=0; i < this.n; i++) {
      rang[i] = i;
      pop[i].f = pop[i].fitness(this.alphabet, this.s);
      this.fc += 1;
      if(pop[i].f>MaxLCh && this.fcp == 0)this.fcp = this.fc;
    }
    this.range();
  }
  this.fcalc = fcalc;

 
  // ---------- FCOMP ----------
  //  compare les morphismes de rangs m et k
  //  m et k sont les rangs (dans this.r[])
  //  >0 si m meilleur que k

  function fcomp(m, k) {
    return (this.p[this.r[m]].f - this.p[this.r[k]].f);
  }
  this.fcomp = fcomp;


  // ---------- FILS ----------
  // remplace le morphisme de rang l par un fils de m et de k
  // s est la chaîne, g la génération

  function fils(l, m, k) {
    var a;
    for(var i=0; i< this.alphabet.length; i++) {
      a = mix(this.p[this.r[m]].m[i], this.p[this.r[k]].m[i]);
      a = this.mute(a);
      this.p[this.r[l]].m[i] = a;
    }
    this.p[this.r[l]].g = this.g;
    this.p[this.r[l]].f = this.p[this.r[l]].fitness(this.alphabet, this.s);
    this.fc += 1;
    if(this.p[this.r[l]].f>MaxLCh && this.fcp == 0)this.fcp = this.fc;
  }
  this.fils = fils;

  // ---------- GENSUIVANTE ----------
  function gensuivante() {
    var i, u, v, nm = Math.floor(nbpop*garde);
    this.g++;
    for(i = nbpop-1; i>=nm; i--) {
      u = Math.floor(i*Math.random());
      do {
        v = Math.floor(i*Math.random());
      } while (u==v && i>1);
      this.fils(i, u, v);
    }   
    this.range();
  }
  this.gensuivante = gensuivante;

  function multigen(k) {
    for(var i=0;i<k;i++) {
      this.gensuivante();
      this.affiche();
    }
  }
  this.multigen = multigen;

  function nonstop() {
    do {
      this.gensuivante();
      this.affiche();
    } while((this.g%100 != 0) && this.fcp<=0);
  }
  this.nonstop = nonstop;

  function affiche() { 
    var i,j,st = "Générations : "+this.g+" calculs f : "+this.fc+((this.fcp>0)?" ("+this.fcp+")":"")+" Alphabet :";
    for(j=0;j<this.alphabet.length;j++) 
      st = st+" "+this.alphabet[j];
    st = st + "\n" + this.s + "\n-----------------------------\n";
    for(i=0;i<10;i++) {
      for(j=0;j<this.alphabet.length;j++) {
        st = st + this.alphabet[j]+"->"+this.p[this.r[i]].m[j]+ " ";
      }
      st = st +  this.p[this.r[i]].f;
      if(this.p[this.r[i]].f> MaxLCh)st = st + " solution";
      st = st +"\n";
      st = st +this.p[this.r[i]].mulimg(this.alphabet,this.alphabet[0]) + "\n";
    }
    document.frm.ar.value = st
  }
  this.affiche = affiche;

  // ---------- MUTE ----------
  // p probabilé de muter,  a alphabet,  s chaîne
  //
  // ATTENTION
  // plus que les autres sans doute, cette fonction, est en cours 
  // d'expérimentation, d'où les valeurs comme 0.05 0.1 ...
  // 
  // 

  function mute1(s) {
    var st, r = Math.random();
    if(r>this.pmute) return s;
    r = Math.random();
    var k = Math.floor(s.length*Math.random());
    var c= this.alphabet[Math.floor(this.alphabet.length*Math.random())];
    var d = this.alphabet[Math.floor(this.alphabet.length*Math.random())];
    if(c==s.charAt(k)) c="";
    var st = "";
     
    var l = s.length;
    if( Math.random()<0.05) l = 1+Math.floor(s.length*Math.random());   
    for(i=0;i<s.length;i++) {
      if(i==k) {
        st = st+c;
        if(r<0.1) st = st+d;
      } else st = st+s.charAt(i);
     
    }
    if(st.length==0) st = st + d;
    r = Math.random();
    if(r<0.1) {
      st = st + this.alphabet[Math.floor(this.alphabet.length*Math.random())];
    }
    return st;
  }

  function mute(s) {
    var i, c, d, k, st="", l;
    if(Math.random()>this.pmute) return s;
    k = Math.floor(s.length*Math.random());
    do {
      c= this.alphabet[Math.floor(this.alphabet.length*Math.random())];
    } while (c==s.charAt(k) && this.alphabet.length>1);
    d = this.alphabet[Math.floor(this.alphabet.length*Math.random())];
    l = s.length;
    if( Math.random()<0.05) l = 1+Math.floor(s.length*Math.random());

    for(i=0;i<l;i++) {
      if(i==k) {
        if(Math.random() > psupp) st = st+c;
        if(Math.random() < pdbl) st = st+d;
      } else st = st+s.charAt(i);
    }
    if(Math.random() < padd) {
      st = st + this.alphabet[Math.floor(this.alphabet.length*Math.random())];
    }
    if(st.length==0) st = st + d;
    return st;
  }
  this.mute = mute;
  
}
/*
var fibo = new Array(0,1,1,2,3,5,8);
function fib(n) {
  if(fibo[n] == void(0)) {
    fibo[n]=fib(n-1)+fib(n-2);
    
  }
  return fibo[n];
}
*/
function chaine() {
  var i, j, u, x, n, s="";
  n = document.frm.tmot.value;
  if(n<80) n = 80;
  document.frm.tmot.value=n;
  with(Math)
    x=eval(document.frm3.r.value);
  if(x==void(0) || x<=0) return
  for(i=1;s.length<n;i++){
    u = Math.floor(i/x)-Math.floor((i-1)/x);
//    u = Math.floor(fib(i)/x)-Math.floor(fib(i-1)/x);
// u = Math.floor((i/x)*(i/x))-Math.floor(((i-1)/x)*((i-1)/x));
    for(j=0;j<u;j++)
      s=s+"0";
    s=s+"1";
  }

  reconf(10,10,n);
  nulf(s,10);
  initie();
  pop.multigen(document.frm.n.value);

}

function ntheta() {
  var i, s="";
  var k=parseInt(document.frm4.k.value);
  if(k<2) {
    k = 2;
    document.frm4.theta.value = k;
  }
  var x;
  with(Math)
    x = eval(document.frm4.theta.value);
  if(x==void(0) || x<=0) return
  var n = document.frm.tmot.value;
  if(n<80) n = 80;
  document.frm.tmot.value=n;
  for(i=1;s.length<n;i++){
    u =Math.floor(i*x)%k;
    s = s + ""+u;
  }
  reconf(10,10,n);
  nulf(s,10);
  initie();
  pop.multigen(document.frm.n.value);
}