package GenRGenS.markov;

import java_cup.runtime.*;
import java.util.*;
import GenRGenS.utility.*;
import GenRGenS.*;

/*********************************************************
 *  Analyse des fichiers de description markoviens       *
 *********************************************************/

/* Declaration de variables et methodes utilitaires ... */

parser code
{:

  private boolean _parseError = false;

  public boolean isParseError()
  { return _parseError; }

  public int getOrder()
  {
    return action_obj.getOrder();
  }

  public int getPhase()
  {
    return action_obj.getPhase();
  }

  public boolean isWord()
  {
    return action_obj.isWord();
  }

  public String[] getSymbols()
  {
    return action_obj.getSymbols();
  }

  public double[][][] getFrequencies()
  {
    return action_obj.getFrequencies();
  }

  public int[][] getStartSequences()
  {
    return action_obj.getStartSequences();
  }

  public double[] getCumulatedStartFrequencies()
  {
    return action_obj.getCumulatedStartFrequencies();
  }

  public int getNbDeadEnds()
  {
    return action_obj.getNbDeadEnds();
  }
  

  public void report_error(String message, Object info)
  {
    _parseError = true;
    if (info instanceof Symbol)
    {
      Symbol cur_token = (Symbol) info;
      int[] coord_left = ((GenRGenSScanner) getScanner()).getRelativePos(cur_token.left);
      int[] coord_right = ((GenRGenSScanner) getScanner()).getRelativePos(cur_token.right);
      if (coord_left[0] == coord_right[0])
      {
        GenRGenS.err.println("Syntax Error at line "+coord_right[0]+" chars "+ coord_left[1] +"-" + coord_right[1]);
      }
      else
      {
        GenRGenS.err.println("Syntax Error from line "+coord_left[0]+" char "+ coord_left[1] + " to line "+coord_right[0]+" char " + coord_right[1]);
      }
    }
    else
    {
      if (info instanceof String)
      {

        int[] coord_left = ((GenRGenSScanner) getScanner()).getRelativePos(cur_token.left);
        int[] coord_right = ((GenRGenSScanner) getScanner()).getRelativePos(cur_token.right);
        if (coord_left[0] == coord_right[0])
        {
          GenRGenS.err.println("At line "+coord_right[0]+" chars "+ coord_left[1] +"-" + coord_right[1] +" : " + message);
        }
        else
        {
          GenRGenS.err.println("From line "+coord_left[0]+" char "+ coord_left[1] + " to line "+coord_right[0]+" char " + coord_right[1] +" : " + message);
        }
      }
      else
      {
         GenRGenS.err.println(message);
      }
    }
  }
  public void report_fatal_error(String message, Object info) throws java.lang.Exception
  {
    _parseError = true;
    report_error(message,info);
    if (info instanceof Symbol)
    {
      Symbol cur_token = (Symbol) info;
      int[] coord_left = ((GenRGenSScanner) getScanner()).getRelativePos(cur_token.left);
      int[] coord_right = ((GenRGenSScanner) getScanner()).getRelativePos(cur_token.right);
      if (coord_left[0] == coord_right[0])
      {
        GenRGenS.err.println("Couldn't repair and continue parse at line "+coord_right[0]+".");
      }
      else
      {
        GenRGenS.err.println("Couldn't repair and continue parse at line "+coord_right[0]+".");
      }
    }
    else
    {
      Symbol current_token = cur_token;
      int[] coord_right = ((GenRGenSScanner) getScanner()).getRelativePos(current_token.right);
        GenRGenS.err.println("Couldn't repair and continue parse at line "+ coord_right[0]+".");
    }
    throw new Exception("Can't recover from previous error(s)");
  }

:}

