/******************************************************************************
IrstLM: IRST Language Model Toolkit
Copyright (C) 2006 Marcello Federico, ITC-irst Trento, Italy

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library 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
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA

******************************************************************************/

#include <cmath>
#include <string>
#include <assert.h>
#include "mfstream.h"
#include "mempool.h"
#include "htable.h"
#include "dictionary.h"
#include "n_gram.h"
#include "mempool.h"
#include "ngramtable.h"
#include "normcache.h"
#include "interplm.h"
#include "mdiadapt.h"
#include "shiftlm.h"

using namespace std;


//
//Minimum discrimination adaptation for interplm
//
mdiadaptlm::mdiadaptlm(char* ngtfile,int depth,TABLETYPE tbtype):
  interplm(ngtfile,depth,tbtype){
  adaptlev=0;
  forelm=NULL;
  cache=NULL;
};


int mdiadaptlm::scalefact(char *ngtfile){
  if (forelm!=NULL) delete forelm;
  if (cache!=NULL) delete cache;
  cache=new normcache(dict);

  forelm=new shiftbeta(ngtfile,1); 
  forelm->train();

  //compute oov scalefact term
  ngram fng(forelm->dict,1); 
  ngram ng(dict,1);
  int* w=fng.wordp(1);

  oovscaling=1.0;
  for ((*w)=0;(*w)<forelm->dict->size();(*w)++)
    if ((*w) != forelm->dict->oovcode()){
      ng.trans(fng);
      if (*ng.wordp(1)==dict->oovcode())
	{
	  cerr << "fg lm contains new words: use -ao=yes option\n";
	  exit(1);
	}
      //forbidden situation
      oovscaling-=backunig(ng);
    }
  *w=forelm->dict->oovcode();
  oovscaling=foreunig(fng)/oovscaling;

  return 1;
};


double mdiadaptlm::scalefact(ngram ng){
  ngram fng(forelm->dict,1);
  fng.trans(ng);
  if (*fng.wordp(1)==forelm->dict->oovcode())
    return pow(oovscaling,gis_step);
  else{
    double prback=backunig(ng);
    double prfore=foreunig(ng);
    return pow(prfore/prback,gis_step);
  }
}


double mdiadaptlm::foreunig(ngram ng){

  double fstar,lambda;
  
  forelm->discount(ng,1,fstar,lambda);
  
  return fstar;
}

double mdiadaptlm::backunig(ngram ng){

  double fstar,lambda;
  
  discount(ng,1,fstar,lambda,0);
  
  return fstar;
};



int mdiadaptlm::adapt(char* ngtfile,int alev,double step){
  
  if (alev > lmsize() || alev<=0){
    cerr << "setting adaptation level to " << lmsize() << "\n";
    alev=lmsize();
  }
  adaptlev=alev;
  

  cerr << "adapt ....";
  gis_step=step;
  
  if (ngtfile==NULL){
    cerr << "adaptation file is missing\n";
    exit(1);
  }

  //compute the scaling factor;
  
  scalefact(ngtfile);
  
  //compute 1-gram zeta
  ngram ng(dict,2); 
  int* w=ng.wordp(1);
  
  cerr << "precomputing 1-gram normalization ...\n";
  zeta0=0;  
  for ((*w)=0;(*w)<dict->size();(*w)++)
    zeta0+=scalefact(ng) * backunig(ng);

  if (alev==1) return 1 ;

  cerr << "precomputing 2-gram normalization:\n";

  //precompute the bigram normalization
  w=ng.wordp(2);
  *ng.wordp(1)=0;

  for ((*w)=0;(*w)<dict->size();(*w)++){
    zeta(ng,2);
    if ((*w % 1000)==0) cerr << "."; 
  }

  cerr << "done\n";

  return 1;
};


double mdiadaptlm::zeta(ngram ng,int size){
  
  assert(size>=1);
  
  double z; // compute normalization term

  ng.size=size;
  
  if (size==1) return zeta0;
  else{ //size>1
    
    //check in the 2gr and 3gr cache
    if (cache->get(ng,size,z)) return z;     
    
    double fstar,lambda;
    ngram histo=ng;    
    int succ=0;
    
    discount(ng,size,fstar,lambda,(int)0);
    
    if ((lambda<1) && get(histo,size,size-1)){;
      
      //scan all its successors
      succ=0;
      
      succscan(histo,ng,INIT,size); 
      while(succscan(histo,ng,CONT,size)){
        
        discount(ng,size,fstar,lambda,0);
        if (fstar>0){
          z+=(scalefact(ng) * fstar);
          succ++;
          //cerr << ng << "zeta= " << z << "\n";
        }
      }
    }
    
    z+=lambda*zeta(ng,size-1);
    
    if ((size==2) || (succ>1))
      cache->put(ng,size,z);
    
    return z;
  }

}


