Implement edit distance for StringRef
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92309 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp
index 2d023e4..9084ea6 100644
--- a/lib/Support/StringRef.cpp
+++ b/lib/Support/StringRef.cpp
@@ -8,6 +8,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/ADT/StringRef.h"
+#include <vector>
using namespace llvm;
// MSVC emits references to this into the translation units which reference it.
@@ -35,6 +36,36 @@
return Length < RHS.Length ? -1 : 1;
}
+/// \brief Compute the edit distance between the two given strings.
+unsigned StringRef::edit_distance(llvm::StringRef Other,
+ bool AllowReplacements) {
+ size_type m = size();
+ size_type n = Other.size();
+
+ std::vector<unsigned> previous(n+1, 0);
+ for (std::vector<unsigned>::size_type i = 0; i <= n; ++i)
+ previous[i] = i;
+
+ std::vector<unsigned> current(n+1, 0);
+ for (size_type y = 1; y <= m; ++y) {
+ current.assign(n+1, 0);
+ current[0] = y;
+ for (size_type x = 1; x <= n; ++x) {
+ if (AllowReplacements) {
+ current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u),
+ min(current[x-1], previous[x])+1);
+ }
+ else {
+ if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1];
+ else current[x] = min(current[x-1], previous[x]) + 1;
+ }
+ }
+ current.swap(previous);
+ }
+
+ return previous[n];
+}
+
//===----------------------------------------------------------------------===//
// String Searching
//===----------------------------------------------------------------------===//