action code
{:
  private int _order = -1;
  private int _phase = 1;
  private boolean _isWord = true;
  private int _nbDeadEnds = 0;
  private String[] symboles = new String[0];


  // Represents a list of  frequencies
  private double[][][] _frequencies = new double[0][0][0];

  // Represents a list of start sequences (each sequence is encoded by a list of numbers)
  private int[][] _startSequences = new int[0][0];
  // Represents a list of start sequences (each sequence is encoded by a list of numbers)
  private double[] _cumulatedStartFrequencies = new double[0];

  private Hashtable<String,Integer> _lexique = new Hashtable<String,Integer>(31);
  private int _nextTokenID = 0;

  // Start Sequences :
  private int _startSequencesSize = -1;
  private Vector<Vector<Integer> > _tmpStartSequences = new Vector<Vector<Integer> >();
  private Vector<Double> _tmpCumulatedStartFrequencies = new Vector<Double>();
  private double _partialStartFrequencySum = 0;


  public int getOrder()
  {
    return _order;
  }

  public int getPhase()
  {
    return _phase;
  }

  public boolean isWord()
  {
    return _isWord;
  }

  public String[] getSymbols()
  {
    return symboles;
  }

  public double[][][] getFrequencies()
  {
    return _frequencies;
  }

  public int[][] getStartSequences()
  {
    return _startSequences;
  }

  public double[] getCumulatedStartFrequencies()
  {
    return _cumulatedStartFrequencies;
  }

  private void addStartFrequency(Stack<String> pile, Double frequency)
  {
    if (_isWord)
    {
      String s;
      Vector<Integer> sequence = new Vector<Integer>();

      // Verification de même taille pour toutes les séquences Start
      if (_startSequencesSize == -1)
      {
        _startSequencesSize = pile.size();
      }
      else
      {
        if (_startSequencesSize != pile.size())
        {
          parser.done_parsing();
          parser.report_error("All start sequences should have the same size ...","");
        }
      }

      if(pile.size() < _order)
      {
          parser.done_parsing();
          parser.report_error("Size of a start sequence should be greater than Markov's order.","");
      }

      while(!pile.empty())
      {
        s = pile.pop();
        Integer i = _lexique.get(s);

        // Si le "mot" n'appartient pas au lexique, on l'y ajoute ...
        if(i == null)
        {
          _lexique.put(s,new Integer(_nextTokenID));
          // Ajout du "token" representant le mot au vecteur
          sequence.add(new Integer(_nextTokenID));

          _nextTokenID++;
        }
        else
        {
          // Ajout du "token" representant le mot au vecteur
          sequence.add(i);
        }
      }
      // Ajout de la sequence au tableau de stockage temporaire
      _tmpStartSequences.add(sequence);
      // Incrémentation de la somme partielle des frequences Start rencontrées ...
      _partialStartFrequencySum += frequency.doubleValue();
      _tmpCumulatedStartFrequencies.add(new Double(_partialStartFrequencySum));
    }
    else
    {
      if (pile.size() > 1)
      {
        parser.done_parsing();
        parser.report_error("Only one Word is allowed in LETTERS mode !!!",null);
      }

      String aWord = pile.pop();
      String s;
      Vector<Integer> sequence = new Vector<Integer>();

      // Verification de même taille pour toutes les séquences Start
      if (_startSequencesSize == -1)
      {
        _startSequencesSize = aWord.length();
      }
      else
      {
        if (_startSequencesSize != aWord.length())
        {
          parser.done_parsing();
          parser.report_error("All start sequences should have the same size ...",null);
        }
      }

      if(aWord.length() < _order)
      {
        parser.done_parsing();
        parser.report_error("Size of a start sequence should be greater or equal than Markov's order.",null);
      }

      for(int j = 0;j< aWord.length(); j++)
      {
        s = "" + aWord.charAt(j);
        Integer i = _lexique.get(s);

        // Si le "mot" n'appartient pas au lexique, on l'y ajoute ...
        if(i == null)
        {
          _lexique.put(s,new Integer(_nextTokenID));
          // Ajout du "token" representant le mot au vecteur
          sequence.add(new Integer(_nextTokenID));

          _nextTokenID++;
        }
        else
        {
          // Ajout du "token" representant le mot au vecteur
          sequence.add(i);
        }
      }
      // Ajout de la sequence au tableau de stockage temporaire
      _tmpStartSequences.add(sequence);
      // Incrémentation de la somme partielle des frequences Start rencontrées ...
      _partialStartFrequencySum += frequency.doubleValue();
      _tmpCumulatedStartFrequencies.add(new Double(_partialStartFrequencySum));
    }
  }

  private void gatherStartFrequencies()
  {
    if (GenRGenS.verbose)
    { GenRGenS.err.println("Gathering Start Frequencies ..."); }

    if (_tmpCumulatedStartFrequencies.size() != _tmpStartSequences.size())
    {
      parser.done_parsing();
      parser.report_error("Internal Error 01 : please report this bug to the developping team ...","");
    }
    _startSequences = new int[_tmpStartSequences.size()][_startSequencesSize];
    _cumulatedStartFrequencies = new double[_tmpCumulatedStartFrequencies.size()];

    for(int i = 0; i<_tmpStartSequences.size(); i++)
    {
      Vector<Integer> v = _tmpStartSequences.elementAt(i);
      if (v.size() != _startSequencesSize)
      {
        parser.done_parsing();
        parser.report_error("Internal Error 02 : please report this bug to the developping team ...","");
      }

      for(int j = 0; j<_startSequencesSize; j++)
      {
        Integer token = v.elementAt(j);
        _startSequences[i][j] = token.intValue();
      }

      Double frequency = _tmpCumulatedStartFrequencies.elementAt(i);
      _cumulatedStartFrequencies[i] = frequency.doubleValue();
    }
  }

  private void addFrequency(Stack<String> pile, Stack<Double> pileFreq, Couple accu, boolean checkSize)
  {
    Vector<Vector<Integer>> _tmpSequences = (Vector) accu.fst();
    Vector<Vector<Double>> _tmpFrequencies = (Vector) accu.snd();
    if (_isWord)
    {
      String s;
      Vector<Integer> sequence = new Vector<Integer>();
      // Verification de taille
      if ((pile.size() != _order + 1)&&(checkSize))
      {
        String seq = "[ ";
        while(pile.size()>0)
        {
          seq = seq + (String) pile.pop()+" ";
        }
        seq = seq + "]";
        parser.done_parsing();
        parser.report_error("Wrong size for sequence "+seq+" !\nThe size of a sequence should be equal to Markov's order + 1.",null);
      }

      while(!pile.empty())
      {
        s = pile.pop();
        Integer i = _lexique.get(s);

        // Si le "mot" n'appartient pas au lexique, on l'y ajoute ...
        if(i == null)
        {
          _lexique.put(s,new Integer(_nextTokenID));
          // Ajout du "token" representant le mot au vecteur
          sequence.add(new Integer(_nextTokenID));

          _nextTokenID++;
        }
        else
        {
          // Ajout du "token" representant le mot au vecteur
          sequence.add(i);
        }
      }
      // Ajout de la sequence au tableau de stockage temporaire
      _tmpSequences.add(sequence);

    }
    else
    {
      String s;
      Vector<Integer> sequence = new Vector<Integer>();
      if (pile.size() > 1)
      {
        String seq = "[ ";
        while(pile.size()>0)
        {
          seq = seq + (String) pile.pop()+" ";
        }
        seq = seq + "]";
        parser.done_parsing();
        parser.report_error("Bad sequence "+seq+"\nOnly one word is allowed in LETTERS mode !!!",null);
      }
      String aWord = pile.pop();


      if((aWord.length() != _order+1)&&(checkSize))
      {
        parser.done_parsing();
        parser.report_error("Wrong size for sequence "+aWord+"\nThe size of a sequence should be equal to Markov's order + 1.",null);
      }

      for(int j = 0;j< aWord.length(); j++)
      {
        s = "" + aWord.charAt(j);
        Integer i = (Integer) _lexique.get(s);

        // Si le "mot" n'appartient pas au lexique, on l'y ajoute ...
        if(i == null)
        {
          _lexique.put(s,new Integer(_nextTokenID));
          // Ajout du "token" representant le mot au vecteur
          sequence.add(new Integer(_nextTokenID));

          _nextTokenID++;
        }
        else
        {
          // Ajout du "token" representant le mot au vecteur
          sequence.add(i);
        }
      }
      // Ajout de la sequence au tableau de stockage temporaire
      _tmpSequences.add(sequence);
    }

    Vector<Double> frequencies = new Vector();

    if ((pileFreq.size() != _phase)&&(checkSize))
    {
      parser.done_parsing();
      parser.report_error("Expecting "+_phase+" frequency(ies), but getting "+pileFreq.size()+" frequency(ies)","");
    }

    if ((pileFreq.size() != _phase)&&(!checkSize))
    {
      parser.done_parsing();
      parser.report_error("Different number of phases are not supported for hidden states . Please provide exactly "+_phase+" frequencies.","");
    }

    while(!pileFreq.empty())
    {
      Double freq = pileFreq.pop();
      frequencies.add(freq);
    }
    _tmpFrequencies.add(frequencies);
  }



  private double convertFrequency(int nbMain,int nbState,Vector tmpSeq, int indexMain, int indexState, Vector<Integer> srcSeq , Vector<Double> srcFreqs, Vector destSeq, Vector destFreqs, 
      double[][][] mainFrequencies, int mainVoc, int stateVoc, int lastChar)
  {
    if(nbMain>nbState)
    {
      double tmp = 0;
      for(int i=0;i<mainVoc;i++)
      {
        for(int j=0;j<stateVoc;j++)
        {
          tmpSeq.add(new Integer(i*stateVoc+j));
          tmp += convertFrequency(nbMain-1,nbState,tmpSeq,indexMain*mainVoc+i,0,srcSeq,srcFreqs,destSeq,destFreqs,mainFrequencies,mainVoc,stateVoc,lastChar);
          tmpSeq.removeElementAt(tmpSeq.size()-1);
        }
      }
      return tmp;
    }
    else
    {
      if(nbMain<nbState)
      {
        double tmp = 0;
        int symb = ((Integer)srcSeq.elementAt(srcSeq.size()-nbState)).intValue()-mainVoc;
        for(int i=0;i<mainVoc;i++)
        {
          tmpSeq.add(new Integer(i*stateVoc+symb));
          tmp += convertFrequency(nbMain,nbState-1,tmpSeq,0,indexState*stateVoc+symb,srcSeq,srcFreqs,destSeq,destFreqs,mainFrequencies,mainVoc,stateVoc,lastChar);
          tmpSeq.removeElementAt(tmpSeq.size()-1);
        }
        return tmp;
      }
      else
      {
        if(nbMain<=1)
        {
          int symb = ((Integer)srcSeq.elementAt(srcSeq.size()-1)).intValue()-mainVoc;
          Vector backup =(Vector) tmpSeq.clone();
          backup.add(new Integer(lastChar*stateVoc+symb));
          destSeq.add(backup);
          Vector<Double> freqs = new Vector<Double>();
          for(int i=0;i<srcFreqs.size();i++)
          { 
            double f = (srcFreqs.elementAt(i)).doubleValue();
            freqs.add(new Double(f*mainFrequencies[indexMain][lastChar][i]));
          }
          destFreqs.add(freqs);
          return 1.;
        }
        else
        {
          double tmp = 0;
          int symb = ((Integer)srcSeq.elementAt(srcSeq.size()-nbState)).intValue()-mainVoc;
          for(int i=0;i<mainVoc;i++)
          {
            tmpSeq.add(new Integer(i*stateVoc+symb));
            tmp += convertFrequency(nbMain-1,nbState-1,tmpSeq,indexMain*mainVoc+i,indexState*stateVoc+symb,srcSeq,srcFreqs,destSeq,destFreqs,mainFrequencies,mainVoc,stateVoc,lastChar);
            tmpSeq.removeElementAt(tmpSeq.size()-1);
          }
          return tmp;
        }
      }
    }
  }


  private Couple convertToMarkov(Couple mainMarkovian, Stack hiddenStates)
  {
   GenRGenS.progress.setWorkName("Converting to a classical markov model...");
    String[] mySymboles = new String[_nextTokenID];
    Enumeration<String> enume = _lexique.keys();
    while(enume.hasMoreElements())
    {
      String s = enume.nextElement();
      Integer i = _lexique.get(s);
      mySymboles[i.intValue()] = s;
    }

    // On extrait le vocabulaire du modéle dominant
    Vector<Vector<Integer>> mainMarkovianSeqs = (Vector<Vector<Integer>>) mainMarkovian.fst();
    Vector<Vector<Double>> mainMarkovianFreqs = (Vector<Vector<Double>>) mainMarkovian.snd();
    boolean[] mainVoc = new boolean[_nextTokenID];
    int mainLexicalSize = 0;
    for(int i=0; i<mainVoc.length; i++)
    { mainVoc[i] = false; }
    for(int i=0; i<mainMarkovianSeqs.size(); i++)
    {
      Vector<Integer> seq =  mainMarkovianSeqs.elementAt(i);
      for(int j=0;j<seq.size();j++)
      {
        mainVoc[seq.elementAt(j).intValue()] = true;
      }
    }
    
    // On construit le tableau de fréquences du modèle dominant
    for(int i=0; i<mainVoc.length; i++)
    { if(mainVoc[i]) mainLexicalSize++;}
    int nbMainSeq = pow(mainLexicalSize,_order);
    double[][][] mainFrequencies = new double[nbMainSeq][mainLexicalSize][_phase];
    for(int i=0; i<mainMarkovianSeqs.size(); i++)
    {
      Vector<Integer> seq = mainMarkovianSeqs.elementAt(i);
      int index = indexOfSequence(seq,mainLexicalSize) ;
      int last = seq.elementAt(seq.size()-1).intValue();
      Vector<Double> freqs = mainMarkovianFreqs.elementAt(i);
      for(int j=0;j<freqs.size();j++)
      {
        Double f = (Double) freqs.elementAt(j);
        mainFrequencies[index][last][j] = f.doubleValue();
      }
    }
    
    // Construire un nouveau vocabulaire
    Hashtable newLexique = new Hashtable();
    String[] myNewSymboles = new String[mainLexicalSize*(_nextTokenID-mainLexicalSize)];
    for(int l=0;l<mainLexicalSize;l++)
    {
      for(int j=mainLexicalSize;j<_nextTokenID;j++)
      {
         newLexique.put(mySymboles[l]+"_"+mySymboles[j],new Integer(l*(_nextTokenID-mainLexicalSize)+(j-mainLexicalSize)));
         myNewSymboles[l*(_nextTokenID-mainLexicalSize)+(j-mainLexicalSize)] = mySymboles[j];
       }
    }

    // Conversion effective des fréquences vers un modele markovien
    int stateOrder = -1;
    Vector newSeqs = new Vector();
    Vector newFreqs = new Vector();
    long amount = 0;
    long progress = 0;
    while(!hiddenStates.isEmpty())
    {
      Couple hiddenStateDecl = (Couple) hiddenStates.pop();
      Integer state = _lexique.get(hiddenStateDecl.fst());
      Couple hiddenFreqsDecl = (Couple)hiddenStateDecl.snd();
      Vector hiddenSeqs = (Vector) hiddenFreqsDecl.fst();
      Vector hiddenFreqs = (Vector) hiddenFreqsDecl.snd();
      for(int i=0;i<hiddenSeqs.size();i++)
      {
        Vector seq = (Vector) hiddenSeqs.elementAt(i);
        if(stateOrder!=seq.size()-1)
        {
          if(stateOrder==-1)
          {
            stateOrder=seq.size()-1;
            amount = pow(mainLexicalSize*(_nextTokenID-mainLexicalSize),Math.max(_order+1,stateOrder+1));
            GenRGenS.progress.setAmount(amount);
            GenRGenS.progress.setProgress(progress);
          }
          else
          {
            parser.done_parsing();
            parser.report_error("Different orders for the hidden states are not supported!","");
          }
        }
        Vector freqs = (Vector) hiddenFreqs.elementAt(i);
        Vector tmpSeq = new Vector();
        double addedFreqs = convertFrequency(_order+1,stateOrder+1,tmpSeq,0,0,seq,freqs,newSeqs,newFreqs,mainFrequencies,mainLexicalSize,_nextTokenID-mainLexicalSize,state.intValue());
        progress += addedFreqs;
        GenRGenS.progress.setProgress(progress);
      }
    }

    GenRGenS.progress.setProgress(amount); 
    _lexique = newLexique;
    _order = Math.max(stateOrder,_order);
    _nextTokenID = newLexique.size();
    return (new Couple(myNewSymboles,new Couple(newSeqs,newFreqs)));
  }

  /**
   * Met en forme les frequences lues de façon ?ce qu'elle puissent être
   * utilisées par la classe HeterogeneousMarkov.
   * Teste au passage la présence d'"impasses"
  */

  private void gatherFrequencies(Couple c)
  {
    Vector<Vector<Integer>> _tmpSequences = (Vector) c.fst();
    Vector<Vector<Double>> _tmpFrequencies = (Vector) c.snd();
    if (GenRGenS.verbose)
    { GenRGenS.err.println("Gathering Frequencies ..."); }

    if (_tmpFrequencies.size() != _tmpSequences.size())
    {
      parser.done_parsing();
      parser.report_error("Internal Error 03 : please report this bug to the developping team ...","");
    }

    int nbContextes = pow(_lexique.size(),_order);
    _frequencies = new double[nbContextes][_phase][_lexique.size()+1];
    for(int i = 0; i<nbContextes; i++)
    {
      for(int j = 0; j<_phase; j++)
      {
        for(int k = 0; k<_lexique.size(); k++)
        {
          _frequencies[i][j][k] = 0.;
        }
      }
    }
    for(int i = 0; i<_tmpSequences.size(); i++)
    {
      Vector<Integer> seq = _tmpSequences.elementAt(i);
      Vector<Double> freqs = _tmpFrequencies.elementAt(i);
      if (freqs.size() != _phase)
      {
        parser.done_parsing();
        parser.report_error("Internal Error 04 : please report this bug to the developping team ...","");
      }

      int index = indexOfSequence(seq,_lexique.size());
      // Le numéro du dernier caractère de la sequence (celui ?générer)
      int last = ((Integer) seq.elementAt(seq.size()-1)).intValue();

      for(int j = 0; j<_phase; j++)
      {
        Double f = (Double) freqs.elementAt(j);
        if(_frequencies[index][j][last] == 0)
        {
          _frequencies[index][j][last] = f.doubleValue();
        }
        else
        {
          parser.done_parsing();
          parser.report_error("Attempting to redefine a frequency !",null);
        }
        _frequencies[index][j][_lexique.size()] += f.doubleValue();
      }
    }
    symboles = new String[_lexique.size()];
    Enumeration<String> enume = _lexique.keys();
    while(enume.hasMoreElements())
    {
      String s = enume.nextElement();
      Integer i = _lexique.get(s);
      symboles[i.intValue()] = s;
    }
    if (MarkovianGenerationConfiguration.ExactSizeMarkovianGeneration)
    {
      testDeadEnds();
    }
  }

  private void testDeadEnds()
  {
    
    if (GenRGenS.verbose)
    { GenRGenS.err.println("Looking for \"Deadends\" ..."); }
    /* On ajoute des couples (a,b) ?ReachedStates o?a est l'index de la
       sequence "contexte" et b la phase du symbole suivant.*/
    LinkedList ReachedStates = new LinkedList();
    int borne = pow(_lexique.size(),_order);
    boolean[][] reached = new boolean[borne][_phase];
    int phaseActuelle = 0;
    
    for(int i=0; i<borne; i++)
    {
      for(int j=0; j<_phase; j++)
      {
        reached[i][j] = false;
      }
    }

    if (_cumulatedStartFrequencies.length != 0)
    {
      for(int i=0; i<_startSequences.length;i++)
      {
        int[] a = _startSequences[i];
        int index = indexOfArray(a,_lexique.size());
        Couple c = new Couple(new Integer(index), new Integer((a.length)%_phase));
        ReachedStates.addFirst(c);
        reached[index][_order % _phase] = true;
      }
    }
    else
    {
      for(int i=0; i<borne; i++)
      {
        if (_frequencies[i][0][_lexique.size()]>0)
        {
          Couple c = new Couple(new Integer(i), new Integer((_order) % _phase));
          ReachedStates.addFirst(c);
          reached[i][_order % _phase] = true;
        }
      }
    }
    // Maintenant on a dans ReachedStates les "contextes" START ...
    String[] symb = getSymbols();
    while(ReachedStates.size()!=0)
    {
      Couple c = (Couple) ReachedStates.removeLast();
      int index = ((Integer)c.fst()).intValue();
      int nphase = (((Integer)c.snd()).intValue()) ;
      GenRGenS.err.println("["+sequenceOfIndex(index,_lexique.size(),_order,symb)+","+nphase+"]");
      if (_frequencies[index][nphase][_lexique.size()]>0)
      {
        for(int i=0; i<_lexique.size() ; i++)
        {
          if (_frequencies[index][nphase][i]>0)
          {
            int nindex = ((index * _lexique.size()) + i) % borne;
            if (!reached[nindex][(nphase+1)%_phase])
            {
              ReachedStates.addFirst(new Couple(new Integer(nindex), new Integer((nphase+1)%_phase)));
              reached[nindex][(nphase+1)%_phase] = true;
            }
          }
        }
      }
      else
      {
          _nbDeadEnds ++;
          GenRGenS.err.println("Warning, deadend : "+sequenceOfIndex(index, _lexique.size(),_order,symb)+" leads to nowhere on phase "+nphase+".");
      }
    }
  }

  public void setSymbols(String[] tab)
  {
    symboles = tab;
  }

  public int getNbDeadEnds()
  {
    return _nbDeadEnds;
  }

  private int indexOfArray(int[] a, int basis)
  {
    int tailleVocabulaire = basis;
    int value = 0;
    int base = 1;
    for(int i = a.length - 1; i >= a.length-_order; i--)
    {
      value += a[i] * base;
      base *= tailleVocabulaire;
    }
    return value;
  }

  private String sequenceOfIndex(int index,int base, int expectedSize, String[] lexique)
  {
    Vector seq = sequenceOfIndex2(index,base,expectedSize);
    String value = "";     
    for(int i = 0;i<seq.size();i++)
    {
      value += lexique[((Integer)seq.elementAt(i)).intValue()];
    }
    return value;
  }


  /**
    Prends les n-1 premiers éléments d'un vecteur de n dimensions, et
    calcule un entier décrivant complétement le sous vecteur sur la base
    du nombre de valeurs potentiellement prise par chacune de ses
    composantes.
  */
  private int indexOfSequence(Vector intVector, int basis)
  {
    int tailleVocabulaire = basis;
    int value = 0;
    int base = 1;
    for(int i = intVector.size() - 2; i >=0; i--)
    {
      Integer token = (Integer) intVector.elementAt(i);
      value += token.intValue() * base;
      base *= tailleVocabulaire;
    }
    return value;
  }

  private Vector sequenceOfIndex2(int index, int base, int expectedSize)
  {
    Vector value = new Vector();
    while(index > 0)
    {
      value.add(new Integer(index%base));
      index = index / base;
    }
    while(value.size() < _order)
    { value.add(new Integer(0));}
    return value;
  }

  /**
    Simulation d'une file :
    Définition des opérations push et pop
    fonctionnant par effet de bord.
  */
  private void fpush(LinkedList l, Object o)
  {
    Couple c = (Couple) o;
    l.addFirst(o);
  }
  private Object fpop(LinkedList l)
  {
    Object o = l.removeLast();
    Couple c = (Couple) o;
    return o;
  }
  private boolean fempty(LinkedList l)
  {
    return (l.size() == 0);
  }


  /**
    Fonction puissance classique (définie pour des exposants positifs).
  */
  private 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));
      }
    }
  }

  /**
    Modifie la representation en String (ah ah ah ...) d'un token :
    un token de representation src prendra comme representation dest.
  */
  private void replace(String src, String dest)
  {
    boolean found = false;
    for(int i=0;i<symboles.length;i++)
    {
      if(symboles[i].equals(src))
      {
        symboles[i] = dest;
        found = true;
      }
    }
    if (!found)
    {
      parser.done_parsing();
      parser.report_error("The left value for the alias declaration \""+src+" = "+dest+"\" doesn't exist !","");
    }
  }