int mdiadaptlm::discount(ngram ng_,int size,double& fstar,double& lambda,int cv){

  ngram ng(dict);ng.trans(ng_);
  
  discount(ng,size,fstar,lambda,0);

  if ((size>0) && (size<=adaptlev) && (lambda<1)){

    if (size>1){

      //compute new lambda and fstar
      double z=zeta(ng,size);
      double z1=zeta(ng,size-1);
      
      lambda=lambda * z1/z;
      fstar=scalefact(ng) * fstar/z;
    }
    else if (size==1){ 
      double alpha=scalefact(ng);
      
      fstar=alpha*fstar/zeta0;
      lambda=lambda*alpha/zeta0;
    }
    else{
      //size==0 do nothing
    }
  }

  return 1;
}


int mdiadaptlm::compute_backoff(){
  
  double fstar,lambda;

  cerr << "compute backoff probabilities ...";

  this->backoff=1;

  for (int size=1;size<lmsize();size++){

    ngram hg(dict,size); 
    
    //cerr << "size " << size << "\n";

    scan(hg,INIT,size);

    while(scan(hg,CONT,size)){

      //cerr << hg << "\n" << "successors:\n";
      
      ngram ng=hg;ng.pushc(0);

      double pr=1.0;
      
      succscan(hg,ng,INIT,size+1); 

      while(succscan(hg,ng,CONT,size+1)){

	mdiadaptlm::discount(ng,size+1,fstar,lambda);	

	if (fstar>0)

	  pr-=mdiadaptlm::prob(ng,size);
	
      }
      
      assert(pr>0 && pr<=1);
      
      boff(hg.link,pr);
	
    }
    
  }



  cerr << "done\n";

  return 1;
}



double mdiadaptlm::prob2(ngram ng,int size,double& fstar){

  double lambda;
  
  mdiadaptlm::discount(ng,size,fstar,lambda);
  
  if (size>1)
    return fstar  + lambda * prob(ng,size-1);
  else
    return fstar;
}


//inline double mdiadaptlm::prob(ngram ng,int size){
double mdiadaptlm::prob(ngram ng,int size){
	double fstar,lambda,bo;
 	return prob(ng,size,fstar,lambda,bo);
}

double mdiadaptlm::prob(ngram ng,int size,double& fstar,double& lambda, double& bo){  
  mdiadaptlm::bodiscount(ng,size,fstar,lambda,bo);
  
  if (fstar >1.0000001 || lambda >1.0000001){
    cerr << "wrong probability: " << ng 
	 << " , size " << size
	 << " , fstar " << fstar 
	 << " , lambda " << lambda << "\n";
    exit(1);
  }

  if (backoff){
    
    if (size>1){
      if (fstar>0) return fstar;
      else{
	if (lambda<1)
	  return lambda/bo * prob(ng,size-1);
	else{
	  assert(lambda < 1.00000001);
	  return prob(ng,size-1);
	}
      }
    }
    else
      return fstar;
  }

  else{ //interpolation

    if (size>1)
      return fstar  + lambda * prob(ng,size-1);
    else
      return fstar;
  }
}




int mdiadaptlm::bodiscount(ngram ng_,int size,double& fstar,double& lambda,double& bo){
  ngram ng(dict);ng.trans(ng_);

  mdiadaptlm::discount(ng,size,fstar,lambda);

  bo=1.0;
  
  if (backoff){ //get back-off probability 

    if (size>1 && lambda<1){
      
      ngram hg=ng;
      
      assert(get(hg,size,size-1));
      
      bo=boff(hg.link);
      
    }
  }  
 
  return 1;
}


