From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Wed, 17 Apr 2024 14:02:58 +0200
Subject: Adding upstream version 1.64.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 vendor/gsgdt/src/levenshtein.rs | 70 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 vendor/gsgdt/src/levenshtein.rs

(limited to 'vendor/gsgdt/src/levenshtein.rs')

diff --git a/vendor/gsgdt/src/levenshtein.rs b/vendor/gsgdt/src/levenshtein.rs
new file mode 100644
index 000000000..8acfefc83
--- /dev/null
+++ b/vendor/gsgdt/src/levenshtein.rs
@@ -0,0 +1,70 @@
+use std::cmp::min;
+
+/// Calculate the levenshtein distance between two strings.
+pub(crate) fn distance(s1: &str, s2: &str) -> usize {
+    let v1: Vec<char> = s1.chars().collect();
+    let v2: Vec<char> = s2.chars().collect();
+
+    let l_v1 = v1.len();
+    let l_v2 = v2.len();
+
+    if l_v1 == 0 {
+        return l_v2;
+    }
+    if l_v2 == 0 {
+        return l_v1;
+    }
+    if l_v1 > l_v2 {
+        return distance(s2, s1);
+    }
+
+    let mut col: Vec<usize> = (0..=l_v1).collect();
+
+    for i in 1..=l_v2 {
+        let mut last_diag = col[0];
+        col[0] += 1;
+        for j in 1..=l_v1 {
+            let last_diag_temp = col[j];
+            if v1[j-1] == v2[i-1] {
+                col[j] = last_diag;
+            } else {
+                col[j] = min(last_diag, min(col[j-1], col[j])) + 1;
+            }
+            last_diag = last_diag_temp;
+        }
+    }
+
+    col[l_v1]
+}
+
+
+#[cfg(test)]
+mod tests {
+    use crate::levenshtein::*;
+    #[test]
+    fn test1() {
+        assert_eq!(distance("kitten", "sitting"), 3);
+    }
+
+    #[test]
+    fn test_diff_len() {
+        assert_eq!(distance("kit", "kitten"), 3);
+    }
+
+    #[test]
+    fn test_equal() {
+        assert_eq!(distance("test", "test"), 0);
+        assert_eq!(distance("", ""), 0);
+        assert_eq!(distance("long string with space", "long string with space"), 0);
+        assert_eq!(distance("unicode 😀", "unicode 😀"), 0);
+    }
+
+    #[test]
+    fn test_one_empty() {
+        assert_eq!(distance("test", ""), 4);
+        assert_eq!(distance("", "test"), 4);
+        assert_eq!(distance("", ""), 0);
+        assert_eq!(distance("long string", ""), 11);
+        assert_eq!(distance("😀", ""), 1);
+    }
+}
-- 
cgit v1.2.3