Merge pull request #3503 from ethereum/develop

Merge develop into release for v0.4.20.

3 files changed, 165 insertions, 0 deletions

diff --git a/libdevcore/CommonData.h b/libdevcore/CommonData.h
index e76a0949..e410af5c 100644
--- a/libdevcore/CommonData.h
+++ b/libdevcore/CommonData.h
@@ -155,6 +155,14 @@ inline std::string formatNumber(bigint const& _value)
 		return _value.str();
 }
 
+inline std::string formatNumber(u256 const& _value)
+{
+	if (_value > 0x1000000)
+		return toHex(toCompactBigEndian(_value), 2, HexPrefix::Add);
+	else
+		return _value.str();
+}
+
 inline std::string toCompactHexWithPrefix(u256 val)
 {
 	std::ostringstream ret;
@@ -183,6 +191,12 @@ template <class T, class U> std::vector<T>& operator+=(std::vector<T>& _a, U con
 		_a.push_back(i);
 	return _a;
 }
+/// Concatenate the contents of a container onto a vector, move variant.
+template <class T, class U> std::vector<T>& operator+=(std::vector<T>& _a, U&& _b)
+{
+	std::move(_b.begin(), _b.end(), std::back_inserter(_a));
+	return _a;
+}
 /// Concatenate the contents of a container onto a set
 template <class T, class U> std::set<T>& operator+=(std::set<T>& _a, U const& _b)
 {
@@ -197,6 +211,17 @@ inline std::vector<T> operator+(std::vector<T> const& _a, std::vector<T> const&
 	ret += _b;
 	return ret;
 }
+/// Concatenate two vectors of elements, moving them.
+template <class T>
+inline std::vector<T> operator+(std::vector<T>&& _a, std::vector<T>&& _b)
+{
+	std::vector<T> ret(std::move(_a));
+	if (&_a == &_b)
+		ret += ret;
+	else
+		ret += std::move(_b);
+	return ret;
+}
 
 template <class T, class V>
 bool contains(T const& _t, V const& _v)
diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp
new file mode 100644
index 00000000..2ff86bd5
--- /dev/null
+++ b/libdevcore/StringUtils.cpp
@@ -0,0 +1,101 @@
+/*
+	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;
+
+bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t _maxDistance)
+{
+	if (_str1 == _str2)
+		return true;
+
+	size_t n1 = _str1.size();
+	size_t n2 = _str2.size();
+	size_t distance = stringDistance(_str1, _str2);
+
+	// 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;
+}
+
+size_t dev::stringDistance(string const& _str1, string const& _str2)
+{
+	size_t n1 = _str1.size();
+	size_t n2 = _str2.size();
+	// Optimize by storing only last 2 rows and current row. So first index is considered modulo 3
+	// This is a two-dimensional array of size 3 x (n2 + 1).
+	vector<size_t> dp(3 * (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)
+		{
+			size_t x = 0;
+			if (min(i1, i2) == 0) // base case
+				x = max(i1, i2);
+			else
+			{
+				size_t left = dp[(i1 - 1) % 3 + i2 * 3];
+				size_t up = dp[(i1 % 3) + (i2 - 1) * 3];
+				size_t upleft = dp[((i1 - 1) % 3) + (i2 - 1) * 3];
+				// deletion and insertion
+				x = min(left + 1, up + 1);
+				if (_str1[i1-1] == _str2[i2-1])
+					// same chars, can skip
+					x = min(x, upleft);
+				else
+					// different chars so try substitution
+					x = min(x, upleft + 1);
+
+				// transposing
+				if (i1 > 1 && i2 > 1 && _str1[i1 - 1] == _str2[i2 - 2] && _str1[i1 - 2] == _str2[i2 - 1])
+					x = min(x, dp[((i1 - 2) % 3) + (i2 - 2) * 3] + 1);
+			}
+			dp[(i1 % 3) + i2 * 3] = x;
+		}
+
+	return dp[(n1 % 3) + n2 * 3];
+}
+
+string dev::quotedAlternativesList(vector<string> const& suggestions)
+{
+	if (suggestions.empty())
+		return "";
+	if (suggestions.size() == 1)
+		return "\"" + suggestions.front() + "\"";
+
+	string choices = "\"" + suggestions.front() + "\"";
+	for (size_t i = 1; i + 1 < suggestions.size(); ++i)
+		choices += ", \"" + suggestions[i] + "\"";
+
+	choices += " or \"" + suggestions.back() + "\"";
+
+	return choices;
+}
+
diff --git a/libdevcore/StringUtils.h b/libdevcore/StringUtils.h
new file mode 100644
index 00000000..acd93e32
--- /dev/null
+++ b/libdevcore/StringUtils.h
@@ -0,0 +1,39 @@
+/*
+	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>
+#include <vector>
+
+namespace dev
+{
+
+// Calculates the Damerau–Levenshtein distance between _str1 and _str2 and returns true if that distance is not greater than _maxDistance
+bool stringWithinDistance(std::string const& _str1, std::string const& _str2, size_t _maxDistance);
+// Calculates the Damerau–Levenshtein distance between _str1 and _str2
+size_t stringDistance(std::string const& _str1, std::string const& _str2);
+// Return a string having elements of suggestions as quoted, alternative suggestions. e.g. "a", "b" or "c"
+std::string quotedAlternativesList(std::vector<std::string> const& suggestions);
+
+}