:}


/* Declaration des  terminaux */

/* Tokens associés ?des mots-clés */

  /* Mots-clés généraux */
    terminal           TYPE, GRAMMAR, MARKOV, MASTERFILE;
    terminal           SYMBOLS, WORDS, LETTERS;
    terminal           EQUALS, SEMI, DBLPOINT, ARROW, ALIASES;
    /* ARROW est le mot cl?de sémantique : "est dériv?en ..." */

  /* Mots-clés spécifiques aux fichiers de description de Markov */
    terminal           START, FREQUENCIES, HMMFREQUENCIES;
    terminal           ORDER, PHASE;

  /* Mots-clés spécifiques aux fichiers "maitres" */
    terminal           QUOTES, EXACT, POISSON;

/* Token "porteurs d'information" */
  terminal  Integer  ENTIER;
  terminal  Double   REEL;
  terminal  String   IDENT, STRING;



/* Non-terminals */
non terminal         MarkovDescription;
non terminal         TypeDeclaration, OrderDeclaration, PhaseDeclaration;
non terminal         SymbolTypeDeclaration, StartSequencesDeclaration, StartSequences;
non terminal         FrequenciesDeclaration, AliasesDeclaration, AliasesList;

non terminal Float   Reel;

non terminal Stack   StringList, DoubleList, HiddenStatesDefinitions;

