/***************************************************************************
                          Ngrams.cpp  -  description
                             -------------------
    begin                : Don Mai 13 2004
    copyright            : (C) 2004 by klaus frieler
    email                : kgf@omniversum.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/
#include "Ngrams.h"
#include "VectorManip.h"

template <class T>
vector<T> getNGram(const vector<T>& seq, const uint start, const uint nLen)
{
   vector<T> ret;
   for(uint i = 0; i<nLen; ++i){
      if(start+i>=seq.size()) break;
      ret.push_back(seq[start+i]);
   }
   return ret;
}

template <class T>
int findNGram(const vector<T>& seq, const vector<T>& nGram, uint start)
{
   bool bFound = true;
   if(seq.empty() || nGram.empty()) return -1;
   for(uint i = start; i<=seq.size()-nGram.size(); ++i){
      //cout<<"First: Testing: "<<seq[i]<<" for "<<nGram[0]<<" at "<<i<<endl;
      if(seq[i] != nGram[0]) continue;
      bFound = true;
      for(uint j = 1; j<nGram.size(); ++j){
         //cout<<"Testing: "<<seq[i+j]<<" for "<<nGram[j]<<" at "<<i+j<<" with j= "<<j<<endl;
         if(seq[i+j] != nGram[j]){
            bFound = false;
            break;
         }
      }
      if(bFound){
         //cout<<"Found at "<<i<<endl;
         return i;
      }
   }

   return -1;
}

template <class T>
vector<uint> findAllNGrams(const vector<T>& seq, const vector<T>& nGram)
{
   vector<uint> l;
   int idx = 0;
   uint start = 0;
   while(idx != -1){
      idx = findNGram<T>(seq, nGram, start);
      if(idx != -1){
         l.push_back(idx);
         start = idx + 1;
      }
   }
   return l;
}

template <class T>
uint getNGramCount(const vector<T>& seq, const vector<T>& nGram)
{
   vector<uint> l = findAllNGrams(seq, nGram);
   return l.size();
   uint nCount = 0;
   int idx = 0;
   uint start = 0;
   while(idx != -1){
      idx = findNGram<T>(seq, nGram, start);
      if(idx != -1){
         nCount++;
         start = idx++ ;
      }
   }
   return nCount;
}

template <class T>
uint getNGramCount(const vector<T>& seq, uint nGramLen)
{
   uint nCount = 0, tmpCount = 0;
   int idx = 0;
   uint start = 0;
   vector<T> nGram;
   list<uint> idz;

   if(seq.size()<nGramLen)
      return 0;

   for(uint i = 0; i<seq.size()-nGramLen; ++i){
      list<uint> l;
      bool bFound = false;
      for(list<uint>::iterator it = idz.begin(); it != idz.end(); ++it){
         if( *it == i){
            bFound = true;
            break;
         }
      }
      if(bFound) continue;
      nGram = getSubVec(seq, i, nGramLen);
      l = findAllNGrams(seq, nGram);
      if(!l.empty()){
         count += l.size();
         idz.merge(l);
      }
   }
   return nCount;
}
template <class T>
uint getAllNGrams(/*in*/const vector<T>& seq, const uint nGramLen, /*out*/ vector<uint>& nGramsIdz, vector<uint>& nGramsFreq)
{
   vector<T> nGram;
   vector<uint> l;
   vector<uint> save;
   //dumpData<T>("GetAllNGrams for ", seq, std::cerr);
   //cerr<<"Ngram length: "<<nGramLen<<endl;
   if(seq.size()<nGramLen)
      return 0;
   nGramsIdz.clear();
   nGramsFreq.clear();

   for(uint i = 0; i<=seq.size()-nGramLen; ++i){
      //cerr<<"i = "<<i<<endl;
      if(find<uint>(save, i) != -1)
         continue;
      nGram = getSubVector(seq, i, i+nGramLen);
      //dumpData<T>("Testing: ", nGram, std::cerr);
      l.clear();
      l = findAllNGrams(seq, nGram);
      //dumpData<uint>("Found: ", l, std::cerr);
      if(!l.empty()){
         nGramsIdz.push_back(i);;
         save.insert(save.end(), l.begin(), l.end());
         //dumpData<uint>("save", save, std::cerr);
         nGramsFreq.push_back(l.size());
      }
   }
   return nGramsIdz.size();
}


template<class T>
double getNGramWeight(const vector<T>& data1,const vector<T>& data2, uint mode, uint nGramLength)
{
   uint i = 0;
   uint sum = 0;
   double corr = 0;
   int ndx = 0;
   vector<uint> nGramIdz1, nGramFreq1, nGramIdz2, nGramFreq2;
   uint maxSum  = 0;

   if(data1.size()<=nGramLength || data2.size()<=nGramLength){
      if(isEqual<T>(data1, data2)) return 1.0;
      else return 0.0;
   }
   if(getAllNGrams<T>(data1, nGramLength, nGramIdz1, nGramFreq1) == 0){
      return 0.0;
   }
   if(getAllNGrams<T>(data2, nGramLength, nGramIdz2, nGramFreq2) == 0 ){
      return 0.0;
   }

   //dumpData("Mel1", data1);
   //dumpData("idz", nGramIdz1);
   //dumpData("freq", nGramFreq1);
   //dumpData("Mel2", data2);
   //dumpData("idz", nGramIdz2);
   //dumpData("freq", nGramFreq2);
   maxSum = nGramIdz1.size()>nGramIdz2.size()?nGramIdz1.size():nGramIdz2.size();
   vector<T> tmp;
   if(mode & SUM_COMMON || mode & COORDINATE){
      uint freqSum = 0;
      uint nGramCount = 0;
      for( i = 0; i < nGramIdz1.size(); ++i){
         tmp = getNGram<T>(data1, nGramIdz1[i], nGramLength);
         //dumpData("searching NGram:", tmp);
         freqSum += nGramFreq1[i];
         if((ndx = findNGram<T>(data2, tmp, 0)) != -1){
            uint freq2 = getNGramCount(data2, tmp);
            sum += nGramFreq1[i]+ freq2;
            nGramCount++;
            //cout<<"found at "<<ndx<<" Freq1: "<<nGramFreq1[i]<<" Freq2: "<<freq2<<endl;
         }
      }
      if( mode & SUM_COMMON){
         //cout<<"Sum = "<<sum<<" len1 "<<data1.size()<<" len2 = "<<data2.size()<<" nGramLen = "<<nGramLength<<endl;
         corr = (sum+0.0)/(data1.size()+data2.size()-2*nGramLength+2.0);
      }


      else
         corr = (nGramCount +0.0)/(maxSum+0.0);
   }
   else
      if(mode & UKKONEN ){
         vector<uint> doubleIdz;
         vector<uint> idz;
         uint totnGramCount = data1.size()-nGramLength;;
         for( i = 0; i < nGramIdz1.size(); ++i){
            tmp = getNGram<T>(data1, nGramIdz1[i], nGramLength);
            idz = findAllNGrams<T>(data2, tmp);
            //dumpData("searching NGram:", tmp);
            if(!idz.empty()){
               doubleIdz.insert(doubleIdz.end(), idz.begin(), idz.end());
               sum += abs((int)(nGramFreq1[i]-idz.size()));
               //cout<<nGramFreq1[i]<<" - found "<<idz.size()<<" times. Current sum: "<<sum<<endl;
            }
            else{
               sum += nGramFreq1[i];
               //cout<<nGramFreq1[i]<<" - Not found. Current sum: "<<sum<<endl;
            }
         }
         //cout<<endl;
         for( i = 0; i < nGramIdz2.size(); ++i){
            if(find<uint>(doubleIdz, nGramIdz2[i]) != -1)
               continue;
            totnGramCount += nGramFreq2[i];
            tmp = getNGram<T>(data2, nGramIdz2[i], nGramLength);
            idz = findAllNGrams<T>(data1, tmp);
            //dumpData("searching NGram:", tmp);
            if(!idz.empty()){
               sum += abs((int)(nGramFreq2[i]-idz.size()));
               //cout<<nGramFreq2[i]<<" - found "<<idz.size()<<" times. Current sum: "<<sum<<endl;
            }
            else{
               sum += nGramFreq2[i];

               //cout<<nGramFreq2[i]<<" - Not found. Current sum: "<<sum<<endl;
            }
         }
         //corr = 1-(sum +0.0)/(totnGramCount+0.0);
         corr = 1-(sum +0.0)/(data1.size()+data2.size()-2*nGramLength+2.0);
      }

   return corr;
}
