use {myers, Diff, Replace};
#[test]
fn test_diff() {
    let a: &[usize] = &[0, 1, 2, 3, 4];
    let b: &[usize] = &[0, 1, 2, 9, 4];
    struct D {}
    impl Diff for D {
        type Error = ();
        fn delete(&mut self, o: usize, len: usize, new: usize) -> Result<(), ()> {
            assert_eq!(o, 3);
            assert_eq!(len, 1);
            assert_eq!(new, 3);
            println!("delete");
            Ok(())
        }
        fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {
            assert_eq!(o, 3);
            assert_eq!(n, 3);
            assert_eq!(len, 1);
            println!("insert");
            Ok(())
        }
    }
    let mut diff = Replace::new(D {});
    myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap()
}
#[test]
fn test_contiguous() {
    let a: &[usize] = &[0, 1, 2, 3, 4, 4, 4, 5];
    let b: &[usize] = &[0, 1, 2, 8, 9, 4, 4, 7];
    struct D {}
    impl Diff for D {
        type Error = ();
        fn delete(&mut self, _o: usize, _len: usize, _new: usize) -> Result<(), ()> {
            panic!("Should not delete")
        }
        fn insert(&mut self, _o: usize, _n: usize, _len: usize) -> Result<(), ()> {
            panic!("Should not insert")
        }
        fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {
            assert!(o != 3 || (l == 2 && nl == 2));
            assert!(o != 7 || (l == 1 && nl == 1));
            println!("replace {:?} {:?} {:?} {:?}", o, l, n, nl);
            Ok(())
        }
    }
    let mut diff = Replace::new(D {});
    myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap();
}
#[test]
fn test_replace() {
    let a: &[usize] = &[0, 1, 2, 3, 4];
    let b: &[usize] = &[0, 1, 2, 7, 8, 9];
    struct D {}
    impl Diff for D {
        type Error = ();
        fn delete(&mut self, _o: usize, _len: usize, _new: usize) -> Result<(), ()> {
            panic!("should not delete")
        }
        fn insert(&mut self, _o: usize, _n: usize, _len: usize) -> Result<(), ()> {
            panic!("should not insert")
        }
        fn replace(&mut self, _o: usize, _l: usize, _n: usize, _nl: usize) -> Result<(), ()> {
            Ok(())
        }
    }
    let mut diff = Replace::new(D {});
    myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap();
}
#[test]
fn test_pat() {
    let a: &[usize] = &[0, 1, 3, 4, 5];
    let b: &[usize] = &[0, 1, 4, 5, 8, 9];
    struct D {}
    impl Diff for D {
        type Error = ();
        fn delete(&mut self, _o: usize, _len: usize, _new: usize) -> Result<(), ()> {
            println!("delete {:?} {:?} {:?}", _o, _len, _new);
            Ok(())
        }
        fn insert(&mut self, _o: usize, _n: usize, _len: usize) -> Result<(), ()> {
            println!("insert {:?} {:?} {:?}", _o, _n, _len);
            Ok(())
        }
        fn replace(&mut self, _o: usize, _l: usize, _n: usize, _nl: usize) -> Result<(), ()> {
            println!("replace {:?} {:?} {:?} {:?}", _o, _l, _n, _nl);
            Ok(())
        }
    }
    let mut diff = Replace::new(D {});
    myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap();
}

