Code

Implement the patience diff algorithm
authorJohannes Schindelin <Johannes.Schindelin@gmx.de>
Wed, 7 Jan 2009 17:04:09 +0000 (18:04 +0100)
committerJunio C Hamano <gitster@pobox.com>
Wed, 7 Jan 2009 21:35:44 +0000 (13:35 -0800)
commit92b7de93fb7801570ddc3195f03f30b9c201a3bd
treee7113b428c97f3e6b107f1d64c74f343eda7ecf9
parent8104ebfe8276657ee803cca7eb8665a78cf3ef83
Implement the patience diff algorithm

The patience diff algorithm produces slightly more intuitive output
than the classic Myers algorithm, as it does not try to minimize the
number of +/- lines first, but tries to preserve the lines that are
unique.

To this end, it first determines lines that are unique in both files,
then the maximal sequence which preserves the order (relative to both
files) is extracted.

Starting from this initial set of common lines, the rest of the lines
is handled recursively, with Myers' algorithm as a fallback when
the patience algorithm fails (due to no common unique lines).

This patch includes memory leak fixes by Pierre Habouzit.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
xdiff/xdiff.h
xdiff/xdiffi.c
xdiff/xdiffi.h
xdiff/xpatience.c [new file with mode: 0644]
xdiff/xprepare.c