Struct lcs::LcsTable

pub struct LcsTable<'a, T: 'a> {
    // some fields omitted
}

Methods

impl<'a, T> LcsTable<'a, T> where 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>

Gets the longest common subsequence between a and 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', &'b', &'c'], lcs);

fn longest_common_subsequences(&self) -> HashSet<Vec<&T>> where T: Hash

Gets all longest common subsequences between a and b.

Example:

use lcs::LcsTable;

let a: Vec<_> = "aaabbb-cccddd".chars().collect();
let b: Vec<_> = "cdab".chars().collect();

let table = LcsTable::new(&a, &b);
let lcses = table.longest_common_subsequences();

assert_eq!(2, lcses.len());
assert!(lcses.contains(&vec![&'a', &'b']));
assert!(lcses.contains(&vec![&'c', &'d']));

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')
]);

Trait Implementations

impl<'a, T: Debug + 'a> Debug for LcsTable<'a, T>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.