From: Lars Rune Nøstdal
Subject: old-list vs. new-list ==> diff wrt. operations
Date: 
Message-ID: <1226736091.15343.172.camel@blackbox.nostdal.org>
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?
From: Michael Weber
Subject: Re: old-list vs. new-list ==> diff wrt. operations
Date: 
Message-ID: <0f2157af-6506-4349-8737-79c3cadc4fcc@z28g2000prd.googlegroups.com>
On Nov 15, 9:01 am, Lars Rune Nøstdal <···········@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
From: Pascal J. Bourguignon
Subject: Re: old-list vs. new-list ==> diff wrt. operations
Date: 
Message-ID: <877i75mk16.fsf@hubble.informatimago.com>
Lars Rune N�stdal <···········@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."
From: Lars Rune Nøstdal
Subject: Re: old-list vs. new-list ==> diff wrt. operations
Date: 
Message-ID: <1226772276.15343.188.camel@blackbox.nostdal.org>
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..)
comp.lang.lisp / 2008 / nov