Листинг 6.19. Конструктор и деструктор класса списка с пропусками

constructor TtdSkipList.Create(aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

var

i : integer;

begin

inherited Create;

{функция сравнения не может быть nil}

if not Assigned(aCompare) then

slError(tdeSkpLstNoCompare, 'Create');

{создать диспетчеры узлов}

slGetNodeManagers;

{выделить начальный узел}

FHead := slAllocNode (pred( tdcMaxSkipLevels));

FHead^.sknData := nil;

{выделить конечный узел}

FTail := slAllocNode (0);

FTail^.sknData := nil;

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

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FHead^.sknPrev := nil;

FTail^.sknNext[0] :=nil;

FTail^.sknPrev := FHead;

{установить курсор на начальный узел}

FCursor := FHead;

{сохранить функцию сравнения и процедуру dispose}

FCompare := aCompare;

FDispose :=aDispose;

{создать генератор случайных чисел}

FPRNG := TtdMinStandardPRNG.Create(0);

end;

destructor TtdSkipList.Destroy;

begin

Clear;

slFreeNode(FHead);

slFreeNode(FTail);

FPRNG.Free;

inherited Destroy;

end;

Конструктор использует функцию сравнения, что позволяет корректно выбирать позицию вставляемых узлов (конечно, функция сравнения не может быть nil). Кроме того, в качестве входного параметра присутствует процедура dispose. Если она содержит nil, список с пропусками не является владельцем хранящихся в нем данных, поэтому при удалении списка данные удаляться не будут. В противном случае список является владельцем данных, и при его удалении данные также будут удаляться. Конструктор Create создает начальный и конечный узлы и устанавливает их указатели. И, наконец, создается генератор случайных чисел. Он впоследствии будет использоваться в методе Add.

Деструктор Destroy очищает содержимое списка с помощью метода Clear, освобождает начальный и конечный узлы и уничтожает генератор случайных чисел.

Метод Clear предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.

Листинг 6.20. Очистка содержимого списка с пропусками

procedure TtdSkipList.Clear;

var

i : integer;

Walker, Temp : PskNode;

begin

{пройти по узлам уровня 0, освобождая все узлы}

Walker := FHead^.sknNext[0];

while (Walker <> FTail) do

begin

Temp Walker;

Walker := Walker^.sknNext[0];

slFreeNode(Temp);

end;

{восстановить начальный и конечный узлы}

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FTail^.sknPrev := FHead;

FCount := 0;

end;

Методы выделения и уничтожения узлов достаточно просты. Они пользуются диспетчерами узлов класса и определяют требуемый диспетчер на основе значения уровня. Для метода выделения узла уровень передается в качестве входного параметра, для метода уничтожения оно определяется исходя из значения, полученного из освобождаемого узла.

Листинг 6.21. Выделение и уничтожение узлов в списке с пропусками

class function TtdSkipList.slAllocNode(aLevel : integer): PskNode;

begin

Result := SLNodeManager[aLevel].AllocNode;

Result^.sknLevel := aLevel;

end;

procedure TtdSkipList.siFreeNode(aNode : PskNode);

begin

if (aNode <> nil) then begin

if Assigned(FDispose) then

FDispose(aNode^.sknData);

SLNodeManager[aNode^.sknLevel].FreeNode(aNode);

end;

end;

class procedure TtdSkipList.slGetNodeManagers;

var

i : integer;

begin

{если диспетчеры узлов еще не созданы, создать их}

if (SLNodeManager[0] =nil) then

for i := 0 to pred(tdcMaxSkipLevels) do SLNodeManager[i] := TtdNodeManager.Create(NodeSize[i]);

end;

Обратите внимание, что метод уничтожения освобождает узлы только в том случае, когда список с пропусками создан в качестве владельца данных.

Остальные методы класса списка с пропусками еще проще - все они содержат всего несколько строк кода.

Листинг 6.22. Остальные методы класса списка с пропусками

procedure TtdSkipList.Delete

begin

{начальный и конечный узлы удалять нельзя}

if (FCursor = FHead) or (FCursor = FTail) then

slError(tdeListCannotDelete, 'Delete');

{удалить узел в позиции курсора}

Remove(FCursor^.sknData);

end;

function TtdSkipList.Examine : pointer;

begin

Result := FCursor^.sknData;

end;

function TtdSkipList.IsAfterLast : boolean;