double mdiadaptlm::txclprob(ngram ng,int size){

  double fstar,lambda;

  if (size>1){
    mdiadaptlm::discount(ng,size,fstar,lambda);
    return fstar  + lambda * txclprob(ng,size-1);
  }
  else{
    double freq=1;
    if ((*ng.wordp(1)!=dict->oovcode()) && get(ng,1,1))
      freq+=ng.freq;

    double N=totfreq()+dict->dub()-dict->size();
    return freq/N;
  }
}


int mdiadaptlm::netsize(){
  double fstar,lambda;
  int size,totsize;
  ngram ng(dict);
  
  cerr << "Computing LM size:\n";
  
  totsize=dict->size() * 2;

  cout << "1-gram " << totsize << "\n";

  for (int i=2;i<=maxlevel();i++){

    size=0;
    
    scan(ng,INIT,i);
    
    while (scan(ng,CONT,i)){
      
      mdiadaptlm::discount(ng,i,fstar,lambda);
      
      if (fstar>0) size++;
      
    }
    
    size+=size * (i<maxlevel());

    totsize+=size;
    
    cout << i << "-gram " << totsize << "\n";
    
  }
  
  return totsize;
}



/*
 * trigram file format:

 --------------------------------

   <idx> dictionary length

   repeat [ dictionary length ] {
        <newline terminated string> word;
   }

   while [ first word != STOP ] {
        <idx> first word
        <idx> number of successors
        repeat [ number of successors ] {
                <idx>   second word
                <float> prob
        }
   }

   <idx> STOP

   while [ first word != STOP ] {
            <idx> first word
	    <idx> number of successor sets
	         repeat [ number of successor sets ] {
		        <idx>   second word
			<idx>   number of successors
			repeat [ number of successors ] {
			      <idx>   third word
			      <float> prob
			}
		 }
   }

   <idx> STOP

*/


//void writeNull(mfbstream& out,unsigned short nullCode,float nullProb){
//  out.writex(&nullCode,sizeof(short));
//  out.writex(&nullProb,sizeof(float));
//}


int swapbytes(char *p, int sz, int n)
{
  char c,*l,*h;
  if((n<1) ||(sz<2)) return 0;
  for(; n--; p+=sz) for(h=(l=p)+sz; --h>l; l++) { c=*h; *h=*l; *l=c; }
  return 0;
};

void fwritex(char *p,int sz,int n,FILE* f){

  if(*(short *)"AB"==0x4241){
    swapbytes((char*)p, sz,n);
  }
  
  fwrite((char *)p,sz,n,f);
  
  if(*(short *)"AB"==0x4241) swapbytes((char*)p, sz,n);
  
}

void ifwrite(long loc,void *ptr,int size,int n,FILE* f)
{
  fflush(f);

  long pos=ftell(f);
   
  fseek(f,loc,SEEK_SET);
   
  fwritex((char *)ptr,size,1,f);
  
  fseek(f,pos,SEEK_SET);
   
  fflush(f);
}

void writeNull(unsigned short nullCode,float nullProb,FILE* f){
  fwritex((char *)&nullCode,sizeof(short),1,f);
  fwritex((char *)&nullProb,sizeof(float),1,f);
}


