package GenRGenS.ratexpr;

import java.util.*;
import java.io.*;
import java.math.*;
import GenRGenS.*;

public class GeneratorRational implements Generator {
		
		/** Constantes */
		private static BigDecimal BIGZERO = new BigDecimal(0);
		private static BigDecimal BIGONE = new BigDecimal(1);
		
		//Correspond a la lettre ajouter en debut de mot pour pouvoir generer
		//des mots de taille quelconque en prosite
		private static Integer LETTRE_INUTILE = new Integer(-1);
		
		/** parser qui contient toutes les informations necessaires a la
		 *  generation de mots */
		private parser _parser;
		private boolean _erreur = false;
		private boolean _isProsite = false;
		
		/** automate associe a l'expression rationelle. */
		private Automate _automate;
		private int _plusLongueBranche = -1;
		
		/** Table des symboles */
		private String[] _symboles;
		
		/** table permettant de connaitre, pour un numero d'etat i et une
		 *  longueur de mot l, le nombre de mots de taille l engendrable a
		 *  partir de l'etat i dans l'automate _automate.
		 */
		private BigDecimal[][] _N;
		
		/** permet d'associer a un indice d'etat dans _N, le vrai numero d'etat 
		 *  dans l'automate. 
		 */
		private Integer[] _case_etat;
		
		/** _etat_case permet de connaitre l'indice d'un etat dans _N, a partir
		 *  de son numero dans l'automate.
		 */
		private HashMap _etat_case;
		
		private static Random _rand = new Random(System.currentTimeMillis());
		private static BigDecimal MAXDOUBLE = new BigDecimal(Double.MAX_VALUE);
		
		public GeneratorRational(File file) 
    throws IOException,GeneratorCreationException
    {
        this(new FileReader(file));
		}
		
		public GeneratorRational(String file) throws GeneratorCreationException{
        this(new StringReader(file));
		}
		
		public GeneratorRational(Reader file) throws GeneratorCreationException
		{
			try{
				int travail = 10000;
				GenRGenS.progress.setWorkName("Initialization");
				GenRGenS.progress.setAmount(travail);
				
				GenRGenSScanner prescan = 
					new GenRGenSScanner(file);
				if (GenRGenS.verbose)
					GenRGenS.err.print("[A...");
				preparser pre_parser = new preparser(prescan);
				if (GenRGenS.verbose)
					GenRGenS.err.print("B...");
        pre_parser.parse();
				Reader correct = new StringReader(pre_parser.getTexte());
				if (GenRGenS.verbose)
					GenRGenS.err.print("C]");
				
				long tdeb = System.currentTimeMillis(),tfin;
				long tinit = tdeb;
				
				if (GenRGenS.verbose)
					GenRGenS.err.print("[Checking input file ...");
				
				GenRGenSScanner s = 
					new GenRGenSScanner(correct);
        		_parser = new parser(s);
				
				if (GenRGenS.verbose)
					GenRGenS.err.print("]\n[Processing input file...");
        		_parser.parse();
        		
        		if (_parser.isParseError()) {
        			GenRGenS.err.println("\nError while parsing!");
        			_erreur = true;
        			return;
        		}
        						
        		RatExpr rat = _parser.getRatExpr();
        		_isProsite = _parser.isProsite();
        		
        		if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.print(" in "+
						(tfin-tdeb)+" ms]\n[Building automaton...");
					tdeb = System.currentTimeMillis();
				}
        		Automate a = new Automate(rat);
				
				if (_isProsite 
				  && GeneratorRationalConfigFile.TAILLE_INDIFFERENTE) {
        			Etat etatInitial = (Etat) a.getEtatsInitiaux().toArray()[0];
        			a.ajoutTransition(etatInitial,LETTRE_INUTILE,etatInitial);
        		}
				
        		if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.print(" in "+
						(tfin-tdeb)+" ms]\n[Determinization...");
					tdeb = System.currentTimeMillis();
				}
        		Automate aDet = a.determinise();
        		
