Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Ignore:
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:
5 edited

Legend:

Unmodified
Added
Removed

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

    r7236 r7238  
    124124                }
    125125            }
    126             else
    127             {
    128                 COUT(5) << "CE_execute: " << this->string_ << "\n";
    129                 return this->execCommand_->getExecutor()->parse(this->tokens_.subSet(this->execArgumentsOffset_), error, " ");
    130             }
    131         }
    132         else
    133             return MT_Type::Null;
     126            else if (error)
     127                *error = CommandExecutor::Incomplete;
     128        }
     129
     130        return MT_Type::Null;
    134131    }
    135132
    … …  
    213210            {
    214211                std::string groupLC = getLowercase(this->getToken(0));
    215                 std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommands().begin();
    216                 for ( ; it_group != ConsoleCommand::getCommands().end(); ++it_group)
    217                     if (getLowercase(it_group->first) == groupLC)
     212                for (std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommandsLC().begin(); it_group != ConsoleCommand::getCommandsLC().end(); ++it_group)
     213                    if (it_group->first == groupLC)
    218214                        return std::string("Error: There is no command in group \"") + this->getToken(0) + "\" starting with \"" + this->getToken(1) + "\".";
    219215
    … …  
    221217            }
    222218        }
     219    }
     220
     221    std::string CommandEvaluation::getCommandSuggestion() const
     222    {
     223        std::string token0_LC = getLowercase(this->getToken(0));
     224        std::string token1_LC = getLowercase(this->getToken(1));
     225
     226        std::string nearestCommand;
     227        unsigned int nearestDistance = (unsigned int)-1;
     228
     229        for (std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommandsLC().begin(); it_group != ConsoleCommand::getCommandsLC().end(); ++it_group)
     230        {
     231            if (it_group->first != "")
     232            {
     233                for (std::map<std::string, ConsoleCommand*>::const_iterator it_name = it_group->second.begin(); it_name != it_group->second.end(); ++it_name)
     234                {
     235                    std::string command = it_group->first + " " + it_name->first;
     236                    unsigned int distance = getLevenshteinDistance(command, token0_LC + " " + token1_LC);
     237                    if (distance < nearestDistance)
     238                    {
     239                        nearestCommand = command;
     240                        nearestDistance = distance;
     241                    }
     242                }
     243            }
     244        }
     245
     246        std::map<std::string, std::map<std::string, ConsoleCommand*> >::const_iterator it_group = ConsoleCommand::getCommandsLC().find("");
     247        if (it_group !=  ConsoleCommand::getCommandsLC().end())
     248        {
     249            for (std::map<std::string, ConsoleCommand*>::const_iterator it_name = it_group->second.begin(); it_name != it_group->second.end(); ++it_name)
     250            {
     251                std::string command = it_name->first;
     252                unsigned int distance = getLevenshteinDistance(command, token0_LC);
     253                if (distance < nearestDistance)
     254                {
     255                    nearestCommand = command;
     256                    nearestDistance = distance;
     257                }
     258            }
     259        }
     260
     261        return nearestCommand;
    223262    }
    224263

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

    r7236 r7238  
    5454            std::string hint();
    5555
     56            std::string getCommandSuggestion() const;
     57
    5658            int evaluateParams(bool bPrintError = false);
    5759

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

    r7236 r7238  
    135135
    136136        int error;
    137         const std::string& result = CommandExecutor::query(command, &error, false);
     137        CommandEvaluation evaluation = CommandExecutor::evaluate(command);
     138        const std::string& result = evaluation.query(&error);
    138139        switch (error)
    139140        {
    … …  
    143144            case CommandExecutor::Denied:      COUT(1) << "Error: Can't execute command \"" << command << "\", access denied. (B)" << std::endl; break;
    144145        }
     146
     147        if (error == CommandExecutor::Error)
     148            COUT(3) << "Did you mean \"" << evaluation.getCommandSuggestion() << "\"?" << std::endl;
    145149
    146150        return result;

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

    r6424 r7238  
    514514        @return Number of replacements
    515515    */
    516     _UtilExport size_t replaceCharacters(std::string& str, char target, char replacement)
     516    size_t replaceCharacters(std::string& str, char target, char replacement)
    517517    {
    518518        size_t j = 0;
    … …  
    527527        return j;
    528528    }
     529
     530    /**
     531        @brief Calculates the Levenshtein distance between two strings.
     532
     533        The Levenshtein distance is defined by the number of transformations needed to convert str1
     534        into str2. Possible transformations are substituted, added, or removed characters.
     535    */
     536    unsigned int getLevenshteinDistance(const std::string& str1, const std::string& str2)
     537    {
     538        size_t cols = str1.size() + 1;
     539        size_t rows = str2.size() + 1;
     540        int matrix[rows][cols];
     541
     542        for (size_t r = 0; r < rows; ++r)
     543            for (size_t c = 0; c < cols; ++c)
     544                matrix[r][c] = 0;
     545
     546        for (size_t i = 1; i < cols; ++i)
     547            matrix[0][i] = i;
     548        for (size_t i = 1; i < rows; ++i)
     549            matrix[i][0] = i;
     550
     551        for (size_t r = 1; r < rows; ++r)
     552            for (size_t c = 1; c < cols; ++c)
     553                matrix[r][c] = (str1[c-1] != str2[r-1]);
     554
     555        for (size_t r = 1; r < rows; ++r)
     556            for (size_t c = 1; c < cols; ++c)
     557                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]));
     558
     559        return matrix[rows-1][cols-1];
     560    }
    529561}

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

    r5738 r7238  
    4343    _UtilExport std::string getUniqueNumberString();
    4444
    45     _UtilExport void        strip(std::string* str);
    46     _UtilExport std::string getStripped(const std::string& str);
     45    _UtilExport void         strip(std::string* str);
     46    _UtilExport std::string  getStripped(const std::string& str);
    4747
    48     _UtilExport std::string removeTrailingWhitespaces(const std::string& str);
     48    _UtilExport std::string  removeTrailingWhitespaces(const std::string& str);
    4949
    50     _UtilExport size_t      getNextQuote(const std::string& str, size_t start);
    51     _UtilExport bool        isBetweenQuotes(const std::string& str, size_t pos);
     50    _UtilExport size_t       getNextQuote(const std::string& str, size_t start);
     51    _UtilExport bool         isBetweenQuotes(const std::string& str, size_t pos);
    5252
    53     _UtilExport bool        hasStringBetweenQuotes(const std::string& str);
    54     _UtilExport std::string getStringBetweenQuotes(const std::string& str);
     53    _UtilExport bool         hasStringBetweenQuotes(const std::string& str);
     54    _UtilExport std::string  getStringBetweenQuotes(const std::string& str);
    5555
    56     _UtilExport std::string stripEnclosingQuotes(const std::string& str);
    57     _UtilExport std::string stripEnclosingBraces(const std::string& str);
     56    _UtilExport std::string  stripEnclosingQuotes(const std::string& str);
     57    _UtilExport std::string  stripEnclosingBraces(const std::string& str);
    5858
    59     _UtilExport bool        isEmpty(const std::string& str);
    60     _UtilExport bool        isComment(const std::string& str);
    61     _UtilExport bool        isNumeric(const std::string& str);
     59    _UtilExport bool         isEmpty(const std::string& str);
     60    _UtilExport bool         isComment(const std::string& str);
     61    _UtilExport bool         isNumeric(const std::string& str);
    6262
    63     _UtilExport std::string addSlashes(const std::string& str);
    64     _UtilExport std::string removeSlashes(const std::string& str);
     63    _UtilExport std::string  addSlashes(const std::string& str);
     64    _UtilExport std::string  removeSlashes(const std::string& str);
    6565
    66     _UtilExport void        lowercase(std::string* str);
    67     _UtilExport std::string getLowercase(const std::string& str);
     66    _UtilExport void         lowercase(std::string* str);
     67    _UtilExport std::string  getLowercase(const std::string& str);
    6868
    69     _UtilExport void        uppercase(std::string* str);
    70     _UtilExport std::string getUppercase(const std::string& str);
     69    _UtilExport void         uppercase(std::string* str);
     70    _UtilExport std::string  getUppercase(const std::string& str);
    7171
    72     _UtilExport int         nocaseCmp(const std::string& s1, const std::string& s2);
    73     _UtilExport int         nocaseCmp(const std::string& s1, const std::string& s2, size_t len);
     72    _UtilExport int          nocaseCmp(const std::string& s1, const std::string& s2);
     73    _UtilExport int          nocaseCmp(const std::string& s1, const std::string& s2, size_t len);
    7474
    75     _UtilExport bool        hasComment(const std::string& str);
    76     _UtilExport std::string getComment(const std::string& str);
    77     _UtilExport size_t      getCommentPosition(const std::string& str);
    78     _UtilExport size_t      getNextCommentPosition(const std::string& str, size_t start = 0);
     75    _UtilExport bool         hasComment(const std::string& str);
     76    _UtilExport std::string  getComment(const std::string& str);
     77    _UtilExport size_t       getCommentPosition(const std::string& str);
     78    _UtilExport size_t       getNextCommentPosition(const std::string& str, size_t start = 0);
    7979
    80     _UtilExport size_t      replaceCharacters(std::string& str, char target, char replacement);
     80    _UtilExport size_t       replaceCharacters(std::string& str, char target, char replacement);
     81
     82    _UtilExport unsigned int getLevenshteinDistance(const std::string& str1, const std::string& str2);
    8183}
    8284
Note: See TracChangeset for help on using the changeset viewer.