unit uMyersDiff;
{$mode objfpc}{$H+}
interface
uses
Classes, SysUtils;
type
TStringArray = array of string;
TDiffOpKind = (dEqual, dAdd, dDelete);
PDiffOp = ^TDiffOp;
TDiffOp = record
Kind: TDiffOpKind;
OldIndex: Integer; // Index in the old (original) sequence
NewIndex: Integer; // Index in the new (modified) sequence
Length: Integer; // Number of items in this operation
end;
TDiffOps = array of TDiffOp;
function ComputeMyersDiff(const A, B: TStringArray): TDiffOps;
function FormatDiffOutput(const DiffOps: TDiffOps; const A, B: TStringArray): string;
implementation
function ComputeMyersDiff(const A, B: TStringArray): TDiffOps;
type
TVectorArray = array of Integer;
function Max(const a, b: Integer): Integer;
begin
if a > b then Result := a else Result := b;
end;
function ShortestEditScript(const A, B: TStringArray): TDiffOps;
var
N, M, MaxD, CurrentD, K, X, Y, PrevX, PrevY, PrevK: Integer;
V: array of Integer;
Trace: array of TVectorArray;
SnakeLength: Integer;
TempOp: TDiffOp;
i, j: Integer;
begin
N := Length(A);
M := Length(B);
MaxD := N + M;
SetLength(V, 2 * MaxD + 1);
SetLength(Trace, MaxD + 1);
CurrentD := 0;
while CurrentD <= MaxD do
begin
SetLength(Trace[CurrentD], 2 * MaxD + 1);
K := -CurrentD;
while K <= CurrentD do
begin
if (K = -CurrentD) or ((K <> CurrentD) and (V[K - 1 + MaxD] < V[K + 1 + MaxD])) then
begin
X := V[K + 1 + MaxD];
PrevK := K + 1;
end
else
begin
X := V[K - 1 + MaxD] + 1;
PrevK := K - 1;
end;
Y := X - K;
PrevX := V[PrevK + MaxD];
PrevY := PrevX - PrevK;
// Follow snake
while (X < N) and (Y < M) and (A[X] = B[Y]) do
begin
Inc(X);
Inc(Y);
end;
V[K + MaxD] := X;
Trace[CurrentD][K + MaxD] := PrevK + MaxD;
if (X >= N) and (Y >= M) then
begin
// Reconstruct the path
SetLength(Result, 0);
CurrentD := CurrentD;
while CurrentD >= 0 do
begin
PrevK := Trace[CurrentD][K + MaxD] - MaxD;
PrevX := V[PrevK + MaxD];
PrevY := PrevX - PrevK;
SnakeLength := V[K + MaxD] - Max(PrevX, PrevY);
if SnakeLength > 0 then
begin
SetLength(Result, Length(Result) + 1);
with Result[High(Result)] do
begin
Kind := dEqual;
OldIndex := PrevX;
NewIndex := PrevY;
Length := SnakeLength;
end;
end;
if CurrentD > 0 then
begin
SetLength(Result, Length(Result) + 1);
with Result[High(Result)] do
begin
if K > PrevK then
begin
Kind := dAdd;
OldIndex := PrevX;
NewIndex := PrevY;
Length := 1;
end
else
begin
Kind := dDelete;
OldIndex := PrevX;
NewIndex := PrevY;
Length := 1;
end;
end;
end;
K := PrevK;
Dec(CurrentD);
end;
// Reverse the result
for i := 0 to (Length(Result) div 2) - 1 do
begin
j := High(Result) - i;
TempOp := Result[i];
Result[i] := Result[j];
Result[j] := TempOp;
end;
Exit;
end;
Inc(K, 2);
end;
Inc(CurrentD);
end;
SetLength(Result, 0);
end;
begin
Result := ShortestEditScript(A, B);
end;
function FormatDiffOutput(const DiffOps: TDiffOps; const A, B: TStringArray): string;
var
I, J: Integer;
Op: TDiffOp;
begin
Result := '';
for I := 0 to High(DiffOps) do
begin
Op := DiffOps[I];
case Op.Kind of
dEqual:
for J := 0 to Op.Length - 1 do
Result := Result + Format(' %s' + LineEnding, [A[Op.OldIndex + J]]);
dAdd:
for J := 0 to Op.Length - 1 do
Result := Result + Format('+ %s' + LineEnding, [B[Op.NewIndex + J]]);
dDelete:
for J := 0 to Op.Length - 1 do
Result := Result + Format('- %s' + LineEnding, [A[Op.OldIndex + J]]);
end;
end;
end;
end.
Recent
