1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
#![crate_name = "editdistancewf"] #![crate_type = "lib"] fn materialise<T, I: Iterator<Item=T>>(iter: I) -> Vec<T> { let mut dest = Vec::new(); dest.extend(iter); dest } pub fn distance<T, I: Iterator<Item=T>>(left_stream: I, right_stream: I) -> usize where T: Eq { let left = materialise(left_stream); let right = materialise(right_stream); let width = left.len() + 1; let depth = right.len() + 1; let mut current = vec![0; width]; let mut previous = vec![0; width]; for i in 0..width { previous[i] = i; } current[0] = previous[0] + 1; for row in 1..depth { for column in 1..width { if left[column - 1] == right[row - 1] { current[column] = previous[column - 1]; } else { let above = previous[column] + 1; let diag = previous[column - 1] + 1; let aside = current [column - 1] + 1; current[column] = *[above, diag, aside] .iter() .min() .unwrap(); } } previous = current.clone(); current = vec![0; width]; current[0] = row+1; } previous[width-1] }