/// unit pocitajuci vzdialenost medzi retazcami (a najdlhsiu spolocnu podpostupnost - LCS)
{$I main.inc}
unit LCS;

interface

uses structures,constants,hashmap,forms;

type
     /// typ pole integerov
     intarray = array of Integer;

     PSnake = ^TSnake;
     /// record obsahujuci dve suradnice (x,y) a (u,v) pre konce daneho snake-u
     TSnake = record
       x,y,u,v: Integer;
     end;

     /// trieda implementujuca edit script a operacie s nim
     TEditScript = class
       Q: TQueueStack;  //(op,index,count),(..,..,..),...
       lastop: Integer;
       FSES: Integer;
       FLCS: Integer;
     public
       procedure getNextReset;
       function getNext(var op, index, count: Integer): Boolean;
       function getSESLength: Integer;
       function getLCSLength: Integer;
       constructor create;
       procedure add(op: Integer; index,count: Integer);
       function toString: xString;
       destructor Destroy; override;
     end;

function calcDist_old(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer): Integer;
function calcDist(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer): Integer;
function calcDist_fast(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer): Integer;
function calcDiff(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer; var es_out: TEditScript): Integer;
function calcStringDist(const S1: xString; const S2: xString): Integer;
function calcStringDiff(const S1: xString; const S2: xString; var es_out: TEditScript): Integer;
//procedure testDiff;
function calcDiff_comp_func(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer; var es_out: TEditScript; comp: TCompareFunc): Integer;
function getLCS(Q1,Q2: TQueueStack;var Q1_out_unmatched,Q2_out_unmatched: TQueueStack;comp: TCompareFunc): TQueueStack;
//function getLCS(Q1,Q2: TQueueStack): TQueueStack;

implementation

uses crc32, simple,SysUtils;

var forwArray: array of Integer;
    revArray: array of Integer;
    halfofarray: Integer;
    DistforwArray: array of Integer;
    Disthalfofarray: Integer;
//    a1,a2: intarray;

{ TEditScript }

/// konstruktor vytvarajuci EditScript objekt
constructor TEditScript.create;
begin
  inherited;
  Q := TQueueStack.create;
  lastop := -1;
end;

/// procedura pridavajuca operaciu op, od pozicie index s mnozstvom count do zoznamu operacii v editscripte
procedure TEditScript.add(op: Integer; index, count: Integer);
var i: Integer;
begin
  if count = 0 then begin
//    Exit;
  end
  else if lastop = op then begin
    i := Q.pop;
    i := i + count;
    Q.push(i);
  end
  else begin
    if op <> ES_MATCH then begin
      FSES := FSES + count;
    end
    else begin
      FLCS := FLCS + count;
    end;
    Q.push(op);
    Q.push(index);
    Q.push(count);
    lastop := op;
  end;
end;

/// funkcia vypisujuca editscript do stringu
function TEditScript.toString: xString;
var op,index,count: Integer;
    S: xString;
begin
  result := '';

  Q.peekNextReset;
  while Q.peekNext(op) do begin
    Q.peekNext(index);
    Q.peekNext(count);
    case op of
      ES_INSERT: S := 'INSERT (from index2 in the other sequence - numof): ';
      ES_DELETE: S := 'DELETE (from index - numof): ';
      ES_CHANGE: S := 'CHANGE (hmm): ';
      ES_MATCH: S := 'MATCH (from index - numof): ';
    else
      S := '???: ';
    end;
    result := result + S + IntToStr(index) + ' - ' + IntToStr(count) + EOL;
  end;
end;

/// procedura restartujuca iterovanie cez prvky editscriptu
procedure TEditScript.getNextReset;
begin
  Q.peekNextReset;
end;

/// funkcia vracajuca nasledujuci prvok editscriptu
function TEditScript.getNext(var op,index,count: Integer): Boolean;
begin
  result := false;

  if Q.peekNext(op) then
    if Q.peekNext(index) then
      if Q.peekNext(count) then
        result := true;
end;

/// funkcia vracajuca dlzku najkratsej editovacej postupnosti vo vstupoch z ktorych bol vytvoreny tento editscript
function TEditScript.getSESLength: Integer;
begin
  result := FSES;
end;

/// funkcia vracajuca dlzku LCS vo vstupoch z ktorych bol vytvoreny tento editscript
function TEditScript.getLCSLength: Integer;
begin
  result := FLCS;
end;

/// destructor uvolnujuci tento objekt z pamate
destructor TEditScript.Destroy;
begin
  Q.Free;
  inherited;
end;

/// funkcia (inline) vracajuca index v poli doprednych a reverznych diagonal (0..n) z povodneho (-n/2,n/2)
function changeindex(i: Integer): Integer; inline;
begin
  result := i + halfofarray;
(*  if (result >= Length(forwArray)) or (result < 0) then begin
    writeln('warning!!! ',i,' - ',result);
  end;*)
end;

/// funkcia (inline) vracajuca index v poli vzdialenosti (0..n) z povodneho (-n/2,n/2) pre di
function Distchangeindex(i: Integer): Integer; inline;
begin
  result := i + Disthalfofarray;
end;

/// procedura uvolnujuca polia diagonal z pamate
procedure freeDiff;
begin
//  if forwArray <> nil then
    forwArray := nil;
//  if revArray <> nil then
    revArray := nil;
end;

/// procedura uvolnujuca pole vzdialenosti z pamate
procedure DistfreeDiff;
begin
    DistforwArray := nil;
end;


/// funkcia pocita vzdialenosti pomocou Myersovho O(ND) algoritmu
/// medzi retazcami vo vstupnych poliach a1 a a2 o dlzke size1 a size2
/// starsia verzia s horsim ohranicenim pocitanych diagonal (deprecated)
function calcDist_old(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer): Integer;
var D: Integer;
    k: Integer;
    _MAX: Integer;
    x,y: Integer;
begin
  result := -1;

  if size1 = 0 then begin
    result := size2;
    DistfreeDiff;
    Exit;
  end
  else if size2 = 0 then begin
    result := size1;
    DistfreeDiff;
    Exit;
  end;

  _MAX := size1 + size2;

  SetLength(DistforwArray,min(max(size1,size2),MAX_D_PATH) shl 2 + 1);
