Text Diff

Public Class Diff
    Implements IEquatable(Of Diff)
    Private _Matches As New List(Of DiffMatch)
    Private _Differences As New List(Of DiffDifference)
    Private _ByteLength1 As Integer
    Private _ByteLength2 As Integer
 
    Public Sub New(ByVal ByteLength1 As Integer, ByVal ByteLength2 As Integer)
        _ByteLength1 = ByteLength1
        _ByteLength2 = ByteLength2
    End Sub
 
    Public ReadOnly Property Matches() As List(Of DiffMatch)
        Get
            Return _Matches
        End Get
    End Property
 
    Public ReadOnly Property Differences() As List(Of DiffDifference)
        Get
            Return _Differences
        End Get
    End Property
 
    Private Function IsPartOf(ByVal Index1 As Integer, ByVal Index2 As Integer) As Boolean
        For Each tMatch As DiffMatch In _Matches
            If tMatch.IsPartOf(Index1, Index2) Then
                Return True
            End If
        Next
    End Function
 
    Private Function GetIntersectIndex(ByVal Match As DiffMatch) As Integer
        For aPos As Integer = 0 To _Matches.Count - 1
            If _Matches(aPos).IntersectsWith(Match) Then
                Return aPos
            End If
        Next
        Return -1
    End Function
 
    Private Function GetFitIndex(ByVal Match As DiffMatch) As Integer
        For aPos As Integer = 0 To _Matches.Count - 1
            With _Matches(aPos)
                If .Index1 + .Length >= Match.Index1 Or .Index2 + .Length >= Match.Index2 Then
                    Return aPos
                End If
            End With
        Next
        With _Matches(_Matches.Count - 1)
            If .Index1 + .Length < Match.Index1 And .Index2 + .Length < Match.Index2 Then
                Return _Matches.Count
            End If
        End With
        Return -1
    End Function
 
    Public Function GetMatchLength() As Integer
        Return Aggregate tMatch In _Matches Into Sum(tMatch.Length)
    End Function
 
    Private Shadows Function Equals(ByVal other As Diff) As Boolean Implements System.IEquatable(Of Diff).Equals
        If _Matches.Count <> other.Matches.Count Then
            Return False
        End If
        For aPos As Integer = 0 To _Matches.Count - 1
            If Not _Matches(aPos).Equals(other.Matches(aPos)) Then
                Return False
            End If
        Next
        Return True
    End Function
 
    Private Sub LoadDifferences()
        Dim tIndex1 As Integer
        Dim tIndex2 As Integer
        Dim tLen1 As Integer
        Dim tLen2 As Integer
        For aPos As Integer = 0 To _Matches.Count - 1
            With _Matches(aPos)
                tLen1 = .Index1 - tIndex1
                tLen2 = .Index2 - tIndex2
                If tLen1 > 0 Or tLen2 > 0 Then
                    _Differences.Add(New DiffDifference(tIndex1, tIndex2, tLen1, tLen2))
                End If
                tIndex1 = .Index1 + .Length
                tIndex2 = .Index2 + .Length
            End With
        Next
        tLen1 = _ByteLength1 - tIndex1
        tLen2 = _ByteLength2 - tIndex2
        If tLen1 > 0 Or tLen2 > 0 Then
            _Differences.Add(New DiffDifference(tIndex1, tIndex2, _ByteLength1 - tIndex1, _ByteLength2 - tIndex2))
        End If
    End Sub
 
    Public Shared Function GetDiff(ByVal Bytes1() As Byte, ByVal Bytes2() As Byte, Optional ByVal MatchTolerance As Integer = 3) As Diff
        Dim tRet As Diff = GetDiffMatches(Bytes1, Bytes2, MatchTolerance)(0)
        tRet.LoadDifferences()
        Return tRet
    End Function
 
    Public Shared Function GetDiffs(ByVal Bytes1() As Byte, ByVal Bytes2() As Byte, Optional ByVal MatchTolerance As Integer = 3) As Diff()
        Dim tRet() As Diff = GetDiffMatches(Bytes1, Bytes2, MatchTolerance)
        For Each tDiff As Diff In tRet
            tDiff.LoadDifferences()
        Next
        Return tRet
    End Function
 
    Public Shared Function GetDiff(ByVal String1 As String, ByVal String2 As String, Optional ByVal MatchTolerance As Integer = 3) As Diff
        Dim tRet As Diff = GetDiffMatches(System.Text.ASCIIEncoding.ASCII.GetBytes(String1), System.Text.ASCIIEncoding.ASCII.GetBytes(String2), MatchTolerance)(0)
        tRet.LoadDifferences()
        Return tRet
    End Function
 
    Public Shared Function GetDiffs(ByVal String1 As String, ByVal String2 As String, Optional ByVal MatchTolerance As Integer = 3) As Diff()
        Dim tRet() As Diff = GetDiffMatches(System.Text.ASCIIEncoding.ASCII.GetBytes(String1), System.Text.ASCIIEncoding.ASCII.GetBytes(String2), MatchTolerance)
        For Each tDiff As Diff In tRet
            tDiff.LoadDifferences()
        Next
        Return tRet
    End Function
 
    Private Shared Function GetDiffMatches(ByVal Bytes1() As Byte, ByVal Bytes2() As Byte, Optional ByVal MatchTolerance As Integer = 3) As Diff()
        Dim tMatchSets As New List(Of Diff)
        For tIndex1 As Integer = 0 To Bytes1.Length - 1
            For tIndex2 As Integer = 0 To Bytes2.Length - 1
                If Bytes1(tIndex1) = Bytes2(tIndex2) Then
                    If Not IsPartOf(tMatchSets, tIndex1, tIndex2) Then
                        Dim tMatchLength As Integer = 0
                        Do While tMatchLength + tIndex1 < Bytes1.Length And tMatchLength + tIndex2 < Bytes2.Length
                            If Bytes1(tMatchLength + tIndex1) <> Bytes2(tMatchLength + tIndex2) Then
                                Exit Do
                            End If
                            tMatchLength += 1
                        Loop
                        If tMatchLength >= MatchTolerance Then
                            Dim tMatch As New DiffMatch(tIndex1, tIndex2, tMatchLength)
                            Dim tMatchSetCount As Integer = 0
                            For aPos As Integer = 0 To tMatchSets.Count - 1
                                With tMatchSets(aPos)
                                    Dim tFitIndex As Integer = .GetFitIndex(tMatch)
                                    Dim tIntersectIndex As Integer = .GetIntersectIndex(tMatch)
                                    If tFitIndex >= 0 Then
                                        tMatchSetCount += 1
                                        If tIntersectIndex < 0 Then
                                            .Matches.Insert(tFitIndex, tMatch)
                                        Else
                                            Dim tNewMatchSet As New Diff(Bytes1.Length, Bytes2.Length)
                                            Dim tExistingIndex As Integer = 0
                                            Dim tNewIndex As Integer = 0
                                            Do While tExistingIndex < .Matches.Count
                                                If Not .Matches(tExistingIndex).IntersectsWith(tMatch) Then
                                                    tNewMatchSet.Matches.Add(.Matches(tExistingIndex))
                                                End If
                                                If tNewIndex <> tFitIndex Then
                                                    tExistingIndex += 1
                                                End If
                                                tNewIndex += 1
                                            Loop
                                            If tNewMatchSet.Matches.Count <= 0 Then
                                                tNewMatchSet.Matches.Add(tMatch)
                                            End If
                                            If Not tMatchSets.Contains(tNewMatchSet) Then
                                                tMatchSets.Add(tNewMatchSet)
                                            End If
                                        End If
                                    End If
                                End With
                            Next
                            If tMatchSetCount <= 0 Then
                                Dim tNewMatchSet As New Diff(Bytes1.Length, Bytes2.Length)
                                tNewMatchSet.Matches.Add(tMatch)
                                tMatchSets.Add(tNewMatchSet)
                            End If
                        End If
                    End If
                End If
            Next
        Next
        Return (From tMatchSet In tMatchSets Order By tMatchSet.GetMatchLength Descending, tMatchSet.Matches.Count Ascending).ToArray
    End Function
 
    Private Shared Function IsPartOf(ByVal MatchSets As List(Of Diff), ByVal Index1 As Integer, ByVal Index2 As Integer) As Boolean
        For Each tMatchSet As Diff In MatchSets
            If tMatchSet.IsPartOf(Index1, Index2) Then
                Return True
            End If
        Next
    End Function
 