non terminal Couple  FrequenciesList, FrequenciesListNoSize;


/* The grammar */

start with MarkovDescription;


MarkovDescription ::=
    TypeDeclaration OrderDeclaration PhaseDeclaration
    SymbolTypeDeclaration StartSequencesDeclaration
    FrequenciesDeclaration AliasesDeclaration  {: :}
  ;


TypeDeclaration ::=
    TYPE EQUALS MARKOV                          {: :}
  ;

OrderDeclaration ::=
    ORDER EQUALS ENTIER:n                       {: _order = n.intValue(); :}
  |                                             {:
                                                  parser.done_parsing();
                                                  parser.report_error("You must define markovian order !",null);
                                                :}
  ;

PhaseDeclaration ::=
    PHASE EQUALS ENTIER:n                       {:
                                                  if(n.intValue()>0)
                                                  {
                                                    _phase = n.intValue();
                                                  }
                                                  else
                                                  {
                                                    parser.done_parsing();
                                                    parser.report_error("NBPhase must be > 0 !",null);
                                                  }
                                                :}
  |                                             {: _phase = 1; :}
  ;

SymbolTypeDeclaration ::=
    SYMBOLS EQUALS WORDS                        {: _isWord = true; :}
  | SYMBOLS EQUALS LETTERS                      {: _isWord = false; :}
  |                                             {: _isWord = true; :}
  ;