int mdiadaptlm::saveASR(char *filename,int backoff,char* subdictfile){
  int totbg,tottr;

  dictionary* subdict;

  if (subdictfile)
    subdict=new dictionary(subdictfile);
  else
    subdict=dict; // default is subdict=dict

  typedef unsigned short code;
  
  system("date");

  if (lmsize()>3 || lmsize()<1)
    {
      cerr << "wrong lmsize\n";
      exit(1);
    }
  
  if (dict->size()>=0xffff && subdict->size()>=0xffff)
    {
      cerr << "save bin requires unsigned short codes\n";
      exit(1);
    }

  FILE* f=fopen(filename,"w");
  
  double fstar,lambda,boff;
  float pr;
  long succ1pos,succ2pos;
  code succ1,succ2,w,h1,h2;
  code stop=0xffff;

  //dictionary
  //#dictsize w1\n ..wN\n NULL\n

  code oovcode=subdict->oovcode();
  
  //includes at least NULL
  code subdictsz=subdict->size()+1; 

  fwritex((char *)&subdictsz,sizeof(code),1,f);

  subdictsz--;
  for (w=0;w<subdictsz;w++)
    fprintf(f,"%s\n",(char *)subdict->decode(w));
  
  fprintf(f,"____\n");

  //unigram part 
  //NULL #succ w1 pr1 ..wN prN
  
  h1=subdictsz;  
  fwritex((char *)&h1,sizeof(code),1,f); //NULL

  succ1=0;succ1pos=ftell(f);
  fwritex((char *)&succ1,sizeof(code),1,f);

  ngram ng(dict);  
  ngram sng(subdict);

  ng.size=sng.size=1;

  scan(ng,INIT,1);
  while(scan(ng,CONT,1))
    {
      sng.trans(ng);
      if (sng.containsWord(subdict->OOV(),1))
	continue;

      pr=(float)mdiadaptlm::prob(ng,1);
      if (pr>1e-50){ //do not consider too low probabilities     
	succ1++;
	w=*sng.wordp(1); 
	fwritex((char *)&w,sizeof(code),1,f);
	fwritex((char *)&pr,sizeof(float),1,f);
      }
      else{
	cerr << "small prob word " << ng << "\n";
      }
    }
    
  // update number of unigrams
  ifwrite(succ1pos,&succ1,sizeof(code),1,f);

  cerr << "finito unigrammi " << succ1 << "\n";
  fflush(f);

  if (lmsize()==1){
    fclose(f);
    return 1;
  }

  // rest of bigrams 
  // w1 #succ w1 pr1 .. wN prN

  succ1=0; h1=subdictsz; totbg=subdictsz;

  ngram hg1(dict,1);

  ng.size=sng.size=2;
  
  scan(hg1,INIT,1);
  while(scan(hg1,CONT,1)){

    if (hg1.containsWord(dict->OOV(),1)) continue;
    
    assert((*hg1.wordp(1))<dict->size());
    
    *ng.wordp(2)=*hg1.wordp(1);
    *ng.wordp(1)=0;
    
    sng.trans(ng);
    if (sng.containsWord(dict->OOV(),1)) continue;

    mdiadaptlm::bodiscount(ng,2,fstar,lambda,boff);

    if (lambda < 1.0){
      
      h1=*sng.wordp(2);
      
      fwritex((char *)&h1,sizeof(code),1,f);

      succ1=0;succ1pos=ftell(f);
      fwritex((char *)&succ1,sizeof(code),1,f);

      ngram shg=hg1;
      get(shg,1,1);
      
      succscan(shg,ng,INIT,2); 
      while(succscan(shg,ng,CONT,2)){
	
	if (*ng.wordp(1)==oovcode) continue;
	
	sng.trans(ng);
	if (sng.containsWord(dict->OOV(),2)) continue;

	mdiadaptlm::discount(ng,2,fstar,lambda);
	
	if (fstar>1e-50){
	  w=*sng.wordp(1);
	  fwritex((char *)&w,sizeof(code),1,f);
	  pr=(float)mdiadaptlm::prob(ng,2);
	  //cerr << ng << " prob=" << log(pr) << "\n";
	
	  fwritex((char *)&pr,sizeof(float),1,f);
	  succ1++;
	}
      }
	
      if (succ1){
	lambda/=boff; //consider backoff
	writeNull(subdictsz,(float)lambda,f);
	succ1++;
	totbg+=succ1;
	ifwrite(succ1pos,&succ1,sizeof(code),1,f);
      }
      else{
	//go back one word
	fseek(f,succ1pos-(streampos)sizeof(code),SEEK_SET);
      }
    }
  }

  fwritex((char *)&stop,sizeof(code),1,f);
  
  cerr << " finito bigrammi! " << subdictsz << "\n";
  fflush(f);

  system("date");

  if (lmsize()<3){
    fclose(f);
    return 1;
  }

  //TRIGRAM PART
   
  h1=subdictsz; h2=subdictsz; tottr=0;
  succ1=0; succ2=0;
  
  ngram hg2(dict,2);
  
  ng.size=sng.size=3;

  scan(hg1,INIT,1);
  while(scan(hg1,CONT,1)){

    if ((*hg1.wordp(1)==oovcode)) continue;
    
    *ng.wordp(3)=*hg1.wordp(1);

    sng.trans(ng);
    if (sng.containsWord(dict->OOV(),1)) continue;

    assert((*sng.wordp(3))<subdictsz);

    h1=*sng.wordp(3);
    fwritex((char *)&h1,sizeof(code),1,f);

    succ1=0;succ1pos=ftell(f);
    fwritex((char *)&succ1,sizeof(code),1,f);

    ngram shg1=ng; get(shg1,3,1);
    
    succscan(shg1,hg2,INIT,2); 
    while(succscan(shg1,hg2,CONT,2)){
	
      if (*hg2.wordp(1)==oovcode) continue;
      
      *ng.wordp(2)=*hg2.wordp(1);
      *ng.wordp(1)=0;
      
      sng.trans(ng);
      if (sng.containsWord(dict->OOV(),2)) continue;

      mdiadaptlm::bodiscount(ng,3,fstar,lambda,boff);
      
      if (lambda < 1.0){
      
	h2=*sng.wordp(2);
	fwritex((char *)&h2,sizeof(code),1,f);

	succ2=0;succ2pos=ftell(f);
	fwritex((char *)&succ2,sizeof(code),1,f);

	ngram shg2=ng;	get(shg2,3,2);
      
	succscan(shg2,ng,INIT,3); 
	while(succscan(shg2,ng,CONT,3)){

	  if (*ng.wordp(1)==oovcode) continue;
	  
	  sng.trans(ng);
	  if (sng.containsWord(dict->OOV(),3)) continue;

	  mdiadaptlm::discount(ng,3,fstar,lambda);
	  //pr=(float)mdiadaptlm::prob2(ng,3,fstar);
	  
	  if (fstar>1e-50){
	    
	    w=*sng.wordp(1);
	    fwritex((char *)&w,sizeof(code),1,f);

	    pr=(float)mdiadaptlm::prob(ng,3);
	  
	    //	    cerr << ng << " prob=" << log(pr) << "\n";
	    fwritex((char *)&pr,sizeof(float),1,f);
	    succ2++;
	  }
	}

	if (succ2){
	  lambda/=boff;
	  writeNull(subdictsz,(float)lambda,f);
	  succ2++;
	  tottr+=succ2;
	  ifwrite(succ2pos,&succ2,sizeof(code),1,f);
	  succ1++;
	}
	else{
	  //go back one word
	  fseek(f,succ2pos-(long)sizeof(code),SEEK_SET);
	}
      }
    }
    
    if (succ1)
      ifwrite(succ1pos,&succ1,sizeof(code),1,f);
    else
      fseek(f,succ1pos-(long)sizeof(code),SEEK_SET);
  }

  fwritex((char *)&stop,sizeof(code),1,f);    

  fclose(f);

  cerr << "Tot bg: " << totbg << " tg: " << tottr<< "\n";

  system("date");

  return 1;
};


