Changeset 7284 for code/trunk/src/libraries/util/StringUtils.cc

Timestamp:

Aug 31, 2010, 3:37:40 AM (14 years ago)

Author:

landauf

Message:

merged consolecommands3 branch back to trunk.

note: the console command interface has changed completely, but the documentation is not yet up to date. just copy an existing command and change it to your needs, it's pretty self-explanatory. also the include files related to console commands are now located in core/command/. in the game it should work exactly like before, except for some changes in the auto-completion.

Location:

code/trunk

Files:

• . (modified) (1 prop)
• src/libraries/util/StringUtils.cc (modified) (3 diffs)

code/trunk/src/libraries/util/StringUtils.cc

@@ -35 +35 @@
 
 #include <cctype>
+#include <boost/scoped_array.hpp>
 #include "Convert.h"
 #include "Math.h"
@@ -514 +515 @@
         @return Number of replacements
     */
-    _UtilExport size_t replaceCharacters(std::string& str, char target, char replacement)
+    size_t replaceCharacters(std::string& str, char target, char replacement)
     {
         size_t j = 0;
@@ -527 +528 @@
         return j;
     }
+
+    /**
+        @brief Calculates the Levenshtein distance between two strings.
+
+        The Levenshtein distance is defined by the number of transformations needed to convert str1
+        into str2. Possible transformations are substituted, added, or removed characters.
+    */
+    unsigned int getLevenshteinDistance(const std::string& str1, const std::string& str2)
+    {
+        size_t cols = str1.size() + 1;
+        size_t rows = str2.size() + 1;
+        boost::scoped_array<int> matrix(new int[rows * cols]);
+
+        for (size_t r = 0; r < rows; ++r)
+            for (size_t c = 0; c < cols; ++c)
+                matrix[r*cols + c] = 0;
+
+        for (size_t i = 1; i < cols; ++i)
+            matrix[0*cols + i] = i;
+        for (size_t i = 1; i < rows; ++i)
+            matrix[i*cols + 0] = i;
+
+        for (size_t r = 1; r < rows; ++r)
+            for (size_t c = 1; c < cols; ++c)
+                matrix[r*cols + c] = (str1[c-1] != str2[r-1]);
+
+        for (size_t r = 1; r < rows; ++r)
+            for (size_t c = 1; c < cols; ++c)
+                matrix[r*cols + c] = std::min(std::min(matrix[(r-1)*cols + c] + 1,
+                                                       matrix[r*cols + c-1] + 1),
+                                              matrix[(r-1)*cols + c-1] + (str1[c-1] != str2[r-1]));
+
+        return matrix[(rows-1)*cols + cols-1];
+    }
 }