; --------------------------------------------------------------------------------------------
; Copyright (c) Fantaisie Software. All rights reserved.
; Dual licensed under the GPL and Fantaisie Software licenses.
; See LICENSE and LICENSE-FANTAISIE in the project root for license information.
; --------------------------------------------------------------------------------------------

; Implementation of the Myers Diff algorithm with the linear space refinement specified in
; "An O(ND) Difference Algorithm and Its Variations" -- Algorithmica 1, 2 (1986), 251-266.
; See here: http://www.xmailserver.org/diff2.pdf
;
; A useful tutorial with code examples:
; https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
; https://blog.jcoglan.com/2017/02/15/the-myers-diff-algorithm-part-2/
; https://blog.jcoglan.com/2017/02/17/the-myers-diff-algorithm-part-3/
; https://blog.jcoglan.com/2017/03/22/myers-diff-in-linear-space-theory/
; https://blog.jcoglan.com/2017/04/25/myers-diff-in-linear-space-implementation/
;
; A very useful tutorial and graphical tool to visualize the algorithm:
; http://simplygenius.net/Article/DiffTutorial1
; http://simplygenius.net/Article/DiffTutorial2
;


; Compute checksum of a line depending on the given Flags
;
Procedure Diff_ComputeChecksum(*Start, Length, Flags)

 If Length = 0
 ProcedureReturn 0
 
 ElseIf Flags = 0
 ProcedureReturn CRC32Fingerprint(*Start, Length)
 
 Else
 ; need to get a string to apply further options first
 ;
 Protected Line$ = PeekS(*Start, Length, #PB_Ascii) ; ok for ascii and utf8, as we just need a checksum and no content

 If Flags & #DIFF_IgnoreCase
 Line$ = LCase(Line$)
 EndIf
 
 If Flags & #DIFF_IgnoreSpaceAll
 Line$ = Trim(ReplaceString(Line,ドル Chr(9), " ")) ; convert tab, remove space on sides
 
 ; collapse any multiple space to single ones, so we have only significant spaces left
 While FindString(Line,ドル " ", 1)
 Line$ = ReplaceString(Line,ドル " ", " ")
 Wend
 
 Else
 If Flags & #DIFF_IgnoreSpaceLeft
 While Left(Line,ドル 1) = " " Or Left(Line,ドル 1) = Chr(9) ; simple trim is not enough here
 Line$ = Right(Line,ドル Len(Line$)-1)
 Wend
 EndIf
 
 If Flags & #DIFF_IgnoreSpaceRight
 While Right(Line,ドル 1) = " " Or Right(Line,ドル 1) = Chr(9)
 Line$ = Left(Line,ドル Len(Line$)-1)
 Wend
 EndIf
 EndIf
 
 If Len(Line$) = 0
 ProcedureReturn 0
 Else
 ; No need to convert back to Ascii. Just compute the hash of the unicode line
 ProcedureReturn CRC32Fingerprint(@Line,ドル StringByteLength(Line$))
 EndIf
 EndIf
 
EndProcedure

; Scan a file and fill the lines array
;
Procedure Diff_PreProcess(*Pointer.Byte, Size, Array Lines.DiffLine(1), Flags)
 Protected *BufferEnd = *Pointer + Size
 
 Protected Lines = 0
 Protected Space = ArraySize(Lines()) ; don't do +1 to have the extra space for the last line
 
 Protected *LineStart = *Pointer
 While *Pointer < *BufferEnd
 
 ; detect next newline
 If *Pointer\b = 13
 *Pointer + 1
 If *Pointer < *BufferEnd And *Pointer\b = 10
 *Pointer + 1
 EndIf
 ElseIf *Pointer\b = 10
 *Pointer + 1
 Else
 ; no newline
 *Pointer + 1
 Continue
 EndIf
 
 ; newline found
 If Space = 0
 ReDim Lines(Lines * 2)
 Space = Lines
 EndIf
 
 Lines(Lines)\Checksum = Diff_ComputeChecksum(*LineStart, *Pointer-*LineStart, Flags)
 Lines(Lines)\Start = *LineStart
 Lines(Lines)\Length = *Pointer - *LineStart
 Lines + 1
 Space - 1
 *LineStart = *Pointer
 Wend
 
 ; add the last line
 If *Pointer > *LineStart
 Lines(Lines)\Checksum = Diff_ComputeChecksum(*LineStart, *Pointer-*LineStart, Flags)
 Lines(Lines)\Start = *LineStart
 Lines(Lines)\Length = *Pointer - *LineStart
 Lines + 1
 EndIf
 
 ProcedureReturn Lines
EndProcedure

; Add a (possible empty) edit to the edit script
; Multiple edits with the same Op are combined into one
;
Procedure Diff_AddEdit(*Ctx.DiffContext, Op, Array Lines.DiffLine(1), StartLine, Lines)
 Protected Line

 If Lines > 0
 If LastElement(*Ctx\Edits()) = 0 Or *Ctx\Edits()\Op <> Op
 ; start a new edit
 AddElement(*Ctx\Edits())
 *Ctx\Edits()\Op = Op
 *Ctx\Edits()\StartLine = StartLine
 *Ctx\Edits()\Start = Lines(StartLine)\Start
 EndIf
 
 ; append lines to existing edit
 *Ctx\Edits()\Lines + Lines
 For Line = StartLine To StartLine + Lines - 1
 *Ctx\Edits()\Length + Lines(Line)\Length
 Next Line
 EndIf

EndProcedure

; Find middle snake
; Returns edit distance D
;
Procedure Diff_FindMiddleSnake(*Ctx.DiffContext, AOffset, N, BOffset, M, *x.Integer, *y.Integer, *u.Integer, *v.Integer)
 Protected DELTA = N - M
 Protected OFFSET = (N + M) * 2
 Protected odd, mid, D, k, c, x, y
 
 odd = Bool(DELTA % 2 <> 0)
 If odd
 mid = (N + M) / 2 + 1
 Else
 mid = (N + M) / 2
 EndIf
 
 *Ctx\FV(1+OFFSET) = 0
 *Ctx\RV(DELTA-1+OFFSET) = N
 
 For D = 0 To mid
 
 ; forward search
 For k = -D To D Step 2
 If k = -D Or (k <> D And *Ctx\FV(k-1+OFFSET) < *Ctx\FV(k+1+OFFSET))
 x = *Ctx\FV(k+1+OFFSET)
 Else
 x = *Ctx\FV(k-1+OFFSET) + 1
 EndIf
 y = x - k
 *x\i = x
 *y\i = y
 While x < N And y < M And *Ctx\A(AOffset + x)\Checksum = *Ctx\B(BOffset + y)\Checksum
 x + 1
 y + 1
 Wend
 *Ctx\FV(k+OFFSET) = x
 If odd And k >= (DELTA - (D - 1)) And k <= (DELTA + (D - 1))
 If x >= *Ctx\RV(k+OFFSET)
 *u\i = x
 *v\i = y
 ProcedureReturn 2 * D - 1
 EndIf
 EndIf
 Next k
 
 ; reverse search
 For k = -D To D Step 2
 c = k + DELTA
 If k = D Or (k <> -D And *Ctx\RV(c-1+OFFSET) < *Ctx\RV(c+1+OFFSET))
 x = *Ctx\RV(c-1+OFFSET)
 Else
 x = *Ctx\RV(c+1+OFFSET) - 1
 EndIf
 y = x - c
 *u\i = x
 *v\i = y
 While x > 0 And y > 0 And *Ctx\A(AOffset + x-1)\Checksum = *Ctx\B(BOffset + y-1)\Checksum
 x - 1
 y - 1
 Wend
 *Ctx\RV(c+OFFSET) = x
 If odd = 0 And c >= -D And c <= D
 If x <= *Ctx\FV(c+OFFSET)
 *x\i = x
 *y\i = y
 ProcedureReturn 2 * D
 EndIf
 EndIf
 Next k
 
 Next D
EndProcedure

; Recursively compute Diff
;
Procedure Diff_Recursive(*Ctx.DiffContext, AOffset, N, BOffset, M)
 Protected D, x, y, u, v

 If N > 0 And M = 0
 ; second sequence is empty: so only deletions
 Diff_AddEdit(*Ctx, #DIFF_DELETE, *Ctx\A(), AOffset, N)
 
 ElseIf N = 0 And M > 0
 ; first sequence is empty: so only additions
 Diff_AddEdit(*Ctx, #DIFF_INSERT, *Ctx\B(), BOffset, M)
 
 ElseIf N > 0 And M > 0
 D = Diff_FindMiddleSnake(*Ctx, AOffset, N, BOffset, M, @x, @y, @u, @v)
 ;Debug "D = " + D + " x=" + x + " y=" + y + " -> u=" + u + " v=" + v

 If D = 0
 ; both sequences are equal
 Diff_AddEdit(*Ctx, #DIFF_MATCH, *Ctx\A(), AOffset, N)
 
 ElseIf D = 1
 ; exactly one edit and 0 or more matches
 If M > N
 If x = u
 ; \
 ; \
 ; |
 Diff_AddEdit(*Ctx, #DIFF_MATCH, *Ctx\A(), AOffset, N)
 Diff_AddEdit(*Ctx, #DIFF_INSERT, *Ctx\B(), BOffset + M-1, 1)
 Else
 ; |
 ; \
 ; \
 Diff_AddEdit(*Ctx, #DIFF_INSERT, *Ctx\B(), BOffset, 1)
 Diff_AddEdit(*Ctx, #DIFF_MATCH, *Ctx\A(), AOffset, N)
 EndIf
 Else
 If x = u
 ; \
 ; \
 ; -
 Diff_AddEdit(*Ctx, #DIFF_MATCH, *Ctx\A(), AOffset, M)
 Diff_AddEdit(*Ctx, #DIFF_DELETE, *Ctx\A(), AOffset + N-1, 1)
 Else
 ; -
 ; \
 ; \
 Diff_AddEdit(*Ctx, #DIFF_DELETE, *Ctx\A(), AOffset, 1)
 Diff_AddEdit(*Ctx, #DIFF_MATCH, *Ctx\A(), AOffset + 1, M)
 EndIf
 EndIf
 
 Else
 ; general case: recurse around the middle snake
 Diff_Recursive(*Ctx, AOffset, x, BOffset, y)
 Diff_AddEdit(*Ctx, #DIFF_MATCH, *Ctx\A(), AOffset + x, u-x)
 Diff_Recursive(*Ctx, AOffset + u, N-u, BOffset + v, M-v)
 
 EndIf
 
 EndIf
EndProcedure

; Main Diff function
;
Procedure Diff(*Ctx.DiffContext, *BufferA, SizeA, *BufferB, SizeB, Flags = 0)
 Protected N, M, MAX, Offset
 
 N = Diff_PreProcess(*BufferA, SizeA, *Ctx\A(), Flags)
 M = Diff_PreProcess(*BufferB, SizeB, *Ctx\B(), Flags)

 *Ctx\LineCountA = N
 *Ctx\LineCountB = M

 Dim *Ctx\FV((N + M)*4+1)
 Dim *Ctx\RV((N + M)*4+1)
 
 ClearList(*Ctx\Edits())
 
 ; Note:
 ; The handling of the D=1 Case in FindMiddleSnake() assumes that we always start
 ; with an inset Or delete. So strip off common lines at the start to ensure this
 Offset = 0
 While Offset < N And Offset < M And *Ctx\A(Offset)\Checksum = *Ctx\B(Offset)\Checksum
 Offset + 1
 Wend
 
 Diff_AddEdit(*Ctx, #DIFF_Match, *Ctx\A(), 0, Offset)
 Diff_Recursive(*Ctx, Offset, N-Offset, Offset, M-Offset)
 
 FreeArray(*Ctx\FV())
 FreeArray(*Ctx\RV())
EndProcedure

; Some debugging utilities
;
CompilerIf #PB_Compiler_Debugger

 Procedure DebugEdit(Prefix,ドル List Edits.DiffEdit(), Array Lines.DiffLine(1))
 Protected Line, Length, Line$
 
 For Line = Edits()\StartLine To Edits()\StartLine + Edits()\Lines - 1
 Line$ = PeekS(Lines(Line)\Start, Lines(Line)\Length, #PB_Ascii)
 Line$ = RTrim(RTrim(Line,ドル Chr(10)), Chr(13)) ; trim newline
 Debug Prefix$ + " " + Line$
 Next Line
 EndProcedure

 Procedure DebugDiff(*Ctx.DiffContext)
 ForEach *Ctx\Edits()
 Select *Ctx\Edits()\Op
 Case #DIFF_Match
 DebugEdit(" ", *Ctx\Edits(), *Ctx\A())
 Case #DIFF_Delete
 DebugEdit("-", *Ctx\Edits(), *Ctx\A())
 Case #DIFF_Insert
 DebugEdit("+", *Ctx\Edits(), *Ctx\B())
 EndSelect
 Next *Ctx\Edits()
 EndProcedure
 
 Procedure DebugFile(FileA,ドル FileB$)
 Protected *BufferA, SizeA, *BufferB, SizeB, Context.DiffContext
 
 If ReadFile(0, FileA$)
 SizeA = Lof(0)
 *BufferA = AllocateMemory(SizeA)
 ReadData(0, *BufferA, SizeA)
 CloseFile(0)
 Else
 Debug "Cannot load: " + FileA$
 End
 EndIf
 
 If ReadFile(0, FileB$)
 SizeB = Lof(0)
 *BufferB = AllocateMemory(SizeB)
 ReadData(0, *BufferB, SizeB)
 CloseFile(0)
 Else
 Debug "Cannot load: " + FileB$
 End
 EndIf
 
 Diff(@Context, *BufferA, SizeA, *BufferB, SizeB)
 DebugDiff(@Context)

 FreeMemory(*BufferA)
 FreeMemory(*BufferB)
 EndProcedure
 
 ;DebugFile("C:\PureBasic\Test\diff\Preferences0081円.pb", "C:\PureBasic\Test\diff\Preferences0082円.pb")
 
CompilerEndIf