///// Save in IRST MT format 

int mdiadaptlm::saveMT(char *filename,int backoff,
		       char* subdictfile,int resolution,double decay){
  
  double logalpha=log(decay);
  dictionary* subdict;

  if (subdictfile)
    subdict=new dictionary(subdictfile);
  else
    subdict=dict; // default is subdict=dict

  ngram ng(dict,lmsize());
  ngram sng(subdict,lmsize());

  cerr << "Adding unigram of OOV word if missing\n";

  for (int i=1;i<=maxlevel();i++)
    *ng.wordp(i)=dict->oovcode();
  
  if (!get(ng,maxlevel(),1)){ 
    cerr << "oov is missing in the ngram-table\n";
    // f(oov) = dictionary size (Witten Bell)
    ng.freq=dict->freq(dict->oovcode());
    cerr << "adding oov unigram " << ng << "\n";
    put(ng);
  }

  cerr << "Eventually adding OOV symbol to subdictionary\n";
  subdict->encode(OOV_);

  system("date");
  
  mfstream out(filename,ios::out);

  //add special symbols
  
  subdict->incflag(1);
  int bo_code=subdict->encode(BACKOFF_);
  int du_code=subdict->encode(DUMMY_);
  subdict->incflag(0);

  out << "nGrAm " << lmsize() << " " << 0 
      << " " << "LM_ " 
      << resolution << " "
      << decay << "\n";
  
  subdict->save(out);

  //start writing ngrams
  
  cerr << "write unigram of oov probability\n";
  ng.size=1; *ng.wordp(1)=dict->oovcode();
  double pr=(float)mdiadaptlm::prob(ng,1);
  sng.trans(ng);sng.size=lmsize();
  for (int s=2;s<=lmsize();s++) *sng.wordp(s)=du_code;
  sng.freq=(int)ceil(pr * (double)10000000)-1;
  out << sng << "\n";
  
  for (int i=1;i<=lmsize();i++){
    cerr << "LEVEL " << i << "\n";

    double fstar,lambda,bo,dummy;

    scan(ng,INIT,i);
    while(scan(ng,CONT,i)){
      
      sng.trans(ng);
      
      sng.size=lmsize();
      for (int s=i+1;s<=lmsize();s++) 
	*sng.wordp(s)=du_code;

      if (i>=1 && sng.containsWord(subdict->OOV(),sng.size)){
	cerr << "skipping : " << sng << "\n";
	continue;
      }
      
      // skip also eos symbols not at the final      
      //if (i>=1 && sng.containsWord(dict->EoS(),sng.size)) 
      //continue;
      
      mdiadaptlm::discount(ng,i,fstar,dummy);
	
      //out << sng << " fstar " << fstar << " lambda " << lambda << "\n";
      //if (i==1 && sng.containsWord(subdict->OOV(),i)){
      //	cerr << sng << " fstar " << fstar << "\n";
      //}
      
      if (fstar>0){
	
	double pr=(float)mdiadaptlm::prob(ng,i);
      
	if (i>1 && resolution<10000000){
	  sng.freq=resolution-(int)(log(pr)/logalpha)-1;
	  sng.freq=(sng.freq>=0?sng.freq:0);
	}
	else
	  sng.freq=(int)ceil(pr * (double)10000000)-1;

	out << sng << "\n";
	  
      }
      
      if (i<lmsize()){ /// write backoff of higher order!!

	ngram ng2=ng; ng2.pushc(0); //extend by one
	mdiadaptlm::bodiscount(ng2,i+1,dummy,lambda,bo);      
	assert(!backoff || (lambda ==1 || bo<1 ));
	
	sng.pushc(bo_code);
	sng.size=lmsize(); 
	
	if (lambda<1){
	  if (resolution<10000000){
	    sng.freq=resolution-(int)(log(lambda/bo)/logalpha)-1;
	    sng.freq=(sng.freq>=0?sng.freq:0);
	  }
	  else
	    sng.freq=(int)ceil(lambda/bo * (double)10000000)-1;
	  
	  out << sng << "\n";
	}
      }
    }
    cerr << "LEVEL " << i << "DONE \n";
  }
  return 1;
};



