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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

//! Sequence alignment
//!
//! This crate implements commonly-used sequence alignment methods based on
//! edit operations. There are multiple crates available to compute edit
//! distances. However, to my knowledge there was no crate that supports
//! all of the following seqalign features:
//!
//! * Works on slices of any type.
//! * Can return both the edit distance and the edit script/alignment.
//! * Can be extended with new measures.
//!
//! # Example
//!
//! ```
//! use seqalign::Align;
//! use seqalign::measures::LevenshteinDamerau;
//!
//! let incorrect = &['t', 'p', 'y', 'o'];
//! let correct = &['t', 'y', 'p', 'o', 's'];
//!
//! let measure = LevenshteinDamerau::new(1, 1, 1, 1);
//! let alignment = measure.align(incorrect, correct);
//!
//! // Get the edit distance
//! assert_eq!(2, alignment.distance());
//!
//! // Get the edit script.
//! use seqalign::measures::LevenshteinDamerauOp;
//! use seqalign::op::IndexedOperation;
//!
//! assert_eq!(vec![
//!     IndexedOperation::new(LevenshteinDamerauOp::Match, 0, 0),
//!     IndexedOperation::new(LevenshteinDamerauOp::Transpose(1), 1, 1),
//!     IndexedOperation::new(LevenshteinDamerauOp::Match, 3, 3),
//!     IndexedOperation::new(LevenshteinDamerauOp::Insert(1), 4, 4)
//!   ], alignment.edit_script());
//! ```

#[cfg(test)]
#[macro_use]
extern crate lazy_static;

#[cfg(test)]
#[macro_use]
extern crate maplit;

#[cfg(test)]
#[macro_use]
extern crate pretty_assertions;

mod dynprog;
pub use crate::dynprog::{Align, Alignment};

pub mod measures;

pub mod op;

/// Trait for edit distance measures.
pub trait Measure<T> {
    /// The edit operations associated with the measure.
    type Operation: op::Operation<T>;

    /// Get a slice with the measure's operations. Typically, this contains
    /// all the enum variants of the associated type `Operation`.
    fn operations(&self) -> &[Self::Operation];
}

/// A pairing of two sequences.
pub struct SeqPair<'a, T> {
    pub source: &'a [T],
    pub target: &'a [T],
}