//  SetLength(DistrevArray,min(max(size1,size2),MAX_D_PATH) shl 2 + 1);
  Disthalfofarray := (Length(DistforwArray) shr 1);

  DistforwArray[Distchangeindex(1)] := 0;
  for D := 0 to _MAX do begin
    k := -D;
    repeat
      if (k = -D) or ((k <> D) and (DistforwArray[Distchangeindex(k-1)] < DistforwArray[Distchangeindex(k+1)])) then
        x := DistforwArray[Distchangeindex(k+1)]
      else
        x := DistforwArray[Distchangeindex(k-1)] + 1;
      y := x - k;

      while (x < size1) and (y < size2) and (a1[x] = a2[y]) do begin
        x := x + 1;
        y := y + 1;
      end;

      DistforwArray[Distchangeindex(k)] := x;
{$IFDEF DEBUG2}
      writeln(D,' : ',k,'(',Distchangeindex(k),')',' -> ', x, ' , ', y);
{$ENDIF}

      if (x >= size1) and (y >= size2) then begin
        result := D;
        DistfreeDiff;
        Exit;
      end;

      Inc(k,2);
    until k > +D;

  end;
  DistfreeDiff;
end;

/// funkcia pocita vzdialenosti pomocou Myersovho O(ND) algoritmu
/// medzi retazcami vo vstupnych poliach a1 a a2 o dlzke size1 a size2
function calcDist(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer): Integer;
var D: Integer;
    k: Integer;
    _MAX: Integer;
    x,y: Integer;
    len: Integer;
    count: Integer;
begin
  result := -1;

  if size1 = 0 then begin
    result := size2;
    DistfreeDiff;
    Exit;
  end
  else if size2 = 0 then begin
    result := size1;
    DistfreeDiff;
    Exit;
  end;

  _MAX := size1 + size2;
{$IFDEF DEBUG4}
   writeln('SIZES: ',size1,',',size2,' (',_MAX,')');
{$ENDIF}

  SetLength(DistforwArray,min(size1 + size2,MAX_D_PATH) shl 1 + 1);
//  SetLength(DistrevArray,min(size1 + size2,MAX_D_PATH) shl 1 + 1);
  if Length(DistforwArray) > (MAX_D_PATH shl 1) then
    Disthalfofarray := MAX_D_PATH
  else
    Disthalfofarray := Length(DistforwArray) shr 1;
  len := Length(DistforwArray);

  count := 0;
  DistforwArray[Distchangeindex(1)] := 0;
  for D := 0 to _MAX do begin
    if FGlobalHalt then
      break;
    k := -D;
    repeat
      if (count and CYCLE_THRESHOLD = 0) then begin
        Application.ProcessMessages;
      end;
      if FGlobalHalt then
        break;
      count := count + 1;

      if (len <= MAX_D_PATH shl 1) or ((k > -halfofarray) and (k < MAX_D_PATH - halfofarray)) then begin
        if (k = -D) or ((k <> D) and (DistforwArray[Distchangeindex(k-1)] < DistforwArray[Distchangeindex(k+1)])) then
          x := DistforwArray[Distchangeindex(k+1)]
        else
          x := DistforwArray[Distchangeindex(k-1)] + 1;
        y := x - k;

        while (x < size1) and (y < size2) and (a1[x] = a2[y]) do begin
          x := x + 1;
          y := y + 1;
        end;

        DistforwArray[Distchangeindex(k)] := x;
{$IFDEF DEBUG2}
        writeln(D,' : ',k,'(',Distchangeindex(k),')',' -> ', x, ' , ', y);
{$ENDIF}

        if (x >= size1) and (y >= size2) then begin
          result := D;
          DistfreeDiff;
          Exit;
        end;
      end
      else begin
        result := MAX_D_PATH;
        DistfreeDiff;
        Exit;
      end;
      Inc(k,2);
    until k > +D;
  end;
  DistfreeDiff;
end;

/// funkcia pocita vzdialenosti pomocou O(NP) algoritmu
/// medzi retazcami vo vstupnych poliach a1 a a2 o dlzke size1 a size2
function calcDist_fast(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer): Integer;
var delta: Integer;
    k: Integer;
    _MAX: Integer;
    x,y: Integer;
    len: Integer;
    i,p: Integer;
    count: Integer;
    array1,array2: intarray;

  function snake(k, y: Integer): Integer;
  begin
    x := y - k;
    while (x < size1) and (y < size2) and (array1[x] = array2[y]) do begin
      x := x + 1; y := y + 1;
    end;
    snake := y;
  end;

begin
  result := -1;

  if size1 = 0 then begin
    result := size2;
    DistfreeDiff;
    Exit;
  end
  else if size2 = 0 then begin
    result := size1;
    DistfreeDiff;
    Exit;
  end;

  if size1 > size2 then begin
    array1 := a2;
    array2 := a1;
    len := size1;
    size1 := size2;
    size2 := len;
  end
  else begin
    array1 := a1;
    array2 := a2;
  end;

  SetLength(DistforwArray,min(size1 + size2 + 2,MAX_D_PATH) + 1);
(*  if Length(DistforwArray) > (MAX_D_PATH) then
    Disthalfofarray := MAX_D_PATH
  else*)
  len := Length(DistforwArray);
  if len = MAX_D_PATH + 1 then
    Disthalfofarray := Pred(len) shr 1
  else
    Disthalfofarray := size1 + 1;

//  DistforwArray[Distchangeindex(1)] := 0;


  for i := -(size1+1) to (size2+1) do begin
    if (Distchangeindex(i) >= 0) and (Distchangeindex(i) < len) then
      DistforwArray[Distchangeindex(i)] := -1;
  end;
  delta := size2 - size1;
  count := 0;
  p := -1;
  repeat
    p := p + 1;

    result := delta + 2*p;
    if result >= MAX_D_PATH then
      break;

    for k := -p to delta-1 do begin
      DistforwArray[Distchangeindex(k)] := snake(k,max(DistforwArray[Distchangeindex(k-1)] + 1,DistforwArray[Distchangeindex(k+1)]));
      Inc(count);
      if count and CYCLE_THRESHOLD = 0 then begin
        Application.ProcessMessages;
        if FGlobalHalt then begin
          DistfreeDiff;
          Exit;
        end;
      end;
    end;
    for k := delta + p downto delta + 1 do begin
      DistforwArray[Distchangeindex(k)] := snake(k,max(DistforwArray[Distchangeindex(k-1)] + 1,DistforwArray[Distchangeindex(k+1)]));
      Inc(count);
      if count and CYCLE_THRESHOLD = 0 then begin
        Application.ProcessMessages;
        if FGlobalHalt then begin
          DistfreeDiff;
          Exit;
        end;
      end;
    end;
    DistforwArray[Distchangeindex(delta)] := snake(delta,max(DistforwArray[Distchangeindex(delta-1)] + 1,DistforwArray[Distchangeindex(delta+1)]));
  until DistforwArray[Distchangeindex(delta)] = size2;

  DistfreeDiff;
