old-list vs. new-list ==> diff wrt. operations

[Lars Rune Nøstdal]

hey,
i'm trying to figure out a way to create diffs between lists .. diffs
that represent what one would need to do to go from old-list to new-list
wrt. operations (move, append, prepend, insert, remove) .. but maybe
something already exists out there?

i'm doing UI type stuff .. say i'm removing something from a list, then
i insert it back at another place .. the "diff" in this case should
yield a move instead of a remove and an insert

(lisp list <-> "ui container")

the idea is to enable one to use normal lisp list functions on "ui
container widgets" .. i'm thinking something like:

(with-bulk-update-of (some-container)
...)

..and, yeah, before vs. after -- something like that..

..done before in some way?

[Pascal J. Bourguignon]

Lars Rune Nøstdal <larsn...@gmail.com> writes:

> hey,
> i'm trying to figure out a way to create diffs between lists .. diffs
> that represent what one would need to do to go from old-list to new-list
> wrt. operations (move, append, prepend, insert, remove) .. but maybe
> something already exists out there?
>
> i'm doing UI type stuff .. say i'm removing something from a list, then
> i insert it back at another place .. the "diff" in this case should
> yield a move instead of a remove and an insert

Are you sure it was a move? Perhaps it was a remove of the elements
before, and an insert of the removed elements after?

(a b c d e f) -> (a d e b c f)
may have been obtained either as:
(a b c d e f) -> (a c d e f) -> (a d e f) -> (a d e c f) -> (a d e b c f)
or:
(a b c d e f) -> (a b c e f) -> (a b c f) -> (a e b c f) -> (a d e b c f)
or a few other ways...

I'll just give you the difference, and let you use them as you want:

C/USER[40]> (COM.INFORMATIMAGO.COMMON-LISP.LIST:TREE-DIFFERENCE
'(a (b nil d) (b c) (d e f) g h)
'(a (b w d) (b c x) (d e y) g h))
(= (= (/= NIL W) = . =) (= = /= NIL (X)) (= = (/= F Y) . =) = = . =)

--
__Pascal Bourguignon__ http://www.informatimago.com/

"I have challenged the entire quality assurance team to a Bat-Leth
contest. They will not concern us again."

[Michael Weber]

On Nov 15, 9:01 am, Lars Rune Nøstdal <larsnost...@gmail.com> wrote:
> i'm trying to figure out a way to create diffs between lists .. diffs
> that represent what one would need to do to go from old-list to new-list
> wrt. operations (move, append, prepend, insert, remove) .. but maybe
> something already exists out there?

[...]

> ..and, yeah, before vs. after -- something like that..
>
> ..done before in some way?

This apparently implements Selkow's algorithms:
<http://www.foldr.org/~michaelw/log/programming/lisp/diff-sexp>

My idea was just to lift Levenshtein distance to trees. There are
better ways, however. Dan Ehrenberg did a survey some time ago:
http://factorforge.org/dan/XHTML_diff_survey.pdf

[Lars Rune Nøstdal]

i decided to try something from scratch, this is quite messy and not
correct, but:

;; using cl-utilities and alexandria

(defun exchange (element-1 element-2 list &key (test #'eql))
(let ((sub-1 (member element-1 list :test test))
(sub-2 (member element-2 list :test test)))
(setf (car sub-1) element-2
(car sub-2) element-1))
list)


(defun determine-diff-operations (before after &key (test #'equal))
(declare (list before after))
(collecting
;; Remove.
(dolist (removed-element (set-difference before after :test test))
(deletef before removed-element :test test)
(collect (list 'remove removed-element)))

;; Exchange or move.
(let ((goal (remove-if-not (lambda (elt) (find elt before :test test)) after)))
(while (catch 'not-done-p
(map nil (lambda (before-elt goal-elt)
(unless (funcall test before-elt goal-elt)
(collect (list 'exchange-pos before-elt goal-elt))
(exchange before-elt goal-elt before :test test)
(throw 'not-done-p t)))
before
goal)
nil)))

;; Append.
;; TODO: SET-DIFFERENCE might not maintain order.
(dolist (added-element (reverse (set-difference after before :test test)))
(collect (list 'append added-element
:after (ignore-errors (nth (1- (position added-element after)) after)))))))



SW> (determine-diff-operations (list "a") (list "a"))
NIL
SW> (determine-diff-operations (list "a") (list "b"))
((REMOVE "a") (APPEND "b" :AFTER NIL))
SW> (determine-diff-operations (list "a") (list "b" "a"))
((APPEND "b" :AFTER NIL))
SW> (determine-diff-operations (list "a") (list "a" "b"))
((APPEND "b" :AFTER "a"))
SW> (determine-diff-operations (list "a" "b") (list "a" "b"))
NIL
SW> (determine-diff-operations (list "a" "b") (list "b" "a"))
((EXCHANGE-POS "a" "b"))
SW> (determine-diff-operations (list "a" "b" "c") (list "b" "a"))
((REMOVE "c") (EXCHANGE-POS "a" "b"))
SW> (determine-diff-operations (list "a" "b" "c") (list "c" "b" "a"))
((EXCHANGE-POS "a" "c"))
SW> (determine-diff-operations (list "a" "b" "c") (list "c" "d" "b" "a"))
((EXCHANGE-POS "a" "c") (APPEND "d" :AFTER "c"))
SW> (determine-diff-operations (list "a" "b" "c" "d") (list "x" "b" "c" "e"))
((REMOVE "d") (REMOVE "a") (APPEND "e" :AFTER "c") (APPEND "x" :AFTER NIL))
SW> (determine-diff-operations (list) (list))
NIL
SW> (determine-diff-operations (list "a" "b" "c" "d") (list "c" "x" "y" "b" ))
((REMOVE "d") (REMOVE "a") (EXCHANGE-POS "b" "c") (APPEND "x" :AFTER "c")
(APPEND "y" :AFTER "x"))

..it does seem to work; maybe Willam "Brain Damage" James could clean it
up for me..

(..i could not use diff-sexp since i need something that'll always try
to move things around (on the client); this is always cheaper in this
context..)