Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1005 insertions, 0 deletions

diff --git a/vendor/strsim/src/lib.rs b/vendor/strsim/src/lib.rs
new file mode 100644
index 000000000..480a64243
--- /dev/null
+++ b/vendor/strsim/src/lib.rs
@@ -0,0 +1,1005 @@
+//! This library implements string similarity metrics.
+
+#![forbid(unsafe_code)]
+
+use std::char;
+use std::cmp::{max, min};
+use std::collections::HashMap;
+use std::error::Error;
+use std::fmt::{self, Display, Formatter};
+use std::hash::Hash;
+use std::str::Chars;
+
+#[derive(Debug, PartialEq)]
+pub enum StrSimError {
+    DifferentLengthArgs,
+}
+
+impl Display for StrSimError {
+    fn fmt(&self, fmt: &mut Formatter) -> Result<(), fmt::Error> {
+        let text = match self {
+            StrSimError::DifferentLengthArgs => "Differing length arguments provided",
+        };
+
+        write!(fmt, "{}", text)
+    }
+}
+
+impl Error for StrSimError {}
+
+pub type HammingResult = Result<usize, StrSimError>;
+
+/// Calculates the number of positions in the two sequences where the elements
+/// differ. Returns an error if the sequences have different lengths.
+pub fn generic_hamming<Iter1, Iter2, Elem1, Elem2>(a: Iter1, b: Iter2) -> HammingResult
+    where Iter1: IntoIterator<Item=Elem1>,
+          Iter2: IntoIterator<Item=Elem2>,
+          Elem1: PartialEq<Elem2> {
+    let (mut ita, mut itb) = (a.into_iter(), b.into_iter());
+    let mut count = 0;
+    loop {
+        match (ita.next(), itb.next()){
+            (Some(x), Some(y)) => if x != y { count += 1 },
+            (None, None) => return Ok(count),
+            _ => return Err(StrSimError::DifferentLengthArgs),
+        }
+    }
+}
+
+/// Calculates the number of positions in the two strings where the characters
+/// differ. Returns an error if the strings have different lengths.
+///
+/// ```
+/// use strsim::{hamming, StrSimError::DifferentLengthArgs};
+///
+/// assert_eq!(Ok(3), hamming("hamming", "hammers"));
+///
+/// assert_eq!(Err(DifferentLengthArgs), hamming("hamming", "ham"));
+/// ```
+pub fn hamming(a: &str, b: &str) -> HammingResult {
+    generic_hamming(a.chars(), b.chars())
+}
+
+/// Calculates the Jaro similarity between two sequences. The returned value
+/// is between 0.0 and 1.0 (higher value means more similar).
+pub fn generic_jaro<'a, 'b, Iter1, Iter2, Elem1, Elem2>(a: &'a Iter1, b: &'b Iter2) -> f64
+    where &'a Iter1: IntoIterator<Item=Elem1>,
+          &'b Iter2: IntoIterator<Item=Elem2>,
+          Elem1: PartialEq<Elem2> {
+    let a_len = a.into_iter().count();
+    let b_len = b.into_iter().count();
+
+    // The check for lengths of one here is to prevent integer overflow when
+    // calculating the search range.
+    if a_len == 0 && b_len == 0 {
+        return 1.0;
+    } else if a_len == 0 || b_len == 0 {
+        return 0.0;
+    } else if a_len == 1 && b_len == 1 {
+        return if a.into_iter().eq(b.into_iter()) { 1.0} else { 0.0 };
+    }
+
+    let search_range = (max(a_len, b_len) / 2) - 1;
+
+    let mut b_consumed = Vec::with_capacity(b_len);
+    for _ in 0..b_len {
+        b_consumed.push(false);
+    }
+    let mut matches = 0.0;
+
+    let mut transpositions = 0.0;
+    let mut b_match_index = 0;
+
+    for (i, a_elem) in a.into_iter().enumerate() {
+        let min_bound =
+            // prevent integer wrapping
+            if i > search_range {
+                max(0, i - search_range)
+            } else {
+                0
+            };
+
+        let max_bound = min(b_len - 1, i + search_range);
+
+        if min_bound > max_bound {
+            continue;
+        }
+
+        for (j, b_elem) in b.into_iter().enumerate() {
+            if min_bound <= j && j <= max_bound && a_elem == b_elem &&
+                !b_consumed[j] {
+                b_consumed[j] = true;
+                matches += 1.0;
+
+                if j < b_match_index {
+                    transpositions += 1.0;
+                }
+                b_match_index = j;
+
+                break;
+            }
+        }
+    }
+
+    if matches == 0.0 {
+        0.0
+    } else {
+        (1.0 / 3.0) * ((matches / a_len as f64) +
+            (matches / b_len as f64) +
+            ((matches - transpositions) / matches))
+    }
+}
+
+struct StringWrapper<'a>(&'a str);
+
+impl<'a, 'b> IntoIterator for &'a StringWrapper<'b> {
+    type Item = char;
+    type IntoIter = Chars<'b>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.chars()
+    }
+}
+
+/// Calculates the Jaro similarity between two strings. The returned value
+/// is between 0.0 and 1.0 (higher value means more similar).
+///
+/// ```
+/// use strsim::jaro;
+///
+/// assert!((0.392 - jaro("Friedrich Nietzsche", "Jean-Paul Sartre")).abs() <
+///         0.001);
+/// ```
+pub fn jaro(a: &str, b: &str) -> f64 {
+    generic_jaro(&StringWrapper(a), &StringWrapper(b))
+}
+
+/// Like Jaro but gives a boost to sequences that have a common prefix.
+pub fn generic_jaro_winkler<'a, 'b, Iter1, Iter2, Elem1, Elem2>(a: &'a Iter1, b: &'b Iter2) -> f64
+    where &'a Iter1: IntoIterator<Item=Elem1>,
+          &'b Iter2: IntoIterator<Item=Elem2>,
+          Elem1: PartialEq<Elem2> {
+    let jaro_distance = generic_jaro(a, b);
+
+    // Don't limit the length of the common prefix
+    let prefix_length = a.into_iter()
+        .zip(b.into_iter())
+        .take_while(|&(ref a_elem, ref b_elem)| a_elem == b_elem)
+        .count();
+
+    let jaro_winkler_distance =
+        jaro_distance + (0.1 * prefix_length as f64 * (1.0 - jaro_distance));
+
+    if jaro_winkler_distance <= 1.0 {
+        jaro_winkler_distance
+    } else {
+        1.0
+    }
+}
+
+/// Like Jaro but gives a boost to strings that have a common prefix.
+///
+/// ```
+/// use strsim::jaro_winkler;
+///
+/// assert!((0.911 - jaro_winkler("cheeseburger", "cheese fries")).abs() <
+///         0.001);
+/// ```
+pub fn jaro_winkler(a: &str, b: &str) -> f64 {
+    generic_jaro_winkler(&StringWrapper(a), &StringWrapper(b))
+}
+
+/// Calculates the minimum number of insertions, deletions, and substitutions
+/// required to change one sequence into the other.
+///
+/// ```
+/// use strsim::generic_levenshtein;
+///
+/// assert_eq!(3, generic_levenshtein(&[1,2,3], &[1,2,3,4,5,6]));
+/// ```
+pub fn generic_levenshtein<'a, 'b, Iter1, Iter2, Elem1, Elem2>(a: &'a Iter1, b: &'b Iter2) -> usize
+    where &'a Iter1: IntoIterator<Item=Elem1>,
+          &'b Iter2: IntoIterator<Item=Elem2>,
+          Elem1: PartialEq<Elem2> {
+    let b_len = b.into_iter().count();
+
+    if a.into_iter().next().is_none() { return b_len; }
+
+    let mut cache: Vec<usize> = (1..b_len+1).collect();
+
+    let mut result = 0;
+
+    for (i, a_elem) in a.into_iter().enumerate() {
+        result = i + 1;
+        let mut distance_b = i;
+
+        for (j, b_elem) in b.into_iter().enumerate() {
+            let cost = if a_elem == b_elem { 0usize } else { 1usize };
+            let distance_a = distance_b + cost;
+            distance_b = cache[j];
+            result = min(result + 1, min(distance_a, distance_b + 1));
+            cache[j] = result;
+        }
+    }
+
+    result
+}
+
+/// Calculates the minimum number of insertions, deletions, and substitutions
+/// required to change one string into the other.
+///
+/// ```
+/// use strsim::levenshtein;
+///
+/// assert_eq!(3, levenshtein("kitten", "sitting"));
+/// ```
+pub fn levenshtein(a: &str, b: &str) -> usize {
+    generic_levenshtein(&StringWrapper(a), &StringWrapper(b))
+}
+
+/// Calculates a normalized score of the Levenshtein algorithm between 0.0 and
+/// 1.0 (inclusive), where 1.0 means the strings are the same.
+///
+/// ```
+/// use strsim::normalized_levenshtein;
+///
+/// assert!((normalized_levenshtein("kitten", "sitting") - 0.57142).abs() < 0.00001);
+/// assert!((normalized_levenshtein("", "") - 1.0).abs() < 0.00001);
+/// assert!(normalized_levenshtein("", "second").abs() < 0.00001);
+/// assert!(normalized_levenshtein("first", "").abs() < 0.00001);
+/// assert!((normalized_levenshtein("string", "string") - 1.0).abs() < 0.00001);
+/// ```
+pub fn normalized_levenshtein(a: &str, b: &str) -> f64 {
+    if a.is_empty() && b.is_empty() {
+        return 1.0;
+    }
+    1.0 - (levenshtein(a, b) as f64) / (a.chars().count().max(b.chars().count()) as f64)
+}
+
+/// Like Levenshtein but allows for adjacent transpositions. Each substring can
+/// only be edited once.
+///
+/// ```
+/// use strsim::osa_distance;
+///
+/// assert_eq!(3, osa_distance("ab", "bca"));
+/// ```
+pub fn osa_distance(a: &str, b: &str) -> usize {
+    let a_len = a.chars().count();
+    let b_len = b.chars().count();
+    if a == b { return 0; }
+    else if a_len == 0 { return b_len; }
+    else if b_len == 0 { return a_len; }
+
+    let mut prev_two_distances: Vec<usize> = Vec::with_capacity(b_len + 1);
+    let mut prev_distances: Vec<usize> = Vec::with_capacity(b_len + 1);
+    let mut curr_distances: Vec<usize> = Vec::with_capacity(b_len + 1);
+
+    let mut prev_a_char = char::MAX;
+    let mut prev_b_char = char::MAX;
+
+    for i in 0..(b_len + 1) {
+        prev_two_distances.push(i);
+        prev_distances.push(i);
+        curr_distances.push(0);
+    }
+
+    for (i, a_char) in a.chars().enumerate() {
+        curr_distances[0] = i + 1;
+
+        for (j, b_char) in b.chars().enumerate() {
+            let cost = if a_char == b_char { 0 } else { 1 };
+            curr_distances[j + 1] = min(curr_distances[j] + 1,
+                                        min(prev_distances[j + 1] + 1,
+                                            prev_distances[j] + cost));
+            if i > 0 && j > 0 && a_char != b_char &&
+                a_char == prev_b_char && b_char == prev_a_char {
+                curr_distances[j + 1] = min(curr_distances[j + 1],
+                                            prev_two_distances[j - 1] + 1);
+            }
+
+            prev_b_char = b_char;
+        }
+
+        prev_two_distances.clone_from(&prev_distances);
+        prev_distances.clone_from(&curr_distances);
+        prev_a_char = a_char;
+    }
+
+    curr_distances[b_len]
+
+}
+
+/* Returns the final index for a value in a single vector that represents a fixed
+   2d grid */
+fn flat_index(i: usize, j: usize, width: usize) -> usize {
+    j * width + i
+}
+
+/// Like optimal string alignment, but substrings can be edited an unlimited
+/// number of times, and the triangle inequality holds.
+///
+/// ```
+/// use strsim::generic_damerau_levenshtein;
+///
+/// assert_eq!(2, generic_damerau_levenshtein(&[1,2], &[2,3,1]));
+/// ```
+pub fn generic_damerau_levenshtein<Elem>(a_elems: &[Elem], b_elems: &[Elem]) -> usize
+    where Elem: Eq + Hash + Clone {
+    let a_len = a_elems.len();
+    let b_len = b_elems.len();
+
+    if a_len == 0 { return b_len; }
+    if b_len == 0 { return a_len; }
+
+    let width = a_len + 2;
+    let mut distances = vec![0; (a_len + 2) * (b_len + 2)];
+    let max_distance = a_len + b_len;
+    distances[0] = max_distance;
+
+    for i in 0..(a_len + 1) {
+        distances[flat_index(i + 1, 0, width)] = max_distance;
+        distances[flat_index(i + 1, 1, width)] = i;
+    }
+
+    for j in 0..(b_len + 1) {
+        distances[flat_index(0, j + 1, width)] = max_distance;
+        distances[flat_index(1, j + 1, width)] = j;
+    }
+
+    let mut elems: HashMap<Elem, usize> = HashMap::with_capacity(64);
+
+    for i in 1..(a_len + 1) {
+        let mut db = 0;
+
+        for j in 1..(b_len + 1) {
+            let k = match elems.get(&b_elems[j - 1]) {
+                Some(&value) => value,
+                None => 0
+            };
+
+            let insertion_cost = distances[flat_index(i, j + 1, width)] + 1;
+            let deletion_cost = distances[flat_index(i + 1, j, width)] + 1;
+            let transposition_cost = distances[flat_index(k, db, width)] +
+                (i - k - 1) + 1 + (j - db - 1);
+
+            let mut substitution_cost = distances[flat_index(i, j, width)] + 1;
+            if a_elems[i - 1] == b_elems[j - 1] {
+                db = j;
+                substitution_cost -= 1;
+            }
+
+            distances[flat_index(i + 1, j + 1, width)] = min(substitution_cost,
+                min(insertion_cost, min(deletion_cost, transposition_cost)));
+        }
+
+        elems.insert(a_elems[i - 1].clone(), i);
+    }
+
+    distances[flat_index(a_len + 1, b_len + 1, width)]
+}
+
+/// Like optimal string alignment, but substrings can be edited an unlimited
+/// number of times, and the triangle inequality holds.
+///
+/// ```
+/// use strsim::damerau_levenshtein;
+///
+/// assert_eq!(2, damerau_levenshtein("ab", "bca"));
+/// ```
+pub fn damerau_levenshtein(a: &str, b: &str) -> usize {
+    let (x, y): (Vec<_>, Vec<_>) = (a.chars().collect(), b.chars().collect());
+    generic_damerau_levenshtein(x.as_slice(), y.as_slice())
+}
+
+/// Calculates a normalized score of the Damerau–Levenshtein algorithm between
+/// 0.0 and 1.0 (inclusive), where 1.0 means the strings are the same.
+///
+/// ```
+/// use strsim::normalized_damerau_levenshtein;
+///
+/// assert!((normalized_damerau_levenshtein("levenshtein", "löwenbräu") - 0.27272).abs() < 0.00001);
+/// assert!((normalized_damerau_levenshtein("", "") - 1.0).abs() < 0.00001);
+/// assert!(normalized_damerau_levenshtein("", "flower").abs() < 0.00001);
+/// assert!(normalized_damerau_levenshtein("tree", "").abs() < 0.00001);
+/// assert!((normalized_damerau_levenshtein("sunglasses", "sunglasses") - 1.0).abs() < 0.00001);
+/// ```
+pub fn normalized_damerau_levenshtein(a: &str, b: &str) -> f64 {
+    if a.is_empty() && b.is_empty() {
+        return 1.0;
+    }
+    1.0 - (damerau_levenshtein(a, b) as f64) / (a.chars().count().max(b.chars().count()) as f64)
+}
+
+/// Returns an Iterator of char tuples.
+fn bigrams(s: &str) -> impl Iterator<Item=(char, char)> + '_ {
+    s.chars().zip(s.chars().skip(1))
+}
+
+
+/// Calculates a Sørensen-Dice similarity distance using bigrams.
+/// See http://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient.
+///
+/// ```
+/// use strsim::sorensen_dice;
+///
+/// assert_eq!(1.0, sorensen_dice("", ""));
+/// assert_eq!(0.0, sorensen_dice("", "a"));
+/// assert_eq!(0.0, sorensen_dice("french", "quebec"));
+/// assert_eq!(1.0, sorensen_dice("ferris", "ferris"));
+/// assert_eq!(1.0, sorensen_dice("ferris", "ferris"));
+/// assert_eq!(0.8888888888888888, sorensen_dice("feris", "ferris"));
+/// ```
+pub fn sorensen_dice(a: &str, b: &str) -> f64 {
+    // implementation guided by
+    // https://github.com/aceakash/string-similarity/blob/f83ba3cd7bae874c20c429774e911ae8cff8bced/src/index.js#L6
+
+    let a: String = a.chars().filter(|&x| !char::is_whitespace(x)).collect();
+    let b: String = b.chars().filter(|&x| !char::is_whitespace(x)).collect();
+
+    if a.len() == 0 && b.len() == 0 {
+        return 1.0;
+    }
+
+    if a.len() == 0 || b.len() == 0 {
+        return 0.0;
+    }
+
+    if a == b {
+        return 1.0;
+    }
+
+    if a.len() == 1 && b.len() == 1 {
+        return 0.0;
+    }
+
+    if a.len() < 2 || b.len() < 2 {
+        return 0.0;
+    }
+
+    let mut a_bigrams: HashMap<(char, char), usize> = HashMap::new();
+
+    for bigram in bigrams(&a) {
+        *a_bigrams.entry(bigram).or_insert(0) += 1;
+    }
+
+    let mut intersection_size = 0;
+
+    for bigram in bigrams(&b) {
+        a_bigrams.entry(bigram).and_modify(|bi| {
+            if *bi > 0 {
+                *bi -= 1;
+                intersection_size += 1;
+            }
+        });
+    }
+
+    (2 * intersection_size) as f64 / (a.len() + b.len() - 2) as f64
+}
+
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn bigrams_iterator() {
+        let mut bi = bigrams("abcde");
+
+        assert_eq!(Some(('a', 'b')), bi.next());
+        assert_eq!(Some(('b', 'c')), bi.next());
+        assert_eq!(Some(('c', 'd')), bi.next());
+        assert_eq!(Some(('d', 'e')), bi.next());
+        assert_eq!(None, bi.next());
+    }
+
+    fn assert_hamming_dist(dist: usize, str1: &str, str2: &str) {
+        assert_eq!(Ok(dist), hamming(str1, str2));
+    }
+
+    #[test]
+    fn hamming_empty() {
+        assert_hamming_dist(0, "", "")
+    }
+
+    #[test]
+    fn hamming_same() {
+        assert_hamming_dist(0, "hamming", "hamming")
+    }
+
+    #[test]
+    fn hamming_numbers() {
+        assert_eq!(Ok(1), generic_hamming(&[1, 2, 4], &[1, 2, 3]));
+    }
+
+    #[test]
+    fn hamming_diff() {
+        assert_hamming_dist(3, "hamming", "hammers")
+    }
+
+    #[test]
+    fn hamming_diff_multibyte() {
+        assert_hamming_dist(2, "hamming", "h香mmüng");
+    }
+
+    #[test]
+    fn hamming_unequal_length() {
+        assert_eq!(
+            Err(StrSimError::DifferentLengthArgs),
+            generic_hamming("ham".chars(), "hamming".chars())
+        );
+    }
+
+    #[test]
+    fn hamming_names() {
+        assert_hamming_dist(14, "Friedrich Nietzs", "Jean-Paul Sartre")
+    }
+
+    #[test]
+    fn jaro_both_empty() {
+        assert_eq!(1.0, jaro("", ""));
+    }
+
+    #[test]
+    fn jaro_first_empty() {
+        assert_eq!(0.0, jaro("", "jaro"));
+    }
+
+    #[test]
+    fn jaro_second_empty() {
+        assert_eq!(0.0, jaro("distance", ""));
+    }
+
+    #[test]
+    fn jaro_same() {
+        assert_eq!(1.0, jaro("jaro", "jaro"));
+    }
+
+    #[test]
+    fn jaro_multibyte() {
+        assert!((0.818 - jaro("testabctest", "testöঙ香test")) < 0.001);
+        assert!((0.818 - jaro("testöঙ香test", "testabctest")) < 0.001);
+    }
+
+    #[test]
+    fn jaro_diff_short() {
+        assert!((0.767 - jaro("dixon", "dicksonx")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_diff_one_character() {
+        assert_eq!(0.0, jaro("a", "b"));
+    }
+
+    #[test]
+    fn jaro_same_one_character() {
+        assert_eq!(1.0, jaro("a", "a"));
+    }
+
+    #[test]
+    fn generic_jaro_diff() {
+        assert_eq!(0.0, generic_jaro(&[1, 2], &[3, 4]));
+    }
+
+    #[test]
+    fn jaro_diff_one_and_two() {
+        assert!((0.83 - jaro("a", "ab")).abs() < 0.01);
+    }
+
+    #[test]
+    fn jaro_diff_two_and_one() {
+        assert!((0.83 - jaro("ab", "a")).abs() < 0.01);
+    }
+
+    #[test]
+    fn jaro_diff_no_transposition() {
+        assert!((0.822 - jaro("dwayne", "duane")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_diff_with_transposition() {
+        assert!((0.944 - jaro("martha", "marhta")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_names() {
+        assert!((0.392 - jaro("Friedrich Nietzsche",
+                              "Jean-Paul Sartre")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_both_empty() {
+        assert_eq!(1.0, jaro_winkler("", ""));
+    }
+
+    #[test]
+    fn jaro_winkler_first_empty() {
+        assert_eq!(0.0, jaro_winkler("", "jaro-winkler"));
+    }
+
+    #[test]
+    fn jaro_winkler_second_empty() {
+        assert_eq!(0.0, jaro_winkler("distance", ""));
+    }
+
+    #[test]
+    fn jaro_winkler_same() {
+        assert_eq!(1.0, jaro_winkler("Jaro-Winkler", "Jaro-Winkler"));
+    }
+
+    #[test]
+    fn jaro_winkler_multibyte() {
+        assert!((0.89 - jaro_winkler("testabctest", "testöঙ香test")).abs() <
+            0.001);
+        assert!((0.89 - jaro_winkler("testöঙ香test", "testabctest")).abs() <
+            0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_diff_short() {
+        assert!((0.813 - jaro_winkler("dixon", "dicksonx")).abs() < 0.001);
+        assert!((0.813 - jaro_winkler("dicksonx", "dixon")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_diff_one_character() {
+        assert_eq!(0.0, jaro_winkler("a", "b"));
+    }
+
+    #[test]
+    fn jaro_winkler_same_one_character() {
+        assert_eq!(1.0, jaro_winkler("a", "a"));
+    }
+
+    #[test]
+    fn jaro_winkler_diff_no_transposition() {
+        assert!((0.840 - jaro_winkler("dwayne", "duane")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_diff_with_transposition() {
+        assert!((0.961 - jaro_winkler("martha", "marhta")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_names() {
+        assert!((0.562 - jaro_winkler("Friedrich Nietzsche",
+                                      "Fran-Paul Sartre")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_long_prefix() {
+        assert!((0.911 - jaro_winkler("cheeseburger", "cheese fries")).abs() <
+            0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_more_names() {
+        assert!((0.868 - jaro_winkler("Thorkel", "Thorgier")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_length_of_one() {
+        assert!((0.738 - jaro_winkler("Dinsdale", "D")).abs() < 0.001);
+    }
+
+    #[test]
+    fn jaro_winkler_very_long_prefix() {
+        assert!((1.0 - jaro_winkler("thequickbrownfoxjumpedoverx",
+                                    "thequickbrownfoxjumpedovery")).abs() <
+            0.001);
+    }
+
+    #[test]
+    fn levenshtein_empty() {
+        assert_eq!(0, levenshtein("", ""));
+    }
+
+    #[test]
+    fn levenshtein_same() {
+        assert_eq!(0, levenshtein("levenshtein", "levenshtein"));
+    }
+
+    #[test]
+    fn levenshtein_diff_short() {
+        assert_eq!(3, levenshtein("kitten", "sitting"));
+    }
+
+    #[test]
+    fn levenshtein_diff_with_space() {
+        assert_eq!(5, levenshtein("hello, world", "bye, world"));
+    }
+
+    #[test]
+    fn levenshtein_diff_multibyte() {
+        assert_eq!(3, levenshtein("öঙ香", "abc"));
+        assert_eq!(3, levenshtein("abc", "öঙ香"));
+    }
+
+    #[test]
+    fn levenshtein_diff_longer() {
+        let a = "The quick brown fox jumped over the angry dog.";
+        let b = "Lorem ipsum dolor sit amet, dicta latine an eam.";
+        assert_eq!(37, levenshtein(a, b));
+    }
+
+    #[test]
+    fn levenshtein_first_empty() {
+        assert_eq!(7, levenshtein("", "sitting"));
+    }
+
+    #[test]
+    fn levenshtein_second_empty() {
+        assert_eq!(6, levenshtein("kitten", ""));
+    }
+
+    #[test]
+    fn normalized_levenshtein_diff_short() {
+        assert!((normalized_levenshtein("kitten", "sitting") - 0.57142).abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_levenshtein_for_empty_strings() {
+        assert!((normalized_levenshtein("", "") - 1.0).abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_levenshtein_first_empty() {
+        assert!(normalized_levenshtein("", "second").abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_levenshtein_second_empty() {
+        assert!(normalized_levenshtein("first", "").abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_levenshtein_identical_strings() {
+        assert!((normalized_levenshtein("identical", "identical") - 1.0).abs() < 0.00001);
+    }
+
+    #[test]
+    fn osa_distance_empty() {
+        assert_eq!(0, osa_distance("", ""));
+    }
+
+    #[test]
+    fn osa_distance_same() {
+        assert_eq!(0, osa_distance("damerau", "damerau"));
+    }
+
+    #[test]
+    fn osa_distance_first_empty() {
+        assert_eq!(7, osa_distance("", "damerau"));
+    }
+
+    #[test]
+    fn osa_distance_second_empty() {
+        assert_eq!(7, osa_distance("damerau", ""));
+    }
+
+    #[test]
+    fn osa_distance_diff() {
+        assert_eq!(3, osa_distance("ca", "abc"));
+    }
+
+    #[test]
+    fn osa_distance_diff_short() {
+        assert_eq!(3, osa_distance("damerau", "aderua"));
+    }
+
+    #[test]
+    fn osa_distance_diff_reversed() {
+        assert_eq!(3, osa_distance("aderua", "damerau"));
+    }
+
+    #[test]
+    fn osa_distance_diff_multibyte() {
+        assert_eq!(3, osa_distance("öঙ香", "abc"));
+        assert_eq!(3, osa_distance("abc", "öঙ香"));
+    }
+
+    #[test]
+    fn osa_distance_diff_unequal_length() {
+        assert_eq!(6, osa_distance("damerau", "aderuaxyz"));
+    }
+
+    #[test]
+    fn osa_distance_diff_unequal_length_reversed() {
+        assert_eq!(6, osa_distance("aderuaxyz", "damerau"));
+    }
+
+    #[test]
+    fn osa_distance_diff_comedians() {
+        assert_eq!(5, osa_distance("Stewart", "Colbert"));
+    }
+
+    #[test]
+    fn osa_distance_many_transpositions() {
+        assert_eq!(4, osa_distance("abcdefghijkl", "bacedfgihjlk"));
+    }
+
+    #[test]
+    fn osa_distance_diff_longer() {
+        let a = "The quick brown fox jumped over the angry dog.";
+        let b = "Lehem ipsum dolor sit amet, dicta latine an eam.";
+        assert_eq!(36, osa_distance(a, b));
+    }
+
+    #[test]
+    fn osa_distance_beginning_transposition() {
+        assert_eq!(1, osa_distance("foobar", "ofobar"));
+    }
+
+    #[test]
+    fn osa_distance_end_transposition() {
+        assert_eq!(1, osa_distance("specter", "spectre"));
+    }
+
+    #[test]
+    fn osa_distance_restricted_edit() {
+        assert_eq!(4, osa_distance("a cat", "an abct"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_empty() {
+        assert_eq!(0, damerau_levenshtein("", ""));
+    }
+
+    #[test]
+    fn damerau_levenshtein_same() {
+        assert_eq!(0, damerau_levenshtein("damerau", "damerau"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_first_empty() {
+        assert_eq!(7, damerau_levenshtein("", "damerau"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_second_empty() {
+        assert_eq!(7, damerau_levenshtein("damerau", ""));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff() {
+        assert_eq!(2, damerau_levenshtein("ca", "abc"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_short() {
+        assert_eq!(3, damerau_levenshtein("damerau", "aderua"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_reversed() {
+        assert_eq!(3, damerau_levenshtein("aderua", "damerau"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_multibyte() {
+        assert_eq!(3, damerau_levenshtein("öঙ香", "abc"));
+        assert_eq!(3, damerau_levenshtein("abc", "öঙ香"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_unequal_length() {
+        assert_eq!(6, damerau_levenshtein("damerau", "aderuaxyz"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_unequal_length_reversed() {
+        assert_eq!(6, damerau_levenshtein("aderuaxyz", "damerau"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_comedians() {
+        assert_eq!(5, damerau_levenshtein("Stewart", "Colbert"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_many_transpositions() {
+        assert_eq!(4, damerau_levenshtein("abcdefghijkl", "bacedfgihjlk"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_diff_longer() {
+        let a = "The quick brown fox jumped over the angry dog.";
+        let b = "Lehem ipsum dolor sit amet, dicta latine an eam.";
+        assert_eq!(36, damerau_levenshtein(a, b));
+    }
+
+    #[test]
+    fn damerau_levenshtein_beginning_transposition() {
+        assert_eq!(1, damerau_levenshtein("foobar", "ofobar"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_end_transposition() {
+        assert_eq!(1, damerau_levenshtein("specter", "spectre"));
+    }
+
+    #[test]
+    fn damerau_levenshtein_unrestricted_edit() {
+        assert_eq!(3, damerau_levenshtein("a cat", "an abct"));
+    }
+
+    #[test]
+    fn normalized_damerau_levenshtein_diff_short() {
+        assert!((normalized_damerau_levenshtein("levenshtein", "löwenbräu") - 0.27272).abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_damerau_levenshtein_for_empty_strings() {
+        assert!((normalized_damerau_levenshtein("", "") - 1.0).abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_damerau_levenshtein_first_empty() {
+        assert!(normalized_damerau_levenshtein("", "flower").abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_damerau_levenshtein_second_empty() {
+        assert!(normalized_damerau_levenshtein("tree", "").abs() < 0.00001);
+    }
+
+    #[test]
+    fn normalized_damerau_levenshtein_identical_strings() {
+        assert!((normalized_damerau_levenshtein("sunglasses", "sunglasses") - 1.0).abs() < 0.00001);
+    }
+
+    #[test]
+    fn sorensen_dice_all() {
+        // test cases taken from
+        // https://github.com/aceakash/string-similarity/blob/f83ba3cd7bae874c20c429774e911ae8cff8bced/src/spec/index.spec.js#L11
+
+        assert_eq!(1.0, sorensen_dice("a", "a"));
+        assert_eq!(0.0, sorensen_dice("a", "b"));
+        assert_eq!(1.0, sorensen_dice("", ""));
+        assert_eq!(0.0, sorensen_dice("a", ""));
+        assert_eq!(0.0, sorensen_dice("", "a"));
+        assert_eq!(1.0, sorensen_dice("apple event", "apple    event"));
+        assert_eq!(0.9090909090909091, sorensen_dice("iphone", "iphone x"));
+        assert_eq!(0.0, sorensen_dice("french", "quebec"));
+        assert_eq!(1.0, sorensen_dice("france", "france"));
+        assert_eq!(0.2, sorensen_dice("fRaNce", "france"));
+        assert_eq!(0.8, sorensen_dice("healed", "sealed"));
+        assert_eq!(
+            0.7878787878787878,
+            sorensen_dice("web applications", "applications of the web")
+        );
+        assert_eq!(
+            0.92,
+            sorensen_dice(
+                "this will have a typo somewhere",
+                "this will huve a typo somewhere"
+            )
+        );
+        assert_eq!(
+            0.6060606060606061,
+            sorensen_dice(
+                "Olive-green table for sale, in extremely good condition.",
+                "For sale: table in very good  condition, olive green in colour."
+            )
+        );
+        assert_eq!(
+            0.2558139534883721,
+            sorensen_dice(
+                "Olive-green table for sale, in extremely good condition.",
+                "For sale: green Subaru Impreza, 210,000 miles"
+            )
+        );
+        assert_eq!(
+            0.1411764705882353,
+            sorensen_dice(
+                "Olive-green table for sale, in extremely good condition.",
+                "Wanted: mountain bike with at least 21 gears."
+            )
+        );
+        assert_eq!(
+            0.7741935483870968,
+            sorensen_dice("this has one extra word", "this has one word")
+        );
+    }
+}