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

/*****************************************************************************
*                          DoubleCountedNCFG
*
*
******************************************************************************/

import java.math.BigDecimal; // pour les poids
import java.util.*;
import java.io.*;

import GenRGenS.*;
import GenRGenS.utility.*;


/**
 * A class for the context-free grammar (CFG) on Normalized Form,
 * with counting facilites, double version (uses 64 bits floats)
 * @author Fr&eacute;d&eacute;ric Sarron
 * @version 1.0
 */

public class DoubleCountedNCFG
		extends NormalContextFreeGrammar
		implements Generator
{
		/*=====================================================================
			                         ATTRIBUTS
		=====================================================================*/

		// le nombre de mot de taille n derive par l'auxiliaire
		// howMany[nt][size] = nombre de mots de taille "size" derive de "nt"
		private double[][] howMany;
		// liste donnant l'ordre de denombrement des structures
		private int[] orderList;

    private Random rdm = new Random(System.currentTimeMillis());


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

		public DoubleCountedNCFG(String source)
			throws BadGrammarException,IOException
		{
		  this(new ContextFreeGrammar(source));
		}

		public DoubleCountedNCFG(File source)
			throws BadGrammarException,IOException
		{
		  this(new ContextFreeGrammar(source));
		}

		public DoubleCountedNCFG(Reader source)
			throws BadGrammarException,IOException
		{
		  this(new ContextFreeGrammar(source));
		}

		public DoubleCountedNCFG(ContextFreeGrammar cfg)
				throws BadGrammarException
		{
				super(cfg);
				howMany = new double[nonTerminaux.length][2];
				makeOrderList();
				makeInitialCount();
		};

		public DoubleCountedNCFG(ContextFreeGrammar cfg, BigDecimal[] masses)
				throws BadGrammarException
		{
				super(cfg);
				howMany = new double[nonTerminaux.length][2];
				terminalsMasses = masses;
				makeOrderList();
				makeInitialCount();
		};

		// le denombrement est effectue a l'initialisation
		// "size" doit etre >=1
		public DoubleCountedNCFG(ContextFreeGrammar cfg, int size)
				throws BadGrammarException
		{
			  super(cfg);
				if (size<1)
						throw(new
									IllegalArgumentException("DoubleCountedNCFG(ContextFreeGrammar, int) demand a size >0"));
				else
						{
								howMany = new double[nonTerminaux.length][size+1];
								makeOrderList();
								makeInitialCount();
								count(size);
						};
		};


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

		private void makeInitialCount()
		{
				int nt;
				double n0,n1;
				NormalContextFreeGrammarProduction prod;
        if (GenRGenS.verbose)
        { GenRGenS.err.println("Computing initial count (0 and 1 sizes) ..."); }
				for (int numProd=0;numProd<productions.length;numProd++)
						{

								nt = (prod=productions[numProd]).getLHS();
								if (!(prod instanceof NormalContextFreeGrammarProductionUnion))
										{
												if (prod instanceof
														NormalContextFreeGrammarProductionTerminal)
														if (prod.isEpsilonProduction())
																{	n0=0;	n1=1;	}
														else
																{
																		n0=0;
																		n1=terminalsMasses
																				[-((NormalContextFreeGrammarProductionTerminal) prod).getRHS()-1].doubleValue();
																}
												else
														// auxiliaire engendrant un produit
														n0 = n1 = 0;
												howMany[nt][0]=n0;
												howMany[nt][1]=n1;
										};
						};

        if (GenRGenS.verbose)
        { GenRGenS.err.println("Sorting union rules ..."); }
				// cas des productions engendrant des unions
				for (int n=0;n<orderList.length;n++)
						if ((prod=productions[nt=orderList[n]]) instanceof
								NormalContextFreeGrammarProductionUnion)
								{
										howMany[nt][0]=
													(((NormalContextFreeGrammarProductionUnion)
														prod).canProduceEpsilon(productions)
													 ? 0 : 1);
										howMany[nt][1]=countUnion(nt,1);
								};
		};

		private void makeOrderList()
		{
				Vector ordreTemp = new Vector();
				Vector alternativesRestantes = new Vector();
				Vector productionsTerminales = new Vector();
				NormalContextFreeGrammarProduction nprod;

        if (GenRGenS.verbose)
        { GenRGenS.err.println("Converting grammar to Chomsky Normal Form ..."); }
				// les produits sont denombres en premier
				for (int numProd=0;numProd<nonTerminaux.length;numProd++)
						if ((nprod = productions[numProd])
								 instanceof NormalContextFreeGrammarProductionProduct)
									ordreTemp.add(new Integer(nprod.getLHS()));
						else
								if (nprod
										instanceof NormalContextFreeGrammarProductionTerminal)
										productionsTerminales.add(new Integer(nprod.getLHS()));
								else
										if (nprod
												instanceof NormalContextFreeGrammarProductionUnion)
												alternativesRestantes.add(nprod);

				// tri topologique des alternatives pour l'ordre de denombrement
				NormalContextFreeGrammarProductionUnion prod;
				while (!alternativesRestantes.isEmpty())
						for (int numAlt=0;numAlt<alternativesRestantes.size();)
								{
										prod = ((NormalContextFreeGrammarProductionUnion)
														alternativesRestantes.get(numAlt));
										if (prod.isNowCountable(ordreTemp, productionsTerminales))
												// cette regle est denombrable en fonction
												// de celles qui le sont deja
												{
														alternativesRestantes.remove(numAlt);
														ordreTemp.add(new Integer(prod.getLHS()));
												}
										else numAlt++;
								};

				// obtention final de la liste (ne pas la trier !)
				// des denombrement
				Object[] preOrderList = ordreTemp.toArray();
				orderList = new int[preOrderList.length];
				for (int i=0;i<orderList.length;i++)
						orderList[i]=((Integer) preOrderList[i]).intValue();
		};


		// procedure de denombrement
		// version iterative
		public void count(int size)
		{
				if (size>howMany[0].length-1)
						// il y a des chose a compter
						{
                if (GenRGenS.verbose)
                { GenRGenS.err.println("Extending table :"); }
								double[][] howManySave = howMany;
								howMany = new double[nonTerminaux.length][size+1];
								
								for (int nt=0;nt<nonTerminaux.length;nt++)
										for (int taille=0;taille<howManySave[0].length;taille++)
												howMany[nt][taille]=howManySave[nt][taille];

                if (GenRGenS.verbose)
                { GenRGenS.err.println("  Terminal Productions ..."); }
								// cas des productions terminales
								NormalContextFreeGrammarProduction prod;
								int nt;
								for (int numProd=0;numProd<productions.length;numProd++)
										if ((prod=productions[numProd])
												instanceof NormalContextFreeGrammarProductionTerminal)
												{
														nt =	prod.getLHS();
														for (int taille=howManySave[0].length;
																 taille<howMany[nt].length;
																 taille++)
																howMany[nt][taille] = 0;
												};

                if (GenRGenS.verbose)
                { GenRGenS.err.print("  Unions and Products ."); }
								long step =   ((howMany[0].length - howManySave[0].length)
								            * orderList.length)/50;
								long toNext = step;
								
								// calcul des nouvelles valeurs
								for (int taille=howManySave[0].length;
										 taille<howMany[0].length;
										 taille++)
								{
										for (int i=0;i<orderList.length;i++)
										{
												if ((prod = productions[nt=orderList[i]])
														instanceof NormalContextFreeGrammarProductionUnion)
												{
													howMany[nt][taille]=countUnion(nt,taille);
												}
												else
												{
													if (prod instanceof
															NormalContextFreeGrammarProductionProduct)
													{
															howMany[nt][taille]=countProduct(nt,taille);
													}
												}
										
                        if (GenRGenS.verbose)
                        { 
						      			  toNext--;
								      	  if (toNext == 0)
									        {
    									      toNext = step;
                            GenRGenS.err.print("."); 
				    					    }
						    			  }
									  }
								}
                GenRGenS.err.println(""); 
						};
		};

		public double count(int nt, int size)
		{
				return(howMany[nt][size]);
		};

		// procedure de denombrement d'une union
		private double countUnion(int aux, int size)
		{
				int[] rhs = ((NormalContextFreeGrammarProductionUnion)
										 productions[aux]).getRHS();
				double temp = 0;
				for (int indexRHS=0;indexRHS<rhs.length;indexRHS++)
						temp += howMany[rhs[indexRHS]][size];
				return(temp);
		}

		// procedure de denombrement d'un produit
		private double countProduct(int aux, int size)
		{
				NormalContextFreeGrammarProductionProduct prod =
						(NormalContextFreeGrammarProductionProduct) productions[aux];
				int nt1 = prod.getNT1();
				int nt2 = prod.getNT2();
				double temp = 0;
				for (int k=1;k<size;k++)
						temp += howMany[nt1][k] * howMany[nt2][size-k];
				return(temp);
		};

		protected String toStringDebugHowMany()
		{
				String temp="";
				for (int i=0;i<howMany.length;i++)
						for (int j=0;j<howMany[i].length;j++)
										temp+="hm["+i+"]["+j+"] = "+howMany[i][j]+"\n";
				return(temp);
		}

		/* fonction de generation d'un mot du langage
			 version litterale */
		public StringBuffer generateRandomWord(int size)
				throws GenerationException
		{
				Vector motResultatToken = generateTokenizedRandomWord(size);
				StringBuffer motResultat = new StringBuffer();
				String wordSpacing = words ? " " : "";
				if (motResultatToken.size()>0)
						{
								motResultat.append
										( terminaux
											[((Integer) motResultatToken.get(0)).intValue()]
											);
								for (int index=1; index<motResultatToken.size(); index++)
										{
												motResultat.append(wordSpacing);
												motResultat.append
														( terminaux
															[
															 ((Integer) motResultatToken.get(index))
															.intValue()
															]
													);
										};
						};
				return motResultat;
		};

		/* fonction de generation d'un mot du langage
			 version tokenisee */
		public Vector generateTokenizedRandomWord(int size)
				throws GenerationException
		{
				count(size);
				if (howMany[symbolStart][size]==0)
						throw
								new GenerationException("No word of size "+size+" to generate");

				// preparation du tableau de correspondance index->Integer(index)
				// utilise pour eviter le gachi de memoire
				// ce qui peut-etre important dans le cas d'une sequence tres longue
				Integer[] int2Integer=new Integer[terminaux.length];
				for (int termIndex=0; termIndex<int2Integer.length; termIndex++)
						int2Integer[termIndex]=new Integer(termIndex);
				// declaration et initialisation des variables locales
				Vector motResultatToken = new Vector();
				int lhs, partialSize;
				NormalContextFreeGrammarProduction prod;
				// pile des tailles de structures a generer
				Stack sizeStack = new Stack();
				// pile des symboles LHS bases de sous-structures
				Stack ntStack = new Stack();

				// point de separation du produit
				int productCutPoint;
				// index du terminal
				int terminalIndex;
				// initialisation de la pile
				sizeStack.push(new Integer(size));
				ntStack.push(new Integer(symbolStart));
				// boucle sur les piles de generation
        try
        {
				  while(!sizeStack.empty())
						{
								partialSize = ((Integer) sizeStack.pop()).intValue();
								lhs = ((Integer) ntStack.pop()).intValue();
								prod = productions[lhs];
								if (prod instanceof NormalContextFreeGrammarProductionProduct)
										{
												productCutPoint = randomProductCutPoint(lhs,
																																partialSize,
																																rdm);
												sizeStack.push(new Integer(partialSize-productCutPoint));
												ntStack.push
														(new Integer
														 ( ((NormalContextFreeGrammarProductionProduct)
																prod).getNT2()));
												sizeStack.push(new Integer(productCutPoint));
												ntStack.push
														(new Integer
														 ( ((NormalContextFreeGrammarProductionProduct)
																prod).getNT1()));

										}
								else
										if (prod instanceof NormalContextFreeGrammarProductionUnion)
												{
														sizeStack.push(new Integer(partialSize));
														ntStack.push(new Integer
																				 (randomUnionRHSaux(lhs,
																														partialSize,
																														rdm)));
												}
										else
												// production terminale
												{
														if ((terminalIndex=
															((NormalContextFreeGrammarProductionTerminal) prod)
																 .getRHS())!=0)
																motResultatToken.add(int2Integer[-terminalIndex-1]);
												};

					};
				if (GrammarGenerationConfiguration.ShowStats)
				{  
				  printStats(motResultatToken);
				}
			}
			catch(Exception e)
			{
			  throw new GenerationException("Generation failed : Double capacity exceeded, retry using Arbitrary Precision !");
			}
			return motResultatToken;
		}


		/* randomProductCutPoint(int lhs, int size, Random rdm)
			 donne la taille de la premiere composante du produit a generer,
			 tiree aleatoirement d'apres le nombre de structures de chaque
			 auxiliaire de la RHS */
		private int randomProductCutPoint(int nt, int size, Random rdm)
		{
				NormalContextFreeGrammarProductionProduct prod =
						(NormalContextFreeGrammarProductionProduct) productions[nt];
				int ntRHS1 = prod.getNT1();
				int ntRHS2 = prod.getNT2();
				double alea = howMany[nt][size] * rdm.nextDouble();
				int k=0;
				for (; k<size; k++)
						{
								alea -= howMany[ntRHS1][k] * howMany[ntRHS2][size-k];
								if (alea<0)
										// on passe dans le negatif, c'est le dernier k
										// qui est la coupure
										break;
						}
				return k;
		};

		/* randomUnionRHSaux(int nt, int size, Random rdm)
			 cf randomUnionRHSaux mais pour les productions-unions,
			 a ceci pres que l'entier retourne est un indexe d'auxiliaire */
		private int randomUnionRHSaux(int nt, int size, Random rdm)
		{
					NormalContextFreeGrammarProductionUnion prod =
						(NormalContextFreeGrammarProductionUnion) productions[nt];
					double alea = howMany[nt][size] * rdm.nextDouble();
					int[] rhs = prod.getRHS();
					int indexRHS=0;
					for (; indexRHS<rhs.length; indexRHS++)
						{
								alea -= howMany[rhs[indexRHS]][size];
								if (alea<0)
										// on passe dans le negatif,
										// c'est le dernier aux qu'on choisit
										break;
						};
				return(rhs[indexRHS]);
		};

		/**************************** pour test de la classe ***************/
		private static void main(String[] arg)
		{

				if (arg.length<2)
						{
								GenRGenS.out.println
										("usage : \n"+
										 "\tjava CountedNCFG <size> <number of generation>");
								System.exit(1);
						};

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

				ContextFreeGrammar cfg;
				CountedNCFG cncfg;
				File[] directoryListing =
						(new File("../testfiles/CountedNCFG/").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()+
															".Double.result"));
										}
								catch (IOException e)
										{
												GenRGenS.out.println("Damned ! "+e.toString());
										}
								if (testResult!=null)
										{
												try
														{
															testResult.println
																		("=*=*= Result for file "+
																		 directoryListing[numFichier]+" =*=*=");
															cfg = new ContextFreeGrammar
																		((new File
																			(directoryListing[numFichier].getAbsolutePath())));
															cncfg = new CountedNCFG(cfg);
															cncfg.setSpacedTerminals(false);
															testResult.println
																		("Stored Normalized CFG :\n"+
																		 cncfg.toString());
															testResult.println("\nCounting :");
															cncfg.count(size);
															for (int i=0; i<=size; i++)
																	testResult.println(i+" -> "+
																										 cncfg.count
																										 (cncfg.symbolStart,i)
																										 .toString());
															testResult.println("\nGeneration size "+
																								 arg[0]+" :");
															for (int i=0; i<howMany; i++)
																	{
																			try
																					{
																							testResult.println
																									("*"+(i+1)+"* "+
																									 cncfg.generateRandomWord(size));
																					}
																			catch (GenerationException e)
																					{
																							testResult.
																									println(e.toString());
																					};
																	};
															testResult.println("\n\n\n\n");
															testResult.close();
															GenRGenS.out.println
																	("wrote "+
																	 directoryListing[numFichier].toString()+
																	 ".result");
														}
												catch (IOException e)
														{ testResult.println ("Damned ! "+e.toString()); }
												catch (BadGrammarException e)
														{ testResult.println(e.toString());};
										};

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