seqdiff/

lib.rs

//! Functions to get correspondence between two sequences like diff,
//! based on Myers' algorithm.
#[cfg(test)]
mod tests;
use std::cmp::{max, min};
#[cfg(test)]
extern crate quickcheck;
#[cfg(test)]
#[macro_use(quickcheck)]
extern crate quickcheck_macros;
use std::isize::{MAX, MIN};

/// An alias for the result of diff type
pub type Diff = Vec<Option<usize>>;

struct Difference<'a, X, Y> {
    xv: &'a [X],
    yv: &'a [Y],

    // working memory for forward path
    vf: Vec<isize>,
    // working memory for backward path
    vb: Vec<isize>,
    offset_d: isize,

    // edit script for xv
    xe: Vec<Option<usize>>,
    // edit script for yv
    ye: Vec<Option<usize>>,
}

impl<'a, X, Y> Difference<'a, X, Y>
where
    X: PartialEq<Y>,
{
    fn new(xv: &'a [X], yv: &'a [Y]) -> Self {
        let dmax = xv.len() + yv.len() + 1;
        let offset_d = yv.len() as isize;
        let vf = vec![MIN; dmax];
        let vb = vec![MAX; dmax];
        let xe = vec![None; xv.len()];
        let ye = vec![None; yv.len()];
        Self {
            xv,
            yv,
            vf,
            vb,
            offset_d,
            xe,
            ye,
        }
    }

    fn diff(&mut self) -> usize {
        self.diff_part((0, self.xv.len()), (0, self.yv.len()))
    }

    fn diff_part(
        &mut self,
        (mut xl, mut xr): (usize, usize),
        (mut yl, mut yr): (usize, usize),
    ) -> usize {
        // shrink by equality
        while xl < xr && yl < yr && self.xv[xl] == self.yv[yl] {
            self.xe[xl] = Some(yl);
            self.ye[yl] = Some(xl);
            xl += 1;
            yl += 1;
        }
        // same as backward
        while xl < xr && yl < yr && self.xv[xr - 1] == self.yv[yr - 1] {
            xr -= 1;
            yr -= 1;
            self.xe[xr] = Some(yr);
            self.ye[yr] = Some(xr);
        }

        // process simple case
        if xl == xr {
            self.ye[yl..yr].iter_mut().for_each(|x| *x = None);
            yr - yl
        } else if yl == yr {
            self.xe[xl..xr].iter_mut().for_each(|x| *x = None);
            xr - xl

        // divide and conquer
        } else {
            let (d, (xm, ym)) = self.find_mid((xl, xr), (yl, yr));
            self.diff_part((xl, xm), (yl, ym));
            self.diff_part((xm, xr), (ym, yr));
            d
        }
    }

    #[allow(clippy::many_single_char_names)]
    fn find_mid(
        &mut self,
        (xl, xr): (usize, usize),
        (yl, yr): (usize, usize),
    ) -> (usize, (usize, usize)) {
        let xl = xl as isize;
        let xr = xr as isize;
        let yl = yl as isize;
        let yr = yr as isize;

        let kmin = xl - yr;
        let kmax = xr - yl;
        let kmidf = xl - yl; // center diag in this fragment for forwad snake
        let kmidb = xr - yr;
        let delta = (xr - xl) - (yr - yl);
        let is_odd = (delta & 1) == 1;

        // convert k to index of working memory (vf, vb)
        let ktoi = {
            let offset = self.offset_d;
            move |k: isize| -> usize { (k + offset) as usize }
        };

        self.vf[ktoi(kmidf)] = xl;
        self.vb[ktoi(kmidb)] = xr;

        let mut kminf = kmidf;
        let mut kmaxf = kmidf;
        let mut kminb = kmidb;
        let mut kmaxb = kmidb;

        let gety = |x: isize, k: isize| x.saturating_sub(k);

        for d in 1i64.. {
            // We don't have to check the case `d == 0` because it is handled in `fn diff_part`

            // forward
            {
                // update range
                if kminf > kmin {
                    kminf -= 1;
                    if let Some(x) = self.vf.get_mut(ktoi(kminf - 1)) {
                        *x = MIN;
                    }
                } else {
                    kminf += 1;
                }
                if kmaxf < kmax {
                    kmaxf += 1;
                    if let Some(x) = self.vf.get_mut(ktoi(kmaxf + 1)) {
                        *x = MIN;
                    }
                } else {
                    kmaxf -= 1
                }

                for k in (kminf..=kmaxf).rev().step_by(2) {
                    let ik = ktoi(k);
                    let x = {
                        let lo = self.vf.get(ktoi(k - 1)).cloned();
                        let hi = self.vf.get(ktoi(k + 1)).cloned();
                        max(lo.map(|x| x + 1), hi).unwrap()
                    };
                    let y = gety(x, k);
                    if !(xl <= x && x <= xr && yl <= y && y <= yr) {
                        continue;
                    }

                    // go forward in diagonal path
                    let (u, v) = {
                        let mut u = x;
                        let mut v = y;
                        let len = self.xv[u as usize..xr as usize]
                            .iter()
                            .zip(self.yv[v as usize..yr as usize].iter())
                            .take_while(|(x, y)| x == y)
                            .count() as isize;
                        u += len;
                        v += len;
                        (u, v)
                    };

                    debug_assert!(xl <= u && u <= xr);
                    debug_assert!(yl <= v && v <= yr);

                    self.vf[ik] = u;
                    if is_odd && kminb <= k && k <= kmaxb && self.vb[ik] <= u {
                        return (2 * d as usize - 1, (x as usize, y as usize));
                    }
                }
            }

            // backward
            {
                // update range
                if kminb > kmin {
                    kminb -= 1;
                    if let Some(x) = self.vb.get_mut(ktoi(kminb - 1)) {
                        *x = MAX;
                    }
                } else {
                    kminb += 1;
                }
                if kmaxb < kmax {
                    kmaxb += 1;
                    if let Some(x) = self.vb.get_mut(ktoi(kmaxb + 1)) {
                        *x = MAX;
                    }
                } else {
                    kmaxb -= 1
                }

                for k in (kminb..=kmaxb).rev().step_by(2) {
                    let x = {
                        let lo = self.vb.get(ktoi(k - 1)).cloned();
                        let hi = self.vb.get(ktoi(k + 1)).cloned();
                        match (lo, hi.map(|x| x - 1)) {
                            (Some(lo), Some(hi)) => min(lo, hi),
                            (Some(lo), _) => lo,
                            (_, Some(hi)) => hi,
                            _ => unreachable!(),
                        }
                    };
                    let y = gety(x, k);
                    if !(xl <= x && x <= xr && yl <= y && y <= yr) {
                        continue;
                    }

                    // go backward in diagonal path
                    let (u, v) = {
                        let mut u = x;
                        let mut v = y;
                        let len = self.xv[xl as usize..u as usize]
                            .iter()
                            .rev()
                            .zip(self.yv[yl as usize..v as usize].iter().rev())
                            .take_while(|(x, y)| x == y)
                            .count() as isize;
                        u -= len;
                        v -= len;
                        (u, v)
                    };
                    debug_assert!(xl <= u && u <= xr);
                    debug_assert!(yl <= v && v <= yr);

                    let ik = ktoi(k);
                    self.vb[ik] = u;
                    if !is_odd && kminf <= k && k <= kmaxf && self.vf[ik] >= u {
                        return (2 * d as usize, (x as usize, y as usize));
                    }
                }
            }
        }

        unreachable!();
    }
}