end;

(*
function calcLCS_changed(const a1: chararray; size1: Integer; const a2: chararray; size2: Integer): Integer;
var D: Integer;
    k: Integer;
    MAX: Integer;
    x,y: Integer;
begin
  MAX := size1 + size2;
  forwArray[changeindex(1)] := 0;
  for D := 0 to MAX do begin
    k := -D;
    repeat
      if (k-1 >= -size2) and (k+1 <= size1) then begin
        if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
          x := forwArray[changeindex(k+1)]
        else
          x := forwArray[changeindex(k-1)] + 1;
        y := x - k;

        while (x < size1) and (y < size2) and (a1[x] = a2[y]) do begin
          x := x + 1;
          y := y + 1;
        end;

        forwArray[changeindex(k)] := x;

        writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

        if (x >= size1) and (y >= size2) then begin
          result := D;
          Exit;
        end;
      end;
      Inc(k,2);
    until k > +D;

  end;
end;
*)
(*
function calcforw(var x,y: Integer): Integer;
var D: Integer;
    k: Integer;
    MAX: Integer;
begin
//  MAX := (size1 + size2 + (size1 + size2) and 1) shr 1;  // |'' (size1 + size2) / 2 ''|
  MAX := size1 + size2;
  forwArray[changeindex(1)] := 0;
  for D := 0 to MAX do begin
    k := -D;
    repeat
      if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
        x := forwArray[changeindex(k+1)]
      else
        x := forwArray[changeindex(k-1)] + 1;
      y := x - k;

      while (x < size1) and (y < size2) and (a1[x] = a2[y]) do begin
        x := x + 1;
        y := y + 1;
      end;

      forwArray[changeindex(k)] := x;

      writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

      if (x >= size1) and (y >= size2) then begin
        result := D;
        Exit;
      end;

      Inc(k,2);
    until k > +D;

  end;
end;

function calcrev(var x,y: Integer): Integer;
var D: Integer;
    k: Integer;
    MAX: Integer;
    delta: Integer;
begin
  delta := size1 - size2;
//  MAX := (size1 + size2 + (size1 + size2) and 1) shr 1;  // |'' (size1 + size2) / 2 ''|
  MAX := size1 + size2;
  revArray[changeindex(delta + 1)] := size1;
  for D := 0 to MAX do begin
    k := -D + delta;
    repeat
      if (k = -D + delta) or ((k <> D + delta) and (revArray[changeindex(k+1)] < revArray[changeindex(k-1)])) then
        x := revArray[changeindex(k+1)] - 1
      else
        x := revArray[changeindex(k-1)];
      y := x - k;

      while (x >= 0) and (y >= 0) and (a1[x] = a2[y]) do begin
        x := x - 1;
        y := y - 1;
      end;

      revArray[changeindex(k)] := x;

      writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

      if (x < 0) and (y < 0) then begin
        result := D;
        Exit;
      end;

      Inc(k,2);
    until k > +D;

  end;
end;

function calcforwFRFDPath(D:Integer; var x,y: Integer): Integer;
var k: Integer;
    MAX: Integer;
begin
    k := -D;
    repeat
      if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
        x := forwArray[changeindex(k+1)]
      else
        x := forwArray[changeindex(k-1)] + 1;
      y := x - k;

      while (x < size1) and (y < size2) and (a1[x] = a2[y]) do begin
        x := x + 1;
        y := y + 1;
      end;

      forwArray[changeindex(k)] := x;

      writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

      if (x >= size1) and (y >= size2) then begin
        result := D;
        Exit;
      end;

      Inc(k,2);
    until k > +D;
end;

function calcrevFRFDPath(D: Integer; var x,y: Integer): Integer;
var k: Integer;
    MAX: Integer;
    delta: Integer;
begin
  delta := size1 - size2;
    k := -D + delta;
    repeat
      if (k = -D + delta) or ((k <> D + delta) and (revArray[changeindex(k+1)] < revArray[changeindex(k-1)])) then
        x := revArray[changeindex(k+1)] - 1
      else
        x := revArray[changeindex(k-1)];
      y := x - k;

      while (x >= 0) and (y >= 0) and (a1[x] = a2[y]) do begin
        x := x - 1;
        y := y - 1;
      end;

      revArray[changeindex(k)] := x;

      writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

      if (x < 0) and (y < 0) then begin
        result := D;
        Exit;
      end;

      Inc(k,2);
    until k > +D;
end;

function calcforwPath(D,k:Integer; off1,off2: Integer; var x,y: Integer): Integer;
begin
  result := -1;
  if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
    x := forwArray[changeindex(k+1)]
  else
    x := forwArray[changeindex(k-1)] + 1;
  y := x - k;

  while (x < size1) and (y < size2) and (a1[x + off1] = a2[y + off2]) do begin
    x := x + 1;
    y := y + 1;
  end;

  forwArray[changeindex(k)] := x;

  writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

  if (x >= size1) and (y >= size2) then begin
    result := D;
    Exit;
  end;
end;

function calcrevPath(D,k: Integer; off1,off2: Integer; var x,y: Integer): Integer;
var delta: Integer;
begin
  delta := size1 - size2;
  result := -1;
  if (k = -D + delta) or ((k <> D + delta) and (revArray[changeindex(k+1)] < revArray[changeindex(k-1)])) then
    x := revArray[changeindex(k+1)] - 1
  else
    x := revArray[changeindex(k-1)];
  y := x - k;

  while (x >= 0) and (y >= 0) and (a1[x + off1] = a2[y + off2]) do begin
    x := x - 1;
    y := y - 1;
  end;

  revArray[changeindex(k)] := x;

  writeln(D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);

  if (x < 0) and (y < 0) then begin
    result := D;
    Exit;
  end;
end;
*)