End Class
 
Public Class DiffMatch
    Implements IEquatable(Of DiffMatch)
    Private _Index1 As Integer
    Private _Index2 As Integer
    Private _Length As Integer
 
    Public Sub New(ByVal Index1 As Integer, ByVal Index2 As Integer, ByVal Length As Integer)
        _Index1 = Index1
        _Index2 = Index2
        _Length = Length
    End Sub
 
    Public ReadOnly Property Index1() As Integer
        Get
            Return _Index1
        End Get
    End Property
 
    Public ReadOnly Property Index2() As Integer
        Get
            Return _Index2
        End Get
    End Property
 
    Public ReadOnly Property Length() As Integer
        Get
            Return _Length
        End Get
    End Property
 
    Friend Function IntersectsWith(ByVal Match As DiffMatch) As Boolean
        With Match
            Return (_Index1 >= ._Index1 And _Index1 < ._Index1 + ._Length) OrElse (._Index1 >= _Index1 And ._Index1 < _Index1 + _Length) OrElse (_Index2 >= ._Index2 And _Index2 < ._Index2 + ._Length) OrElse (._Index2 >= _Index2 And ._Index2 < _Index2 + _Length)
        End With
    End Function
 
    Friend Function IsPartOf(ByVal Index1 As Integer, ByVal Index2 As Integer) As Boolean
        Return Index1 - _Index1 = Index2 - _Index2
    End Function
 
    Friend Shadows Function Equals(ByVal other As DiffMatch) As Boolean Implements System.IEquatable(Of DiffMatch).Equals
        Return _Index1 = other._Index1 And _Index2 = other._Index2 And _Length = other._Length
    End Function
 
End Class
 
Public Class DiffDifference
    Private _Index1 As Integer
    Private _Index2 As Integer
    Private _Length1 As Integer
    Private _Length2 As Integer
 
    Public Sub New(ByVal Index1 As Integer, ByVal Index2 As Integer, ByVal Length1 As Integer, ByVal Length2 As Integer)
        _Index1 = Index1
        _Index2 = Index2
        _Length1 = Length1
        _Length2 = Length2
    End Sub
 
    Public ReadOnly Property Index1() As Integer
        Get
            Return _Index1
        End Get
    End Property
 
    Public ReadOnly Property Index2() As Integer
        Get
            Return _Index2
        End Get
    End Property
 
    Public ReadOnly Property Length1() As Integer
        Get
            Return _Length1
        End Get
    End Property
 
    Public ReadOnly Property Length2() As Integer
        Get
            Return _Length2
        End Get
    End Property
 
End Class
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279: