Struct lcs::LcsTable
[−]
[src]
pub struct LcsTable<'a, T: 'a> { /* fields omitted */ }
Methods
impl<'a, T> LcsTable<'a, T> where
T: Eq,
[src]
T: Eq,
Finding longest common subsequences ("LCS") between two sequences requires constructing a n x
m table (where the two sequences are of lengths n and m). This is expensive to construct
and there's a lot of stuff you can calculate using it, so LcsTable
holds onto this data.
fn new(a: &'a [T], b: &'a [T]) -> LcsTable<'a, T>
Constructs a LcsTable for matching between two sequences a
and b
.
fn longest_common_subsequence(&self) -> Vec<(&T, &T)>
Gets the longest common subsequence between a
and b
. Returned elements are in the form
(elem_a, elem_b)
, where elem_a
is a reference to an element in a
, elem_b
is a
reference to an element in b
, and elem_a == elem_b
.
Example:
use lcs::LcsTable; let a: Vec<_> = "a--b---c".chars().collect(); let b: Vec<_> = "abc".chars().collect(); let table = LcsTable::new(&a, &b); let lcs = table.longest_common_subsequence(); assert_eq!(vec![(&'a', &'a'), (&'b', &'b'), (&'c', &'c')], lcs);
fn longest_common_subsequences(&self) -> HashSet<Vec<(&T, &T)>> where
T: Hash,
T: Hash,
Gets all longest common subsequences between a
and b
. Returned elements are in the form
(elem_a, elem_b)
, where elem_a
is a reference to an element in a
, elem_b
is a
reference to an element in b
, and elem_a == elem_b
.
Example:
use lcs::LcsTable; let a: Vec<_> = "gac".chars().collect(); let b: Vec<_> = "agcat".chars().collect(); let table = LcsTable::new(&a, &b); let subsequences = table.longest_common_subsequences(); assert_eq!(3, subsequences.len()); assert!(subsequences.contains(&vec![(&'a', &'a'), (&'c', &'c')])); assert!(subsequences.contains(&vec![(&'g', &'g'), (&'a', &'a')])); assert!(subsequences.contains(&vec![(&'g', &'g'), (&'c', &'c')]));
fn diff(&self) -> Vec<DiffComponent<&T>>
Computes a diff from a
to b
.
Example
use lcs::{DiffComponent, LcsTable}; let a: Vec<_> = "axb".chars().collect(); let b: Vec<_> = "abc".chars().collect(); let table = LcsTable::new(&a, &b); let diff = table.diff(); assert_eq!(diff, vec![ DiffComponent::Unchanged(&'a', &'a'), DiffComponent::Deletion(&'x'), DiffComponent::Unchanged(&'b', &'b'), DiffComponent::Insertion(&'c') ]);