use Diff;
/// A "differ" that combines deletions and insertions to give blocks
/// of maximal length, and replacements when appropriate.
pub struct Replace<D: Diff> {
    d: D,
    del: Option<(usize, usize, usize)>,
    ins: Option<(usize, usize, usize)>,
    eq: Option<(usize, usize, usize)>,
}
impl<D: Diff> Replace<D> {
    pub fn new(d: D) -> Self {
        Replace {
            d,
            del: None,
            ins: None,
            eq: None,
        }
    }
    pub fn into_inner(self) -> D {
        self.d
    }
}
impl<D: Diff> AsRef<D> for Replace<D> {
    fn as_ref(&self) -> &D {
        &self.d
    }
}
impl<D: Diff> AsMut<D> for Replace<D> {
    fn as_mut(&mut self) -> &mut D {
        &mut self.d
    }
}
impl<D: Diff> Diff for Replace<D> {
    type Error = D::Error;
    fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
        if let Some((old0, len0, new0)) = self.del.take() {
            if let Some((_, new1, new_len1)) = self.ins.take() {
                self.d.replace(old0, len0, new1, new_len1)?
            } else {
                self.d.delete(old0, len0, new0)?
            }
        } else if let Some((old0, new0, new_len0)) = self.ins.take() {
            self.d.insert(old0, new0, new_len0)?
        }
        if let Some((a, b, c)) = self.eq.take() {
            self.eq = Some((a, b, c + len))
        } else {
            self.eq = Some((old, new, len))
        }
        Ok(())
    }
    fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        if let Some((old0, len0, new0)) = self.del.take() {
            assert_eq!(old, old0 + len0);
            self.del = Some((old0, len0 + len, new0))
        } else {
            self.del = Some((old, len, new))
        }
        Ok(())
    }
    fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        if let Some((old1, new1, new_len1)) = self.ins.take() {
            assert_eq!(new1 + new_len1, new);
            self.ins = Some((old1, new1, new_len + new_len1))
        } else {
            self.ins = Some((old, new, new_len))
        }
        Ok(())
    }
    fn replace(
        &mut self,
        old: usize,
        old_len: usize,
        new: usize,
        new_len: usize,
    ) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        self.d.replace(old, old_len, new, new_len)
    }
    fn finish(&mut self) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        if let Some((old0, len0, new0)) = self.del.take() {
            if let Some((_, new1, new_len1)) = self.ins.take() {
                self.d.replace(old0, len0, new1, new_len1)?
            } else {
                self.d.delete(old0, len0, new0)?
            }
        } else if let Some((old0, new0, new_len0)) = self.ins.take() {
            self.d.insert(old0, new0, new_len0)?
        }
        self.d.finish()
    }
}
#[test]
fn myers() {
    use myers;
    let a: &[&str] = &[
        ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n",
        "a\n",
        "b\n",
        "c\n",
        "================================\n",
        "d\n",
        "e\n",
        "f\n",
        "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
    ];
    let b: &[&str] = &[
        ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n",
        "x\n",
        "b\n",
        "c\n",
        "================================\n",
        "y\n",
        "e\n",
        "f\n",
        "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
    ];
    struct D {}
    impl Diff for D {
        type Error = ();
        fn equal(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {
            println!("equal {:?} {:?} {:?}", o, n, len);
            Ok(())
        }
        fn delete(&mut self, o: usize, len: usize, new: usize) -> Result<(), ()> {
            println!("delete {:?} {:?} {:?}", o, len, new);
            Ok(())
        }
        fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {
            println!("insert {:?} {:?} {:?}", o, n, len);
            Ok(())
        }
        fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {
            println!("replace {:?} {:?} {:?} {:?}", o, l, n, nl);
            Ok(())
        }
    }
    let mut d = Replace::new(D {});
    myers::diff(&mut d, a, 0, a.len(), b, 0, b.len()).unwrap();
}

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::hash::Hash;
use std::ops::Index;
use {myers, Diff, Replace};
struct I<'a, S: 'a + Index<usize> + ?Sized> {
    p: &'a S,
    i: usize,
}
impl<'a, A: Index<usize> + 'a> std::fmt::Debug for I<'a, A>
where
    A::Output: std::fmt::Debug,
{
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(fmt, "{:?}", &self.p[self.i])
    }
}
impl<'a, 'b, A: Index<usize> + 'b + ?Sized, B: Index<usize> + 'b + ?Sized> PartialEq<I<'a, A>>
    for I<'b, B>
where
    B::Output: PartialEq<A::Output>,
{
    fn eq(&self, b: &I<'a, A>) -> bool {
        self.p[self.i] == b.p[b.i]
    }
}
fn unique<A: Hash + Eq, S: Index<usize, Output = A> + ?Sized>(
    p: &S,
    e0: usize,
    e1: usize,
) -> Vec<I<S>> {
    let mut aa = HashMap::new();
    for i in e0..e1 {
        match aa.entry(&p[i]) {
            Entry::Vacant(e) => {
                e.insert(Some(i));
            }
            Entry::Occupied(mut e) => {
                let e = e.get_mut();
                if e.is_some() {
                    *e = None
                }
            }
        }
    }
    let mut v: Vec<_> = aa
        .into_iter()
        .filter_map(|(_, x)| x)
        .map(|i| I { p, i })
        .collect();
    v.sort_by(|a, b| a.i.cmp(&b.i));
    v
}
/// Patience diff algorithm.
pub fn diff<
    A: Hash + Eq,
    B: Hash + Eq + PartialEq<A>,
    S: Index<usize, Output = A> + ?Sized,
    T: Index<usize, Output = B> + ?Sized,
    D: Diff,
>(
    d: &mut D,
    e: &S,
    e0: usize,
    e1: usize,
    f: &T,
    f0: usize,
    f1: usize,
) -> Result<(), D::Error> {
    let au = unique(e, e0, e1);
    let bu = unique(f, f0, f1);
    struct Patience<
        'a,
        'b,
        'd,
        S: 'a + Index<usize> + ?Sized,
        T: 'b + Index<usize> + ?Sized,
        D: Diff + 'd,
    > {
        current_a: usize,
        current_b: usize,
        a1: usize,
        b1: usize,
        a: &'a S,
        b: &'b T,
        d: &'d mut D,
        au: &'a [I<'a, S>],
        bu: &'b [I<'b, T>],
    }
    impl<
            'a,
            'b,
            'd,
            S: 'a + Index<usize> + ?Sized,
            T: 'b + Index<usize> + ?Sized,
            D: Diff + 'd,
        > Diff for Patience<'a, 'b, 'd, S, T, D>
    where
        T::Output: PartialEq<S::Output>,
    {
        type Error = D::Error;
        fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
            // eprintln!("equal {:?} {:?} {:?}", old, new, len);
            for (old, new) in (old..old + len).zip(new..new + len) {
                let a0 = self.current_a;
                let b0 = self.current_b;
                while self.current_a < self.au[old].i
                    && self.current_b < self.bu[new].i
                    && self.b[self.current_b] == self.a[self.current_a]
                {
                    self.current_a += 1;
                    self.current_b += 1;
                }
                if self.current_a > a0 {
                    self.d.equal(a0, b0, self.current_a - a0)?
                }
                // let a = &self.a[self.current_a..self.au[old].i];
                // let b = &self.b[self.current_b..self.bu[new].i];
                // eprintln!("matching a: {:?} {:?}", self.current_a, self.au[old].i);
                // eprintln!("matching b: {:?} {:?}", self.current_b, self.bu[new].i);
                myers::diff_offsets(
                    self.d,
                    self.a,
                    self.current_a,
                    self.au[old].i,
                    self.b,
                    self.current_b,
                    self.bu[new].i,
                )?;
                self.current_a = self.au[old].i;
                self.current_b = self.bu[new].i;
            }
            Ok(())
        }
        /*
        fn insert(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
            eprintln!("insert {:?} {:?} {:?}", old, new, len);
            Ok(())
        }
        fn delete(&mut self, old: usize, len: usize) -> Result<(), D::Error> {
            eprintln!("delete {:?} {:?}", old, len);
            Ok(())
        }
        fn replace(
            &mut self,
            old: usize,
            len: usize,
            new: usize,
            new_len: usize,
        ) -> Result<(), D::Error> {
            eprintln!("replace {:?} {:?} {:?} {:?}", old, len, new, new_len);
            Ok(())
        }
        */
        fn finish(&mut self) -> Result<(), D::Error> {
            myers::diff(
                self.d,
                self.a,
                self.current_a,
                self.a1,
                self.b,
                self.current_b,
                self.b1,
            )
        }
    }
    let mut d = Replace::new(Patience {
        current_a: e0,
        current_b: f0,
        a: e,
        a1: e1,
        b: f,
        b1: f1,
        d,
        au: &au,
        bu: &bu,
    });
    myers::diff(&mut d, &au, 0, au.len(), &bu, 0, bu.len())?;
    Ok(())
}
#[test]
fn patience() {
    let a: &[usize] = &[11, 1, 2, 2, 3, 4, 4, 4, 5, 47, 19];
    let b: &[usize] = &[10, 1, 2, 2, 8, 9, 4, 4, 7, 47, 18];
    struct D(Vec<(usize, usize, usize, usize)>);
    impl Diff for D {
        type Error = ();
        fn delete(&mut self, o: usize, len: usize, new: usize) -> Result<(), ()> {
            self.0.push((o, len, new, 0));
            Ok(())
        }
        fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {
            self.0.push((o, 0, n, len));
            Ok(())
        }
        fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {
            self.0.push((o, l, n, nl));
            Ok(())
        }
    }
    let mut d = Replace::new(D(Vec::new()));
    diff(&mut d, a, 0, a.len(), b, 0, b.len()).unwrap();
    let d: D = d.into_inner();
    assert_eq!(
        d.0.as_slice(),
        &[(0, 1, 0, 1), (4, 2, 4, 2), (8, 1, 8, 1), (10, 1, 10, 1)]
    );
}