(*
function findMiddleSnake(const a1: intarray; const a2: intarray; off1,n,off2,m: Integer; snake: PSnake): Integer;
var delta: Integer;
    D: Integer;
    k,kdelta: Integer;
    MAX: Integer;
    len: Integer;
    x,y,u,v: Integer;
    i1,i2: Integer;
begin
//  MAX := (size1 + size2 + (size1 + size2) and 1) shr 1;  // |'' (size1 + size2) / 2 ''|
//  delta := size1 - size2;
//  MAX := (x1 - x0 + y1 - y0 + (x1 - x0 + y1 - y0) and 1) shr 1;
//  delta := (x1 - x0) - (y1 - y0);

//  i1 := h1 - l1;
//  i2 := h2 - l2;
//  MAX := (i1 + i2 + (i1 + i2) and 1) shr 1;
//  delta := i1 - i2;


  MAX := (n + m + ((n + m) and 1)) shr 1;
  delta := n - m;


//  x := 0;
//  y := 0;
//  u := size1;
//  v := size2;
//  len := -1;

  forwArray[changeindex(1)] := 0;
  revArray[changeindex(delta-1)] := n;

  for D := 0 to MAX do begin
    k := -D;
    repeat

//      if (k >= -m) and (k <= n) then begin
//      calcforwPath(D,k,off1,off2,x,y);
        if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
          x := forwArray[changeindex(k+1)]
        else
          x := forwArray[changeindex(k-1)] + 1;
        y := x - k;

        snake.x := x;
        snake.y := y;

        while (x < n) and (y < m) and (a1[x + off1] = a2[y + off2]) do begin
          x := x + 1;
          y := y + 1;
        end;

        forwArray[changeindex(k)] := x;
{$IFDEF DEBUG2}
        writeln('F',D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);
{$ENDIF}

        if ((delta and 1) = 1) and (k >= delta - (D - 1)) and (k <= delta + (D - 1)) then begin
          if x >= revarray[changeindex(k)] then begin
            snake.u := x;
            snake.v := y;
            result := 2*D - 1;
            exit;
          end;
        end;
//      end;
      Inc(k,2);
    until k > +D;

    k := -D;
    repeat

      kdelta := k + delta;
//      if (kdelta >= -m) and (kdelta <= n) then begin
//      calcrevPath(D,k+delta,off1,off2,u,v);
        if (k = +D) or ((k <> -D) and (revArray[changeindex(kdelta-1)] < revArray[changeindex(kdelta+1)])) then
          x := revArray[changeindex(kdelta-1)]
        else
          x := revArray[changeindex(kdelta+1)] - 1;
        y := x - kdelta;

        snake.u := x;
        snake.v := y;

        while (x > 0) and (y > 0) and (a1[x + off1 - 1] = a2[y + off2 - 1]) do begin
          x := x - 1;
          y := y - 1;
        end;

        revArray[changeindex(kdelta)] := x;
{$IFDEF DEBUG2}
        writeln('R',D,' : ',kdelta,'(',changeindex(kdelta),')',' -> ', x, ' , ', y);
{$ENDIF}

        if ((delta and 1) = 0) and (kdelta >= -D) and (kdelta <= +D) then begin
          if x <= forwarray[changeindex(kdelta)] then begin
            snake.x := x;
            snake.y := y;
            result := 2*D;
            exit;
          end;
        end;
//      end;
      Inc(k,2);
    until k > +D;
  end;

  result := -1;
end;
*)

/// funkcia zistujuca middle snake pre vstupne retazce v poliach a1 a a2 od indexov off1,off2 o dlzke n,m
/// vracia hodnotu v strukture TSnake na adrese urcenej vstupnym pointerom - snake
/// cast lineaneho algoritmu pre vypocet editovacieho scriptu, zalozeny na uprave Myersovho algoritmu na linearny
/// priestor, funkcia vracia vzdialenost medzi vstupnymi polami
function findMiddleSnake_better(const a1: intarray; const a2: intarray; off1,n,off2,m: Integer; snake: PSnake): Integer;
var delta: Integer;
    D: Integer;
    k,kdelta: Integer;
    MAX: Integer;
    x,y,u,v: Integer;
    i1,i2: Integer;
    len: Integer;
    count: Integer;
begin
  MAX := (n + m + ((n + m) and 1)) shr 1;
  delta := n - m;
  len := Length(forwArray);

  forwArray[changeindex(1)] := 0;
  revArray[changeindex(delta-1)] := n;

  count := 0;
  for D := 0 to MAX do begin
    if FGlobalHalt then
      break;
    k := -D;
    repeat
      if (count and CYCLE_THRESHOLD = 0) then begin
        Application.ProcessMessages;
      end;
      if FGlobalHalt then
        break;
      count := count + 1;

      if (k >= -m-m+D) and (k <= n+n-D) then begin
        if (len <= MAX_D_PATH) or ((k > -halfofarray) and (k < MAX_D_PATH - halfofarray)) then begin
          if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
            x := forwArray[changeindex(k+1)]
          else
            x := forwArray[changeindex(k-1)] + 1;
          y := x - k;

          snake.x := x;
          snake.y := y;

          while (x < n) and (y < m) and (a1[x + off1] = a2[y + off2]) do begin
            x := x + 1;
            y := y + 1;
          end;

          forwArray[changeindex(k)] := x;
{$IFDEF DEBUG2}
          writeln('F',D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);
{$ENDIF}

          if ((delta and 1) = 1) and (k >= delta - (D - 1)) and (k <= delta + (D - 1)) then begin
            if x >= revarray[changeindex(k)] then begin
              snake.u := x;
              snake.v := y;
              result := 2*D - 1;
              exit;
            end;
          end;
        end
        else begin
          result := MAX_D_PATH;
          Exit;
        end;
      end;
      Inc(k,2);
    until k > +D;

    if FGlobalHalt then
      break;
    k := -D;
    repeat
      if (count and CYCLE_THRESHOLD = 0) then begin
        Application.ProcessMessages;
      end;
      if FGlobalHalt then
        break;
      count := count + 1;

      kdelta := k + delta;
      if (kdelta >= -n-m+D) and (kdelta <= n+m-D) then begin
        if (len <= MAX_D_PATH) or ((kdelta > -halfofarray) and (kdelta < MAX_D_PATH - halfofarray)) then begin
          if (k = +D) or ((k <> -D) and (revArray[changeindex(kdelta-1)] < revArray[changeindex(kdelta+1)])) then
            x := revArray[changeindex(kdelta-1)]
          else
            x := revArray[changeindex(kdelta+1)] - 1;
          y := x - kdelta;

          snake.u := x;
          snake.v := y;

          while (x > 0) and (y > 0) and (a1[x + off1 - 1] = a2[y + off2 - 1]) do begin
            x := x - 1;
            y := y - 1;
          end;

          revArray[changeindex(kdelta)] := x;
{$IFDEF DEBUG2}
          writeln('R',D,' : ',kdelta,'(',changeindex(kdelta),')',' -> ', x, ' , ', y);
{$ENDIF}

          if ((delta and 1) = 0) and (kdelta >= -D) and (kdelta <= +D) then begin
            if x <= forwarray[changeindex(kdelta)] then begin
              snake.x := x;
              snake.y := y;
              result := 2*D;
              exit;
            end;
          end;
        end
        else begin
          result := MAX_D_PATH;
          Exit;
        end;
      end;
      Inc(k,2);
    until k > +D;
  end;

  result := -1;
