http://subversion.tigris.org/issues/show_bug.cgi?id=405
http://subversion.tigris.org/issues/show_bug.cgi?id=405

Take another stab at implementing our own diff lib.
Drop the LCS algorithm used before (which looked promising
but didn't scale) and switch to a different algorithm.

Thanks a lot to Philip Martin for getting me clued in on how
to recover the actual LCS (which isn't in the paper
describing the algorithm).


* subversion/libsvn_delta/diff.c

  (svn_diff__tree_compare_common_token_count,
   svn_diff__tree_largest_common_alphabet_user,
   svn_diff__hat_create, svn_diff__hat_set,
   svn_diff__hat_get): Removed.

  (svn_diff__get_tokens): Modified to return a ring of positions,
    starting at the last one.
  
  (svn_diff__snake): New function.

  (svn_diff__lcs): Modified to implement a different algorithm:
    "An O(NP) Sequence Comparison Algorithm" by Sun Wu, Udi Manber
    and Gene Meyers.
    
  (svn_diff): Modified to cope with the new lcs format.

  (svn_diff3): Same.  Also make a start at better conflict/common diff
    detection (disabled for now).

jmckaskill/subversion,jmckaskill/subversion,jmckaskill/subversion,jmckaskill/subversion,jmckaskill/subversion,jmckaskill/subversion,jmckaskill/subversion,jmckaskill/subversion