Changeset 7238 for code/branches/consolecommands3/src/libraries/util

Timestamp:

Aug 28, 2010, 4:48:48 PM (14 years ago)

Author:

landauf

Message:

added a function to compute the Levenshtein distance between two strings to StringUtils.
used this in CommandEvaluation to correct misspelled commands (not automatically though, just to print a suggestion to the user)

Location:

code/branches/consolecommands3/src/libraries/util

Files:

• StringUtils.cc (modified) (2 diffs)
• StringUtils.h (modified) (1 diff)

code/branches/consolecommands3/src/libraries/util/StringUtils.cc

@@ -514 +514 @@
         @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 +527 @@
         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;
+        int matrix[rows][cols];
+
+        for (size_t r = 0; r < rows; ++r)
+            for (size_t c = 0; c < cols; ++c)
+                matrix[r][c] = 0;
+
+        for (size_t i = 1; i < cols; ++i)
+            matrix[0][i] = i;
+        for (size_t i = 1; i < rows; ++i)
+            matrix[i][0] = i;
+
+        for (size_t r = 1; r < rows; ++r)
+            for (size_t c = 1; c < cols; ++c)
+                matrix[r][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][c] = std::min(std::min(matrix[r-1][c] + 1, matrix[r][c-1] + 1), matrix[r-1][c-1] + (str1[c-1] != str2[r-1]));
+
+        return matrix[rows-1][cols-1];
+    }
 }

code/branches/consolecommands3/src/libraries/util/StringUtils.h

@@ -43 +43 @@
     _UtilExport std::string getUniqueNumberString();
 
-    _UtilExport void        strip(std::string* str);
-    _UtilExport std::string getStripped(const std::string& str);
+    _UtilExport void         strip(std::string* str);
+    _UtilExport std::string  getStripped(const std::string& str);
 
-    _UtilExport std::string removeTrailingWhitespaces(const std::string& str);
+    _UtilExport std::string  removeTrailingWhitespaces(const std::string& str);
 
-    _UtilExport size_t      getNextQuote(const std::string& str, size_t start);
-    _UtilExport bool        isBetweenQuotes(const std::string& str, size_t pos);
+    _UtilExport size_t       getNextQuote(const std::string& str, size_t start);
+    _UtilExport bool         isBetweenQuotes(const std::string& str, size_t pos);
 
-    _UtilExport bool        hasStringBetweenQuotes(const std::string& str);
-    _UtilExport std::string getStringBetweenQuotes(const std::string& str);
+    _UtilExport bool         hasStringBetweenQuotes(const std::string& str);
+    _UtilExport std::string  getStringBetweenQuotes(const std::string& str);
 
-    _UtilExport std::string stripEnclosingQuotes(const std::string& str);
-    _UtilExport std::string stripEnclosingBraces(const std::string& str);
+    _UtilExport std::string  stripEnclosingQuotes(const std::string& str);
+    _UtilExport std::string  stripEnclosingBraces(const std::string& str);
 
-    _UtilExport bool        isEmpty(const std::string& str);
-    _UtilExport bool        isComment(const std::string& str);
-    _UtilExport bool        isNumeric(const std::string& str);
+    _UtilExport bool         isEmpty(const std::string& str);
+    _UtilExport bool         isComment(const std::string& str);
+    _UtilExport bool         isNumeric(const std::string& str);
 
-    _UtilExport std::string addSlashes(const std::string& str);
-    _UtilExport std::string removeSlashes(const std::string& str);
+    _UtilExport std::string  addSlashes(const std::string& str);
+    _UtilExport std::string  removeSlashes(const std::string& str);
 
-    _UtilExport void        lowercase(std::string* str);
-    _UtilExport std::string getLowercase(const std::string& str);
+    _UtilExport void         lowercase(std::string* str);
+    _UtilExport std::string  getLowercase(const std::string& str);
 
-    _UtilExport void        uppercase(std::string* str);
-    _UtilExport std::string getUppercase(const std::string& str);
+    _UtilExport void         uppercase(std::string* str);
+    _UtilExport std::string  getUppercase(const std::string& str);
 
-    _UtilExport int         nocaseCmp(const std::string& s1, const std::string& s2);
-    _UtilExport int         nocaseCmp(const std::string& s1, const std::string& s2, size_t len);
+    _UtilExport int          nocaseCmp(const std::string& s1, const std::string& s2);
+    _UtilExport int          nocaseCmp(const std::string& s1, const std::string& s2, size_t len);
 
-    _UtilExport bool        hasComment(const std::string& str);
-    _UtilExport std::string getComment(const std::string& str);
-    _UtilExport size_t      getCommentPosition(const std::string& str);
-    _UtilExport size_t      getNextCommentPosition(const std::string& str, size_t start = 0);
+    _UtilExport bool         hasComment(const std::string& str);
+    _UtilExport std::string  getComment(const std::string& str);
+    _UtilExport size_t       getCommentPosition(const std::string& str);
+    _UtilExport size_t       getNextCommentPosition(const std::string& str, size_t start = 0);
 
-    _UtilExport size_t      replaceCharacters(std::string& str, char target, char replacement);
+    _UtilExport size_t       replaceCharacters(std::string& str, char target, char replacement);
+
+    _UtilExport unsigned int getLevenshteinDistance(const std::string& str1, const std::string& str2);
 }