[darcs-devel] [patch1083] name change Lcs.hs -> Diff/Myers.hs (and 2 more)

[José Neder]

The functions dropStart and dropEnd run the first part of the
algorithm that is the same that in myers algorithm (ie step 1 and 2).
genNestedChanges do the 3 and 4 step. It first try to do it
byparagraph, then bylines and at last it make the remaining hunks with
mkdiff and patienceLcs.

1. Match the first lines of both if they're identical, then match the
second, third, etc. until a pair doesn't match. (dropStart)
2. Match the last lines of both if they're identical, then match the
next to last, second to last, etc. until a pair doesn't match.
(dropEnd)
3. Find all lines which occur exactly once on both sides, then do
longest common subsequence on those lines, matching them up.
(genNestedChanges ~ lcus)
4. Do steps 1-2 on each section between matched lines.
(genNestedChanges with break calls)

I'm running the tests now in case i miss something.

2013/7/30 Guillaume Hoffmann <bugs at darcs.net>:
>
> Guillaume Hoffmann <guillaumh at gmail.com> added the comment:
>
> Here is the report:
>
> http://hub.darcs.net/gh/bench/raw/crit2.html
>
> The same without the "totally different" benchmarks:
>
> http://hub.darcs.net/gh/bench/raw/crit2b.html
>
> So now on this example Patience is on par with Myers. I compiled the
> benchmark program with only the flag -Wall (no -O2 for instance).
>
> Can you submit the patch bundle with this new implementation?
>
> Can you add comments to Darcs.Diff.Patience? The functions dropStart,
> dropEnd, genNestedChanges, for instance.
>
> __________________________________
> Darcs bug tracker <bugs at darcs.net>
> <http://bugs.darcs.net/patch1083>
> __________________________________