type
TtdSkipList = class private
FCompare : TtdCompareFunc;
FCount : integer;
FCursor : PskNode;
FDispose : TtdDisposeProc;
FHead : PskNode;
FMaxLevel : integer;
FName : TtdNameString;
FPRNG : TtdMinStandardPRNG;
FTail : PskNode;
protected
class function slAllocNode(aLevel : integer): PskNode;
procedure slError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure slFreeNode(aNode : PskNode);
class procedure slGetNodeManagers;
function slSearchPrim(aItem : pointer;
var aBeforeNodes : TskNodeArray): boolean;
public
constructor Create( aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
destructor Destroy; override;
procedure Add(aItem : pointer);
procedure Clear;
procedure Deleter-function Examine : pointer;
function IsAfterLast : boolean;
function IsBeforeFirst : boolean;
function IsEmpty : boolean;
procedure MoveAfterLast;
procedure MoveBeforeFirst;
procedure MoveNext;
procedure MovePrior;
procedure Remove(aItem : pointer);
function Search(aItem : pointer): boolean;
property Count : integer read FCount;
property MaxLevel : integer read FMaxLevel;
property Name : TtdNameString read FName write FName;
end;
Назначение большинства методов и свойств станет понятным, если вы вернетесь к описанию методов класса связных списков, которое приводится в главе 3.
Как и для классов связных списков, используется диспетчер узлов, который позволяет эффективно выделять и освобождать узлы. Тем не менее, для списков с пропусками имеется небольшое, однако важное отличие: узлы в списке с пропусками имеют разные размеры. Фактически в списке может быть до 12 видов узлов. Следовательно, для работы с узлами потребуется 12 диспетчеров. Процедура класса slGetNodeManagers выполняет инициализацию 12 диспетчеров узлов. Она вызывается в конструкторе Create класса списка с пропусками. Все объекты списков будут пользоваться одними и теми же диспетчерами. В заключительной части модуля все диспетчеры узлов удаляются.
Листинг 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
