/*******************************************************************************
 * GenRGenS v.1.0, Generation of Random Genomic Sequences                      *
 * Copyright (C) 2001  Alain Denise/Yann Ponty                                 *
 *                                                                             *
 * This program is free software; you can redistribute it and/or               *
 * modify it under the terms of the GNU General Public License                 *
 * as published by the Free Software Foundation; either version 2              *
 * of the License, or (at your option) any later version.                      *
 *                                                                             *
 * This program is distributed in the hope that it will be useful,             *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of              *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               *
 * GNU General Public License for more details.                                *
 *                                                                             *
 * You should have received a copy of the GNU General Public License           *
 * along with this program; if not, write to the Free Software                 *
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA. *
 *******************************************************************************/

package GenRGenS.markov;


import java.util.*;
import java.io.*;
import GenRGenS.*;
import GenRGenS.utility.*;
import GenRGenS.Generator;
import GenRGenS.GenerationException;
/**
 * Classe Markov
 *
 * Implémentant les méthodes de l'interface <code>Generator</code>
 * cette classe est destinée à la génération de séquences de Markov.
 * Les générations acceptées par cette classe sont soit la génération 
 * homogène, soit la génération inhomogène selon les valeurs choisies
 * pour Ordre et Phase dans le fichier de description.
 * @author Fr&eacute;d&eacute;ric Sarron
 * @author Yann Ponty
 * @version 1.0
 */