        		if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.print(" in "+
						(tfin-tdeb)+" ms]\n[Minimization...");
					tdeb = System.currentTimeMillis();
				}
        		Automate aMin = aDet.minimise();
        		
        		if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.println(" in "+(tfin-tdeb)+" ms]");
				}
        		
        		_automate = aMin;
				
        		if (GeneratorRationalConfigFile.RESULAT_INTERMEDIAIRE) {
					GenRGenS.err.println("\tAuto\tDeterm\tMini");
					GenRGenS.err.println(
						"States\t"+
						a.getEtats().size()+"\t"+
						aDet.getEtats().size()+"\t"+
						aMin.getEtats().size()
					);
					GenRGenS.err.println(
						"Minimal automaton :\n"+_automate);
				}
				
				/* Construction de la table des symboles */
				_symboles = _parser.getLexique();
				
        		if (!construitAssociation())
        			GenRGenS.err.println("Error occured during  initialization.");
        		
        		if (GenRGenS.verbose)
					GenRGenS.err.println("...Initialization ended]");
      } catch (Exception e) { GenRGenS.err.println(); _erreur = true; throw(new GeneratorCreationException(e.toString())); }
		}

		/**
		 * L'ensemble des etats de l'automate n'etant pas numerotes de 0 a n, il
		 * faut construire de tables d'associations entre un etat et son indice 
		 * dans le tableau _N.
		 * @return retourne true si et seulement si l'operation s'est effectuee 
		 * sans probleme.
		 */
		private boolean construitAssociation() {
			if (_automate == null)
				return false;
			
			_case_etat = new Integer[_automate.getEtats().size()];
			_etat_case = new HashMap(_automate.getEtats().size());
			
			int i = 0;
			for(Iterator it = _automate.getEtats().keySet().iterator();
				it.hasNext();
				i++) {
				Integer numEtat = (Integer) it.next();
				_case_etat[i] = numEtat;
				_etat_case.put(numEtat,new Integer(i));
			}
			
			return true;
		}

		/**
		 * Pour generer un mot aleatoire, il faut faire un pre-traitement qui
		 * consiste en une construction d'une table _N a double entree.
		 * _N[i][l] represente le nombre de mot de longueur l pouvant etre
		 * generer a partir de l'etat_case_etat[i] dans l'automate.
		 * @param N est la taille des mots a generer.
		 * @return retourne true si et seulement si la construction s'est bien 
		 * passe.
		 */
		private boolean construitN(int N) throws GenerationException {
			
			double tdeb = 0., tfin = 0.;
			if (GenRGenS.verbose) {
				tdeb = System.currentTimeMillis();
				GenRGenS.err.print("[Preprocessing... ");
			}
			
			if (_case_etat == null || _etat_case == null) {
				if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.println(" in "+(tfin-tdeb)+" ms");
				}
				return false;
			}
			
			GenRGenS.progress.setWorkName("Precomputing transition probabilities");
			GenRGenS.progress.setAmount(_case_etat.length * (N+1));
			int avancement = 0;
			
			_N = new BigDecimal[_case_etat.length][N+1];
			int i, j;
			for(i = 0; i <= N; i++) {
				boolean toutZero = true;
				for(j = 0; j < _case_etat.length; j++) {
					
					avancement++;
					GenRGenS.progress.setProgress(avancement);
					
					if (i == 0) {
						if (((Etat)_automate.getEtats().get(_case_etat[j]))
							.isTerminal()) {
							toutZero = false;
							_N[j][i] = new BigDecimal(1);
						}
						else
							_N[j][i] = new BigDecimal(0);
					}
					else {
						BigDecimal nbMots = BIGZERO;
						Set succ;
						Object etiq;
						for(Iterator it = _automate.getAlphabet().iterator(); 
							it.hasNext();) {
							etiq = it.next();
							
							succ = _automate.successeur(_case_etat[j].intValue()
								,etiq);
							if (!succ.isEmpty()) {
								Integer numEtatSucc = 
									((Etat) ((succ.toArray())[0])).getNum();
								nbMots = nbMots.add(_parser.getPoids(etiq).
									multiply(_N[((Integer) _etat_case.
										get(numEtatSucc)).intValue()][i-1]));
							}
						}
						_N[j][i] = nbMots;
						if (_N[j][i].compareTo(BIGZERO) != 0)
							toutZero = false;
					}
				}
				if (toutZero) {
					if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.println(" in "+(tfin-tdeb)+" ms]");
					}
					throw new GenerationException("No sequence of size "+N+
						"\nMax size = "+(i-1));
				}
			}
			if (GenRGenS.verbose) {
				tfin = System.currentTimeMillis();
				GenRGenS.err.println(" in "+(tfin-tdeb)+" ms]");
			}
			return true;
		}
		
		private void afficheN() {
			GenRGenS.progress.setWorkName("Printing Precomputation tables");
			GenRGenS.progress.setAmount(_N.length * _N[0].length);
			int avancement = 0;
			
			GenRGenS.err.println("[_N = ");
			String s = "";
			for(int i = 0 ; i < _N.length ; i++) {
				s += _case_etat[i]+" :\t";
				for(int j = 0 ; j < _N[i].length ; j++) {
					avancement++;
					GenRGenS.progress.setProgress(avancement);
					s += _N[i][j]+" ";
				}
				s += "\n";
			}
			GenRGenS.err.println(s+"= _N]");
		}
		
		/** fonction de calcul de la longueur de la plus grande branche de
		 *  l'automate */
		private void calculBrancheMax() {
			
			Set etats = new HashSet()
			   ,tmp = new HashSet();
			Etat depart = (Etat) _automate.getEtatsInitiaux().toArray()[0];
			etats.add(depart);
			int taille = 0;
			while (!etats.isEmpty()) {
				tmp.clear();
				taille++;
				for(Iterator it = _automate.getAlphabet().iterator() ;
					it.hasNext() ;) {
					Object etiq = it.next();
					if (!etiq.equals(LETTRE_INUTILE))
						tmp.addAll(_automate.successeurEnsemble(etats,etiq));
				}
				etats.clear();
				etats.addAll(tmp);
			}
			
			_plusLongueBranche = taille - 1;
		}
		
		
		/**
		 * Calcule la probabilite de sortie de la lettre etiq pour un etat q et
		 * une profondeur i
		 * @param i est la taille du mot a generer
		 * @param q est l'etat courant
		 * @param etiq est la lettre dont on veut la probabilite de sortie
		 * @return retourne la probabilite voulue
		 */
		private BigDecimal p(int i, Etat q, Object etiq) {
			Set succ = _automate.successeur(q,etiq);
			if (succ.isEmpty())
			//il n'y a pas de transition etiq possible depuis q
				return BIGZERO;
			else {  //q a un successeur par la transition etiq
				int indice_q = ((Integer)_etat_case.get(q.getNum())).intValue();
				int indice_succ_q = ((Integer) _etat_case.
					get(((Etat) (succ.toArray()[0])).getNum())).intValue();
				
				if (_N[indice_q][i].compareTo(BIGZERO) == 0)
					return BIGZERO;
				return _parser.getPoids(etiq).
					multiply(_N[indice_succ_q][i-1].
						divide(_N[indice_q][i],30,BigDecimal.ROUND_HALF_UP));
			}
		}
		
		/** 
		 * Génération d'une chaine de caractere
		 * @param size Le nombre de symboles de la séquence à generer
		 * @param retourne un mot de taille size qui appartient au langage.
		 */
		public StringBuffer generateRandomWord(int size)
				throws GenerationException {
			if (_erreur)
				throw new GenerationException(
			"Couldn't perform random generation: bad description file!");
			
			if (!_automate.isMinimal())
				throw new GenerationException(
			"Couldn't perform random generation: automaton is not minimized!");
			
			if (_isProsite && GeneratorRationalConfigFile.TAILLE_INDIFFERENTE) {
				long tdeb = 0, tfin = 0;
				if (GenRGenS.verbose && _plusLongueBranche == -1) {
					tdeb = System.currentTimeMillis();
					GenRGenS.err.print("[Building longest path ... ");
				}
				
				if (_plusLongueBranche == -1)
					calculBrancheMax();
				size = _plusLongueBranche;
				
				if (GenRGenS.verbose && tdeb != 0) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.print(" in "+(tfin-tdeb)+" ms]");
					if (GeneratorRationalConfigFile.RESULAT_INTERMEDIAIRE)
						GenRGenS.err.println(" = "+_plusLongueBranche);
					else
						GenRGenS.err.println("");
				}
			}
			
			
    		// On engendre un mot "tokenisé" ...
			
			Vector motToken = generateTokenizedRandomWord(size);
    		
			//On le convertit en StringBuffer en utilisant les représentations
			//"en chaînes" des tokens.
    		StringBuffer mot = new StringBuffer();
			for (int i=0; i<motToken.size(); i++) {
		        
	    	    if (!GeneratorRationalConfigFile.TAILLE_INDIFFERENTE
	    	     || !((Integer) motToken.get(i)).equals(LETTRE_INUTILE)) {
					if (_parser.isWord())
	    	    		mot.append(" ");
	    	    	mot.append(
	    	    		_symboles[((Integer)motToken.get(i)).intValue()]);
	    	    }
			};
      		return mot;
		}

		/** 
		 * generation tokenizee : chaine d'entier representant les indexes
		 * des symboles dans le generateur
		 * @param size Le nombre de symboles de la séquence à generer
		 */
		public Vector generateTokenizedRandomWord(int size)
				throws GenerationException {
			try {
			
			if (_N == null) {
				construitN(size);
				if (GeneratorRationalConfigFile.RESULAT_INTERMEDIAIRE)
					afficheN();
			}
			
			double tdeb = 0., tfin = 0.;
			if (GenRGenS.verbose) {
				tdeb = System.currentTimeMillis();
				GenRGenS.err.print("[Generating a word ... ");
			}
			
			Vector mot = new Vector();
			Etat q = (Etat) _automate.getEtatsInitiaux().toArray()[0];
			Set successeur;
			BigDecimal h, proba;
			Object etiq;
			for(int i = size ; i > 0 ; i--) {
				
				h = new BigDecimal(_rand.nextDouble());
				proba = BIGZERO;
				etiq = null;
				/*!!!!!!faire sur les transitions sortante de q*/
				for(Iterator it = _automate.getAlphabet().iterator();
					it.hasNext() && proba.compareTo(h) < 0;) {
					etiq = it.next();
					proba = proba.add(p(i,q,etiq));
				}
				successeur = _automate.successeur(q,etiq);
				if (successeur.isEmpty())
					throw new GenerationException(
						"No such word of size "+size);
				else {
					mot.add(etiq);
					q = (Etat) successeur.toArray()[0];
				}
			}
			
			if (q.isTerminal()) {
				if (GenRGenS.verbose) {
					tfin = System.currentTimeMillis();
					GenRGenS.err.println(" in "+(tfin-tdeb)+" ms]");
				}
				return mot;
			}
			else 
				throw new GenerationException("No such word of size "+size);
			
			}catch (Error e) {
				e.printStackTrace(GenRGenS.err);
				throw new GenerationException("Runtime error");
			}
			
		}

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

		/** 
		 * 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 (_symboles[i].equals(name))
					return true;
			
			return false;
		}

		/**
		 * 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) {
			for (int i = 0; i < _symboles.length ; i++)
				if (_symboles[i].equals(name))
					return i;
			
			return -1;
		}

		/** 
		 * Renvoie le nom du symbole d'index donné en argument
		 */
		public String symbolName(int index) {
			return _symboles[index];
		}
		
		public static void main(String[] argv) {
			try {
				File f = new File("tmp_TestGeneratorRational.ggd");
				f.deleteOnExit();
				DataOutputStream out;
				GeneratorRational g;
				boolean appartient;
				Vector v;
				int i = 0;
				System.setOut(new PrintStream(
					new OutputStream () {
							public void write(byte[] b) {};
						public void write(byte[] b, int off, int len) {};
						public void write(int b) {};
					}
				));
				
				//Test1 : appartenance des mots au langage Rational
				System.err.print("Appartenance des mots au langage ... ");
				out =	new DataOutputStream(
							new FileOutputStream(f));
				out.writeBytes(
					"TYPE = RATIONAL\n"+
					"LANGAGE = RATIONAL\n"+
					"SYMBOLS = LETTERS\n"+
					"EXPRESSION = (a.b+|c*)^2.de^(2,4)"
				);
				out.close();
				g = new GeneratorRational(f);
				appartient = true;
				v = null;
				for(i = 0; i < 1000 && appartient; i++) {
					v = g.generateTokenizedRandomWord(50);
					if (!g._automate.reconnait(v))
						appartient = false;
				}
				if (appartient)
					System.err.println("OK");
				else
					System.err.println("KO au mot "+i+" "+v);
				
				//Test2 : appartenance des mots au langage Prosite
				System.err.print("Appartenance des mots au langage ... ");
				out =	new DataOutputStream(
							new FileOutputStream(f));
				out.writeBytes(
					"TYPE = RATIONAL\n"+
					"LANGAGE = PROSITE\n"+
					"SYMBOLS = LETTERS\n"+
					"EXPRESSION = A(1,4)-D(3)-x-[ABC](2,7)-{ABC}"
				);
				out.close();
				g = new GeneratorRational(f);
				GeneratorRationalConfigFile.TAILLE_INDIFFERENTE = true;
				appartient = true;
				v = null;
				for(i = 0; i < 1000 && appartient; i++) {
					v = g.generateTokenizedRandomWord(1);
					if (!g._automate.reconnait(v))
						appartient = false;
				}
				if (appartient)
					System.err.println("OK");
				else
					System.err.println("KO au mot "+i+" "+v);
					
			} catch (Exception e) { System.out.println(e); }
		}
}