Linux C or C ++ library for markup and patches?

Question

Possible duplicate:
Is there a way to separate files from C ++?

I have long text lines that I want to split and plan. These are lines a and b:

string a = ...; string b = ...; string a_diff_b = create_patch(a,b); string a2 = apply_patch(a_diff_b, b); assert(a == a2); 

If a_diff_b was a person to read, that would be a bonus.

One way to implement this is to use system(3) to invoke the diff and patch shell commands from diffutils and pass them to the lines. Another way would be to implement the functions on my own (I thought of each line atomically and used the standard editing distance n ^ 3 of the algorithm with reverse tracing).

I was wondering if anyone knows of a good Linux C or C ++ library that will do the job in the process?

Answer 1

You can run the Google Myers Diff algorithm. ("The algorithm of difference errors and its variations") or libraries that solve the problem "The longest common subsequence."

As far as I know, the situation with diff / patch in C ++ is not very good - there are several libraries (including diff match patch , libmba ), but, in my experience, they are either poorly documented or have heavy external dependencies (to fix matches require Qt 4, for example) or are specialized in a type that you don't need (std :: string when you need unicode, for example), or are not generalized enough, or use a general algorithm that has very high memory requirements (( M + N) ^ 2, where M and N are the lengths of the input sequences).

You can also try to implement the Myers ((N + M)) memory requirements, but the solution to the problem is extremely difficult to understand - expect to lose at least a week reading the documentation. In a sense, a human-readable explanation of the Myers algorithm is available here .

Answer 2

I think that

https://github.com/cubicdaiya/dtl/wiki/Tutorial

may have what you need

Answer 3

http://code.google.com/p/google-diff-match-patch/

The Diff Match and Patch libraries offer robust algorithms to perform the operations necessary to synchronize plain text.

Java, JavaScript, Dart, C ++, C #, Objective-C, Lua, and Python are currently available. Regardless of the language, each library has the same API and the same functions. All versions also have complete test harnesses.