editdistancewf/
lib.rs

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

editdistancewf/
lib.rs
