/*******************************************************************************
 * 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.grammar;

/*****************************************************************************
*              NormalContextFreeGrammar
*         
*
******************************************************************************/

import java.math.BigDecimal;
import java.io.*;
import java.util.*;
import GenRGenS.*;
import GenRGenS.grammar.*;
import GenRGenS.utility.*;


/** 
 * A class for the context-free grammar (CFG) on Normalized Form
 * @author Fr&eacute;d&eacute;ric Sarron
 * @version 1.0
 */
public class NormalContextFreeGrammar
{		
		public static final BigDecimal bigOne = new BigDecimal(1);
		
		private static final String newSymbolNamePrefix="_New";
		// numero utilisé pour l'ajout de nouveaux auxiliaires
		private int numeroNouvelAuxiliaire;

		// index du symbol start
		protected int symbolStart;
		// representation textuelle des symboles non-terminaux
		protected String[] nonTerminaux;
    // representation textuelle des symboles terminaux
		protected String[] terminaux;
		// representqtion des production
		protected NormalContextFreeGrammarProduction[] productions;
		// true ssi les symboles sont des chaines de caracteres
		// false : un symbole <-> une lettre -> pas d'espaces de separation
		protected boolean words=true;
		// ponderation des terminaux
		protected BigDecimal[] terminalsMasses;

		/*==================================================================
			                        CONSTRUCTEURS
    ==================================================================*/
		
