Chris@11: 
Chris@11: #include "EditDistance.h"
Chris@17: #include <algorithm>
Chris@11: 
Chris@13: #include <cstdlib> // abs
Chris@13: 
Chris@11: namespace ClassicalData
Chris@11: {
Chris@11: 
Chris@11: int
Chris@13: EditDistance::calculate(QString a, QString b, int threshold)
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@13:     if (threshold > 0 && abs(al - bl) > threshold) return threshold + 1;
Chris@13: 
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@28: 	prevRow[i] = i;
Chris@11:     }
Chris@11: 
Chris@11:     for (int j = 1; j < al; ++j) {
Chris@28: 	currRow[0] = j;
Chris@13: 	bool stillAcceptable = (threshold == 0);
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@28: 		horizontal = currRow[i-1] + 1;
Chris@28: 		diagonal   = prevRow[i-1] + 1;
Chris@28: 		if (i+1 == bl) vertical = prevRow[i] + 1;
Chris@28: 		else vertical = prevRow[i] + 1;
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@28: 		    currRow[i] = std::min(currRow[i], ppreRow[i-2] + 1);
Chris@11: 		}
Chris@11: 	    }
Chris@13: 	    if (threshold > 0 && currRow[i] <= threshold) {
Chris@13: 		stillAcceptable = true;
Chris@13: 	    }
Chris@11: 	}
Chris@13: 	if (!stillAcceptable) return threshold + 1;
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:     return result;
Chris@11: }
Chris@11: 
Chris@11: }
Chris@11: