Adapted from the paper: http://citeseer.ist.psu.edu/cache/papers/cs/31172/http:zSzzSzxmailserver.orgzSzdiff2.pdf/myers86ond.pdf (require "lib/defpat.arc")
(def seqdiff (a b (o is is))
; data structure:
; (aseq bseq diff N)
(breakable:withs
(
build list
; dt here is the data structure above
snake
(fn (dt)
(let (aseq bseq diff N) dt
(if
(is (car aseq) (car bseq))
(do
(while (and aseq bseq (is (car aseq) (car bseq)))
(= diff (cons `(skip) diff)
N ( N 2)
aseq (cdr aseq)
bseq (cdr bseq)))
(if (is N 0) (break:rev diff))
(build aseq bseq diff N))
(is N 0)
(break:rev diff)
; else
dt)))
downsnake
(fn (dt)
(let (aseq bseq diff N) dt
(if bseq
(snake (build
aseq
(cdr bseq)
(cons `(insert ,(car bseq)) diff)
( N 1))))))
rightsnake
(fn (dt)
(let (aseq bseq diff N) dt
(if aseq
(snake (build
(cdr aseq)
bseq
(cons `(delete ,(car aseq)) diff)
( N 1))))))
Nof [_ 3]
minN
(fn (dt1 dt2)
(if (no dt1) dt2
(no dt2) dt1
(with (N1 (Nof dt1) N2 (Nof dt2))
(if (< N1 N2) dt1 dt2))))
nextline
(pm:afn
((x y . zs)) (cons (minN (rightsnake x) (downsnake y)) (self (cons y zs)))
((x)) (list (rightsnake x))))
((afn (line)
(self
(cons
(downsnake (car line))
(nextline line))))
; start the triangle with a single line
(list (snake (build a b nil (+ (len a) (len b))))))))
Example: arc> (seqdiff '(a b b d) '(a b d b))
((skip) (skip) (insert d) (skip) (delete d))