StartSequencesDeclaration ::=
    START EQUALS StartSequences                 {: gatherStartFrequencies(); :}
  |                                             {:  :}
  ;


StartSequences ::=
    StringList:p1 REEL:n StartSequences       {: addStartFrequency(p1,n); :}
  | StringList:p1 ENTIER:n StartSequences       {: addStartFrequency(p1,new Double(n)); :}
  | StringList:p1 REEL:n                      {: addStartFrequency(p1,n); :}
  | StringList:p1 ENTIER:n                      {: addStartFrequency(p1,new Double(n)); :}
  ;

StringList ::=
    IDENT:s StringList:p                        {:
                                                  p.push(s);
                                                  RESULT = p;
                                                :}
  | IDENT:s                                     {:
                                                  Stack pile = new Stack();
                                                  pile.push(s);
                                                  RESULT = pile;
                                                :}
  ;

DoubleList ::=
    REEL:i DoubleList:p                          {:
                                                  p.push(i);
                                                  RESULT = p;
                                                :}
  |  ENTIER:i DoubleList:p                          {:
                                                  p.push(new Double(i));
                                                  RESULT = p;
                                                :}
  | REEL:i                                    {:
                                                  Stack<Double> pile = new Stack<Double>();
                                                  pile.push(i);
                                                  RESULT = pile;
                                                :}
  | ENTIER:i                                    {:
                                                  Stack<Double> pile = new Stack<Double>();
                                                  pile.push(new Double(i));
                                                  RESULT = pile;
                                                :}
  ;


