This module implements Eugene Myers' Greedy Difference Algorithm described in 'An O(ND) Difference Algorithm and Its Variations' [Mye86].
The implementation is parametric in the comparison predicate. This predicate has to succeed if two elements are considered equal.
This 'greedy' algorithm that computes the number differences has complexity O((N+M)D) in both time and space. With M and N the lenghts of the input lists and D the number of changes.
This pseudocode is copied from the original article, where:
Constant MAX [0,M+N] Var V: Array [-MAX.. MAX] of Integer V = 0 For D = 0 to MAX Do For k = -D to D in steps of 2 Do If k = -D or (k = D and V[k-1] < V[k+1] Then x = V[k+1] Else x = V[k-1] + 1 y = x - k While (x < N, y < M and a(x+1) = b(y+1) Do (x,y) = (x+1,y+1) V[k] = x If (x >= N and y >= M) Then Length of an SES is D Stop Length of an SES is greater than MAX
?- diff([a,a,b,c], [b,c,d], '=', Diff). Diff = [del(0,a),del(0,a),ins(2,d)] ? yes ?-
The patch operation applies a list of changes expressed as diff_item/1 to obtain a new list. Note that given two lists L1, L2, if their Diff is applied to L1, it will be obtained L2:
?- L1 = [a,a,b,c], L2 = [b,c,d], diff(L1, L2, '=', Diff), patch(L1, Diff, L2). Diff = [del(0,a),del(0,a),ins(2,d)], L1 = [a,a,b,c], L2 = [b,c,d] ? yes ?-
Diff are the changes needed to transform Ls1 into Ls2.
diff_item(ins(P,_1)) :- nnegint(P). diff_item(del(P,_1)) :- nnegint(P).
X is a single edition in a sequence (insertion or deletion)