diffs 0.2.1

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::hash::Hash;
use {myers, Diff, Replace};

#[derive(Debug)]
struct I<'a, A: 'a> {
    p: &'a [A],
    i: usize,
}

#[cfg(test)]
impl<'a, A: std::fmt::Debug + 'a> std::fmt::Debug for I<'a, A> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(fmt, "{:?}", self.p[self.i])
    }
}

impl<'a, 'b, A: 'a, B: PartialEq<A> + 'b> PartialEq<I<'a, A>> for I<'b, B> {
    fn eq(&self, b: &I<'a, A>) -> bool {
        self.p[self.i] == b.p[b.i]
    }
}

fn unique<A: Hash + Eq>(p: &[A]) -> Vec<I<A>> {
    let mut aa = HashMap::new();
    for (i, a) in p.iter().enumerate() {
        match aa.entry(a) {
            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, // + std::fmt::Debug,
    B: Hash + Eq + PartialEq<A>, // + std::fmt::Debug,
    D: Diff,
>(
    d: &mut D,
    a: &[A],
    b: &[B],
) -> Result<(), D::Error> {
    let au = unique(a);
    let bu = unique(b);

    struct Patience<'a, 'b, 'd, A: 'a, B: 'b, D: Diff + 'd> {
        current_a: usize,
        current_b: usize,
        a: &'a [A],
        b: &'b [B],
        d: &'d mut D,
        au: &'a [I<'a, A>],
        bu: &'b [I<'b, B>],
    }
    impl<
            'a,
            'b,
            'd,
            A: 'a, // + std::fmt::Debug,
            B: 'b + PartialEq<A>, // + std::fmt::Debug,
            D: Diff + 'd,
        > Diff for Patience<'a, 'b, 'd, A, B, D>
    {
        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, a, b, self.current_a, self.current_b)?;
                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> {
            let a = &self.a[self.current_a..];
            let b = &self.b[self.current_b..];
            myers::diff_offsets(self.d, a, b, self.current_a, self.current_b)?;
            self.d.finish()
        }
    }
    let mut d = Replace::new(Patience {
        current_a: 0,
        current_b: 0,
        a,
        b,
        d,
        au: &au,
        bu: &bu,
    });
    myers::diff(&mut d, &au, &bu)?;
    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 {}
    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) -> Result<(), ()> {
            println!("delete {:?} {:?}", o, len);
            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 {});
    diff(&mut d, a, b).unwrap();
}