From a762b470185f27dbca6d75e58a29e3a055b2969c Mon Sep 17 00:00:00 2001
From: Marcus Eggenberger <egs@quassel-irc.org>
Date: Sun, 30 Sep 2007 17:05:16 +0000
Subject: [PATCH] Added uint editingDistance(const QString &s1, const QString
 &s2) for string comparision

---
 src/common/util.cpp | 35 +++++++++++++++++++++++++++++++++++
 src/common/util.h   |  2 +-
 2 files changed, 36 insertions(+), 1 deletion(-)

diff --git a/src/common/util.cpp b/src/common/util.cpp
index 1c3d9058..47541eef 100644
--- a/src/common/util.cpp
+++ b/src/common/util.cpp
@@ -97,3 +97,38 @@ bool readDataFromDevice(QIODevice *dev, quint32 &blockSize, QVariant &item) {
   in >> item;
   return true;
 }
+
+
+uint editingDistance(const QString &s1, const QString &s2) {
+  uint n = s1.size()+1;
+  uint m = s2.size()+1;
+  uint matrix[n][m];
+
+  for(uint i = 0; i < n; i++)
+    matrix[i][0] = i;
+
+  for(uint i = 0; i < m; i++)
+    matrix[0][i] = i;
+
+  uint min;
+  for(uint i = 1; i < n; i++) {
+    for(uint j = 1; j < m; j++) {
+      uint deleteChar = matrix[i-1][j] + 1;
+      uint insertChar = matrix[i][j-1] + 1;
+
+      if(deleteChar < insertChar)
+	min = deleteChar;
+      else
+	min = insertChar;
+      
+      if(s1[i-1] == s2[j-1]) {
+	uint inheritChar = matrix[i-1][j-1];
+	if(inheritChar < min)
+	  min = inheritChar;
+      }
+
+      matrix[i][j] = min;
+    }
+  }
+  return matrix[n-1][m-1];
+}
diff --git a/src/common/util.h b/src/common/util.h
index 067bd76e..01797233 100644
--- a/src/common/util.h
+++ b/src/common/util.h
@@ -54,7 +54,7 @@ void writeDataToDevice(QIODevice *, const QVariant &);
 bool readDataFromDevice(QIODevice *, quint32 &, QVariant &);
 
 
-
+uint editingDistance(const QString &s1, const QString &s2);
 
 
 #endif
-- 
2.20.1