Читать «Фундаментальные алгоритмы и структуры данных в Delphi» онлайн - страница 348

protected

function mxGetItem(aRow, aCol : integer): PtdLCSData;

procedure mxSetItem(aRow, aCol : integer;

aValue : PtdLCSData);

public

constructor Create(aRowCount, aColCount : integer);

destructor Destroy; override;

procedure Clear;

property Items [aRow, aCol : integer] : PtdLCSData

read mxGetItem write mxSetItem;

default;

property RowCount : integer read FRows;

property ColCount : integer read FCols;

end;

constructor TtdLCSMatrix.Create(aRowCount, aColCount : integer);

var

Row : integer;

ColList : TList;

begin

{создать производный объект}

inherited Create;

{выполнить простую проверку}

Assert ((aRowCount > 0) and (aColCount > 0),

' TtdLCSMatrix.Create: Invalid Row or column count');

FRows := aRowCount;

FCols := aColCount;

{создать матрицу: она будет матрицей TList матриц TLists, упорядоченных по строкам}

FMatrix := TList.Create;

FMatrix.Count := aRowCount;

for Row := 0 to pred(aRowCount) do

begin

ColList := TList.Create;

ColList.Count := aColCount;

TList(FMatrix.List^[Row]) := ColList;

end;

end;

destructor TtdLCSMatrix.Destroy;

var

Row : integer;

begin

{уничтожить матрицу}

if (matrix <> nil) then begin

Clear;

for Row := 0 to pred(FRows) do

TList(FMatrix.List^[Row]).Free;

FMatrix.Free;

end;

{уничтожить производный объект}

inherited Destroy;

end;

procedure TtdLCSMatrix.Clear;

var

Row, Col : integer;

ColList : TList;

begin

for Row := 0 to pred(FRows) do

begin

ColList := TList(FMatrix.List^[Row]);

if (ColList <> nil) then

for Col := 0 to pred(FCols) do

begin

if (ColList.List^[Col] <> nil) then

Dispose(PtdLCSData(ColList.List^[Col]));

ColList.List^[Col] :=nil;

end;

end;

end;

function TtdLCSMatrix.mxGetItem(aRow, aCol : integer): PtdLCSData;

begin

if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then

raise Exception.Create(

'TtdLCSMatrix.mxGetItem: Row or column index out of bounds');

Result := PtdLCSData(TList(FMatrix.List^[aRow]).List^[aCol]);

end;

procedure TtdLCSMatrix.mxSetItem(aRow, aCol : integer;

aValue : PtdLCSData);

begin

if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then

raise Exception.Create(

'TtdLCSMatrix.mxSetItem: Row or column index out of bounds');

TList(Matrix.List^[aRow]).List^[aCol] := aValue;

end;

Следующий шаг заключается в создании класса, который реализует алгоритм вычисления LCS для строк. Код интерфейса и выполнения служебных функций класса TtdStringLCS приведен в листинге 12.23.

Листинг 12.23. Класс TtdStringLCS

type

TtdStringLCS = class private

FFromStr : string;

FMatrix : TtdLCSMatrix;

FToStr : string;

protected

procedure slFillMatrix;

function slGetCell(aFromInx, aToInx : integer): integer;

procedure slWriteChange(var F : System.Text;

aFromInx, aToInx : integer);

public

constructor Create(const aFromStr, aToStr : string);

destructor Destroy; override;

procedure WriteChanges(const aFileName : string;

end;

constructor TtdStringLCS.Create(const aFromStr, aToStr : string);

begin

{создать производный объект}

inherited Create;

{сохранить строки}

FFromStr := aFromStr;

FToStr :=aToStr;

{создать матрицу}

FMatrix := TtdLCSMatrix.Create(succ(length(aFromStr)), succ(length(aToStr)));