///// Save in format for ARPA backoff N-gram models

int mdiadaptlm::saveARPA(char *filename,int backoff,char* subdictfile )
{

  system("date");

  //subdict and accumulated unigram oov prob 
  dictionary* subdict; double oovprob=0; 
  if (subdictfile){
    subdict=new dictionary(subdictfile);
    //check that oov word is the last word
    assert(dict->oovcode()==(dict->size()-1));
  }  
  else
    subdict=dict; // default is subdict=dict

  fstream out(filename,ios::out);
  //  out.precision(15);
  
  streampos pos[lmsize()+1];
  int num[lmsize()+1];
  char buff[100];

  //print header
  out << "\n\\data\\" << "\n";
  
  for (int i=1;i<=lmsize();i++){
    num[i]=0;
    pos[i]=out.tellp();
    sprintf(buff,"ngram %2d=%10d\n",i,num[i]);
    out << buff;
  }

  out << "\n";

  //start writing n-grams

	for (int i=1;i<=lmsize();i++){
		
		out << "\n\\" << i << "-grams:\n";
		
		double totp=0;
		double fstar,lambda,bo,dummy,dummy2,pr;
		
		
		ngram ng(dict,1);
		ngram ng2(dict);
		ngram sng(subdict,1);
		
		if (i==1){ //unigram case
			
			//scan the dictionary
			
			for (int w=0;w<dict->size();w++)
			{
				*ng.wordp(1)=w;
				
				sng.trans(ng);        
				pr=mdiadaptlm::prob(ng,1);
				totp+=pr;
				
				if (sng.containsWord(subdict->OOV(),i) && !ng.containsWord(dict->OOV(),i)){
					oovprob+=pr; //accumulate oov probability
					continue;
				}
				
				
				if (ng.containsWord(dict->OOV(),i)) pr+=oovprob;
				
				//cerr << ng << " freq " << dict->freq(w) << " -  Pr " << pr << "\n";
				//out << (pr?log10(pr):-99);
				out << (float) (pr?log10(pr):-99);
								
				num[i]++;
				
				if (w==dict->oovcode())
					out << "\t" << "<unk>\n";
				else{
					out << "\t" << (char *)dict->decode(w);
					
					if (lmsize()>1){
						ngram ng2=ng; ng2.pushc(0); //extend by one
						
						//cerr << ng2 << "\n";
						
						mdiadaptlm::bodiscount(ng2,i+1,fstar,lambda,bo);	  
						assert(!backoff || ((lambda<1.00000001 && lambda>0.99999999) || bo< 1.0000001 ));
						
						if (lmsize()> 1 && lambda < 1.0000001) //output back-off prob 
//							out << "\t" << log10(lambda) -log10(bo);
							out << "\t" << (float) (log10(lambda) - log10(bo));
					}
					out << "\n";
				}
			}
			//cerr << "totprob = " << totp << "\n";
		}
		else{ //i>1 , bigrams, trigrams, fourgrams...
			scan(ng,INIT,i);
			while(scan(ng,CONT,i)){
				
				sng.trans(ng);
				if (sng.containsWord(subdict->OOV(),i)) continue;
				
				// skip also eos symbols not at the final
				if (sng.containsWord(dict->EoS(),i-1)) continue;
				
//				mdiadaptlm::discount(ng,i,fstar,dummy);
//				pr=mdiadaptlm::prob(ng,i);
				pr=mdiadaptlm::prob(ng,i,fstar,dummy,dummy2);
				
				//PATCH by Nicola (16-04-2008)
				/* 
				 if (!(pr<=1.0 && pr > 1e-10)){
				 cerr << ng << " " << pr << "\n";
				 assert(pr<=1.0 && pr > 1e-10);
				 };
				 */
				if (!(pr<=1.0 && pr > 1e-10)){
					cerr << ng << " " << pr << "\n";
					assert(pr<=1.0);
					cerr << "prob modified to 1e-10\n";
					pr=1e-10;
				};
				
				if (i<lmsize()){ 
					ng2=ng; ng2.pushc(0); //extend by one
					
					mdiadaptlm::bodiscount(ng2,i+1,dummy,lambda,bo);
					
					if (fstar>=0.0000000001 || lambda <= 0.9999999999){
						//out << log10(pr);
						out << (float) log10(pr);
						out << "\t" << (char *)dict->decode(*ng.wordp(i));
						for (int j=i-1;j>0;j--) 
							out << " " << (char *)dict->decode(*ng.wordp(j));
						//if (lambda < 0.9999999999)  out << "\t" << log10(lambda/bo);
						if (lambda < 0.9999999999)  out << "\t" << (float) (log10(lambda) - log10(bo));						
						out << "\n";
						num[i]++;
					}
				}
				else
					if (fstar >0.0000000001){
						//out << log10(pr);
						out << (float) log10(pr);
						out << "\t" << (char *)dict->decode(*ng.wordp(i));
						for (int j=i-1;j>0;j--) 
							out << " " << (char *)dict->decode(*ng.wordp(j));
						out << "\n";
						
						num[i]++;
					}
			}
		}
		
		cerr << i << "grams tot:" << num[i] << "\n";
	}

  streampos last=out.tellp();
  
  //update headers
  for (int i=1;i<=lmsize();i++){
    sprintf(buff,"ngram %2d=%10d\n",i,num[i]);
    out.seekp(pos[i]);
    out << buff;
  }
  
  out.seekp(last);
  out << "\\end\\" << "\n";
  system("date");
  
  return 1;
};



/*
main(int argc,char** argv){
  char* dictname=argv[1];
  char* backngram=argv[2];
  int depth=atoi(argv[3]);
  char* forengram=argv[4];
  char* testngram=argv[5];
  
  dictionary dict(dictname);
  ngramtable test(&dict,testngram,depth);
  
  shiftbeta lm2(&dict,backngram,depth);
  lm2.train();
  //lm2.test(test,depth);
  
  mdi lm(&dict,backngram,depth);
  lm.train();
  for (double w=0.0;w<=1.0;w+=0.1){
  lm.getforelm(forengram);
  lm.adapt(w);
  lm.test(test,depth);
  }
}
*/