FrequenciesDeclaration ::=
    FREQUENCIES EQUALS FrequenciesList:c        {: 
                                                  gatherFrequencies(c);
                                                :}
  | HMMFREQUENCIES EQUALS FrequenciesList:c SEMI HiddenStatesDefinitions:s
                                                {: 
                                                  Couple c2 = convertToMarkov(c,s);
                                                  gatherFrequencies((Couple)c2.snd());
                                                  setSymbols((String[])c2.fst());
                                                :}
  | HMMFREQUENCIES EQUALS FrequenciesList:c 
                                                {: 
                                                  parser.done_parsing();
                                                  parser.report_error("Definition required for the hidden states emission probabilities !",null);
                                                :}
  ;

FrequenciesList ::=
    StringList:p1 DoubleList:p2 FrequenciesList:c  
                                                {: 
                                                   addFrequency(p1,p2,c,true); 
                                                   RESULT = c;
                                                :}
  | StringList:p1 DoubleList:p2                    {: 
                                                   Vector freqs = new Vector();
                                                   Vector seqs = new Vector();
                                                   Couple c = new Couple(seqs,freqs);
                                                   addFrequency(p1,p2,c,true); 
                                                   RESULT = c;
                                                :}
  ;

FrequenciesListNoSize ::=
    StringList:p1 DoubleList:p2 FrequenciesListNoSize:c  
                                                {: 
                                                   addFrequency(p1,p2,c,false); 
                                                   RESULT = c;
                                                :}
  | StringList:p1 DoubleList:p2                    {: 
                                                   Vector freqs = new Vector();
                                                   Vector seqs = new Vector();
                                                   Couple c = new Couple(seqs,freqs);
                                                   addFrequency(p1,p2,c,false); 
                                                   RESULT = c;
                                                :}
  ;

