/***************************************************************************
                          EditDistance.cpp  -  description
                             -------------------
    begin                : Don Mai 8 2003
    copyright            : (C) 2003 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 "EditDistance.h"
#include  "Types.h"

inline
double min3(const double a, const  double b, const double c)
{
   double min = a < b ? a : b;
   return  min < c ? min : c;
}

template<class T>
double EditDistance<T>::calcDistance(const T s, const uint n,  const T t, const uint m)
{
   uint i = 0;
   double **d;
   double dRet = 0.0;
   //if( s == 0  || t == 0 ) return 0;
   if( n == 0 || m == 0) return 0;

   d = new double*[n + 1];
   if ( !d ) return 0;
   for(i = 0; i < n + 1; i++){
      d[i] = new double[m + 1];
      if( !d[i] ) goto out;
   }
   d[0][0] = 0;

   for(i = 1; i<n + 1; ++i){
      d[i][0] = i;
      for(uint j = 1; j<m + 1 ; ++j){
         if(i==1)d[0][j] = j;
         double cost = m_pCost(static_cast<double>(s[i-1]),static_cast<double>(t[j-1]));
         d[i][j] = min3( d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + cost);
         //cerr<<d[i][j]<<" ";
      }
      //cerr<<endl;
   }

   dRet = d[n][m];
   
out:

   for(i = 0; i<n + 1; i++){
      if(d[i]) delete[] d[i];
   }
   if(d)delete[]d;
   return dRet;
}

template<class T>
double EditDistance<T>::operator()  (const T s, const uint sLen, const T t, const uint tLen)
{
   return calcDistance(s, sLen, t, tLen);
}

template<class T>
double EditDistance2<T>::calcDistance(const T* s, uint sLen, const T* t, uint tLen)
{
   uint i = 0;
   vector<T> sV, tV;
   if( s == 0){
      if( t != 0) return tLen;
      return 0;
   }
   if( t == 0){
      if( s != 0) return sLen;
      return 0;
   }
   for(i = 0; i<sLen; ++i)
      sV.push_back(s[i]);
   for(i = 0; i<tLen; ++i)
      tV.push_back(t[i]);
      
   return calcDistance(sV, tV);
}

template<class T>
double EditDistance2<T>::calcDistance(const vector<T>& s, const vector<T>& t)
{
   uint i = 0;
   double **d;
   double dRet = 0.0;
   uint n = s.size(),m = t.size();
   
   if( n == 0 || m == 0){
     if(n == 0) return m;
     return n; 
   } 
   d = new double*[n + 1];
   if ( !d ) return 0;
   for(i = 0; i < n + 1; i++){
      d[i] = new double[m + 1];
      if( !d[i] ) goto out;
   }

   d[0][0] = 0;

   for(i = 1; i <= n; ++i){
      d[i][0] = d[i-1][0] + m_pCost->costDelete(s[i-1]);
      for(uint j = 1; j <= m; ++j){
         if(i==1)d[0][j] = d[0][j-1] + m_pCost->costInsert(t[j-1]);
         d[i][j] = min3( d[i-1][j]   + m_pCost->costDelete(s[i-1]),
                         d[i][j-1]   + m_pCost->costInsert(t[j-1]),
                         d[i-1][j-1] + m_pCost->costSubstitute(s[i-1], t[j-1]));
         //cerr<<"Cost("<<i<<","<<j<<")  = "<<d[i][j]<<" "<<endl;
      }
      //cerr<<endl;
   }
   m_dMaxDist = d[n][0];
   if(d[0][m]> m_dMaxDist) m_dMaxDist = d[0][m];
   dRet = d[n][m];

out:

   for(i = 0; i<n + 1; i++){
      if(d[i]) delete[] d[i];
   }
   if(d)delete[]d;
   return dRet;
}

