VersionedFile.walk deprecated?

[John Yates]

On Wednesday, 2006-04-19 Martin Pool wrote:

> On 19 Apr 2006, Aaron Bentley <aaron.bentley at utoronto.ca> wrote:
>
> [..SNIP..]
> 
> > This sounds very similar to the Patience sequence matcher which we will
> > merge in 0.9.
> > 
> > http://en.wikipedia.org/wiki/Patience_sorting
> 
> > >   http://www.abridgegame.org/pipermail/darcs-users/2005-April/006561.html
> 
> It's somewhat similar, and an interesting variation.  The description
> there doesn't say how you pick a line from the work list, or whether one
> is just chosen at random.

Early in that write-up  I pointed out that I had not worked on the diff
code but was writing based on a distant memory of a verbal description
of the algorithm.  I am sorry that I cannot provide more details.

>                            The patience-diff approach of trying to find
> the longest common subsequence is probably good.

The matching algorithm repeatedly eliminates maximal regions of
identical text from both files.  The work list invariant is that for any
line on the list there remains in each file exactly one "unmatched"
instance.  That invariant is incrementally maintained during the growth
of a matched region.  I fail to see how the order of selecting lines
from the work list can alter the final result.

In referencing the "longest common subsequence" heuristic are you
perhaps suggesting how one might proceed once the work list becomes
empty (no more unique unmatched lines)?

/john