"

 Copyright (c) 2007-2010 Jan Vrany, SWING Research Group, Czech Technical University in Prague

 Copyright (c) 2009-2010 eXept Software AG

 Permission is hereby granted, free of charge, to any person

 obtaining a copy of this software and associated documentation

 files (the 'Software'), to deal in the Software without

 restriction, including without limitation the rights to use,

 copy, modify, merge, publish, distribute, sublicense, and/or sell

 copies of the Software, and to permit persons to whom the

 Software is furnished to do so, subject to the following

 conditions:

 The above copyright notice and this permission notice shall be

 included in all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,

 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

 HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

 WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 OTHER DEALINGS IN THE SOFTWARE.

"

"{ Package: 'stx:libtool' }"

Object subclass:#Diff

	instanceVariableNames:'equivMax heuristic nodiscards xvec yvec fdiag bdiag fdiagoff

		bdiagoff filevec cost snakeLimit inhibit'

	classVariableNames:''

	poolDictionaries:''

!

Link subclass:#Change

	instanceVariableNames:'inserted deleted line0 line1'

	classVariableNames:''

	poolDictionaries:''

	privateIn:Diff

!

Object subclass:#Data

	instanceVariableNames:'bufferedLines equivs undiscarded realindexes nondiscardedLines

		changedFlag'

	classVariableNames:''

	poolDictionaries:''

	privateIn:Diff

!

Object subclass:#ForwardScript

	instanceVariableNames:''

	classVariableNames:''

	poolDictionaries:''

	privateIn:Diff

!

Object subclass:#ReverseScript

	instanceVariableNames:''

	classVariableNames:''

	poolDictionaries:''

	privateIn:Diff

!

!Diff class methodsFor:'documentation'!

copyright

"

 Copyright (c) 2007-2010 Jan Vrany, SWING Research Group, Czech Technical University in Prague

 Copyright (c) 2009-2010 eXept Software AG

 Permission is hereby granted, free of charge, to any person

 obtaining a copy of this software and associated documentation

 files (the 'Software'), to deal in the Software without

 restriction, including without limitation the rights to use,

 copy, modify, merge, publish, distribute, sublicense, and/or sell

 copies of the Software, and to permit persons to whom the

 Software is furnished to do so, subject to the following

 conditions:

 The above copyright notice and this permission notice shall be

 included in all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,

 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

 HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

 WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 OTHER DEALINGS IN THE SOFTWARE.

"

!

documentation

"

    I'm standard diff implementation written purely in Smalltalk. I can

    compute differences between two sequenceable collections, not neccesaarily

    holding strings. Elements are compared using #=.

    Result of comparison is an edit script, a linked list of Diff::Changes,

    each keeping one difference: whether change is insert and/or delete,

    and positions in A and B.

    I'm a port of Java diff.

    [author:]

        Jakub Zelenka (zelenj7@fel.cvut.cz)

        Vladislav Skoumal (skoumal@skoumal.net)

        Jan Vrany (jan.vrany@fit.cvut.cz)

    [instance variables:]

    [class variables:]

    [see also:]

"

!

documentation_czech

    "

první fáze:

#############################################################################################################################

first := #('prvni' 'druhy' 'treti' 'treti' 'paty' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy' 'treti' 'bbb' 'ccc' 'aaa' 'aaa' 'hhh' 'iii' 'mmm' 'nnn' 'ppp' 'aaa' 'aaa' ).

############################################################################################################################

First a second pøedstavujou dvì pole, které chceme porovnávat. Jednotlivé položky v poli si lze pøedstavit jako øádky, pøípadnì jako slova v øádku.

Podle toho, co je potøeba porovnávat.

*****************************************************************************************************************************

diff := FelDiff new felDiff.

*****************************************************************************************************************************

Zde probíhá inicializace defaultníh promìnných. Funguje to jako konstruktor.

############################################################################################################################

diff diff: first b: second

############################################################################################################################

První fáze nutná pro porovnávání polí.  Vzniknou dvì instance tøíde filedata uložené do pole. Tyto instance budou obsahovat následující údaje:

filevec[1].equivs=#(1 2 3 3 4 5 6)

filevec[1].bufferedLines=7

filevec[1].changedFlag=#()

filevec[2].equivs=#(1 3 6 7 3 8 9 10 10 11 12 13 14 15 10 10)

filevec[2].bufferedLines=16

filevec[2].changedFlag=#()

V zásadì se vytvoøila structura Dictionary, která jednotlivé øádky(slova) pøevedla na èísla. Pole equvs pak pøedstavuje èíselnì slova(øádky).

èísla, která se nalézají v obou dbou polí equivs znaèí, že soubory sdílí alespoò nìjaké slovo(øádek).

*****************************************************************************************************************************

change:= diff diff2: true.

*****************************************************************************************************************************

Zde již dochází k porovnání obou dvou polí s øádky(slovy). Lze si vybrat mezi forwardscriptem a reversescriptem. 

1) metoda discardconfusinglines

výsledek:

filevec[1].undiscardeded=#(1 3 3 5 6 0 0)

filevec[1].realIndexes=  #(0 2 3 5 6 0 0)

filevec[1].nondiscardedLines=5

filevec[1].changedFlag=#(false false true false false true false false false)

filevec[2].undiscardeded=#(1 3 5 6 3 0 0 0 0 0 0 0 0 0 0 0)

filevec[2].realIndexes=  #(0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 0)

filevec[2].nondiscardedLines=5

Undiscarded- Øádky soubory, které jsou shodné.

RealIndexes     - indexy øádkù v poli(je potøeba pøièíst jedna)

                        - to znamená že index prvního 3->3 pozice v prvním vstupním poli

                        - index druhého 3->2 pozice v druhém vstupním poli a 3->5 pozice v druhém vstupním poli 

NondiscardedLines- znaèí kolik èádkù(slov) je shodných v obou polích.

2)Následuje porovnávání jednotlivých polí a vytvoøení výsledku

3)Výsledek Reverse skript

inserted=12('treti' 'bbb' 'ccc' 'aaa' 'aaa' 'hhh' 'iii' 'mmm' 'nnn' 'ppp' 'aaa' 'aaa')

deleted=0

line0=7('ruzovy')

line1=4('ruzovy')

link=next

inserted- kolik znakù bylo vloženo

deleted - kolik znakù bylo smazáno

line0 - poøadí znaku za kterým bylo nìco vloženo(smazáno) v prvním poli(poslední znak který je shodný v obou polích)

line1 - poøadí znaku za kterým bylo nìco smazáno(vloženo) v prvním poli(poslední znak který je shodný v obou polích)

Takže po znaku na pozici 4, je 12 vložených znakù oproti prvnímu 

Zbytek pole vypadá takto:

first := #('prvni' 'druhy' 'treti' 'treti' 'paty' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy').

link není null a tudíž odkazuje na další informace o zmìnách.

inserted=0

deleted=2('treti' 'paty')

line0=3('treti')

line1=2('treti')

link=next

zbytek pole vypadá takto:

first := #('prvni' 'druhy' 'treti' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy').

link není null a tudíž odkazuje na další informace o zmìnách.

inserted=0

deleted=1('druhy')

line0=1('prvni')

line1=1('prvni')

link=nil

zbytek pole vypadá takto:

first :=  #('prvni' 'treti' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy').

link je nil. Neexistuje žádná zmìna a tato pole jsou shodná.

4)Výsledek Forward skript

inserted=0

deleted=1('druhy')

line0=1('prvni')

line1=1('prvni')

link=next

zbytek pole vypadá takto:

first :=  #('prvni' 'treti' 'treti' 'paty' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy' 'treti' 'bbb' 'ccc' 'aaa' 'aaa' 'hhh' 'iii' 'mmm' 'nnn' 'ppp' 'aaa' 'aaa' ).

link není nil jdeme na odkaz:

inserted=0

deleted=2('treti' 'paty')

line0=3('treti')

line1=2('treti')

link=next

zbytek pole vypadá takto:

first :=  #('prvni' 'treti' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy' 'treti' 'bbb' 'ccc' 'aaa' 'aaa' 'hhh' 'iii' 'mmm' 'nnn' 'ppp' 'aaa' 'aaa' ).

link není nil jdeme na odkaz:

inserted=12('treti' 'bbb' 'ccc' 'aaa' 'aaa' 'hhh' 'iii' 'mmm' 'nnn' 'ppp' 'aaa' 'aaa')

deleted=0

line0=7('ruzovy')

line1=4('ruzovy')

link=nil

zbytek pole vypadá takto:

first :=  #('prvni' 'treti' 'zeleny' 'ruzovy' ).

second := #('prvni' 'treti' 'zeleny' 'ruzovy').

Konec

"

! !

!Diff class methodsFor:'instance creation'!

new

    "return an initialized instance"

    ^ self basicNew initialize.

! !

!Diff class methodsFor:'diffing'!

between: a and: b 

    ^self between: a and: b reverse: false

    "Created: / 16-02-2010 / 23:08:55 / Jan Vrany <jan.vrany@fit.cvut.cz>"

!

between: a and: b reverse: reverse

    ^self new

        a: a b: b;

        diff: reverse

    "Created: / 16-02-2010 / 23:04:50 / Jan Vrany <jan.vrany@fit.cvut.cz>"

! !

!Diff methodsFor:'diffing'!

a:gA b:gB 

    "Prepare to find differences between two arrays.  Each element of

     the arrays is translated to an"

    "equivalence number"

    " based on

the result of <code>equals</code>.  The original Object arrays

are no longer needed for computing the differences.  They will

be needed again later to print the results of the comparison as

an edit script, if desired."

    |h data|

    h := Dictionary new:(gA size + gB size).

    data := Data new.

    data fileData.

    data 

        fileData:gA

        hashTable:h

        felDiff:self.

    self filevec at:1 put:data.

    data := Data new.

    data fileData.

    data 

        fileData:gB

        hashTable:h

        felDiff:self.

    self filevec at:2 put:data.

    "Modified: / 12-02-2010 / 14:22:56 / Jan Vrany <jan.vrany@fit.cvut.cz>"

!

diff

    ^self diff: false

    "Created: / 16-02-2010 / 22:50:26 / Jan Vrany <jan.vrany@fit.cvut.cz>"

!

diff:reverse 

    ^reverse 

        ifTrue:[self diffUsingScript: ReverseScript new]

        ifFalse:[self diffUsingScript: ForwardScript new]

    "Modified: / 16-02-2010 / 22:51:43 / Jan Vrany <jan.vrany@fit.cvut.cz>"

!

diffUsingScript:bld 

    "Get the results of comparison as an edit script.  The script

         is described by a list of changes.  The standard ScriptBuilder

         implementations provide for forward and reverse edit scripts.

         Alternate implementations could, for instance, list common elements

         instead of differences.

         @param bld an object to build the script from change flags

         @return the head of a list of changes

     Some lines are obviously insertions or deletions

           because they don't match anything.  Detect them now,

           and avoid even thinking about them in the main comparison algorithm."

    |diags first second ret|

    self discardConfusingLines.

     "Now do the main comparison algorithm, considering just the

     undiscarded lines."

    first := filevec at:1.

    second := filevec at:2.

    xvec := first undiscarded.

    yvec := second undiscarded.

    diags := (first nondiscardedLines) + (second nondiscardedLines) + 3.

    fdiag := Array new:diags withAll:0.

    fdiagoff := second nondiscardedLines + 1.

    bdiag := Array new:diags withAll:0.

    bdiagoff := second nondiscardedLines + 1.

    self 

        compareseq:0

        xlim:first nondiscardedLines

        yoff:0

        ylim:second nondiscardedLines.

    fdiag := nil.

    bdiag := nil.

    self shiftBoundaries.

    ret := bld 

                buildScript:first changedFlag

                length0:first bufferedLines

                changed1:second changedFlag

                length1:second bufferedLines.

    ^ ret.

    "Modified: / 12-02-2010 / 13:57:09 / Jan Vrany <jan.vrany@fit.cvut.cz>"

! !

!Diff methodsFor:'initialization'!

initialize

    "konstruktor"

    equivMax := 1.

    heuristic := false.

    nodiscards := false.

    xvec := Array new.

    yvec := Array new.

    fdiag := Array new.

    bdiag := Array new.

    filevec := Array new:2.

    snakeLimit := 20.

    inhibit := false.

    "Modified: / 16-02-2010 / 22:51:04 / Jan Vrany <jan.vrany@fit.cvut.cz>"

! !

!Diff methodsFor:'private'!

compareseq:gXoff xlim:gXlim yoff:gYoff ylim:gYlim

    "Compare in detail contiguous subsequences of the two files

     which are known, as a whole, to match each other.

     The results are recorded in the vectors filevec[N].changedflag, by

     storing a 1 in the element for each line that is an insertion or deletion.

     The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.

     Note that XLIM, YLIM are exclusive bounds.

     All line numbers are origin-0 and discarded lines are not counted."

    |xoff xlim yoff ylim c d f b|

    xoff := gXoff.

    xlim := gXlim.

    yoff := gYoff.

    ylim := gYlim.

    "Slide down the bottom initial diagonal."

    [(xoff < xlim) and: [(yoff < ylim) and: [(xvec at: xoff + 1) = (yvec at: yoff + 1)]]] whileTrue:

    [

        xoff := xoff + 1.

        yoff := yoff + 1.

    ].

    "Slide up the top initial diagonal."

    [(xlim > xoff) and: [(ylim > yoff) and: [(xvec at: xlim) = (yvec at: ylim)]]] whileTrue:

    [

        xlim := xlim - 1.

        ylim := ylim - 1.

    ].

    "Handle simple cases."

    (xoff = xlim) ifTrue:

    [

        [yoff < ylim] whileTrue:

        [

            ((filevec at: 2) changedFlag) at: (2 + ((filevec at: 2) realindexes at: yoff+1)) put: true.

            yoff := yoff + 1.

        ]

    ]

    ifFalse:

    [

        (yoff = ylim) ifTrue:

        [

            [xoff < xlim] whileTrue:

            [

                ((filevec at: 1) changedFlag) at: (2 + ((filevec at: 1) realindexes at: xoff+1)) put: true.

                xoff := xoff + 1.

            ]

        ]

        ifFalse:

        [

            "Find a point of correspondence in the middle of the files."

            d := self diag: xoff xlim: xlim yoff: yoff ylim: ylim.

            c := cost.

            f := fdiag at: (fdiagoff + d+1).

            b := bdiag at: (bdiagoff + d+1).

            (c = 1) ifTrue:

            [

                "This should be impossible, because it implies that

                 one of the two subsequences is empty,

                 and that case was handled above without calling `diag'.

                 Let's verify that this is true."

                d := Exception new.

                d signal.

            ]

            ifFalse:

            [

                 "Use that point to split this problem into two subproblems."

                 self compareseq: xoff xlim: b yoff: yoff ylim: (b - d).

                 "This used to use f instead of b,

                  but that is incorrect!!

                  It is not necessarily the case that diagonal d

                  has a snake from b to f."

                 self compareseq: b xlim: xlim yoff: (b - d) ylim: ylim.

            ]

        ]

    ]

!

diag: anXoff xlim: anXlim yoff: aYoff ylim: aYlim

    |fd bd xv yv dmin dmax fmid fmax bmid bmax fmin bmin odd c cont d bigsnake tlo thi x oldx y best bestpos dd v temp k cont2|

    fd := fdiag.    "Give the compiler a chance."

    bd := bdiag.    "Additional help for the compiler."

    xv := xvec.     "Still more help for the compiler."

    yv := yvec.     "And more and more . . ."

    dmin := anXoff-aYlim.   "Minimum valid diagonal."

    dmax := anXlim-aYoff.   "Maximum valid diagonal."

    fmid := anXoff-aYoff.   "Center diagonal of top-down search."

    bmid := anXlim-aYlim.   "Center diagonal of bottom-up search."

    fmin := fmid.   "Limits of top-down search."

    fmax := fmid.   " --||-- "

    bmin := bmid.   "Limits of bottom-up search."

    bmax := bmid.   " --||-- "

    odd := (fmid-bmid) odd. "True if southeast corner is on an odd diagonal with respect to the northwest."

    "Added + 1 to all arrays since StX uses index 1 as first"

    fd at:(fdiagoff+fmid + 1) put: anXoff.

    bd at:(bdiagoff+bmid + 1) put: anXlim.

    c := 1.

    cont := true.

    [cont = true] whileTrue:[

        d := nil.   "Active diagonal."

        bigsnake := false.

        "Extend the top-down search by an edit step in each diagonal."

        (fmin > dmin) ifTrue:[

            fmin := fmin-1.

            fd at:(fdiagoff + fmin - 1 + 1) put: -1.

        ]   ifFalse:[ fmin := fmin + 1. ].

        (fmax < dmax) ifTrue:[

            fmax := fmax+1.

            fd at:(fdiagoff + fmax + 1 + 1) put: -1.

        ]   ifFalse:[ fmax := fmax - 1. ].

        d := fmax.

        [(d >= fmin)] whileTrue:[

            tlo := fd at:(fdiagoff + d - 1 + 1).

            thi := fd at:(fdiagoff + d + 1 + 1).

            (tlo >= thi) ifTrue:[