Making a good diff algorithm
I might be wildly misreading the code, but it seems like [1,2,3,a,b,c] diffed with [a,b,c,1,2,3] is going to appear as six lines of replacement.<p>The table will be {a :(1,1), b :(1,1), ...} because each line appears in both files exactly once.<p><pre><code>    do {
    c = a;
    d = b;
    &#x2F;&#x2F; first pass a=0, b=0
    &#x2F;&#x2F; the lines aren&#x27;t equal, they&#x27;re &quot;1&quot; and &quot;a&quot; so we pass this case.
    if (one[a] === two[b]) {
        equality();
    } else {
        &#x2F;&#x2F;one[0] is &quot;1&quot;, matching 1:(1,1)
        &#x2F;&#x2F;two[0] is &quot;a&quot;, matching a:(1,1)
        if (table[one[a]].two &lt; 1 &amp;&amp; table[two[b]].one &lt; 1)     {
            &#x2F;&#x2F;can&#x27;t get here
            replaceUniques();
        } else if (table[one[a]].two &lt; 1 &amp;&amp; one[a + 1] !== two[b + 2]) {
            &#x2F;&#x2F; 1:(1,1) cdr not less than 1, so this is out
            deletion();
        } else if (table[two[b]].one &lt; 1 &amp;&amp; one[a + 2] !== two[b + 1]) {
         &#x2F;&#x2F; a:(1,1) car not less than 1, so this is out
            insertion();
        } else if (table[one[a]].one - table[one[a]].two === 1 &amp;&amp; one[a + 1] !== two[b + 2]) {
            &#x2F;&#x2F; 0 === one[a+1] !== two[b+2]
            &#x2F;&#x2F;   === &quot;2&quot; !== &quot;c&quot;
            &#x2F;&#x2F;   === true
            deletionStatic();
        } else if (table[two[b]].two - table[two[b]].one === 1 &amp;&amp; one[a + 2] !== two[b + 1]) {
            &#x2F;&#x2F; 0 === one[a+2] !== two[b+1]
            &#x2F;&#x2F;   === &quot;3&quot; !== &quot;b&quot;
            &#x2F;&#x2F;   === true
            insertionStatic();
        } else {
            &#x2F;&#x2F; so we&#x27;re stuck replacing.
            replacement();
        }
    }
    a += 1;
    b += 1;
    } while (a &lt; lena &amp;&amp; b &lt; lenb);

</code></pre>
it&#x27;s very pretty, it just seems like it&#x27;s not not doing enough lookahead to find those long distance relationships.<p>(although i didn&#x27;t run it, i could have screwed up my interpretation)<p>in my limited experience, diff is very hard.<p><i>edit</i><p>fixed a couple typos in the comments.<p>yeah, three deletes and three inserts showing at least 3 lines of equality is preferable. ideally it&#x27;d show a single edit, move of 3 lines, but that&#x27;s really hard to do.