		/* construction d'une grammaire normalisée à partir
		   d'une CFG quelconque */
		NormalContextFreeGrammar(ContextFreeGrammar cfgGrammar)
				throws BadGrammarException
		{
				if (!cfgGrammar.describeNonEmptyLanguage())
						throw(new BadGrammarException("Empty Language"));
				else
						{
								/* on test si tous les auxiliaires de la grammaire
									 sont accesibles. Si ce n'est pas le cas
									 un exception sera levée dans la fonction appellée */
								cfgGrammar.testNonTerminalsAccessibility();
								// transformation de cfgGrammar en e-free CFG
								cfgGrammar.removeEpsilonProductions();
								// éliminations des productions singulières
								cfgGrammar.removeSingleProductions();

								/*-----------------------------
									       Normalisation 
									-----------------------------*/
								/* récupération des données utiles */
								numeroNouvelAuxiliaire=cfgGrammar.newNTid();
								symbolStart=cfgGrammar.startSymbol();
								terminaux=cfgGrammar.terminalsNames();
								nonTerminaux=cfgGrammar.nonTerminalsNames();
								terminalsMasses=cfgGrammar.getWeights();
								words=cfgGrammar.getWords();

								// traitement des productions */
								Vector newProductions = new Vector();
								// les productions terminales , l'epsilon-production eventuelle,
								// les produits binaires
								// et les produits non binaires entre non-terminaux
								ContextFreeGrammarProduction prod;
								for (int numProd=0;
										 numProd<cfgGrammar.numberOfProductions();
										 numProd++)
										if ((prod=cfgGrammar.getProduction(numProd))
												.isTerminalProduction())
												newProductions.add(new NormalContextFreeGrammarProductionTerminal(prod.getLHS(),prod.get(1)));
										else
												if (prod.isEpsilonProduction())
														newProductions.add(new NormalContextFreeGrammarProductionTerminal(prod.getLHS(),0));
												else
														if (prod.size()==3)
																// produit binaire
																binaryProductDecomposition(prod.getLHS(), 1,
																													 prod,
																													 newProductions);
														else
																// produit non-binaire -> décomposition
																productDecomposition(prod.getLHS(), 1,
																										 prod, newProductions);
								
								/* et enfin rassemblons les règles concurrentes
									 dans une production-alternative */
								Vector[] prodOfNT = new Vector[nonTerminaux.length];
								for (int i=0;i<prodOfNT.length;i++)
										prodOfNT[i] = new Vector();
								for (int numProd=0;numProd<newProductions.size();numProd++)
										{
												NormalContextFreeGrammarProduction nprod =
														(NormalContextFreeGrammarProduction)
														newProductions.get(numProd);
												prodOfNT[nprod.getLHS()].add(nprod);
										};
								Vector newProductionsFinal = new Vector();
								for (int indexNT=0;indexNT<prodOfNT.length;indexNT++)
										if (prodOfNT[indexNT].size()==1)
												newProductionsFinal.add(prodOfNT[indexNT].get(0));
										else
												{
														int nombreAlternatives = prodOfNT[indexNT].size();
														int indexAlternativeMin = nonTerminaux.length;
														makeNewNonTerminals(nombreAlternatives);
														int[] alternatives = new int[nombreAlternatives];
														for (int i=0;i<nombreAlternatives;i++)
																{
																		alternatives[i]=indexAlternativeMin+i;
																		NormalContextFreeGrammarProduction p =
																				(NormalContextFreeGrammarProduction)
																				prodOfNT[indexNT].get(i);
																		p.setLHS(alternatives[i]);
																		newProductionsFinal.add(p);
																};
														newProductionsFinal
																.add(new NormalContextFreeGrammarProductionUnion
																		 (indexNT, alternatives));
												};
								
								/* rassemblement des productions terminales :
									 il est fort probable que plusieurs auxiliaires
									 generent un meme non-terminal.
									 Dans ce cas il faut supprimer les auxiliaires inutiles
									 tout en faisant repointer leur reference dans les regles */
								
								// auxiliairesTerminal : 
								// donne le permier non-terminal generant un terminal 
								int[] auxiliairesTerminal = new int[terminaux.length];
								// auxiliairesRedirection :
								// indexe par les auxiliaires
								// -1 si l'auxiliaire va rester dans la grammaire
								// l'index d'e l'auxiliaire qui est 
								// auxiliairesTerminal[le terminal genere]
								int poolNT=nonTerminaux.length;
								int[] auxiliairesRedirection = new int[poolNT];
								Arrays.fill(auxiliairesTerminal,-1);
								Arrays.fill(auxiliairesRedirection,-1);
								int numProd=0, termIndex, aux;
								NormalContextFreeGrammarProduction nprod;
								while (numProd<newProductionsFinal.size())
										{
												
												nprod = (NormalContextFreeGrammarProduction)
														newProductionsFinal.get(numProd);
												if ((nprod instanceof
														 NormalContextFreeGrammarProductionTerminal))
														{
																termIndex=-(
																	(NormalContextFreeGrammarProductionTerminal)
																	   nprod).getRHS()-1;
																if (termIndex!=-1)
																		{
																				aux=nprod.getLHS();
																				if(auxiliairesTerminal[termIndex]<0 )
																						{
																								auxiliairesTerminal[termIndex]=
																										aux;
																								numProd++;
																						}
																				else
																						{
																								auxiliairesRedirection[aux]=
																									 auxiliairesTerminal
																										[termIndex];
																								newProductionsFinal
																										.remove(numProd);
																						}
																		}
																else
																		numProd++;
														}
												else
														numProd++;									
										};
								
								// alignement des references aux auxiliaires
								// dans les productions
								for (numProd =0;
										 numProd<newProductionsFinal.size();
										 numProd++)
										((NormalContextFreeGrammarProduction)
												newProductionsFinal.get(numProd))
												.modifyReferences(auxiliairesRedirection);

								/* cycle de simplification des auxiliaires
									 generant des produits ou des unions.
									 les deux fontions booleenes doivent retourner false
									 pour indiquer que la grammaire est stable
									 du point de vue des simplifications */
								while (simplify(newProductionsFinal, poolNT));

								/*===== Compacter une fois ======*/

								// creation de la nouvelle assignation
								auxiliairesRedirection = 
										new int[poolNT];
								Arrays.fill(auxiliairesRedirection,-1);
								int indexInsertion=0;
								for (numProd=0;
										 numProd<newProductionsFinal.size();
										 numProd++)
										auxiliairesRedirection
												[((NormalContextFreeGrammarProduction) 
												newProductionsFinal.get(numProd)).getLHS()]
												= indexInsertion++;
								// alignement des references aux auxiliaires
								// dans les productions
								for (numProd=0;numProd<newProductionsFinal.size();numProd++)
										((NormalContextFreeGrammarProduction)
										 newProductionsFinal.get(numProd))
												.modifyReferences(auxiliairesRedirection);
								symbolStart=auxiliairesRedirection[symbolStart];
									
									// ramassage des productions finales
									productions =	new 
											NormalContextFreeGrammarProduction
											[newProductionsFinal.size()];
									for (numProd =0;numProd<newProductionsFinal.size();
											 numProd++)
											{
													nprod = (NormalContextFreeGrammarProduction)
															newProductionsFinal.get(numProd);									
													productions[nprod.getLHS()] = nprod;
											};
									
									renameNonTerminals(newProductionsFinal.size(),
																		 auxiliairesRedirection);
						};
		};