end;

/// funkcia ziskavajuca editscript pre vstupne postupnosti v poliach a1,a2 od indexov off1,off2 o dlzke n,m
/// vystupny edit script je v objekte es
/// vystup z tejto funkcie je vzdialenost medzi kompletnymi vstupnymi polami
function calcSES(const a1: intarray; const a2: intarray; off1,n,off2,m: Integer; var es: TEditScript): Integer;
var snake: PSnake;
    D: Integer;
    i,j: Integer;
begin
  result := -1;
  if FGlobalHalt then
    Exit;
  if n = 0 then begin
    if m <> 0 then begin
      es.add(ES_INSERT,off2,m);
      D := m;
    end
    else begin  //dve prazdne postupnosti => quit su zhodne => prazdny es
      D := 0;
    end;
  end
  else if m = 0 then begin
    es.add(ES_DELETE,off1,n);
    D := n;
  end
  else begin
    new(snake);
    D := findMiddleSnake_better(a1,a2,off1,n,off2,m,snake);
    if D = -1 then begin
      //invalid snake
      dispose(snake);
      Exit;
    end
    else if D = MAX_D_PATH then begin
      //too many differences !!!!!!
      dispose(snake);
      result := D;
      Exit;
    end;

{$IFDEF DEBUG1}
    writeln('Middle SNAKE(',D,'): ',snake.x,' , ',snake.y,' -> ',snake.u,' , ',snake.v);
{$ENDIF}

    if D > 1 then begin
      i := calcSES(a1,a2,off1,snake.x,off2,snake.y,es);
      if i = -1 then begin
        //invalid first half
        dispose(snake);
        Exit;
      end;

      es.add(ES_MATCH,off1 + snake.x,snake.u - snake.x);

      j := calcSES(a1,a2,off1 + snake.u, n - snake.u, off2 + snake.v, m - snake.v,es);
      if j = -1 then begin
        //invalid second half
        dispose(snake);
        Exit;
      end;
    end
    else begin
      if m > n then begin
        if snake.x = snake.u then begin
          es.add(ES_MATCH,off1,n);
          es.add(ES_INSERT,off2 + (m - 1),1);
        end
        else begin
          es.add(ES_INSERT,off2,1);
          es.add(ES_MATCH,off1,n);
        end;
      end
      else begin
        if snake.x = snake.u then begin
          es.add(ES_MATCH,off1,m);
          es.add(ES_DELETE,off1 + (n - 1),1);
        end
        else begin
          es.add(ES_DELETE,off1,1);
          es.add(ES_MATCH,off1 + 1,m);
        end;
      end;
    end;
    dispose(snake);
  end;
  result := D;
end;

/// funkcia inicializujuca zistovanie vzdialenosti medzi vstupnymi retazcami
/// vo vstupnych poliach a1,a2 o dlzke size1,size2 a vracajuca editscript ako es_out
/// vystup z tejto funkcie je vzdialenost medzi kompletnymi vstupnymi polami
/// funkcia posobi ako preprocessor k calcSES, pricom odstrani zhodne prvky z oboch koncov
/// vstupnych postupnosti, cize vstupom pre calcSES su postupnosti, kde prve aj posledne prvky
/// su rozne
function calcDiff(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer; var es_out: TEditScript): Integer;
var l1,h1,l2,h2: Integer;
begin
  es_out := TEditScript.create;

//  a1 := array1;
//  a2 := array2;

(*
  //works with findmiddlesnake
  SetLength(forwArray,min(max(size1,size2),MAX_D_PATH) shl 2 + 1);
  SetLength(revArray,min(max(size1,size2),MAX_D_PATH) shl 2 + 1);
  halfofarray := (Length(forwArray) shr 1);
*)
  SetLength(forwArray,min(size1 + size2,MAX_D_PATH) + 1);
  SetLength(revArray,min(size1 + size2,MAX_D_PATH) + 1);
  if Length(forwArray) > MAX_D_PATH then
    halfofarray := MAX_D_PATH shr 1
  else
    halfofarray := size2;

(*  for i := 0 to Pred(Length(forwArray)) do
    forwArray[i] := 0;
  for i := 0 to Pred(Length(revArray)) do
    revArray[i] := size1;*)


  l1 := 0;
  h1 := size1-1;
  l2 := 0;
  h2 := size2-1;

  while (l1 <= h1) and (l2 <= h2) and (a1[l1] = a2[l2]) do begin
    Inc(l1);
    Inc(l2);
  end;
  while (l1 < h1) and (l2 < h2) and (a1[h1] = a2[h2]) do begin
    Dec(h1);
    Dec(h2);
  end;

  if (l1 > h1) and (l2 > h2) then begin
    es_out.add(ES_MATCH,0,h1+1);
    result := 0;  //no diff, work done
  end
  else begin
    es_out.add(ES_MATCH,0,l1-0);
    result := calcSES(a1,a2,l1,h1-l1+1,l2,h2-l2+1,es_out);
    es_out.add(ES_MATCH,h1+1,size1-1-h1);
  end;

  freeDiff;
end;

/// funkcia pocitajuca rozdiely medzi vstupnymi stringami
/// vytvori pomocne polia a pouzije funkciu calcDist
function calcStringDist(const S1: xString; const S2: xString): Integer;
var array1,array2: intarray;
begin
  SetLength(array1,Length(S1));
  if Length(S1) > 0 then
    ArrayMemCopyBtoDW(S1[1],array1[0],Length(S1));
  SetLength(array2,Length(S2));
  if Length(S2) > 0 then
    ArrayMemCopyBtoDW(S2[1],array2[0],Length(S2));
  result := calcDist(array1,Length(array1),array2,Length(array2));
  array1 := nil;
  array2 := nil;
end;

/// funkcia ziskavajuca editscript medzi vstupnymi stringami
/// vytvori pomocne polia a pouzije funkciu calcDiff
function calcStringDiff(const S1: xString; const S2: xString; var es_out: TEditScript): Integer;
var array1,array2: intarray;
begin
  SetLength(array1,Length(S1));
  if Length(S1) > 0 then
    ArrayMemCopyBtoDW(S1[1],array1[0],Length(S1));
  SetLength(array2,Length(S2));
  if Length(S2) > 0 then
    ArrayMemCopyBtoDW(S2[1],array2[0],Length(S2));
  result := calcDiff(array1,Length(array1),array2,Length(array2),es_out);
  array1 := nil;
  array2 := nil;
end;

(*
procedure testDiff;
var S1,S2: xString;
    i,j: Integer;
    es: TEditScript;
begin
//  S1 := 'abcxyzabcbacbacabc';
//  S2 := 'abcbacabcbacxyzabc';
  S1 := 'abcxyzabcabcabcabc';
  S2 := 'abcbacabcabcxyzabc';
  i := calcStringDiff(S1,S2,es);
  S1 := '';
  S2 := '';
  writeln(S1);
  writeln(S2);
  writeln('---------');
  writeln('Edit script size: ' + IntToStr(es.Q.getSize div 3));
  writeln('LCS size: ' + IntToStr(es.getLCSLength));
  writeln('SES size: ' + IntToStr(es.getSESLength));
  writeln('Successful D-Path: ' + IntToStr(i));
  j := calcStringDist(S1,S2);
  writeln('---------');
  writeln('Distance: ' + IntToStr(j));
  write(es.toString);
  es.Free;
end;
*)
(*
procedure test;
var S1,S2: xString;
    i,j,k: Integer;
    es: TEditScript;
begin
  S1 := 'abcdef';
//  S1 := 'abcabba';
//  S1 := 'abcdef';
  SetLength(a1,Length(S1));
  FastCharMove(S1[1],a1[0],Length(S1));
  writeln(S1);
  S2 := 'abedcf';
//  S2 := 'cbabac';
//  S2 := 'ghijkl';//'ghijkl';
  SetLength(a2,Length(S2));
  FastCharMove(S2[1],a2[0],Length(S2));
  writeln(S2);
  writeln('---------');
  initDiff(a1,Length(a1),a2,Length(a2),es);
  writeln('Edit script size: ' + IntToStr(es.Q.getSize div 3));
  es.Q.peekNextReset;
  while es.Q.peekNext(i) do begin
    es.Q.peekNext(j);
    es.Q.peekNext(k);
    writeln(i,': ',j,' - ',k);
  end;
  es.Free;
  writeln(calcDist(a1,Length(a1),a2,Length(a2)));
  freeDiff;
  a1 := nil;
  a2 := nil;

  writeln('##############');

  S1 := 'fedcba';
//  S1 := 'abcabba';
  SetLength(a1,Length(S1));
  FastCharMove(S1[1],a1[0],Length(S1));
  writeln(S1);
  S2 := 'fcdeba';
//  S2 := 'cbabac';
  SetLength(a2,Length(S2));
  FastCharMove(S2[1],a2[0],Length(S2));
  writeln(S2);
  writeln('---------');
  initDiff(a1,Length(a1),a2,Length(a2),es);
  es.Free;
  writeln(calcDist(a1,Length(a1),a2,Length(a2)));
  freeDiff;
  a1 := nil;
  a2 := nil;

  writeln('##############');

  S1 := 'abcdef';
//  S1 := 'abcabba';
//  S1 := 'abcdef';
  SetLength(a1,Length(S1));
  FastCharMove(S1[1],a1[0],Length(S1));
  writeln(S1);
  S2 := 'abedcf';
//  S2 := 'cbabac';
//  S2 := 'ghijkl';//'ghijkl';
  SetLength(a2,Length(S2));
  FastCharMove(S2[1],a2[0],Length(S2));
  writeln(S2);
  writeln('---------');
  initDiff(a1,Length(a1),a2,Length(a2),es);
  es.Free;
  writeln(calcforw(i,j));
  freeDiff;
  a1 := nil;
  a2 := nil;

  writeln('##############');

  S1 := 'fedcba';
//  S1 := 'abcabba';
  SetLength(a1,Length(S1));
  FastCharMove(S1[1],a1[0],Length(S1));
  writeln(S1);
  S2 := 'fcdeba';
//  S2 := 'cbabac';
  SetLength(a2,Length(S2));
  FastCharMove(S2[1],a2[0],Length(S2));
  writeln(S2);
  writeln('---------');
  initDiff(a1,Length(a1),a2,Length(a2),es);
  es.Free;
  writeln(calcrev(i,j));
  freeDiff;
  a1 := nil;
  a2 := nil;
end;
*)


/// funkcia zistujuca middle snake pre vstupne retazce v poliach a1 a a2 od indexov off1,off2 o dlzke n,m
/// vracia hodnotu v strukture TSnake na adrese urcenej vstupnym pointerom - snake
/// cast lineaneho algoritmu pre vypocet editovacieho scriptu, zalozeny na uprave Myersovho algoritmu na linearny
/// priestor, funkcia vracia vzdialenost medzi vstupnymi polami
/// pricom na zistovanie zhody medzi dvomi prvkami v poliach sa pouziva vstupna porovnavacia funkcia - comp
function findMiddleSnake_better_comp_func(const a1: intarray; const a2: intarray; off1,n,off2,m: Integer; snake: PSnake; comp: TCompareFunc): Integer;
var delta: Integer;
    D: Integer;
    k,kdelta: Integer;
    MAX: Integer;
    x,y,u,v: Integer;
    i1,i2: Integer;
    len: Integer;
    count: Integer;
begin
  MAX := (n + m + ((n + m) and 1)) shr 1;
{$IFDEF DEBUG4}
   writeln('MIDDLESNAKESIZES: ',n,',',m,' (',MAX,')');
{$ENDIF}

  delta := n - m;
  len := Length(forwArray);

  forwArray[changeindex(1)] := 0;
  revArray[changeindex(delta-1)] := n;

  count := 0;
  for D := 0 to MAX do begin
    if FGlobalHalt then
      break;
    k := -D;
    repeat
      if (count and CYCLE_THRESHOLD = 0) then begin
        Application.ProcessMessages;
      end;
      if FGlobalHalt then
        break;
      count := count + 1;

      if (k >= -m-m+D) and (k <= n+n-D) then begin
        if (len <= MAX_D_PATH) or ((k > -halfofarray) and (k < MAX_D_PATH - halfofarray)) then begin
          if (k = -D) or ((k <> D) and (forwArray[changeindex(k-1)] < forwArray[changeindex(k+1)])) then
            x := forwArray[changeindex(k+1)]
          else
            x := forwArray[changeindex(k-1)] + 1;
          y := x - k;

          snake.x := x;
          snake.y := y;

          while (x < n) and (y < m) and comp(a1[x + off1],a2[y + off2]) do begin
            x := x + 1;
            y := y + 1;
          end;

          forwArray[changeindex(k)] := x;
{$IFDEF DEBUG2}
          writeln('F',D,' : ',k,'(',changeindex(k),')',' -> ', x, ' , ', y);
{$ENDIF}

          if ((delta and 1) = 1) and (k >= delta - (D - 1)) and (k <= delta + (D - 1)) then begin
            if x >= revarray[changeindex(k)] then begin
              snake.u := x;
              snake.v := y;
              result := 2*D - 1;
              exit;
            end;
          end;
        end
        else begin
          result := MAX_D_PATH;
          Exit;
        end;
      end;
      Inc(k,2);
    until k > +D;

    if FGlobalHalt then
      break;
    k := -D;
    repeat
      if (count and CYCLE_THRESHOLD = 0) then begin
        Application.ProcessMessages;
      end;
      if FGlobalHalt then
        break;
      count := count + 1;

      kdelta := k + delta;
      if (kdelta >= -n-m+D) and (kdelta <= n+m-D) then begin
        if (len <= MAX_D_PATH) or ((kdelta > -halfofarray) and (kdelta < MAX_D_PATH - halfofarray)) then begin
          if (k = +D) or ((k <> -D) and (revArray[changeindex(kdelta-1)] < revArray[changeindex(kdelta+1)])) then
            x := revArray[changeindex(kdelta-1)]
          else
            x := revArray[changeindex(kdelta+1)] - 1;
          y := x - kdelta;

          snake.u := x;
          snake.v := y;

          while (x > 0) and (y > 0) and comp(a1[x + off1 - 1],a2[y + off2 - 1]) do begin
            x := x - 1;
            y := y - 1;
          end;

          revArray[changeindex(kdelta)] := x;
{$IFDEF DEBUG2}
          writeln('R',D,' : ',kdelta,'(',changeindex(kdelta),')',' -> ', x, ' , ', y);
{$ENDIF}

          if ((delta and 1) = 0) and (kdelta >= -D) and (kdelta <= +D) then begin
            if x <= forwarray[changeindex(kdelta)] then begin
              snake.x := x;
              snake.y := y;
              result := 2*D;
              exit;
            end;
          end;
        end
        else begin
          result := MAX_D_PATH;
          Exit;
        end;
      end;
      Inc(k,2);
    until k > +D;
  end;

  result := -1;
end;

/// funkcia ziskavajuca editscript pre vstupne postupnosti v poliach a1,a2 od indexov off1,off2 o dlzke n,m
/// vystupny edit script je v objekte es
/// vystup z tejto funkcie je vzdialenost medzi kompletnymi vstupnymi polami
/// pricom na zistovanie zhody medzi dvomi prvkami v poliach sa pouziva vstupna porovnavacia funkcia - comp
function calcSES_comp_func(const a1: intarray; const a2: intarray; off1,n,off2,m: Integer; var es: TEditScript; comp: TCompareFunc): Integer;
var snake: PSnake;
    D: Integer;
    i,j: Integer;
begin
  result := -1;
  if FGlobalHalt then
    Exit;
  if n = 0 then begin
    if m <> 0 then begin
      es.add(ES_INSERT,off2,m);
      D := m;
    end
    else begin  //dve prazdne postupnosti => quit su zhodne => prazdny es
      D := 0;
    end;
  end
  else if m = 0 then begin
    es.add(ES_DELETE,off1,n);
    D := n;
  end
  else begin
    new(snake);
    D := findMiddleSnake_better_comp_func(a1,a2,off1,n,off2,m,snake,comp);
    if D = -1 then begin
      //invalid snake
      dispose(snake);
      Exit;
    end
    else if D = MAX_D_PATH then begin
      //too many differences !!!!!!
      dispose(snake);
      result := D;
      Exit;
    end;

