Add basic support for username auto-completion

fixes #40

1 files changed, 28 insertions, 0 deletions

diff --git a/src/Utils.cc b/src/Utils.cc

index 6f438c20..169be75e 100644
--- a/src/Utils.cc
+++ b/src/Utils.cc
@@ -149,3 +149,31 @@ utils::humanReadableFileSize(uint64_t bytes)
 
         return QString::number(size, 'g', 4) + ' ' + units[u];
 }
+
+int
+utils::levenshtein_distance(const std::string &s1, const std::string &s2)
+{
+        const int nlen = s1.size();
+        const int hlen = s2.size();
+
+        if (hlen == 0)
+                return -1;
+        if (nlen == 1)
+                return s2.find(s1);
+
+        std::vector<int> row1(hlen + 1, 0);
+
+        for (int i = 0; i < nlen; ++i) {
+                std::vector<int> row2(1, i + 1);
+
+                for (int j = 0; j < hlen; ++j) {
+                        const int cost = s1[i] != s2[j];
+                        row2.push_back(
+                          std::min(row1[j + 1] + 1, std::min(row2[j] + 1, row1[j] + cost)));
+                }
+
+                row1.swap(row2);
+        }
+
+        return *std::min_element(row1.begin(), row1.end());
+}