FTree[GrandDad].hnLeftInx := aNodeInx;
end;
if (FTree[Dad].hnLeftInx = aNodeInx) then
FTree[Dad].hnLeftInx := Uncle
else
FTree[Dad].hnRightInx := Uncle;
FTree[Uncle].hnParentInx := Dad;
FTree[aNodeInx].hnParentInx :=GrandDad;
{возобновить цикл с узла-деда}
aNodeInx :=GrandDad;
end;
until (aNodeInx = 0);
end;
При восстановлении мы устанавливаем дерево в исходную конфигурацию, как это делалось на этапе сжатия. Затем мы по одному выбираем биты из потока битов и выполняем обычное перемещение вниз по дереву. По достижении листа, содержащего символ (который мы выводим в качестве восстановленных данных), мы будем выполнять скос родительского узла данного узла к корню дерева. При условии, что обновление дерева выполняется одинаково и во время сжатия, и во время восстановления, алгоритм декодирования может поддерживать дерево в том же состоянии, что и на соответствующем этапе выполнения алгоритма кодирования.
Листинг 11.20. Базовый алгоритм восстановления скошенного дерева
procedure TDSplayDecompress(aInStream, aOutStream : TStream);
var
Signature : longint;
Size : longint;
STree : TSplayTree;
BitStrm : TtdInputBitStream;
begin
{выполнить проверку того, что входной поток является корректно закодированным с использованием скошенного дерева}
aInStream.Seek(0, soFromBeginning);
aInStream.ReadBuffer(Signature, sizeof(Signature));
if (Signature <> TDSplayHeader) then
raise EtdSplayException.Create(FmtLoadStr(tdeSplyBadEncodedStrm,
[UnitName, 'TDSplayDecompress']));
aInStream.ReadBuffer(Size, sizeof(longint));
{при отсутствии данных для восстановления выйти из подпрограммы}
if (Size = 0) then
Exit;
{подготовиться к восстановлению}
STree := nil;
BitStrm := nil;
try
{создать поток битов}
BitStrm := TtdInputBitStream.Create(aInStream);
BitStrm.Name := 'Splay compressed stream';
{создать скошенное дерево}
STree := TSplayTree.Create;
{восстановить символы входного потока с использованием скошенного дерева}
DoSplayDecompression(BitStrm, aOutStream, STree, Size);
finally
BitStrm.Free;
STree.Free;
end;
end;
В процессе восстановления потока вначале за счет проверки сигнатуры выполняется проверка того, что поток является сжатым с использованием скошенного дерева. Затем мы считываем размер несжатых данных и осуществляем выход из подпрограммы, если он равен нулю.
При наличии данных для восстановления мы создаем входной поток битов, который будет содержать входной поток и скошенное дерево. Затем для выполнения реального декодирования вызывается метод DoSplayDecompression (см. листинг 11.21).
Листинг 11.21. Цикл восстановления скошенного дерева
procedure DoSplayDecompression(aBitStream : TtdInputBitStream;
aOutStream : TStream;
aTree : TSplayTree;
aSize : longint);
var
CharCount : longint;
Ch : byte;
Buffer : PByteArray;
BufEnd : integer;
begin
GetMem(Buffer, SplayBufferSize);
try
{предварительная установка значений переменных цикла}
BufEnd := 0;
CharCount := 0;
{повторять цикл до тех пор, пока не будут восстановлены все символы}
while (CharCount < aSize) do
begin {считать следующий байт}
Buffer^[BufEnd] := aTree.DecodeByte(aBitStream);
inc(BufEnd);
inc(CharCount);
{записать буфер в случае его заполнения}
if (BufEnd = SplayBufferSize) then begin
aOutStream.WriteBuffer(Buffer^,SplayBufferSize);
BufEnd := 0;
end;
end;
{записать любые оставшиеся в буфере данные}
if (BufEnd <> 0) then
aOutStream.WriteBuffer(Buffer^, BufEnd);
finally
FreeMem(Buffer, SplayBufferSize);
end;