HiddenStatesDefinitions ::=
    IDENT:state DBLPOINT FrequenciesListNoSize:c SEMI HiddenStatesDefinitions:s
                                                {:
                                                   Couple ctmp = new Couple(state,c);
                                                   s.push(ctmp);
                                                   RESULT = s;
                                                :}
  | IDENT:state DBLPOINT FrequenciesListNoSize:c 
                                                {:
                                                   Stack s = new Stack();
                                                   Couple ctmp = new Couple(state,c);
                                                   s.push(ctmp);
                                                   RESULT = s;
                                                :}
  | IDENT:state DBLPOINT FrequenciesListNoSize:c SEMI
                                                {:
                                                   Stack s = new Stack();
                                                   Couple ctmp = new Couple(state,c);
                                                   s.push(ctmp);
                                                   RESULT = s;
                                                :}
  ;                                           


AliasesDeclaration ::=
    ALIASES EQUALS AliasesList                  {: :}
  | ALIASES EQUALS                              {:
                                                  parser.done_parsing();
                                                  parser.report_error("You should define at least one alias !",null);
                                                :}
  |                                             {: :}
  ;

AliasesList ::=
    IDENT:i_src EQUALS IDENT:i_dest AliasesList {:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src EQUALS STRING:i_dest AliasesList{:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src EQUALS IDENT:i_dest             {:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src EQUALS STRING:i_dest            {:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src ARROW IDENT:i_dest AliasesList {:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src ARROW STRING:i_dest AliasesList{:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src ARROW IDENT:i_dest             {:
                                                  replace(i_src,i_dest);
                                                :}
  | IDENT:i_src ARROW STRING:i_dest            {:
                                                  replace(i_src,i_dest);
                                                :}
  ;