use std::cmp::{max, min};
use std::ops::Index;
use Diff;
fn modulo(a: isize, b: usize) -> usize {
    let b = b as isize;
    (((a % b) + b) % b) as usize
}
#[test]
fn test_modulo() {
    assert_eq!(modulo(-11, 10), 9);
    assert_eq!(modulo(23, 7), 2);
    assert_eq!(modulo(-12, 6), 0);
}
/// Myers' diff algorithm. Diff `e`, between indices `e0` (included)
/// and `e1` (excluded), on the one hand, and `f`, between indices
/// `f0` (included)` and `f1` (excluded), on the other hand.
pub fn diff<S: Index<usize> + ?Sized, T: Index<usize> + ?Sized, D: Diff>(
    d: &mut D,
    e: &S,
    e0: usize,
    e1: usize,
    f: &T,
    f0: usize,
    f1: usize,
) -> Result<(), D::Error>
where
    T::Output: PartialEq<S::Output>,
{
    diff_offsets(d, e, e0, e1, f, f0, f1)?;
    d.finish()
}
pub(crate) fn diff_offsets<D: Diff + ?Sized, S: Index<usize> + ?Sized, T: Index<usize> + ?Sized>(
    diff: &mut D,
    e: &S,
    i: usize,
    i_: usize,
    f: &T,
    j: usize,
    j_: usize,
) -> Result<(), D::Error>
where
    T::Output: PartialEq<S::Output>,
{
    if i_ > i && j_ > j {
        let n = i_ - i;
        let m = j_ - j;
        let l = (n + m) as isize;
        let z = (2 * min(n, m) + 2) as usize;
        let w = n as isize - m as isize;
        let mut g = vec![0; z as usize];
        let mut p = vec![0; z as usize];
        for h in 0..=(l / 2 + l % 2) {
            macro_rules! search {
                ($e: expr, $c: expr, $d: expr) => {
                    let (k0, k1) = {
                        let (m, n) = (m as isize, n as isize);
                        (-(h - 2*max(0, h - m)), h-2*max(0, h-n)+1)
                    };
                    for k in (k0..k1).step_by(2) {
                        let mut a: usize = if k == -h || k != h && $c[modulo(k-1, z)] < $c[modulo(k+1, z)] {
                            $c[modulo(k+1, z)]
                        } else {
                            $c[modulo(k-1, z)] + 1
                        };
                        let mut b = (a as isize - k) as usize;
                        let (s, t) = (a, b);
                        while a < n && b < m && {
                            let (e_i, f_i) = if $e { (a, b) } else { (n - a - 1, m - b - 1) };
                            f[j + f_i] == e[i + e_i]
                        } {
                            a += 1;
                            b += 1;
                        }
                        $c[modulo(k, z)] = a;
                        let bound = if $e { h-1 } else { h };
                        if (l%2 == 1) == $e
                            && w-k >= -bound && w-k <= bound
                            && $c[modulo(k, z)]+$d[modulo(w-k, z)] >= n
                        {
                            let (x, y, u, v) = if $e {
                                (s, t, a, b)
                            } else {
                                (n-a, m-b, n-s, m-t)
                            };
                            if h + bound > 1 || (x != u && y != v) {
                                diff_offsets(diff, e, i, i+x, f, j, j+y)?;
                                if x != u {
                                    diff.equal(i + x, j + y, u-x)?;
                                }
                                diff_offsets(diff, e, i+u, i_, f, j+v, j_)?;
                                return Ok(())
                            } else if m > n {
                                diff.equal(i, j, n)?;
                                diff.insert(i+n, j+n, m-n)?;
                                return Ok(())
                            } else if m < n {
                                diff.equal(i, j, m)?;
                                diff.delete(i+m, n-m, j+m)?;
                                return Ok(())
                            } else {
                                return Ok(())
                            }
                        }
                    }
                }
            }
            search!(true, g, p);
            search!(false, p, g);
        }
    } else if i_ > i {
        diff.delete(i, i_ - i, j)?
    } else if j_ > j {
        diff.insert(i, j, j_ - j)?
    }
    Ok(())
}