public class Markov
  implements Generator
{
  /** 
   * Tableau associant aux tokens (entiers) représentant des symboles les 
   * chaînes de caractères permettant le rendu.
   */
  String[] symboles;
  
  /**
   * Dimension 1 : Dernieres lettres generees
   * Dimension 2 : Phase de la lettre à générer
   * Dimension 3 : Lettre a generer
   *               Dernier element -> Somme des fréquences dans ce contexte sur 
   *               TOUTES les lettres à générer.
   *               Frequences cumulées des séquences :
   *               On tire souvent des nombres entre 0 et la somme de séquences
   *               pour un contexte donné. => On précalcule cette somme !
   * Contenu     : La fréquence du symbole dans le contexte donné, à la phase voulue
   *               et pour le caractère donné.
   * Ex : Soit tok une fonction qui à un symbole renvoie sont token(entier),
   *      et N le nombre de symboles :
   *   La fréquence de 'a' dans le contexte 'acg' et en phase 1 est 
   *        f = frequencies[tok('a') + tok('c')*N + tok('g')*N*N][1][tok('a')]
   *   La somme de toutes les fréquences dans le contexte 'atg' en phase 2 est 
   *        f = frequencies[tok('a') + tok('t')*N + tok('g')*N*N][2][N]
   */
  double[][][] frequencies;
  
  /** Ordre de Markov */
  int order = -1;
  
  /** Nombre de phases */
  int nbPhase = 1;

  /** 
   * true -> Chaque symbole doit etre separe des autres par au moins un espace 
   *         dans une sequence. En particulier dans la liste des frequences du 
   *         fichier. Un espace est ajouté dans l'affichage génération entre 2 symboles.
   * false-> Les symboles sont fournis "concaténés" et sont représentés par des lettres.
   *         La séquence générée est un mot (pas d'espace ...)
   */
  boolean words=true;

  /**
   * Type de génération :
   *   - Si exact=true, la présence d'impasse dans le fichier descripteur
   *     est proscrite(levée d'une exception ...)
   *     Les mots engendrés auront donc comme longueur EXACTEMENT celle requise
   *     par l'utilisateur.
   *   - Si exact=false, on est en "génération libre bornée", la présence
   *     d'impasse est signalée à l'utilisateur mais pas interdite.
   *     Lors de la génération, la rencontre d'une impasse provoque l'arrèt
   *     de la génération => les mots engendrés seront de tailles inférieures
   *     ou égales à la longueur spécifiée.
   */
   boolean _exact=true;

  /** 
   * Fréquences cumulées :
   * Somme progressive des fréquences des différentes
   * séquences proposées en début de chaîne afin de 
   * choisir une chaîne "début" plus efficacement.
   */
  double[] startSequencesCumulatedFrequences;

  /** 
   * Séquences de debut : 
   *   Dimension 1 : Le numéro de la séquence Start
   *   Dimension 2 : Le numéro du symbole voulu dans la séquence
   *   Contenu     : Un symbole.
   * Permet d'accéder au contenu des séquences de départ.
   */
  int[][] startSequences;

  /** 
   * Le générateur aléatoire utilisé au sein de cette instance 
   */
  Random _rdm = new Random(System.currentTimeMillis());

  /*==================================================================
                             CONSTRUCTEURS
   ================================================================*/

  /**
   * Construit une instance de <code>Markov</code> vide (Sans aucun intérêt + Gare 
   au <code>NullPointerException</code> !)
   */
  
  public Markov()
  { super(); };

  /**
   * Construit une instance de <code>Markov</code> à partir d'une chaîne de caractères 
   * décrivant un fichier de description Markovien.
   * @param s Un fichier de description markovien.
   */
  public Markov(String s)
    throws IOException,
        BadMarkovException
  {
    this(new StringReader(s));
  };

  /**
   * Construit une instance de <code>Markov</code> à partir d'un descripteur de fichier
   * pointant vers un fichier de description Markovien.
   * @param s Un descripteur de fichier pointant vers un fichier de description.
   */
  public Markov(File fd)
    throws IOException,
        BadMarkovException
  {
    this(new FileReader(fd));
  };

  /**
   * Construit une instance de <code>Markov</code> à partir d'un lecteur générique
   * dont le contenu est un fichier de description Markovien.
   * @param s Un lecteur générique dont le contenu est un fichier de description Markovien
   */
  public Markov(Reader r)
    throws IOException,
        BadMarkovException
  {
        ParseMarkov p = null;
        GenRGenSScanner s = new GenRGenSScanner(r);
        p = new ParseMarkov(s);
        try
        {
          if (GenRGenS.verbose)
          { GenRGenS.err.println("Parsing description file ..."); }
          p.parse();
        }
        catch(Exception e)
        {
          /*
            Il s'agit d'une exception due à une erreur syntaxique.
            => On ne traite pas car le booléen isParseError a été mis à true.
          */
          //GenRGenS.err.println(e);
        }
        /* 
          Si une erreur syntaxique a eu lieu, alors isParseError() == true.
          On interrompt la construction de l'objet.
        */
        if (p.isParseError())
        {
          throw(new BadMarkovException("Invalid description file !"));
        }
        /* 
          S'il y a des impasses dans le fichier et qu'une taille exacte est 
          demandée, alors on interrompt la génération de l'objet.
        */
        if ((p.getNbDeadEnds()>0)&(MarkovianGenerationConfiguration.ExactSizeMarkovianGeneration == true))
        {
          throw(new BadMarkovException(p.getNbDeadEnds()+" deadend(s) reported, can't proceed to EXACT generation !"));
        }
        else
        {
          if ((GenRGenS.verbose) && (p.getNbDeadEnds()==0) && MarkovianGenerationConfiguration.ExactSizeMarkovianGeneration)
          { GenRGenS.err.print("No DeadEnds, "); }
          if (GenRGenS.verbose)
          { GenRGenS.err.println("Generator built successfully !"); }
        }
        // Une fois le parsing terminé on récupère les données.
        order = p.getOrder();
        nbPhase = p.getPhase();
        words = p.isWord();
        symboles = p.getSymbols();
        frequencies = p.getFrequencies();
        startSequences = p.getStartSequences();
        startSequencesCumulatedFrequences = p.getCumulatedStartFrequencies();
  };

  /**
   * Génere un mot de taille fournie en paramètre en respectant les caractéristiques
   * du fichier de description analysé au moment de la génération de l'instance.
   * @param size La taille voulue pour le mot à génerer (TailleRéelle <= size)
   * @return Une instance de la classe <code>StringBuffer</code> contenant les chaînes
   * de caractères dont la concaténation contient la séquence.
   */

  public StringBuffer generateRandomWord(int size) throws GenerationException
  {
    
    // On engendre un mot "tokenisé" ...
    Vector<Integer> motResultatToken = generateTokenizedRandomWord(size);
    
    // On le convertit en StringBuffer en utilisant les représentations "en chaînes" des tokens.
    StringBuffer motResultat = new StringBuffer(motResultatToken.size());
     for (int i=0; i<motResultatToken.size(); i++)
      {
        if (words)
        { motResultat.append(" "); }
        motResultat.append(symboles[motResultatToken.get(i)]);
      };
    return motResultat;
  };

  /**
   * Génere un mot de taille fournie en paramètre en respectant les caractéristiques
   * du fichier de description analysé au moment de la génération de l'instance.
   * @param size La taille voulue pour le mot à génerer (TailleRéelle <= size)
   * @return Une instance de la classe <code>Vector</code> contenant les entiers (classe <code>Integer</code>)
   * correspondant aux symboles de la séquence générée.
   */
  public Vector<Integer> generateTokenizedRandomWord(int size)
    throws GenerationException
  {
    Vector<Integer> motResultatToken;
    // Contient le contexte des Ordre derniers symboles générés.
    LinkedList<Integer> lastGenerated;
    
    // Si la taille voulue est inférieure à l'ordre, on ne peut rien générer.
    if (size<order)
    { throw new GenerationException("The size of a generated sequence can't be < order"); }
    
    // On construit le début de la chaîne
    if (startSequencesCumulatedFrequences.length>0)
    // Il y a des fréquences Start spécifiées ...
    { motResultatToken = generateRandomBeginningWithStartSequences(); }
    else
    // Il y a des fréquences Start spécifiées ...
    { motResultatToken = generateRandomBeginning(); }
    
    // Phase de début de génération en chaîne
    int phase = motResultatToken.size()%nbPhase;

    // On dispose désormais d'un nombre Ordre de lettres prêtes à être ajoutées au contexte
    lastGenerated = new LinkedList<Integer>();
    for (int i=motResultatToken.size() - order; i<motResultatToken.size(); i++)
    { 
      lastGenerated.addLast(motResultatToken.get(i));
    }
    
    int indexLastGenerated;
    double tirage;
    try
    {
      while (motResultatToken.size()<size)
      {
        
        // On calcule l'index correspondant au contexte (ordre derniers caractères)
        indexLastGenerated = indexOfSequence(lastGenerated);
        
        /* 
          On tire un nombre aléatoire entre 0 et la somme des fréquences pour les symboles 
          de la phase actuelle dans le contexte courant.
        */
        double mass = frequencies[indexLastGenerated][phase][symboles.length];
        
        if (mass==0)
        {
        	throw new IllegalArgumentException("Generation prematurely terminated!");
        }
        tirage = _rdm.nextDouble()*mass;
        
        int i = 0;
        while((tirage>=0) && (i<symboles.length))
        {
          // On retire les fréquences des symboles respectifs jusqu'à arriver à 0
          tirage -= frequencies[indexLastGenerated][phase][i];
          if (tirage<0)
          {
            // On ajoute le symbole, car c'est celui ci qui a été choisi par le tirage aléatoire.
            motResultatToken.add(new Integer(i));
            lastGenerated.addLast(new Integer(i));
            lastGenerated.removeFirst();
          }
          else
          { i++; }
        }
        // On actualise la phase.
        phase = (phase+1)%nbPhase;
      };
    }
    catch(IllegalArgumentException e)
    {
      if (!MarkovianGenerationConfiguration.ExactSizeMarkovianGeneration)
      {
        /* 
          On ne fait rien, et on considère la génération comme terminée car
          cette exception est lancée quand un état accessible ne mène à aucun 
          autre <=> Impasse de Markov tolérée dans ce cas.
        */
      }
      else
      {
        throw( new GenerationException("Internal Error 05 : please report this bug to the developping team ..."));
      }
    }
    return motResultatToken;
  };

  /**
   * Fonction de conversion de contexte markovien en "contexte".
   * @param lasts Les "ordre" derniers caractères générés.
   * @return L'index entier de la séquence.
   */
  private int indexOfSequence(LinkedList lasts)
  {
    int index=0;
    int loginf=1;
    for (int i=lasts.size()-1; i>=0; i--)
      {
        index+=loginf*((Integer) lasts.get(i)).intValue();
        loginf*=symboles.length;
      };
    return index;
  };

  /** 
   * Choix d'une séquence Start parmis celles proposées suivant les fréquences de ces séquences.
   * @return Une instance de la classe Vector dans laquelle est stockée la séquence de départ choisie.
   */
  private Vector<Integer> generateRandomBeginningWithStartSequences()
  {
    // On tire un nombre entre 0 et la somme des fréquences des séquences Start.
    double tirage = _rdm.nextDouble()*startSequencesCumulatedFrequences[startSequencesCumulatedFrequences.length-1];
    int indexStartSequence;
    
    // On en déduit un index de séquence.
    for (indexStartSequence=0;
       indexStartSequence<startSequencesCumulatedFrequences.length;
       indexStartSequence++)
      if (tirage<startSequencesCumulatedFrequences[indexStartSequence])
        break;
    Vector temp = new Vector();

    // On construit cette séquence à partir de l'index.
    temp.add(new Integer(startSequences[indexStartSequence][0]));
    for (int i=1; i<startSequences[indexStartSequence].length; i++)
      temp.add(new Integer(startSequences[indexStartSequence][i]));
    return(temp);
  };

  /** 
   * Choix de "ordre" symboles quand aucune séquence de départ n'est specifiée 
   * dans le fichier de description.
   * @return Une instance de la classe Vector dans laquelle est stockée la séquence de départ choisie.
   * @throws GenerationException Si toutes les fréqences sont égales à 0.
   */
  private Vector<Integer> generateRandomBeginning() throws GenerationException
  {
    // Sommation de toutes les fréquences de phase 0
    double sommeFreq=0;
    double tirage=0;
    for (int i=0; i<frequencies.length; i++)
      for (int j=0; j<symboles.length; j++)
        sommeFreq+=frequencies[i][order%nbPhase][j];

    try
    {
      // Calcul d'un nombre aléatoire compris entre 0 et la somme des fréquences de phase 0
      tirage = _rdm.nextDouble()*sommeFreq;
    }
    catch(IllegalArgumentException e)
    {
      throw( new GenerationException("All frequencies are equal to 0 ..."+this.toString()));
    }

    // Recherche de la sequence choisie
    int[] decomposition=new int[0];
    boolean fini = false;
    int sequence_resultat = -1;
    for (int i=0; (i<frequencies.length) && (!fini); i++)
    {
     for (int j=0; (j<symboles.length) && (!fini); j++)
     {
    	 tirage -= frequencies[i][order%nbPhase][j];
      if (tirage<0.)
      {
       fini = true;
       sequence_resultat = i;
      };
     }
    };
    // Décomposition de la séquence choisie sur la base symbole^ordre.
    decomposition = projectSequenceIndex(sequence_resultat);
    Vector temp=new Vector();
    for (int i=0; i<decomposition.length; i++)
      temp.add(new Integer(decomposition[i]));
    return(temp);
  };

  /**
   * Fonction de débuggage renvoyant la chaîne représentant un contexte décrit 
   * par un entier.
   * @param index Le numéro du contexte.
   * @return Une chaîn de cractère représentant ce contexte.
   */
  private String sequenceOfIndex(int index)
  {
    
    int num = 0;
    String value = "";
    String[] lexique = symboles;
    while(index != 0)
    {
      value = lexique[index%lexique.length] + " " +value;
      num++;
      index = index / lexique.length;
    }
    while(num != order)
    { 
      value = lexique[0] + " " + value; 
      num++;
    }
    return value;
  }

  /** 
   * Fonction de projection du numero de sequence sur la base du 
   * nombre de symboles.
   * @param sequenceIndex Un nombre symbolisant une séquence de taille l'ordre de markov.
   */
  private int[] projectSequenceIndex(int sequenceIndex)
  {
    int[] resultat = new int[order];
    int index;
    for(index = order-1; index>=0;index --)
    {
     resultat[index] = sequenceIndex % symboles.length;
     sequenceIndex = sequenceIndex / symboles.length;
    }
    return resultat;
  };


/**************************************************************************
      Implementation des autres méthodes de l'interface Generator
**************************************************************************/


	/** 
	 * Renvoie le nom du symbole d'index donné en argument.
	 * @return le nom du symbole d'index donné en argument.
	 */
  public String symbolName(int index) throws IllegalArgumentException
  {
    if (index >= symboles.length)
    {throw new IllegalArgumentException("String symbolName(int) : index("+index+") out of index range [0.."+(symboles.length-1)+"]");}
    
    return symboles[index];
  };

	/** 
	 * Renvoie le type de symboles choisi pour la génération.
	 * @return true ssi l'espacement est WORDS, false sinon (LETTERS)
	 */
  public boolean isWORDS()
  { return words; };

	/** 
	 * Renvoie la chaine de caractere correspondant a la liste
	 * d'indexs en entree, traduction des indexs en noms de symboles
	 * @param sequence La séquence d'indexs engendrée par une génération
	 * @param spacing true si les représentations graphiques des symboles
	 * doivent être séparés d'un " ", false sinon.
	 */
  public StringBuffer litteralSequence(List sequence, boolean spacing)
  {
    StringBuffer result = new StringBuffer();
    String spacingChar = spacing ? " " : "";
    for (int symbolIndex=0; symbolIndex<sequence.size(); symbolIndex++)
      result.append
        (symboles
         [ ((Integer) sequence.get(symbolIndex)).intValue() ]+
         spacingChar);
    return result;
  };

	/**
	 * Renvoie le nombre de symboles terminaux
	 * suivant la generation.
	 * @return Les nombre de symboles
	 */
  public int numberOfterminalsSymbols()
  {
    return symboles.length;
  };

	/**
	 * Renvoie l'index du symbole dont le nom est donne en argument.
	 * @param name Le nom d'un symbole.
	 * @return L'index du symbole si <code>name</code> représente 
	 * bien un symbole
	 */
  public int symbolIndex(String name)
    throws IllegalArgumentException
  {
    for (int i=0; i<symboles.length; i++)
      if (name.equals(symboles[i]))
        return i;
    throw new IllegalArgumentException("int symbolIndex(String) : "+name+" is not a symbol");
  };

	/** 
	 * Renvoie true ssi la chaine de caracteres donnee
	 * est bien le nom d'un des symbols terminaux
	 * @param name La représentation littérale d'un symbole
	 * @return True si <code>name</code> est un terminal,
	 * false sinon.
	 */
  public boolean isTerminalSymbol(String name)
  {
    for (int i=0; i<symboles.length; i++)
      if (name.equals(symboles[i]))
        return true;
    return false;
  };



   /*==================================================================
                             UTILITAIRES
   ================================================================*/

  /**
   * Elèves un nombre donné à une puissance positive donnée.
   * @param a L'entier à élever à une puissance.
   * @param b La puissance demandée.
   */
  private static int pow(int a, int b)
  {
    if (b==0)
      return 1;
    else
      if (b%2==0)
        return(pow(a*a,b/2));
      else
        return(a*pow(a*a,b/2));
  };

  /**
   * Renvoie une représentation littérale de cet objet.
   * @return Une représentation littérale de cet objet.
   */
  public String toString()
  {
    String temp =
      "Order : "+order+"\n"+
      "Phase : "+nbPhase+"\n"+
      "Symbols : "+symboles.length+"\n  ";
    for (int i=0;i<symboles.length;i++)
      temp+=" "+symboles[i];
    if (startSequences.length>0)
      {
        temp+="\nStart : \n";
        for (int i=0; i<startSequences.length; i++)
          {
            for (int j=0; j<startSequences[i].length; j++)
              temp+=(words?" ":"")+symboles[startSequences[i][j]];
            temp+=" : "+startSequencesCumulatedFrequences[i]+"\n";
          };
      };
    temp+="\nFrequencies :\n  ";
    for(int i=0;i<frequencies.length;i++)
      for(int j=0;j<frequencies[i].length;j++)
      {
        int[] ctxt = projectSequenceIndex(i);
        for(int k=0;k<ctxt.length;k++)
        {
            temp+=symboles[ctxt[k]]+" ";
        }
        for(int k=0;k<frequencies[i][j].length;k++)
        {
            temp+=frequencies[i][j][k]+" ";
        }
      }
    return temp;
  };


  /**
   * Renvoie une représentation littérale de cet objet.
   * @return Une représentation littérale de cet objet.
   */
  public void display()
  {
      GenRGenS.err.print(
      "Order : "+order+"\n"+
      "Phase : "+nbPhase+"\n"+
      "Symbols : "+symboles.length+"\n  ");
    for (int i=0;i<symboles.length;i++)
        GenRGenS.err.print(" "+symboles[i]);
    if (startSequences.length>0)
      {
          GenRGenS.err.print("\nStart : \n");
        for (int i=0; i<startSequences.length; i++)
          {
            for (int j=0; j<startSequences[i].length; j++)
                GenRGenS.err.print((words?" ":"")+symboles[startSequences[i][j]]);
            GenRGenS.err.print(" : "+startSequencesCumulatedFrequences[i]+"\n");
          };
      };
    GenRGenS.err.print("\nFrequencies :\n  ");
    for(int i=0;i<frequencies.length;i++)
      for(int j=0;j<symboles.length;j++)
      {
            GenRGenS.err.print(sequenceOfIndex(i));
            GenRGenS.err.print(symboles[j]+" "); 
        for(int k=0;k<nbPhase;k++)
        {
            GenRGenS.err.print(frequencies[i][k][j]+" ");
        }
        GenRGenS.err.print("\n  ");
      }
  };











/************************** pour tests ***********************************/
  private static void main(String[] arg)
  {
    if (arg.length<2)
      {
        GenRGenS.out.println
          ("usage : \n"+
           "\tjava HeterogeneousMarkov <size> <number of generation>");
        System.exit(1);
      };

    int size = (Integer.valueOf(arg[0])).intValue(),
     howMany = (Integer.valueOf(arg[1])).intValue();

    Markov hm;
    String Path = "tests/markov/";
    File[] directoryListing =
      (new File(Path).listFiles
       (new FileExtensionFilter("ggd")));
    PrintStream testResult;

    for (int numFichier=0;
       numFichier<directoryListing.length;
       numFichier++)
      {
        int k=0;
        hm = new Markov();
        // = null : seule solution trouvée au prb du
        // try/catch et "may not have been init."
        testResult = null;
        try
          {
            try
            {
              while(true)
              {
                FileReader f = new FileReader(Path+"/results/"+directoryListing[numFichier].getName()+"."+k+".results");
                k++;
              }
            }
            catch(FileNotFoundException e3)
            {}
            testResult = new PrintStream
            (new FileOutputStream(Path+"/results/"+directoryListing[numFichier].getName()+"."+k+".results"));
          }
        catch (IOException e)
          {
            GenRGenS.err.println("Damned ! "+e.toString());
          }
        if (testResult!=null)
          {
            try
              {
                System.setErr(testResult);
                testResult.println
                  ("=*=*= Result for file "+
                   directoryListing[numFichier]+" =*=*=");
                hm = new Markov
                  ((new FileReader
                   (directoryListing[numFichier].getAbsolutePath())));
                testResult.println
                  ("Stored Markov :\n"
                   +hm.toString());
                testResult.println("size "+arg[0]+" :");
                for (int i=0; i<howMany; i++)
                  testResult.println
                    ("*"+(i+1)+"*"+
                     hm.generateRandomWord(size));
                testResult.println("\n\n\n\n");
                testResult.close();
                GenRGenS.out.println
                  ("wrote "+
                   directoryListing[numFichier].getName()+"."+k+".result");

              }
            catch (IOException e)
              { 
                testResult.println ("Damned ! "+e.toString()); 
              }
            catch (BadMarkovException e)
              { testResult.println(e.toString());
              }
            catch (GenerationException e)
              { testResult.println(e.toString());
              };
          };

      };
    GenRGenS.out.println("All done !");
    System.exit(0);
  };

}