	  /*==================================================================
			                    METHODES AUXILIAIRES
    ==================================================================*/

		public void setSpacedTerminals(boolean newWord)
		{
				words = newWord;
		};

		public void makeNewNonTerminals(int combien)
		{
				int nombreDeNonTerminaux=nonTerminaux.length+combien, index;
				String[] nouveauxAuxiliaires=new String[nombreDeNonTerminaux];
				// repointage
				for (index=0;index<nonTerminaux.length;index++)
						nouveauxAuxiliaires[index]=nonTerminaux[index];
				// ajout des nouveaux noms
				for (;index<nombreDeNonTerminaux;index++)
						nouveauxAuxiliaires[index]=newSymbolNamePrefix+(numeroNouvelAuxiliaire++);
				nonTerminaux=nouveauxAuxiliaires;
		};

		private void binaryProductDecomposition(int indexLHS,int indexRHSp,
																						ContextFreeGrammarProduction p,
																						Vector v)
		{
				int symbol1, symbol2;
				if ((symbol1=p.get(indexRHSp))<0)
						if ((symbol2=p.get(indexRHSp+1))<0)
								{
										makeNewNonTerminals(2);
										int indexMax=nonTerminaux.length-1;
										v.add(new NormalContextFreeGrammarProductionTerminal(indexMax-1, symbol1));
										v.add(new NormalContextFreeGrammarProductionTerminal(indexMax, symbol2));
										v.add(new NormalContextFreeGrammarProductionProduct(indexLHS, indexMax-1, indexMax));
								}
						else
								{
										makeNewNonTerminals(1);
										int newIndex=nonTerminaux.length-1;
										v.add(new NormalContextFreeGrammarProductionTerminal(newIndex, symbol1));
										v.add(new NormalContextFreeGrammarProductionProduct(indexLHS, newIndex, symbol2));
								}
				else
						if ((symbol2=p.get(indexRHSp+1))<0)
								{
										makeNewNonTerminals(1);
										int newIndex=nonTerminaux.length-1;
										v.add(new NormalContextFreeGrammarProductionTerminal(newIndex, symbol2));
										v.add(new NormalContextFreeGrammarProductionProduct(indexLHS, symbol1, newIndex));
								}
						else
								v.add(new NormalContextFreeGrammarProductionProduct(indexLHS,symbol1,symbol2));
		};

		/* ajout au vecteur v de nouvelles productions normales,
			 productions issues de la décomposition du produit non-binaire
			 représenté par p.
			 la LHS est donnée par indexLHS
			 le prochain élément du produit a éxaminer est indexRHSp */
		private void productDecomposition(int indexLHS,
																			int indexRHSp,
																			ContextFreeGrammarProduction p,
																			Vector v)
		{
				int symbol,indexSymbol;
				if (indexRHSp>p.size()-3)
						// terminaison
						binaryProductDecomposition(indexLHS, indexRHSp, p, v);			
				else
						{
								if ((symbol=p.get(indexRHSp))<0)
										// terminal
										{
												makeNewNonTerminals(1);
												indexSymbol=nonTerminaux.length-1;
												v.add(new NormalContextFreeGrammarProductionTerminal(indexSymbol,symbol));										
										}
								else
										indexSymbol=symbol;
								// ajout d'un nouveau symbole pour le reste de la production
								makeNewNonTerminals(1);
								// ajout de la nouvelle production
								// et depart en récursif
								v.add(new NormalContextFreeGrammarProductionProduct(indexLHS,
																																		indexSymbol,
																														nonTerminaux.length-1));
								productDecomposition(nonTerminaux.length-1, indexRHSp+1, p, v);
						};
		};

