Chris@11: 
Chris@11: #include "EditDistance.h"
Chris@11: 
Chris@11: namespace ClassicalData
Chris@11: {
Chris@11: 
Chris@11: int
Chris@11: EditDistance::calculate(QString a, QString b)
Chris@11: {
Chris@11:     // Note: restricted Damerau-Levenshtein edit distance, or
Chris@11:     // Levenshtein if NoTransposition
Chris@11: 
Chris@11:     int al = a.length() + 1;
Chris@11:     int bl = b.length() + 1;
Chris@11: 
Chris@11:     int *currRow = (int *)alloca(sizeof(int) * bl);
Chris@11:     int *prevRow = (int *)alloca(sizeof(int) * bl);
Chris@11:     int *ppreRow = (int *)alloca(sizeof(int) * bl);
Chris@11:     int *tmp = 0;
Chris@11:     
Chris@11:     for (int i = 0; i < bl; ++i) {
Chris@11: 	prevRow[i] = i * m_editPenalty;
Chris@11:     }
Chris@11: 
Chris@11:     for (int j = 1; j < al; ++j) {
Chris@11: 	currRow[0] = j * m_editPenalty;
Chris@11: 	for (int i = 1; i < bl; ++i) {
Chris@11: 	    if (a[j-1] == b[i-1]) {
Chris@11: 		currRow[i] = prevRow[i-1];
Chris@11: 	    } else {
Chris@11: 		int horizontal, vertical, diagonal;
Chris@11: 		horizontal = currRow[i-1] + m_editPenalty;
Chris@11: 		diagonal   = prevRow[i-1] + m_editPenalty;
Chris@11: 		if (i+1 == bl) vertical = prevRow[i] + m_suffixPenalty;
Chris@11: 		else vertical = prevRow[i] + m_editPenalty;
Chris@11: 		currRow[i] =
Chris@11: 		    std::min(horizontal, std::min(vertical, diagonal));
Chris@11: 	    }
Chris@11: 	    if (m_transpositionMode == RestrictedTransposition) {
Chris@11: 		if (i > 1 && j > 1 && a[i-1]==b[j-2] && a[i-2]==b[j-1]) {
Chris@11: 		    currRow[i] = std::min(currRow[i],
Chris@11: 					  ppreRow[i-2] + m_editPenalty);
Chris@11: 		}
Chris@11: 	    }
Chris@11: 	}
Chris@11: 	tmp = ppreRow;
Chris@11: 	ppreRow = prevRow;
Chris@11: 	prevRow = currRow;
Chris@11: 	currRow = tmp;
Chris@11:     }
Chris@11: 
Chris@11:     int result = prevRow[bl-1];
Chris@11:     if (m_normalise) {
Chris@11: 	result = result / m_editPenalty;
Chris@11: 	if (result % m_editPenalty) ++result;
Chris@11:     }
Chris@11:     return result;
Chris@11: }
Chris@11: 
Chris@11: }
Chris@11: