diffscript.vb

an lcs algorithm for finding common string

                ' -c(1) +d(1) will be translated to (replace) ~d(1)

                '' the LCS algorithm favours - modification over + modification
                '' so they (all of them) should come up first
                '' this might result in a difflist of -3c-2d+2C+2D
                '' which translates to ~3C ~2D
                '' note that this procedure could have been made simpler when
                '' after - operation + operations would have been favoured.
                '' this is now chosen as the solution
                'If mod1.Operation = Operation.Remove Then

                '    ' h represents the number (-1) of consecutive joined remove operations
                '    For h As Integer = 1 To mods.Count - i
                '        mod2 = mods(i + j)
                '        If mod2.Operation = Operation.Remove Then
                '            If mod2.Index = mod1.Index - j Then
                '                ' this is a consecutive joined remove operation, keep going
                '            Else
                '                ' the next remove operation is gapped
                '                ' (e.g. -4d-2d)
                '                ' this means that there's no replace as the next operation will not be
                '                ' +3
                '                Exit For
                '            End If
                '        ElseIf mod2.Operation = Operation.Add Then
                '            ' this is the first add operation detected, determine howmany we have at the
                '            ' location of last remove. this will represent the number of replacements
                '            ' note that it's possible to have -c3-2d+2c alone, which makes it
                '            ' undetermined whether the 1st or the second element has been replaced.
                '            ' (and also ofcourse -c3+2c+2d)
                '            ' this should be kept in mind when determining how to applying
                '            ' the modification to the destination
                '            ' g represents the number of related remove operations
                '            ' we're only interested in the first (h+1) items as they are the only ones
                '            ' that can represent replacements
                '            For g = 1 To (h + 1)
                '                mod2=mods(
                '            Next
                '        End If
                '    Next

                'End If

                If mod1.Operation = Operation.Remove Then
                    If i < mods.Count - 1 Then
                        mod2 = mods(i + 1)
                        If mod2.Operation = Operation.Add AndAlso mod1.Index = mod2.Index Then
                            ' -+ combination found for the same index,
                            ' replace it with Replace
                            ' note that -+-+ combinations come up only because of a modification in the 
                            ' LCS backtrack algorithm. originally, --++ combination would have been returned instead
                            ' it still favors - as the first modification in a list

                            ' replace+modify mod1 so that it will not be evaluated for move later
                            mod1.Operation = Operation.Replace
                            mod1.Item = mod2.Item
                            mods(i) = mod1
                            mods.RemoveAt(i + 1)
                        End If
                    End If
                End If
                'If mod1.Index = mod2.Index Then
                '    If mod1.Operation = Operation.Add AndAlso mod2.Operation = Operation.Remove Then
                '        mod1.Operation = Operation.Replace
                '        mods(i) = mod1
                '        mods.RemoveAt(j)
                '        j -= 1
                '    ElseIf mod1.Operation = Operation.Remove AndAlso mod2.Operation = Operation.Add Then
                '        mod2.Operation = Operation.Replace
                '        mods(j) = mod2
                '        mods.RemoveAt(i)
                '        i -= 1
                '    End If
                'End If

                If mod1.Operation = Operation.Add Or mod1.Operation = Operation.Remove Then

                    ' move
                    ' -c(1)  +c(3) changes to (move) >1,3
                    j = i + 1
                    While j < mods.Count

                        mod2 = mods(j)

                        ' move
                        ' -c(1)  +c(3) changes to (move) >1,3
                        If mod1.Item.Equals(mod2.Item) Then
                            If mod1.Operation = Operation.Add AndAlso mod2.Operation = Operation.Remove Then

                                ' moving an item from a lower index to a higher index
                                ' (removing at the lower index, adding at the higher index)

                                ' testscenario: 
                                ' abdef -> abefcd

                                'old: (it is decided to move move operations down the line, to the second modification
                                ' because of index sliding, this will only need the move modification index
                                ' to be changed (otherwise, all the operations in between would need to be modified)
                                'mod1.Operation = Operation.Move
                                'mod1.FromIndex = mod2.Index
                                'mods(i) = mod1
                                'mods.RemoveAt(j)
                                'j -= 1
                                mod2.Operation = Operation.Move
                                mod2.FromIndex = mod2.Index
                                mod2.Index = mod1.Index

                                Debug.Assert(mod2.FromIndex < mod2.Index, "the diff array should be build from high to low index")
                                ' now the remove operation has moved from an earlier exectution to a later execution
                                ' the indexes in the result array between the original add and remove
                                ' might move the original position of the remove operation.
                                ' we need to compensate:
                                For k = i + 1 To j - 1
                                    Select Case mods(k).Operation
                                        Case Operation.Add
                                            mod2.Index += 1
                                        Case Operation.Remove
                                            mod2.Index -= 1
                                        Case Operation.Move
                                            mod3 = mods(k)
                                            ' the other move operation was moved down to between here,
                                            ' this means that they are overlapping
                                            ' determine if the original at this lower location was the
                                            ' add or the remove
                                            If mod3.FromIndex > mod3.Index Then
                                                ' the add (move to lower position)
                                                ' see below for explanintion of mod3 modification
                                                ' mod2: move from 1 to 3 (-1,+3)
                                                ' mod3: move from 4 to 2 (-4,+2)
                                                ' mod3 expects the +3 to happen first
                                                Debug.Assert(mod3.FromIndex > mod2.Index)
                                                Debug.Assert(mod3.Index > mod2.FromIndex)
                                                mod2.Index += 1
                                                mod3.FromIndex -= 1
                                            Else
                                                ' the remove (move from lower position to later position)
                                                ' mod2: move from 1 to 3 (-1,+3)
                                                ' mod3: move from 2 to 4 (-2,+4)
                                                ' mod3 expects +3 to be performed befor
                                                Debug.Assert(mod3.FromIndex > mod2.FromIndex)
                                                Debug.Assert(mod3.Index > mod2.Index)
                                                mod2.Index -= 1
                                                mod3.Index -= 1
                                            End If
                                            mods(k) = mod3
                                        Case Operation.Replace
                                            ' ignore replace operations as they dont change the index
                                    End Select
                                Next

                                mods(j) = mod2
                                mods.RemoveAt(i)

                                j = mods.Count ' we've replaced mod1, move to the next mod1
                                i -= 1

                            ElseIf mod1.Operation = Operation.Remove AndAlso mod2.Operation = Operation.Add Then

                                ' moving an item from a higher index to a lower index
                                ' (removing at the higher index, adding at the lower index)

                                ' testscenario: 
                                ' abefcd -> abdef

                                mod2.Operation = Operation.Move
                                mod2.FromIndex = mod1.Index

                                Debug.Assert(mod2.FromIndex > mod2.Index, "the diff array should be build from high to low index")
                                ' now the remove operation has moved from an earlier exectution to a later execution
                                ' the indexes in the result array between the original add and remove
                                ' might move the original position of the remove operation.
                                ' we need to compensate:
                                For k = i + 1 To j - 1
                                    Select Case mods(k).Operation
                                        Case Operation.Add
                                            mod2.FromIndex += 1
                                        Case Operation.Remove
                                            mod2.FromIndex -= 1
                                        Case Operation.Move
                                            mod3 = mods(k)
                                            ' the other move operation was moved down to between here,
                                            ' this means that they are overlapping
                                            ' determine if the original at this lower location was the
                                            ' add or the remove
                                            If mod3.FromIndex > mod3.Index Then
                                                ' the add (move to lower position)
                                                ' now we have for example situation
                                                ' mod2: move from 3 to 1 (-3,+1)
                                                ' mod3: move from 4 to 2 (-4,+2)
                                                ' mod3 now expects the -3 to occur first
                                                ' but we're moving this operation to after it
                                                ' so effectively, the remove in the middle has not been performed
                                                ' the FromIndex on mod3 should thus be increased
                                                Debug.Assert(mod3.FromIndex >= mod2.FromIndex)
                                                Debug.Assert(mod3.Index >= mod2.Index)
                                                mod2.FromIndex += 1
                                                mod3.FromIndex += 1
                                            Else
                                                ' the remove (move from lower position to later position)
                                                Debug.Assert(mod3.Index >= mod2.FromIndex)
                                                Debug.Assert(mod3.FromIndex >= mod2.Index)
                                                ' mod2: move from 3 to 1 (-3,+1)
                                                ' mod3: move from 2 to 4 (-2,+4)
                                                mod2.FromIndex -= 1
                                                mod3.Index += 1
                                            End If
                                            mods(k) = mod3
                                        Case Operation.Replace
                                            ' ignore replace operations as they dont change the index
                                    End Select
                                Next
                                mods(j) = mod2
                                mods.RemoveAt(i)

                                j = mods.Count ' we've replaced mod1, move to the next mod1
                                i -= 1

                            End If
                        End If

                        j += 1
                    End While

                End If

                i += 1
            End While

            Me.Clear()
            Me.AddRange(mods)

        End Sub

#If DEBUG Then
        Public Sub ApplyTo(ByVal list As List(Of T))

            For Each modification As Modification In Me
                modification.ApplyTo(list)
            Next

        End Sub
#End If

#If DEBUG Then
        Public Function print() As String
            Dim sb As New System.Text.StringBuilder
            For Each modification As Modification In Me
                Select Case modification.Operation
                    Case Operation.Add
                        sb.AppendLine("Add " & modification.Item.ToString & " after " & modification.Index)
                    Case Operation.Remove
                        sb.AppendLine("Remove " & modification.Item.ToString & " from " & modification.Index)
                    Case Operation.Replace
                        sb.AppendLine("Replace " & "at " & modification.Index & " with " & modification.Item.ToString)
                    Case Operation.Move
                        sb.AppendLine("Move " & modification.Item.ToString & " from " & modification.FromIndex & " to " & modification.Index)
                End Select
            Next
            Return sb.ToString
        End Function

        Public Function print2() As String
            Dim sb As New System.Text.StringBuilder
            For Each modification As Modification In Me
                Select Case modification.Operation
                    Case Operation.Add
                        sb.Append("+" & modification.Item.ToString & "(" & modification.Index & ")")
                    Case Operation.Remove
                        sb.Append("-" & modification.Item.ToString & "(" & modification.Index & ")")
                    Case Operation.Replace
                        sb.Append("~" & modification.Item.ToString & "(" & modification.Index & ")")
                    Case Operation.Move
                        sb.Append(">" & modification.Item.ToString & "(" & modification.FromIndex & "," & modification.Index & ")")
                End Select
            Next
            Return sb.ToString
        End Function
#End If

    End Class

End Namespace