An O(ND) diff algorithm in Arc 13 points by almkglor 5973 days ago | 10 comments 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))``````
 1 point by almkglor 5971 days ago | link `````` (let expander (fn (f var name body) `(let ,var (,f ,name) (after (do ,@body) (close ,var)))) `````` Unindented here. Is the above given its own division? But it wouldn't make much sense to group this by itself, since it's used privately by other functions.`````` (mac w/infile (var name . body) " Opens the given file `name' for input, assigning the stream to `var'. The stream is automatically closed on exit from the `body'. See also [[w/outfile]] [[w/instring]] [[w/stdin]] [[w/socket]] " (expander 'infile var name body)) `````` Again, unindented at this point. However, it shares some code with other functions after it.`````` (mac w/outfile (var name . body) " Opens the given file `name' for output, assigning the stream to `var'. The stream is automatically closed on exit from the `body'. See also [[w/infile]] [[w/appendfile]] [[w/outstring]] [[w/stdout]] " (expander 'outfile var name body)) `````` ... etc.Of course, we could just define a definition as being divided by unindented non-empty lines ^^.-----