{"header":{"message":"Add the optimized diff routine","description":null,"timestamp":"2021-09-14T23:32:05.107917118Z","authors":[{}]},"hash":"BORN6A37DOU775BMVOCDMQW3IBBI7PWU3V5A5ITJIS7TIUIYUFTQC","authors":[{"key":"FHRXP5Jnb2MWLDrPrnLnkN2ryWcGCo6CRr1dXR9FW2YA"}],"deps":{"hashes":[["BORN6A37DOU775BMVOCDMQW3IBBI7PWU3V5A5ITJIS7TIUIYUFTQC","Add the optimized diff routine"],["AA",null],["IZUDXVF5R7IYD2D4LRII7Z6WFMY7ARFSNULPBOKQLPBGIFLPXHIQC","Add a simple testing executable"],["XNQ4AFHIXFKIQECZRFK3NUVN5SZYLH2B5SG2GEYLQNIMDR3KHLFQC","Init with the new Pijul"]],"deps":["IZUDXVF5R7IYD2D4LRII7Z6WFMY7ARFSNULPBOKQLPBGIFLPXHIQC"],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"optimized.rs","metadata":0},"context":[{"change":4,"pos":6}],"contents":[{"Add":"use std::collections::HashSet;"},{"Add":"use std::hash::Hash;"},{"Add":""},{"Add":"use crate::{myers, Diff};"},{"Add":""},{"Add":"#[derive(Debug)]"},{"Add":"enum Elems {"},{"Add":" UniqueRun(Vec),"},{"Add":" NormalElem(T),"},{"Add":"}"},{"Add":""},{"Add":"struct MapDiff<'a, D> {"},{"Add":" elems1: &'a [usize],"},{"Add":" elems2: &'a [usize],"},{"Add":" diff: D,"},{"Add":" e0: usize,"},{"Add":" f0: usize,"},{"Add":"}"},{"Add":""},{"Add":"fn create_elems<'a, T: Hash + Eq>(v: &'a [T], w: &'a [T]) -> (Vec, Vec>) {"},{"Add":" let hs: HashSet<_> = w.iter().collect();"},{"Add":" let mut elems = Vec::new();"},{"Add":" let mut ix_map = Vec::new();"},{"Add":" for (i, elem) in v.iter().enumerate() {"},{"Add":" if i == 0 || hs.contains(elem) {"},{"Add":" elems.push(Elems::NormalElem(elem));"},{"Add":" ix_map.push(i);"},{"Add":" // TODO: resurrect the last UniqueRun if it was too short"},{"Add":" } else {"},{"Add":" let l = elems.len();"},{"Add":" if let Elems::UniqueRun(e_vec) = &mut elems[l - 1] {"},{"Add":" e_vec.push(elem);"},{"Add":" } else {"},{"Add":" elems.push(Elems::UniqueRun(Vec::new()));"},{"Add":" ix_map.push(i);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" ix_map.push(v.len());"},{"Add":" (ix_map, elems)"},{"Add":"}"},{"Add":""},{"Add":"impl PartialEq for Elems {"},{"Add":" fn eq(&self, other: &Self) -> bool {"},{"Add":" match (self, other) {"},{"Add":" (Self::NormalElem(x), Self::NormalElem(y)) => x == y,"},{"Add":" _ => false,"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, D> MapDiff<'a, D> {"},{"Add":" pub fn new(diff: D, elems1: &'a [usize], elems2: &'a [usize], e0: usize, f0: usize) -> Self {"},{"Add":" Self {"},{"Add":" diff,"},{"Add":" elems1,"},{"Add":" elems2,"},{"Add":" e0,"},{"Add":" f0,"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, D: Diff> Diff for MapDiff<'a, D> {"},{"Add":" type Error = D::Error;"},{"Add":" fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {"},{"Add":" let old2 = self.elems1[old] + self.e0;"},{"Add":" let new2 = self.elems2[new] + self.f0;"},{"Add":" let len2 = self.elems1[old + len] - self.elems1[old];"},{"Add":" self.diff.equal(old2, new2, len2)"},{"Add":" }"},{"Add":""},{"Add":" fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), D::Error> {"},{"Add":" let old2 = self.elems1[old] + self.e0;"},{"Add":" let len2 = self.elems1[old + len] - self.elems1[old];"},{"Add":" let new2 = self.elems2[new] + self.f0;"},{"Add":" self.diff.delete(old2, len2, new2)"},{"Add":" }"},{"Add":""},{"Add":" fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), D::Error> {"},{"Add":" let old2 = self.elems1[old] + self.e0;"},{"Add":" let new2 = self.elems2[new] + self.f0;"},{"Add":" let new_len2 = self.elems2[new + new_len] - self.elems2[new];"},{"Add":" self.diff.insert(old2, new2, new_len2)"},{"Add":" }"},{"Add":""},{"Add":" fn replace("},{"Add":" &mut self,"},{"Add":" old: usize,"},{"Add":" old_len: usize,"},{"Add":" new: usize,"},{"Add":" new_len: usize,"},{"Add":" ) -> Result<(), D::Error> {"},{"Add":" let old2 = self.elems1[old] + self.e0;"},{"Add":" let old_len2 = self.elems1[old + old_len] - self.elems1[old];"},{"Add":" let new2 = self.elems2[new] + self.f0;"},{"Add":" let new_len2 = self.elems2[new + new_len] - self.elems2[new];"},{"Add":" self.diff.replace(old2, old_len2, new2, new_len2)"},{"Add":" }"},{"Add":""},{"Add":" fn finish(&mut self) -> Result<(), D::Error> {"},{"Add":" self.diff.finish()"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Optimized Myers' diff algorithm."},{"Add":"///"},{"Add":"/// Repeated sequences of unique elements are merged into one."},{"Add":"pub fn diff("},{"Add":" d: &mut D,"},{"Add":" e: &[T],"},{"Add":" e0: usize,"},{"Add":" e1: usize,"},{"Add":" f: &[T],"},{"Add":" f0: usize,"},{"Add":" f1: usize,"},{"Add":") -> Result<(), D::Error>"},{"Add":"where"},{"Add":" T: Eq + Hash + std::fmt::Debug,"},{"Add":"{"},{"Add":" let (ivec1, st1) = create_elems(&e[e0..e1], &f[f0..f1]);"},{"Add":" let (ivec2, st2) = create_elems(&f[f0..f1], &e[e0..e1]);"},{"Add":" let mut diff = MapDiff::new(d, &ivec1, &ivec2, e0, f0);"},{"Add":" myers::diff(&mut diff, &st1, 0, st1.len(), &st2, 0, st2.len())"},{"Add":"}"}]}},{"Edit":{"inode":{"change":4,"pos":18119},"path":"\"src/lib.rs\"","line":18,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":18734}],"down_context":[{"change":4,"pos":18734}],"flag":"BLOCK","start":3624,"end":3672,"inode":{"change":4,"pos":18119}}},"contents":[{"Add":"/// Unique line optimization"},{"Add":"pub mod optimized;"}]}},{"Replacement":{"inode":{"change":2,"pos":166},"path":"\"src/bin.rs\"","line":20,"ins":{"up_context":[{"change":2,"pos":640}],"down_context":[{"change":2,"pos":673}],"flag":"BLOCK","start":3673,"end":3705,"inode":{"change":2,"pos":166}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":640},"to":{"change":2,"start":640,"end":673},"introduced_by":2}],"inode":{"change":2,"pos":166}},"ins_contents":[{"Add":" println!(\"={}\", l);"}],"del_contents":[{"Del":" println!(\"= {}\", l);\n"}]}},{"Replacement":{"inode":{"change":2,"pos":166},"path":"\"src/bin.rs\"","line":27,"ins":{"up_context":[{"change":2,"pos":825}],"down_context":[{"change":2,"pos":858}],"flag":"BLOCK","start":3706,"end":3738,"inode":{"change":2,"pos":166}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":825},"to":{"change":2,"start":825,"end":858},"introduced_by":2}],"inode":{"change":2,"pos":166}},"ins_contents":[{"Add":" println!(\"<{}\", l);"}],"del_contents":[{"Del":" println!(\"< {}\", l);\n"}]}},{"Replacement":{"inode":{"change":2,"pos":166},"path":"\"src/bin.rs\"","line":34,"ins":{"up_context":[{"change":2,"pos":1008}],"down_context":[{"change":2,"pos":1041}],"flag":"BLOCK","start":3739,"end":3771,"inode":{"change":2,"pos":166}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":1008},"to":{"change":2,"start":1008,"end":1041},"introduced_by":2}],"inode":{"change":2,"pos":166}},"ins_contents":[{"Add":" println!(\">{}\", l);"}],"del_contents":[{"Del":" println!(\"> {}\", l);\n"}]}},{"Replacement":{"inode":{"change":2,"pos":166},"path":"\"src/bin.rs\"","line":45,"ins":{"up_context":[{"change":2,"pos":1186}],"down_context":[{"change":2,"pos":1282}],"flag":"BLOCK","start":3772,"end":3879,"inode":{"change":2,"pos":166}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":1186},"to":{"change":2,"start":1186,"end":1282},"introduced_by":2}],"inode":{"change":2,"pos":166}},"ins_contents":[{"Add":" \"Usage: diff \\nwhere is myers, optimized, or patience.\""}],"del_contents":[{"Del":" \"Usage: diff \\nwhere is myers, or patience.\"\n"}]}},{"Edit":{"inode":{"change":2,"pos":166},"path":"\"src/bin.rs\"","line":65,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":1819}],"down_context":[{"change":2,"pos":1819}],"flag":"BLOCK","start":3880,"end":4011,"inode":{"change":2,"pos":166}}},"contents":[{"Add":" } else if algorithm == \"optimized\" {"},{"Add":" diffs::optimized::diff(&mut differ, &l1, 0, l1.len(), &l2, 0, l2.len()).unwrap();"}]}}],"owner":"pijul","repo":"diffs","token":"OZaHLAprM49/zxw+dCXW7bwY3JI1LgSMiLeTjv2AYvc=","login":null}

…

Dependencies

Change contents