Changeset 7238 for code/branches

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

Files:

• core/command/CommandEvaluation.cc (modified) (3 diffs)
• core/command/CommandEvaluation.h (modified) (1 diff)
• core/command/TclBind.cc (modified) (2 diffs)
• util/StringUtils.cc (modified) (2 diffs)
• util/StringUtils.h (modified) (1 diff)

code/branches/consolecommands3/src/libraries/core/command/CommandEvaluation.cc

@@ -124 +124 @@
                 }
             }
-            else
-            {
-                COUT(5) << "CE_execute: " << this->string_ << "\n";
-                return this->execCommand_->getExecutor()->parse(this->tokens_.subSet(this->execArgumentsOffset_), error, " ");
-            }
-        }
-        else
-            return MT_Type::Null;
+            else if (error)
+                *error = CommandExecutor::Incomplete;
+        }
+
+        return MT_Type::Null;
     }
 
@@ -213 +210 @@
             {
                 std::string groupLC = getLowercase(this->getToken(0));
-                std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommands().begin();
-                for ( ; it_group != ConsoleCommand::getCommands().end(); ++it_group)
-                    if (getLowercase(it_group->first) == groupLC)
+                for (std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommandsLC().begin(); it_group != ConsoleCommand::getCommandsLC().end(); ++it_group)
+                    if (it_group->first == groupLC)
                         return std::string("Error: There is no command in group \"") + this->getToken(0) + "\" starting with \"" + this->getToken(1) + "\".";
 
@@ -221 +217 @@
             }
         }
+    }
+
+    std::string CommandEvaluation::getCommandSuggestion() const
+    {
+        std::string token0_LC = getLowercase(this->getToken(0));
+        std::string token1_LC = getLowercase(this->getToken(1));
+
+        std::string nearestCommand;
+        unsigned int nearestDistance = (unsigned int)-1;
+
+        for (std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommandsLC().begin(); it_group != ConsoleCommand::getCommandsLC().end(); ++it_group)
+        {
+            if (it_group->first != "")
+            {
+                for (std::map<std::string, ConsoleCommand*>::const_iterator it_name = it_group->second.begin(); it_name != it_group->second.end(); ++it_name)
+                {
+                    std::string command = it_group->first + " " + it_name->first;
+                    unsigned int distance = getLevenshteinDistance(command, token0_LC + " " + token1_LC);
+                    if (distance < nearestDistance)
+                    {
+                        nearestCommand = command;
+                        nearestDistance = distance;
+                    }
+                }
+            }
+        }
+
+        std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommandsLC().find("");
+        if (it_group !=  ConsoleCommand::getCommandsLC().end())
+        {
+            for (std::map<std::string, ConsoleCommand*>::const_iterator it_name = it_group->second.begin(); it_name != it_group->second.end(); ++it_name)
+            {
+                std::string command = it_name->first;
+                unsigned int distance = getLevenshteinDistance(command, token0_LC);
+                if (distance < nearestDistance)
+                {
+                    nearestCommand = command;
+                    nearestDistance = distance;
+                }
+            }
+        }
+
+        return nearestCommand;
     }
 

code/branches/consolecommands3/src/libraries/core/command/CommandEvaluation.h

@@ -54 +54 @@
             std::string hint();
 
+            std::string getCommandSuggestion() const;
+
             int evaluateParams(bool bPrintError = false);
 

code/branches/consolecommands3/src/libraries/core/command/TclBind.cc

@@ -135 +135 @@
 
         int error;
-        const std::string& result = CommandExecutor::query(command, &error, false);
+        CommandEvaluation evaluation = CommandExecutor::evaluate(command);
+        const std::string& result = evaluation.query(&error);
         switch (error)
         {
@@ -143 +144 @@
             case CommandExecutor::Denied:      COUT(1) << "Error: Can't execute command \"" << command << "\", access denied. (B)" << std::endl; break;
         }
+
+        if (error == CommandExecutor::Error)
+            COUT(3) << "Did you mean \"" << evaluation.getCommandSuggestion() << "\"?" << std::endl;
 
         return result;

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);
 }