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