dam_lev 0.2.0

Implements the Damerau–Levenshtein diff algorithm.
Documentation 
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

`dam_lev` implements the [Damerau–Levenshtein diff algorithm](https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance).  That is, it will take two sequences and determine the minimum number of transpositions, substitutions, insertions, and deletions needed to transform the first sequence into the second.

# Usage

`dam_lev::diff` takes two vectors (of some type `T` which implements `Clone + PartialEq`) and returns a vector of `dam_lev::Mutation` objects.  This is an enum type with four variants corresponding to the four types of transformations.  For example,

```rust
use dam_lev::Mutation;

let seq1 = String::from("abcdef");
let seq2 = String::from("bcedxy");
let diffs = dam_lev::diff(&seq1.chars().collect(), &seq2.chars().collect());
assert_eq!(diffs, vec![Mutation::Deletion(0), Mutation::Transposition(3), Mutation::Substitution(5, 4), Mutation::Insertion(6, 5)]);
```

We see that the sequence of transformations is

* Delete the item at index 0 (`'a'`).
* Transpose the item at index 3 (`'d'`) with its successor.
* Substitute the item at index 5 (`'f'`) with the item from the second sequence at index 4 (`'x'`).
* Insert at index 6 the item from the second sequence at index 5 (`'y'`).

Note the index for the transposition.  Even though, after the deletion, the `'d'` is at index 2, it's at index 3 in the original version of the sequence.  Likewise for the successive mutations.

## Key function

If you want to customize how the items are compared, you can use `diff_with_key`:

```rust
let seq1 = vec![1, 2, 3];
let seq2 = vec![91, 92, 93];
let key = |num: &u32| num % 3;
let diffs = dam_lev::diff_with_key(&seq1, &seq2, key);
assert_eq!(diffs.len(), 0);
```

In this case, the items must only implement `Clone` and `key` must be of type `FnMut(&T) -> U` where `U` implements `PartialEq`.