		/* cette fonction supprime les productions redondantes (au niveau RHS)
			 et les auxiliaires LHS associe.
			 Elle revoie false ssi aucune suppression n'a ete effectuee
			 (cas de grammaire stable)
		   poolNT est la limite superieure des indexes d'auxiliaires a manipuler */
		private boolean simplify(Vector vProductions, int poolNT)
		{
				// la valeur de retour
				boolean simplificationsOccurred = false;
				 
				/* rhs2lhs : les cles sont des rhs
					           (tableaux d'entiers sous ecran-objet "IntArray")
										 et les valeurs sont des vecteurs d'entiers(les lhs) */
				Hashtable rhs2lhs=new Hashtable();
				IntArray intAprod;
				int[] productRHS, auxiliairesRedirection;
				NormalContextFreeGrammarProductionProduct nprodprod;
				Object o;
				// creation de la table de correspondance rhs2lhs	
				int numProd=0;
				auxiliairesRedirection=new int[poolNT];
				Arrays.fill(auxiliairesRedirection,-1);
				while (numProd<vProductions.size())
						{
								o = vProductions.get(numProd);
								if (o instanceof NormalContextFreeGrammarProductionProduct)
										{
												nprodprod = 
														(NormalContextFreeGrammarProductionProduct) o;
												productRHS = new int[2];
												productRHS[0] = nprodprod.getNT1();
												productRHS[1] = nprodprod.getNT2();
												intAprod = new IntArray(productRHS);
												if (rhs2lhs.containsKey(intAprod))
														{
																auxiliairesRedirection[nprodprod.getLHS()]=
																		((Integer) rhs2lhs.get(intAprod))
																		.intValue();
																vProductions.remove(numProd);
																simplificationsOccurred=true;
														}
												else
														{
																rhs2lhs.put(intAprod,
																						new Integer(nprodprod.getLHS()));
																numProd++;
														};
												
										}
								else numProd++;
						};

				// alignement des references aux auxiliaires
				// dans les productions
				for (numProd=0;numProd<vProductions.size();numProd++)
						((NormalContextFreeGrammarProduction)
						 vProductions.get(numProd))
								.modifyReferences(auxiliairesRedirection);
				

				// le retour dit si une simplification quelconque s'est produite
				return(simplificationsOccurred);
		};
		
		/* Methode de renommage des auxiliaires.
			 l'attribut String[] nonTerminaux est modifie selon
			 le tableau des index "redirection"
			 redirection[ntindex]=-1 si reste dans la grammaire
			                     != nt_index si disparait.
			 Cette methode a pour but de compacifier les indexes des auxiliaires
		   (en particulier la correspondance textuelle), en vue
			 notement d'un rereferencage dans les regles.
			 Le tableau de retour est identique a "redirection"
			 exception faite que les non-terminaux qui restent dans la grammaire
			 se voient assigner un nouvel indexe resultant de la suppression de
			 certains auxiliaires et de la compaction resultante */
		private int[] compactRedirection(int[] redirection)
		{
				int combienASupprimer=0, indexInsertion=0;;
				for (int i=0;i<redirection.length;i++)
						if (redirection[i]!=-1) combienASupprimer++;
				String[] nonTerminauxSave = nonTerminaux;
				nonTerminaux = new String
						[nonTerminauxSave.length-combienASupprimer];
				for (int nt=0;nt<nonTerminauxSave.length;nt++)
						if (redirection[nt]==-1)
								{
										redirection[nt]=indexInsertion;
										nonTerminaux[indexInsertion++]=
												nonTerminauxSave[nt];
								};
				return(redirection);
		};

		/* methode pour le renommage des auxiliaires */
		public void renameNonTerminals(int combien, int[] reassignement)
		{
				String[] nonTerminauxSave=nonTerminaux;
				nonTerminaux=new String[combien];
				numeroNouvelAuxiliaire=1;
				// sauvegarde des noms d'origine
				int assign;
				for (int i=0;i<reassignement.length;i++)
						if ( ((assign=reassignement[i])>=0)
								 &&
								 (nonTerminauxSave[i].charAt(0)
								 !=newSymbolNamePrefix.charAt(0)))
								nonTerminaux[assign]=nonTerminauxSave[i];
				// nouveaux noms
				for (int i=0;i<nonTerminaux.length;i++)
						if (nonTerminaux[i]==null)
								nonTerminaux[i]=newSymbolNamePrefix+(numeroNouvelAuxiliaire++);
		};

		public String toString()
		{
				String temp="Start : "+nonTerminaux[symbolStart]+"\nAux : ";
				for (int i=0;i<nonTerminaux.length;i++)
						temp+=nonTerminaux[i]+" ";
				temp+="\nTerm : ";
				for (int i=0;i<terminaux.length;i++)
						temp+=terminaux[i]+" ";
				temp+="\nProd :\n";
				NormalContextFreeGrammarProduction prod;
				for (int i=0;i<productions.length;i++)
						{
								temp+="\t"+productions[i].toString(this)+"\n";
						};
				return(temp);
		}

