On Tue, 29 Dec 2009, Andreas Raab wrote:
> Levente Uzonyi wrote:
>> Hi,
>>
>> We rewrote TextDiffBuilder using a modified version of the greedy longest
>> common subsequence algorithm from 'An O(ND) Difference Algorithm and Its
>> Variations (1986)' by Eugene W. Myers [1]. It's in The Inbox as:
>>
>> System-klub.209. The implementation is smaller, faster, gives a minimal
>> patch and passes the tests.
>>
>> Old New Ratio
>> Number of classes 5 4 0.8
>> Number of methods 50 29 0.58
>> Lines of code 387 197 0.51
>>
>> We would appreciate if someone can review this before moving into trunk.
>
> Looks good. There seem to be a few matches that are shown differently (tried
> with various MC diffs) but that's to be expected since it's a different
> algorithm. Ship it :-)
Done. The main reason for the rewrite was that the old version didn't
create minimal patches, even for really simple cases (see the failing
tests). First I tried to fix it, but when I saw how bloated the
implementation was for such a simple thing, I thought a rewrite would be
better. Actually I couldn't find out how the old version worked.
Another reason for the differences in the diffs is that we accidentally
swapped the order of insertions and removals when they occured after each
other. This made only a "visual" difference. With the latest version, this
is fixed too.
Levente
>
> Cheers,
> - Andreas
>
>
>
Locked