//! Various diff (longest common subsequence) algorithms, used in
//! practice:
//!
//! - Myers' diff, in time O((N+M)D) and space O(N+M), where N and M
//! are the sizes of the old and new version, respectively. See [the
//! original article by Eugene
//! W. Myers](http://www.xmailserver.org/diff2.pdf).
//!
//! - Patience diff, in time O(N log N + M log M + (N+M)D), and space
//! O(N+M), which tends to give more human-readable outputs. See [Bram
//! Cohen's blog post describing
//! it](https://bramcohen.livejournal.com/73318.html).
mod replace;
pub use replace::*;
/// Myers' diff algorithm
pub mod myers;
/// Patience diff algorithm
pub mod patience;
pub use myers::diff;
#[cfg(test)]
mod test;
#[allow(unused_variables)]
/// A trait for reacting to an edit script from the "old" version to
/// the "new" version.
pub trait Diff: Sized {
    type Error;
    /// Called when lines with indices `old` (in the old version) and
    /// `new` (in the new version) start an section equal in both
    /// versions, of length `len`.
    fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), Self::Error> {
        Ok(())
    }
    /// Called when a section of length `len`, starting at `old`,
    /// needs to be deleted from the old version.
    fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), Self::Error> {
        Ok(())
    }
    /// Called when a section of the new version, of length `new_len`
    /// and starting at `new`, needs to be inserted at position `old'.
    fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), Self::Error> {
        Ok(())
    }
    /// Called when a section of the old version, starting at index
    /// `old` and of length `old_len`, needs to be replaced with a
    /// section of length `new_len`, starting at `new`, of the new
    /// version.
    fn replace(
        &mut self,
        old: usize,
        old_len: usize,
        new: usize,
        new_len: usize,
    ) -> Result<(), Self::Error> {
        self.delete(old, old_len, new)?;
        self.insert(old, new, new_len)
    }
    /// Always called at the end of the algorithm.
    fn finish(&mut self) -> Result<(), Self::Error> {
        Ok(())
    }
}
impl<'a, D: Diff + 'a> Diff for &'a mut D {
    type Error = D::Error;
    fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), Self::Error> {
        (*self).equal(old, new, len)
    }
    fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), Self::Error> {
        (*self).delete(old, len, new)
    }
    fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), Self::Error> {
        (*self).insert(old, new, new_len)
    }
    fn replace(
        &mut self,
        old: usize,
        old_len: usize,
        new: usize,
        new_len: usize,
    ) -> Result<(), Self::Error> {
        (*self).replace(old, old_len, new, new_len)
    }
    fn finish(&mut self) -> Result<(), Self::Error> {
        (*self).finish()
    }
}

[package]
name = "diffs"
description = "A number of diff algorithms, also called longest common subsequence."
documentation = "https://docs.rs/diffs"
homepage = "https://nest.pijul.com/pijul_org/pijul"
version = "0.4.0"
license = "MIT/Apache-2.0"
authors = ["Pierre-Étienne Meunier <pe@pijul.org>"]
include = ["Cargo.toml", "src/lib.rs", "src/replace.rs", "src/patience.rs", "src/myers.rs", "src/test.rs"]