Version Compare/Merge: The Algorithm

[Marc Stiegler <marcs>]

All right, we're ready to program. The steps involved 
in transforming the original document into the final 
document are:

- Create a working document composed of movement runs.

- If the working document contains only a single 
movement run, we're done: only insertions and deletions are 
needed to transform the one document to the other.

- Repeat the following cycle until the working document 
is composed of a single composite run.

     -If there is are two runs that are properly 
adjacent, meld them together into a composite run 
     - If there are no properly adjacent runs, look 
for a reversed sequence. If there is a 
reversed sequence, treat that sequence as a working 
document and rearrange the sequence using the anchor 
method (described below).
     - If there are neither properly adjacent runs 
nor reversed sequences, use the anchor method to select 
and move a run.

-That's all, folks. Your document is transformed.

The only remaining question is, what is the anchor 
method? Here goes:

-Find the current anchor for the working document.  
-Compare the sizes of the 2 runs in the working 
document which would be neighbors to the anchor in the 
final document. 
-Move the smaller of those 2 runs to be  
properly adjacent to the anchor.

Wasn't that fun?

This algorithm has the following properties: 
Unreversing reversed sequences tends to localize 
motion--rather than moving each individual run in the 
sequence to a distant location, you shuffle them all 
locally and then move the collection as a single composite 
run. The anchor method, meanwhile, enforces the movement of 
small objects a long distance in preference to moving large 
objects small distances. Note that the anchor method, when 
used by itself, never produces nested motion; all nesting 
arises from local reverses that then get moved again.

This algorithm does NOT guarantee a minimum total count 
of movements. Therefore, it does not guarantees a 
heuristically optimal result. However, you'll have to work 
at it to construct a counterexample...at least, you'll have 
to work to construct a counterexample that you yourself 
understand (a random stream of sufficient length will 
eventually supply the counterexample...but how well would 
you, smart human, do at unraveling it yourself? :-)

The failures of this algorithm to create heuristically 
optimal solutions are discussed in the section on 
deficiencies coming up later.

--marcs