diff options
author | Balajiganapathi S <balajiganapathi.s@gmail.com> | 2017-11-18 00:11:15 +0800 |
---|---|---|
committer | Alex Beregszaszi <alex@rtfs.hu> | 2018-02-13 22:59:33 +0800 |
commit | b1417b318f3b3cbfd0bf79a4cabc656825a84e5a (patch) | |
tree | 3586f671841b6605b8b6cb7e41e6a96c931907da /libdevcore | |
parent | 2859834e58e37e7b15a15f7df60feef3e1527c97 (diff) | |
download | dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.tar dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.tar.gz dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.tar.bz2 dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.tar.lz dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.tar.xz dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.tar.zst dexon-solidity-b1417b318f3b3cbfd0bf79a4cabc656825a84e5a.zip |
Move string distance function to utils and format error message
Diffstat (limited to 'libdevcore')
-rw-r--r-- | libdevcore/StringUtils.cpp | 77 | ||||
-rw-r--r-- | libdevcore/StringUtils.h | 35 |
2 files changed, 112 insertions, 0 deletions
diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp new file mode 100644 index 00000000..7b2b4f5e --- /dev/null +++ b/libdevcore/StringUtils.cpp @@ -0,0 +1,77 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** @file StringUtils.h + * @author Balajiganapathi S <balajiganapathi.s@gmail.com> + * @date 2017 + * + * String routines + */ + +#include "StringUtils.h" +#include <algorithm> +#include <string> +#include <vector> + +using namespace std; +using namespace dev; + +namespace dev +{ + +bool stringWithinDistance(string const& _name1, string const& _name2, size_t _maxDistance) +{ + if (_name1 == _name2) + return true; + + size_t n1 = _name1.size(), n2 = _name2.size(); + vector<vector<size_t>> dp(n1 + 1, vector<size_t>(n2 + 1)); + + // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. + // So index accesser to _name1 and _name2 have to be adjusted accordingly + for (size_t i1 = 0; i1 <= n1; ++i1) + { + for (size_t i2 = 0; i2 <= n2; ++i2) + { + if (min(i1, i2) == 0) + // Base case + dp[i1][i2] = max(i1, i2); + else + { + dp[i1][i2] = min(dp[i1 - 1][i2] + 1, dp[i1][i2 - 1] + 1); + // Deletion and insertion + if (_name1[i1 - 1] == _name2[i2 - 1]) + // Same chars, can skip + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1]); + else + // Different chars so try substitution + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1] + 1); + + if (i1 > 1 && i2 > 1 && _name1[i1 - 1] == _name2[i2 - 2] && _name1[i1 - 2] == _name2[i2 - 1]) + // Try transposing + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 2][i2 - 2] + 1); + } + } + } + + size_t distance = dp[n1][n2]; + + // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, + // they can be considered similar this is to avoid irrelevant suggestions + return distance <= _maxDistance && distance < n1 && distance < n2; +} + +} diff --git a/libdevcore/StringUtils.h b/libdevcore/StringUtils.h new file mode 100644 index 00000000..d3f9f8d9 --- /dev/null +++ b/libdevcore/StringUtils.h @@ -0,0 +1,35 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** @file StringUtils.h + * @author Balajiganapathi S <balajiganapathi.s@gmail.com> + * @date 2017 + * + * String routines + */ + +#pragma once + +#include <string> + +namespace dev +{ + +/// Calculates the Damerau–Levenshtein distance between @a _name1 and @a _name2 and +/// @returns true if that distance is not greater than @a _maxDistance +bool stringWithinDistance(std::string const& _name1, std::string const& _name2, size_t _maxDistance); + +} |