Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

var

LCSData : PtdLCSData;

NorthLen: integer;

WestLen : integer;

begin

if (aFromInx = -1) or (aToInx = -1) then

Result := 0

else begin

LCSData := FMatrix[aFromInx, aToInx];

if (LCSData <> nil) then

Result := LCSData^.ldLen

else begin

{создать новый элемент}

New(LCSData);

{если две текущие строки совпадают, необходимо увеличить значение счетчика относительно элемента, расположенное о к северо-западу от текущего, т.е. предшествующего элемента}

if (FFromFile[aFromInx] = FToFile [aToInx]) then begin

LCSData^.ldPrev := ldNorthWest;

LCSData^.ldLen := slGetCell(aFromInx-1, aToInx-1) + 1;

end

{в противном случае текущие строки различны: необходимо использовать максимальный из элементов, расположенных к северу или западу (использование элемента, расположенного к западу, предпочтительнее)} else begin

NorthLen := slGetCell(aFromInx-1, aToInx);

WestLen := slGetCell(aFromInx, aToInx-1);

if (NorthLen > WestLen) then begin

LCSData^.ldPrev := ldNorth;

LCSData^.ldLen := NorthLen;

end

else begin

LCSData^.ldPrev := ldWest;

LCSData^.ldLen := WestLen;

end;

end;

{установить элемент в матрице}

FMatrix [ aFromInx, aToInx ] := LCSData;

{вернуть длину данного LCS}

Result := LCSData^.ldLen;

end;

end;

end;

Метод записи последовательности редактирования, которая обеспечивает преобразование первого файла во второй, не особенно изменился по сравнению с рассмотренным ранее, за исключением того, что выполняется запись строк, а не символов. Эта подпрограмма приведена в листинге 12.29.

Листинг 12.29. Запись последовательности редактирования для пары файлов

procedure TtdFileLCS.slWriteChange(var F : System.Text;

aFromInx, aToInx : integer);

var

Cell : PtdLCSData;

begin

{если оба индекса меньше нуля, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}

if (aFromInx = -1) and (aToInx = -1) then

Exit;

{если индекс строки From меньше нуля, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}

if (aFromInx = -1) then begin

slWriteChange(F, aFromInx, aToInx-1);

writeln(F, '->', FToFile[aToInx]);

end

{если индекс строки To меньше нуля, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}

else

if (aToInx = -1) then begin

slWriteChange(F, aFromInx-1, aToInx);

writeln(F, '<-', FFromFile[aFromInx]);

end

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

else begin

Cell := FMatrix[aFromInx, aToInx];

case Cell^.ldPrev of

ldNorth :

begin

slWriteChange(F, aFromInx-1, aToInx);

writeln(F, '<-', FFromFile [aFromInx]);

end;

ldNorthWest : begin

slWriteChange(F, aFromInx-1, aToInx-1);

writeln(F, 1 ', FFromFile[aFromInx]);

end;

ldWest : begin

slWriteChange(F, aFromInx, aToInx-1);

writeln(Ff FToFile[aToInx]);

end;

end;

end;

end;

procedure TtdFileLCS.WriteChanges(const aFileName : string);

var

F : System.Text;

begin

System.Assign(F, aFileName);

System.Rewrite(F);

try

slWriteChange (F, pred(FFromFile.Count), pred(FToFile.Count)) finally

System.Close(F);

end;

end;

В этой главе были рассмотрены три дополнительных алгоритма. Первые два предназначены для работы с многопоточными приложениями. Третий представляет собой весьма значимый, однако малоизвестный алгоритм поиска различий между двумя версиями файла.

Применительно к многопоточным приложениям, мы рассмотрели решение проблемы синхронизации потоков считывания-записи - алгоритма, который играет большую роль во множестве программ подобного рода. Применительно к проблеме использования потоков производителей-потребителей, мы рассмотрели алгоритм, который может применяться во многих ситуациях, когда большие объемы данных должны одновременно обрабатываться, причем различным образом.

Алгоритм определения наиболее длинной общей подпоследовательности (LCS) является более специализированным, но находит применение в системах управления исходным кодом, а также в качестве программ наподобие diff.

Если быть кратким, написание этой книги явилось интересным опытом (а также работой, попортившей немало кровушки).

В течение долгих лет я считал, что Delphi, Visual Basic, а теперь и Kylix, порождали, порождают и будут порождать программистов, которые не имеют ни малейшего представления об этом занятии. Да, они могут создавать приложения простым перетаскиванием, с использованием небольшого объема связующего кода и нескольких обработчиков событий. Тем не менее, любое приложение, достойное того, чтобы его создавать, требует определенного мастерства, опыта и теоретической подготовки, которые могут быть предоставлены традиционными компьютерными науками и программированием. Конечно, при создании программы можно немало напутать, и, тем не менее, программа таки будет работать. Однако различие будет столь же разительным, как и различие между яйцом, сваренным вкрутую, и яйцом Фаберже.