1 //! Hamming distance 2 use crate::{Algorithm, Result}; 3 4 /// [Hamming distance] is the number of positions at which the corresponding symbols are different. 5 /// 6 /// [Hamming distance]: https://en.wikipedia.org/wiki/Hamming_distance 7 #[derive(Default)] 8 pub struct Hamming { 9 /// If false (default), the longer strings is truncated to the same length 10 /// as the shorter one. 11 pub truncate: bool, 12 } 13 14 impl Algorithm<usize> for Hamming { for_iter<C, E>(&self, mut s1: C, mut s2: C) -> Result<usize> where C: Iterator<Item = E>, E: Eq,15 fn for_iter<C, E>(&self, mut s1: C, mut s2: C) -> Result<usize> 16 where 17 C: Iterator<Item = E>, 18 E: Eq, 19 { 20 let mut result = 0; 21 let mut l1 = 0; 22 let mut l2 = 0; 23 loop { 24 match (s1.next(), s2.next()) { 25 (Some(c1), Some(c2)) => { 26 l1 += 1; 27 l2 += 1; 28 if c1 != c2 { 29 result += 1; 30 } 31 } 32 (Some(_), None) => { 33 l1 += 1; 34 if !self.truncate { 35 result += 1; 36 } 37 } 38 (None, Some(_)) => { 39 l2 += 1; 40 if !self.truncate { 41 result += 1; 42 } 43 } 44 (None, None) => { 45 break; 46 } 47 } 48 } 49 Result { 50 abs: result, 51 is_distance: true, 52 max: l1.max(l2), 53 len1: l1, 54 len2: l2, 55 } 56 } 57 } 58 59 #[cfg(test)] 60 mod tests { 61 #![allow(clippy::float_cmp)] 62 63 use super::{Algorithm, Hamming}; 64 use crate::str::hamming; 65 use assert2::assert; 66 use proptest::prelude::*; 67 use rstest::rstest; 68 69 #[rstest] 70 #[case("", "", 0)] 71 #[case("", "\0", 1)] 72 #[case("", "abc", 3)] 73 #[case("abc", "", 3)] 74 #[case("sitting", "sitting", 0)] 75 #[case("abcdefg", "hijklmn", 7)] 76 #[case("karolin", "kathrin", 3)] 77 #[case("hello", "world", 4)] 78 #[case("Rust", "rust", 1)] 79 #[case("hi mark", "hi markus", 2)] function_str(#[case] s1: &str, #[case] s2: &str, #[case] exp: usize)80 fn function_str(#[case] s1: &str, #[case] s2: &str, #[case] exp: usize) { 81 assert!(hamming(s1, s2) == exp); 82 } 83 84 #[test] default_struct_result()85 fn default_struct_result() { 86 let r = Hamming::default().for_str("Rust", "rust"); 87 assert!(r.dist() == 1); 88 assert!(r.sim() == 3); 89 assert!(r.ndist() == 0.25); 90 } 91 92 #[test] truncate()93 fn truncate() { 94 let a = Hamming { truncate: true }; 95 assert!(a.for_str("hi mark", "hi markus").val() == 0); 96 assert!(a.for_str("Hi mark", "hi markus").val() == 1); 97 } 98 99 proptest! { 100 #[test] 101 fn prop(s1 in ".*", s2 in ".*") { 102 let res = hamming(&s1, &s2); 103 let res2 = hamming(&s2, &s1); 104 prop_assert_eq!(res, res2); 105 prop_assert!(res <= s1.len() || res <= s2.len()); 106 } 107 } 108 } 109