use std::collections::HashMap;
use std::collections::hash_map::Entry;
use rand::Rng;
use adler32::*;

fn main() {
    let mut rng = rand::thread_rng();
    let m: Vec<u8> = (0..1000).map(|_| rng.gen()).collect();

    let n = {
        let (a, b) = m.split_at(420);
        let mut n = a.to_vec();
        n.extend((0..10).map(|_| rng.gen::<u8>()));
        n.extend(b);
        n
    };

    let window = 100;

    let mut m_ad = Vec::with_capacity(m.len() / window);
    let mut m_h = HashMap::with_capacity(m.len() / window);
    'outer: for ch in m.chunks(window) {
        let ad = adler32(ch).unwrap();
        match m_h.entry(ad) {
            Entry::Vacant(e) => { e.insert(vec![m_ad.len()]); },
            Entry::Occupied(mut e) => {
                let e = e.get_mut();
                for &i in e.iter() {
                    let old = &n[i * window .. (i+1) * window];
                    if old == ch {
                        continue 'outer
                    }
                }
                e.push(m_ad.len());
            },
        }
        m_ad.push(ad);
    }

    println!("{:?}", m_ad);


    let mut ad = RollingAdler32::from_buffer(&n[..window]);

    let mut mm = Vec::new();

    let mut i = window;
    while i < n.len() {

        let h = ad.hash();
        if let Some(v) = m_h.get(&h) {
            for &v in v.iter() {
                let old = &m[v * window .. (v+1)*window];
                let new = &n[i - window .. i];
                if old == new {
                    mm.push(Chunk::Old {
                        pos: v
                    });
                    for _ in 0..window {
                        let a = n[i];
                        let b = n[i - window];
                        ad.remove(window, b);
                        ad.update(a);
                        i += 1;
                    }
                    break
                }
            }
        } else {
            if let Some(Chunk::New { ref mut len, .. }) = mm.last_mut() {
                *len += 1
            } else {
                mm.push(Chunk::New { start: i - window, len: 1 })
            }
            let a = n[i];
            let b = n[i - window];
            ad.remove(window, b);
            ad.update(a);
            i += 1;
        };
    }

    println!("{:?}", mm);
}

#[derive(Debug)]
enum Chunk {
    Old { pos: usize },
    New { start: usize, len: usize },
}