/// Returns the correspondence between two sequences.
///
/// The return value is a pair of tuples. The first tuple contains the index
/// where the item from the first sequence appears in the 2nd sequence or `None`
/// if the item doesn't appear in the 2nd sequence. The 2nd tuple is the same
/// but listing the corresponding indexes for the 2nd sequence in the first
/// sequence.
///
/// # Examples
///
/// ```
/// use seqdiff;
/// let (a2b, b2a) = seqdiff::diff(&[1, 2, 3], &[1, 3]);
/// assert_eq!(a2b, vec![Some(0), None, Some(1)]);
/// assert_eq!(b2a, vec![Some(0), Some(2)]);
/// ```
pub fn diff<A: PartialEq<B>, B>(a: &[A], b: &[B]) -> (Diff, Diff) {
    let mut st = Difference::new(a, b);
    st.diff();
    let Difference { xe, ye, .. } = st;
    (xe, ye)
}

/// Compute similarity of two sequences.
/// The similarity is a floating point number in [0., 100.], computed based on
/// Levenshtein distance.
/// This is useful, for example, fuzzy search.
///
/// # Examples
///
/// ```
/// use seqdiff::ratio;
/// let r = ratio(
///     &"Hello world!".chars().collect::<Vec<_>>(),
///     &"Holly grail!".chars().collect::<Vec<_>>(),
/// );
/// assert!((r - 58.333333333333337).abs() < 1e-5);
/// ```
#[allow(clippy::many_single_char_names)]
pub fn ratio<A: PartialEq<B>, B>(a: &[A], b: &[B]) -> f64 {
    let l = a.len() + b.len();
    if l == 0 {
        return 100.;
    }
    let dist = Difference::new(a, b).diff();
    let ret = l - dist;
    (ret * 100) as f64 / l as f64
}