		// juste pour le debugging : on ne voit les symboles que par leur indexes
		protected String toStringDebug(Vector vprod)
		{
				String temp=
						"Start : " + symbolStart +
						"\nIndexNTmax : " + (nonTerminaux.length-1) +
						"\nIndexTmin : " + (-terminaux.length) +
						"\nProds :\n";
				for (int n=0;n<vprod.size();n++)
						temp +=
								((NormalContextFreeGrammarProduction)
								 vprod.get(n)).toStringDebug()+"\n";
				return(temp);
		};
	
		public String CFGsymbolName(int index)
		{
				if (index<0)
						return(terminaux[-1-index]);
				else
						return(nonTerminaux[index]);
		};

/**************** necessaires a l'interface Generator **********************/

		public String symbolName(int index)
				throws IllegalArgumentException
		{
				if (index<terminaux.length)
						return terminaux[index];
				else
						throw new IllegalArgumentException("String symbolName(int) : index out of bounds");
		};

		public boolean isWORDS()
		{ return words; };

		public StringBuffer litteralSequence(List sequence, boolean spacing)
		{
				StringBuffer result=new StringBuffer();
				String spacingChar = spacing ? " " : "";
				for (int symbolIndex=0; symbolIndex<sequence.size(); symbolIndex++)
						result.append
								(terminaux
								 [ ((Integer) sequence.get(symbolIndex)).intValue() ]+
								 spacingChar);
				return result;
		};

		public int symbolIndex(String name)
				throws IllegalArgumentException
		{
				for (int i=0; i<terminaux.length; i++)
						if (name.equals(terminaux[i]))
								return i;
				throw new IllegalArgumentException("int symbolIndex(String) : "+name+" is not a terminal symbol");
		};

		public int numberOfterminalsSymbols()
		{ return terminaux.length; };

		public boolean isTerminalSymbol(String name)
		{
				for (int i=0; i<terminaux.length; i++)
						if (name.equals(terminaux[i]))
								return true;
				return false;
		};


    public void printStats(Vector TokenizedWord)
    {
      long[] compte = new long[terminaux.length];
      for(int i = 0; i < compte.length ;i++)
      { compte[i] = 0; }
      
      for(int i = 0; i < TokenizedWord.size() ;i++)
      {
        Integer index = (Integer) TokenizedWord.elementAt(i);
        compte[index.intValue()] ++;
      }
      
      GenRGenS.err.println("Symbols Frequencies : ");
      for(int i = 0; i < compte.length ;i++)
      {GenRGenS.err.println(terminaux[i] + " : "+ ((float) compte[i]) / (float) TokenizedWord.size());}
    }
		


/********************* test de la classe ***********************************/	
		private static void main(String[] arguments)
		{
				ContextFreeGrammar cfg;
				NormalContextFreeGrammar ncfg;
				File[] directoryListing = 
						(new File("../testfiles/NormalContextFreeGrammar/").listFiles
						 (new FileExtensionFilter("ggd")));
				PrintStream testResult;

				for (int numFichier=0;
						 numFichier<directoryListing.length;
						 numFichier++)
						{
								cfg = new ContextFreeGrammar();
								// = null : seule solution trouvée au prb du
								// try/catch et "may not have been init."
								testResult = null;
								try
										{
												testResult = new PrintStream
														(new FileOutputStream
														 (directoryListing[numFichier].toString()+
															".result"));
										}
								catch (IOException e) 
										{ 
												GenRGenS.out.println("Damned ! "+e.toString());
										}
								if (testResult!=null)
										{
												try
														{
															testResult.println
																		("=*=*= Result for file "+
																		 directoryListing[numFichier]+" =*=*=");
															cfg = new ContextFreeGrammar
																		(directoryListing[numFichier]);
															testResult.println
																	("Stored CFG :\n"+
																	 cfg.toString());
															ncfg = new NormalContextFreeGrammar(cfg);
															testResult.println
																	("\nNormal equivalent grammar :\n"+ncfg.toString());
														}
												catch (BadGrammarException e)
														{ testResult.println(e.toString());}
												catch (IOException e)
												    { GenRGenS.out.println("Damned !"); }
												testResult.println("\n\n\n\n");
												testResult.close();
												GenRGenS.out.println
														("wrote "+
														 directoryListing[numFichier].toString()+
														 ".result");
										};
						};
				GenRGenS.out.println("All done !");
				System.exit(0);				
		}
	 
}
