pub struct LevenshteinDistance;

impl LevenshteinDistance {
    pub fn filter_similar<'a>(str: &str, slice: &[&'a str], threshold: usize) -> Vec<&'a str> {
        slice
            .iter()
            .filter(|s| levenshtein_distance(str, s) <= threshold)
            .copied()
            .collect()
    }

    pub fn compare(a: impl AsRef<str>, b: impl AsRef<str>) -> usize {
        let a = a.as_ref();
        let b = b.as_ref();
        levenshtein_distance(a, b)
    }
}

fn levenshtein_distance(a: &str, b: &str) -> usize {
    let a_chars: Vec<char> = a.chars().collect();
    let b_chars: Vec<char> = b.chars().collect();
    let m = a_chars.len();
    let n = b_chars.len();
    if m == 0 {
        return n;
    }
    if n == 0 {
        return m;
    }

    let mut prev: Vec<usize> = (0..=n).collect();
    let mut curr = vec![0; n + 1];
    for (i, ca) in a_chars.iter().enumerate() {
        curr[0] = i + 1;
        for (j, cb) in b_chars.iter().enumerate() {
            let cost = if ca == cb { 0 } else { 1 };
            let del = prev[j + 1] + 1;
            let ins = curr[j] + 1;
            let rep = prev[j] + cost;
            curr[j + 1] = del.min(ins).min(rep);
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[n]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_levenshtein_distance_identical_strings() {
        assert_eq!(LevenshteinDistance::compare("hello", "hello"), 0);
    }

    #[test]
    fn test_levenshtein_distance_completely_different() {
        let dist = LevenshteinDistance::compare("abc", "xyz");
        assert_eq!(dist, 3);
    }

    #[test]
    fn test_levenshtein_distance_one_insertion() {
        assert_eq!(LevenshteinDistance::compare("cat", "cats"), 1);
    }

    #[test]
    fn test_levenshtein_distance_one_deletion() {
        assert_eq!(LevenshteinDistance::compare("dogs", "dog"), 1);
    }

    #[test]
    fn test_levenshtein_distance_one_substitution() {
        assert_eq!(LevenshteinDistance::compare("cat", "cut"), 1);
    }

    #[test]
    fn test_levenshtein_distance_empty_strings() {
        assert_eq!(LevenshteinDistance::compare("", ""), 0);
    }

    #[test]
    fn test_levenshtein_distance_empty_vs_nonempty() {
        assert_eq!(LevenshteinDistance::compare("", "abc"), 3);
        assert_eq!(LevenshteinDistance::compare("xyz", ""), 3);
    }

    #[test]
    fn test_levenshtein_distance_unicode() {
        // Chinese characters
        assert_eq!(LevenshteinDistance::compare("你好", "你好"), 0);
        assert_eq!(LevenshteinDistance::compare("你好", "您好"), 1);
        assert_eq!(LevenshteinDistance::compare("你好", "您不好"), 2);
    }

    #[test]
    fn test_filter_similar_exact_threshold() {
        let words = vec!["cat", "cart", "ca", "cats", "cut"];
        let result = LevenshteinDistance::filter_similar("cat", &words, 2);
        // cat -> cat: 0, cat -> cart: 1, cat -> ca: 1, cat -> cats: 1, cat -> cut: 1
        assert_eq!(result.len(), 5);
    }

    #[test]
    fn test_filter_similar_empty_slice() {
        let words: Vec<&str> = vec![];
        let result = LevenshteinDistance::filter_similar("hello", &words, 3);
        assert!(result.is_empty());
    }

    #[test]
    fn test_filter_similar_threshold_zero() {
        let words = vec!["hello", "hallo", "hello!"];
        let result = LevenshteinDistance::filter_similar("hello", &words, 0);
        assert_eq!(result, vec!["hello"]);
    }
}