{$IFDEF DEBUG1}
    writeln('Middle SNAKE(',D,'): ',snake.x,' , ',snake.y,' -> ',snake.u,' , ',snake.v);
{$ENDIF}

    if D > 1 then begin
      i := calcSES_comp_func(a1,a2,off1,snake.x,off2,snake.y,es,comp);
      if i = -1 then begin
        //invalid first half
        dispose(snake);
        Exit;
      end;

      es.add(ES_MATCH,off1 + snake.x,snake.u - snake.x);

      j := calcSES_comp_func(a1,a2,off1 + snake.u, n - snake.u, off2 + snake.v, m - snake.v,es,comp);
      if j = -1 then begin
        //invalid second half
        dispose(snake);
        Exit;
      end;
    end
    else begin
      if m > n then begin
        if snake.x = snake.u then begin
          es.add(ES_MATCH,off1,n);
          es.add(ES_INSERT,off2 + (m - 1),1);
        end
        else begin
          es.add(ES_INSERT,off2,1);
          es.add(ES_MATCH,off1,n);
        end;
      end
      else begin
        if snake.x = snake.u then begin
          es.add(ES_MATCH,off1,m);
          es.add(ES_DELETE,off1 + (n - 1),1);
        end
        else begin
          es.add(ES_DELETE,off1,1);
          es.add(ES_MATCH,off1 + 1,m);
        end;
      end;
    end;
    dispose(snake);
  end;
  result := D;
end;

/// funkcia inicializujuca zistovanie vzdialenosti medzi vstupnymi retazcami
/// vo vstupnych poliach a1,a2 o dlzke size1,size2 a vracajuca editscript ako es_out
/// vystup z tejto funkcie je vzdialenost medzi kompletnymi vstupnymi polami
/// funkcia posobi ako preprocessor k calcSES, pricom odstrani zhodne prvky z oboch koncov
/// vstupnych postupnosti, cize vstupom pre calcSES su postupnosti, kde prve aj posledne prvky
/// su rozne
/// pricom na zistovanie zhody medzi dvomi prvkami v poliach sa pouziva vstupna porovnavacia funkcia - comp
function calcDiff_comp_func(const a1: intarray; size1: Integer; const a2: intarray; size2: Integer; var es_out: TEditScript; comp: TCompareFunc): Integer;
var l1,h1,l2,h2: Integer;
begin
  es_out := TEditScript.create;

//  a1 := array1;
//  a2 := array2;

(*
  //works with findmiddlesnake
  SetLength(forwArray,min(max(size1,size2),MAX_D_PATH) shl 2 + 1);
  SetLength(revArray,min(max(size1,size2),MAX_D_PATH) shl 2 + 1);
  halfofarray := (Length(forwArray) shr 1);
*)
  SetLength(forwArray,min(size1 + size2,MAX_D_PATH) + 1);
  SetLength(revArray,min(size1 + size2,MAX_D_PATH) + 1);
  if Length(forwArray) > MAX_D_PATH then
    halfofarray := MAX_D_PATH shr 1
  else
    halfofarray := size2;

(*  for i := 0 to Pred(Length(forwArray)) do
    forwArray[i] := 0;
  for i := 0 to Pred(Length(revArray)) do
    revArray[i] := size1;*)


  l1 := 0;
  h1 := size1-1;
  l2 := 0;
  h2 := size2-1;

  while (l1 <= h1) and (l2 <= h2) and comp(a1[l1],a2[l2]) do begin
    Inc(l1);
    Inc(l2);
  end;
  while (l1 < h1) and (l2 < h2) and comp(a1[h1],a2[h2]) do begin
    Dec(h1);
    Dec(h2);
  end;

  if (l1 > h1) and (l2 > h2) then begin
    es_out.add(ES_MATCH,0,h1+1);
    result := 0;  //no diff, work done
  end
  else begin
    es_out.add(ES_MATCH,0,l1-0);
    result := calcSES_comp_func(a1,a2,l1,h1-l1+1,l2,h2-l2+1,es_out,comp);
    es_out.add(ES_MATCH,h1+1,size1-1-h1);
  end;
  freeDiff;
end;

/// funkcia vracajuca ako vysledok zhodne prvky vstupnych stackov Q1 a Q2 a stacky prvkov,
/// ktore su navyse v prvom vstupe v stacku Q1_out_unmatched a tie, ktore su navyse v druhom
/// vstupe v stacku Q2_out_unmatched
/// funkcia vytvori docasne polia a zavola calcDiff_comp_func
/// pricom na zistovanie zhody medzi dvomi prvkami v poliach sa pouziva vstupna porovnavacia funkcia - comp
function getLCS(Q1,Q2: TQueueStack;var Q1_out_unmatched,Q2_out_unmatched: TQueueStack;comp: TCompareFunc): TQueueStack;
var array1,array2: intarray;
    i,j,k: Integer;
    es: TEditScript;
    d: Integer;
    op,index,count: Integer;
//    P: PPair;
begin
  if Q1 <> nil then begin
    SetLength(array1,Q1.getSize);
    Q1.peekNextReset;
    j := 0;
    while Q1.peekNext(i) do begin
      array1[j] := i;
      j := j + 1;
    end;
  end
  else
    SetLength(array1,0);

  if Q2 <> nil then begin
    SetLength(array2,Q2.getSize);
    Q2.peekNextReset;
    j := 0;
    while Q2.peekNext(i) do begin
      array2[j] := i;
      j := j + 1;
    end;
  end
  else
    SetLength(array2,0);

  d := calcDiff_comp_func(array1,Length(array1),array2,Length(array2),es,comp);
(*
  es.getNextReset;
  i := 0; j := 0;
  while es.getNext(op,index,count) do begin
    if op = ES_MATCH then begin
      new(P);
      P.x :=
    end;
  end;
*)
  result := TQueueStack.create;
  Q1_out_unmatched := TQueueStack.create;
  Q2_out_unmatched := TQueueStack.create;

  I := 0; J := 0;
  es.getNextReset;
  while es.getNext(op,index,count) do begin
    if op = ES_MATCH then begin
      for k := 1 to count do begin
(*        new(p);
        p.x := array1[i];
        p.y := array2[j];
        result.push(Integer(p));*)
        result.push(array1[i]);
        result.push(array2[j]);
        I := I + 1;
        J := J + 1;
      end;
    end
    else if op = ES_INSERT then begin
      for k := 1 to count do begin
        Q2_out_unmatched.push(array2[j]);
        J := J + 1;
      end;
//      J := J + count;
    end
    else if op = ES_DELETE then begin
      for k := 1 to count do begin
        Q1_out_unmatched.push(array1[i]);
        I := I + 1;
      end;
//      I := I + count;
    end;
  end;

  es.Free;
  array1 := nil;
  array2 := nil;
end;

end.
